33 explicit AdjacencyList(
const std::int32_t n) : _array(n), _offsets(n + 1)
35 std::iota(_array.begin(), _array.end(), 0);
36 std::iota(_offsets.begin(), _offsets.end(), 0);
43 template <std::convertible_to<std::vector<T>> U,
44 std::convertible_to<std::vector<std::
int32_t>> V>
46 : _array(std::forward<U>(data)), _offsets(std::forward<V>(
offsets))
48 _array.reserve(_offsets.back());
49 assert(_offsets.back() == (std::int32_t)_array.size());
61 _offsets.reserve(data.size() + 1);
62 _offsets.push_back(0);
63 for (
const auto& row : data)
64 _offsets.push_back(_offsets.back() + row.size());
66 _array.reserve(_offsets.back());
67 for (
const auto& e : data)
68 _array.insert(_array.end(), e.begin(), e.end());
90 return this->_array == list._array and this->_offsets == list._offsets;
95 std::int32_t
num_nodes()
const {
return _offsets.size() - 1; }
102 assert((node + 1) < (
int)_offsets.size());
103 return _offsets[node + 1] - _offsets[node];
112 return std::span<T>(_array.data() + _offsets[node],
113 _offsets[node + 1] - _offsets[node]);
120 std::span<const T>
links(
int node)
const
122 return std::span<const T>(_array.data() + _offsets[node],
123 _offsets[node + 1] - _offsets[node]);
127 const std::vector<T>&
array()
const {
return _array; }
130 std::vector<T>&
array() {
return _array; }
133 const std::vector<std::int32_t>&
offsets()
const {
return _offsets; }
136 std::vector<std::int32_t>&
offsets() {
return _offsets; }
143 s <<
"<AdjacencyList> with " + std::to_string(this->
num_nodes()) +
" nodes"
145 for (std::size_t e = 0; e < _offsets.size() - 1; ++e)
147 s <<
" " << e <<
": [";
148 for (
auto link : this->
links(e))
150 s <<
"]" << std::endl;
157 std::vector<T> _array;
160 std::vector<std::int32_t> _offsets;
172 typename std::decay_t<U>::value_type;
173 requires std::convertible_to<
174 U, std::vector<typename std::decay_t<U>::value_type>>;
176AdjacencyList<typename std::decay_t<U>::value_type>
179 if (degree == 0 and !data.empty())
181 throw std::runtime_error(
"Degree is zero but data is not empty for "
182 "constant degree AdjacencyList");
185 if (degree > 0 and data.size() % degree != 0)
187 throw std::runtime_error(
188 "Incompatible data size and degree for constant degree AdjacencyList");
191 std::int32_t num_nodes = degree == 0 ? data.size() : data.size() / degree;
192 std::vector<std::int32_t> offsets(num_nodes + 1, 0);
193 for (std::size_t i = 1; i < offsets.size(); ++i)
194 offsets[i] = offsets[i - 1] + degree;
196 std::forward<U>(data), std::move(offsets));
This class provides a static adjacency list data structure. It is commonly used to store directed gra...
Definition: AdjacencyList.h:28
std::span< T > links(int node)
Get the links (edges) for given node.
Definition: AdjacencyList.h:110
bool operator==(const AdjacencyList &list) const
Equality operator.
Definition: AdjacencyList.h:88
std::vector< std::int32_t > & offsets()
Offset for each node in array()
Definition: AdjacencyList.h:136
const std::vector< T > & array() const
Return contiguous array of links for all nodes (const version)
Definition: AdjacencyList.h:127
AdjacencyList & operator=(AdjacencyList &&list)=default
Move assignment operator.
int num_links(int node) const
Number of connections for given node.
Definition: AdjacencyList.h:100
AdjacencyList(const std::int32_t n)
Construct trivial adjacency list where each of the n nodes is connected to itself.
Definition: AdjacencyList.h:33
AdjacencyList(AdjacencyList &&list)=default
Move constructor.
AdjacencyList & operator=(const AdjacencyList &list)=default
Assignment operator.
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:58
std::int32_t num_nodes() const
Get the number of nodes.
Definition: AdjacencyList.h:95
AdjacencyList(const AdjacencyList &list)=default
Copy constructor.
std::vector< T > & array()
Return contiguous array of links for all nodes.
Definition: AdjacencyList.h:130
std::span< const T > links(int node) const
Get the links (edges) for given node (const version)
Definition: AdjacencyList.h:120
const std::vector< std::int32_t > & offsets() const
Offset for each node in array() (const version)
Definition: AdjacencyList.h:133
std::string str() const
Informal string representation (pretty-print)
Definition: AdjacencyList.h:140
~AdjacencyList()=default
Destructor.
AdjacencyList(U &&data, V &&offsets)
Construct adjacency list from arrays of data.
Definition: AdjacencyList.h:45
Graph data structures and algorithms.
Definition: dofmapbuilder.h:25
AdjacencyList< typename std::decay_t< U >::value_type > regular_adjacency_list(U &&data, int degree)
Construct a constant degree (valency) adjacency list.
Definition: AdjacencyList.h:177