10 #include <boost/functional/hash.hpp>
14 #include <type_traits>
33 explicit AdjacencyList(
const std::int32_t n) : _array(n), _offsets(n + 1)
35 std::iota(_array.data(), _array.data() + n, 0);
36 std::iota(_offsets.data(), _offsets.data() + n + 1, 0);
43 template <
typename U,
typename V,
44 std::enable_if_t<std::is_base_of<Eigen::EigenBase<std::decay_t<V>>,
45 std::decay_t<V>>::value,
48 : _array(std::forward<U>(data)), _offsets(std::forward<V>(
offsets))
58 template <
typename U,
typename V,
59 std::enable_if_t<!std::is_base_of<Eigen::EigenBase<std::decay_t<V>>,
60 std::decay_t<V>>::value,
63 : _array(data.size()), _offsets(
offsets.size())
65 assert(
offsets.back() == (std::int32_t)data.size());
66 std::copy(data.begin(), data.end(), _array.data());
75 const Eigen::Ref<
const Eigen::Array<T, Eigen::Dynamic, Eigen::Dynamic,
76 Eigen::RowMajor>>& matrix)
77 : _array(matrix.rows() * matrix.cols()), _offsets(matrix.rows() + 1)
79 const std::int32_t
num_links = matrix.cols();
80 for (Eigen::Index e = 0; e < _offsets.rows(); e++)
85 for (Eigen::Index i = 0; i < matrix.rows(); ++i)
86 _array.segment(_offsets(i),
num_links) = matrix.row(i);
94 explicit AdjacencyList(
const std::vector<X>& data) : _offsets(data.size() + 1)
97 std::int32_t size = 0;
98 for (std::size_t e = 0; e < data.size(); e++)
101 size += data[e].size();
103 _offsets[data.size()] = size;
107 for (
auto e = data.begin(); e != data.end(); ++e)
108 c.insert(c.end(), e->begin(), e->end());
110 _array = Eigen::Array<T, Eigen::Dynamic, 1>(c.size());
111 std::copy(c.begin(), c.end(), _array.data());
132 return (this->_array == list._array).all()
133 and (this->_offsets == list._offsets).all();
138 std::int32_t
num_nodes()
const {
return _offsets.rows() - 1; }
145 assert((node + 1) < _offsets.rows());
146 return _offsets[node + 1] - _offsets[node];
153 typename Eigen::Array<T, Eigen::Dynamic, 1>::SegmentReturnType
links(
int node)
155 return _array.segment(_offsets[node], _offsets[node + 1] - _offsets[node]);
162 typename Eigen::Array<T, Eigen::Dynamic, 1>::ConstSegmentReturnType
165 return _array.segment(_offsets[node], _offsets[node + 1] - _offsets[node]);
171 return &_array[_offsets[node]];
175 const Eigen::Array<T, Eigen::Dynamic, 1>&
array()
const {
return _array; }
178 const Eigen::Array<std::int32_t, Eigen::Dynamic, 1>&
offsets()
const
186 return boost::hash_range(_array.data(), _array.data() + _array.size());
193 s <<
"<AdjacencyList> with " + std::to_string(this->
num_nodes()) +
" nodes"
195 for (Eigen::Index e = 0; e < _offsets.size() - 1; e++)
196 s <<
" " << e <<
": " << this->
links(e).transpose() << std::endl;
202 Eigen::Array<T, Eigen::Dynamic, 1> _array;
205 Eigen::Array<std::int32_t, Eigen::Dynamic, 1> _offsets;
This class provides a static adjacency list data structure. It is commonly used to store directed gra...
Definition: AdjacencyList.h:28
bool operator==(const AdjacencyList &list) const
Equality operator.
Definition: AdjacencyList.h:130
std::string str() const
Return informal string representation (pretty-print)
Definition: AdjacencyList.h:190
AdjacencyList & operator=(AdjacencyList &&list)=default
Move assignment.
~AdjacencyList()=default
Destructor.
AdjacencyList(const AdjacencyList &list)=default
Copy constructor.
AdjacencyList(const std::int32_t n)
Construct trivial adjacency list where each of the n nodes is connected to itself.
Definition: AdjacencyList.h:33
std::int32_t num_nodes() const
Number of nodes.
Definition: AdjacencyList.h:138
AdjacencyList(AdjacencyList &&list)=default
Move constructor.
std::size_t hash() const
Hash of graph.
Definition: AdjacencyList.h:184
const Eigen::Array< T, Eigen::Dynamic, 1 > & array() const
Return contiguous array of links for all nodes (const version)
Definition: AdjacencyList.h:175
Eigen::Array< T, Eigen::Dynamic, 1 >::ConstSegmentReturnType links(int node) const
Links (edges) for given node (const version)
Definition: AdjacencyList.h:163
AdjacencyList(U &&data, V &&offsets)
Construct adjacency list from arrays of data (Eigen data types)
Definition: AdjacencyList.h:47
Eigen::Array< T, Eigen::Dynamic, 1 >::SegmentReturnType links(int node)
Links (edges) for given node.
Definition: AdjacencyList.h:153
int num_links(int node) const
Number of connections for given node.
Definition: AdjacencyList.h:143
const Eigen::Array< std::int32_t, Eigen::Dynamic, 1 > & offsets() const
Offset for each node in array() (const version)
Definition: AdjacencyList.h:178
AdjacencyList(const std::vector< X > &data)
Set all connections for all entities (T is a '2D' container, e.g. a std::vector<<std::vector<std::siz...
Definition: AdjacencyList.h:94
AdjacencyList(const Eigen::Ref< const Eigen::Array< T, Eigen::Dynamic, Eigen::Dynamic, Eigen::RowMajor >> &matrix)
Construct adjacency list for a problem with a fixed number of links (edges) for each node.
Definition: AdjacencyList.h:74
AdjacencyList & operator=(const AdjacencyList &list)=default
Assignment.
const std::int32_t * links_ptr(int node) const
TODO: attempt to remove.
Definition: AdjacencyList.h:169
Graph data structures and algorithms.
Definition: AdjacencyList.h:18