36template <
typename LinkData,
typename NodeData = std::
nullptr_t>
48 explicit AdjacencyList(
const std::int32_t n) : _array(n), _offsets(n + 1)
50 std::iota(_array.begin(), _array.end(), 0);
51 std::iota(_offsets.begin(), _offsets.end(), 0);
61 template <
typename U,
typename V>
62 requires std::is_convertible_v<std::remove_cvref_t<U>,
63 std::vector<LinkData>>
64 and std::is_convertible_v<std::remove_cvref_t<V>,
65 std::vector<std::int32_t>>
67 : _array(std::forward<U>(data)), _offsets(std::forward<V>(
offsets))
69 _array.reserve(_offsets.back());
70 assert(_offsets.back() == (std::int32_t)_array.size());
81 template <
typename U,
typename V,
typename W>
82 requires std::is_convertible_v<std::remove_cvref_t<U>,
83 std::vector<LinkData>>
84 and std::is_convertible_v<std::remove_cvref_t<V>,
85 std::vector<std::int32_t>>
86 and std::is_convertible_v<std::remove_cvref_t<W>,
87 std::vector<NodeData>>
89 : _array(std::forward<U>(data)), _offsets(std::forward<V>(
offsets)),
92 assert(_node_data.has_value()
93 and _node_data->size() == _offsets.size() - 1);
94 _array.reserve(_offsets.back());
95 assert(_offsets.back() == (std::int32_t)_array.size());
103 template <
typename X>
107 _offsets.reserve(data.size() + 1);
108 _offsets.push_back(0);
109 for (
auto& row : data)
110 _offsets.push_back(_offsets.back() + row.size());
112 _array.reserve(_offsets.back());
114 _array.insert(_array.end(), e.begin(), e.end());
136 return this->_array == list._array and this->_offsets == list._offsets;
141 std::int32_t
num_nodes()
const {
return _offsets.size() - 1; }
148 assert((node + 1) < _offsets.size());
149 return _offsets[node + 1] - _offsets[node];
156 std::span<LinkData>
links(std::size_t node)
158 return std::span<LinkData>(_array.data() + _offsets[node],
159 _offsets[node + 1] - _offsets[node]);
166 std::span<const LinkData>
links(std::size_t node)
const
168 return std::span<const LinkData>(_array.data() + _offsets[node],
169 _offsets[node + 1] - _offsets[node]);
173 const std::vector<LinkData>&
array()
const {
return _array; }
176 std::vector<LinkData>&
array() {
return _array; }
179 const std::vector<std::int32_t>&
offsets()
const {
return _offsets; }
182 std::vector<std::int32_t>&
offsets() {
return _offsets; }
186 const std::optional<std::vector<NodeData>>&
node_data()
const
193 std::optional<std::vector<NodeData>>&
node_data() {
return _node_data; }
200 s <<
"<AdjacencyList> with " + std::to_string(this->
num_nodes()) +
" nodes"
202 for (std::size_t e = 0; e < _offsets.size() - 1; ++e)
204 s <<
" " << e <<
": [";
205 for (
auto link : this->
links(e))
215 std::vector<LinkData> _array;
218 std::vector<std::int32_t> _offsets;
221 std::optional<std::vector<NodeData>> _node_data = std::nullopt;
225template <
typename T,
typename U>
226AdjacencyList(T, U) -> AdjacencyList<typename T::value_type, std::nullptr_t>;
229template <
typename T,
typename U,
typename W>
230AdjacencyList(T, U, W)
231 -> AdjacencyList<typename T::value_type, typename W::value_type>;
241template <
typename V = std::
nullptr_t,
typename U>
243 typename std::decay_t<U>::value_type;
244 requires std::convertible_to<
245 U, std::vector<typename std::decay_t<U>::value_type>>;
247AdjacencyList<typename std::decay_t<U>::value_type, V>
250 if (degree == 0 and !data.empty())
252 throw std::runtime_error(
"Degree is zero but data is not empty for "
253 "constant degree AdjacencyList");
256 if (degree > 0 and data.size() % degree != 0)
258 throw std::runtime_error(
259 "Incompatible data size and degree for constant degree AdjacencyList");
262 std::int32_t num_nodes = degree == 0 ? data.size() : data.size() / degree;
263 std::vector<std::int32_t> offsets(num_nodes + 1, 0);
264 for (std::size_t i = 1; i < offsets.size(); ++i)
265 offsets[i] = offsets[i - 1] + degree;
267 std::forward<U>(data), std::move(offsets));
This class provides a static adjacency list data structure.
Definition AdjacencyList.h:38
int num_links(std::size_t node) const
Number of connections for given node.
Definition AdjacencyList.h:146
bool operator==(const AdjacencyList &list) const
Definition AdjacencyList.h:134
std::vector< std::int32_t > & offsets()
Offset for each node in array().
Definition AdjacencyList.h:182
AdjacencyList & operator=(AdjacencyList &&list)=default
Move assignment operator.
AdjacencyList(U &&data, V &&offsets, W &&node_data)
Construct adjacency list from arrays of link (edge) data, offsets, and node data.
Definition AdjacencyList.h:88
const std::vector< LinkData > & array() const
Return contiguous array of links for all nodes (const version).
Definition AdjacencyList.h:173
AdjacencyList(const std::int32_t n)
Construct trivial adjacency list where each of the n nodes is connected to itself.
Definition AdjacencyList.h:48
AdjacencyList(AdjacencyList &&list)=default
Move constructor.
AdjacencyList & operator=(const AdjacencyList &list)=default
Assignment operator.
std::span< LinkData > links(std::size_t node)
Get the links (edges) for given node.
Definition AdjacencyList.h:156
AdjacencyList(U &&data, V &&offsets)
Construct adjacency list from arrays of link (edge) data and offsets.
Definition AdjacencyList.h:66
AdjacencyList(const std::vector< X > &data)
Definition AdjacencyList.h:104
NodeData node_data_type
Adjacency list node data type.
Definition AdjacencyList.h:43
std::int32_t num_nodes() const
Get the number of nodes.
Definition AdjacencyList.h:141
AdjacencyList(const AdjacencyList &list)=default
Copy constructor.
LinkData link_type
Adjacency list link (edge) type.
Definition AdjacencyList.h:41
const std::optional< std::vector< NodeData > > & node_data() const
Definition AdjacencyList.h:186
const std::vector< std::int32_t > & offsets() const
Offset for each node in array() (const version).
Definition AdjacencyList.h:179
std::span< const LinkData > links(std::size_t node) const
Get the links (edges) for given node (const version).
Definition AdjacencyList.h:166
std::string str() const
Informal string representation (pretty-print).
Definition AdjacencyList.h:197
std::optional< std::vector< NodeData > > & node_data()
Definition AdjacencyList.h:193
~AdjacencyList()=default
Destructor.
std::vector< LinkData > & array()
Return contiguous array of links for all nodes.
Definition AdjacencyList.h:176
Graph data structures and algorithms.
Definition AdjacencyList.h:20
AdjacencyList< typename std::decay_t< U >::value_type, V > regular_adjacency_list(U &&data, int degree)
Construct a constant degree (valency) adjacency list.
Definition AdjacencyList.h:248