35template <
typename T,
typename NodeData_t = std::
nullptr_t>
42 explicit AdjacencyList(
const std::int32_t n) : _array(n), _offsets(n + 1)
44 std::iota(_array.begin(), _array.end(), 0);
45 std::iota(_offsets.begin(), _offsets.end(), 0);
55 template <
typename U,
typename V>
56 requires std::is_convertible_v<std::remove_cvref_t<U>, std::vector<T>>
57 and std::is_convertible_v<std::remove_cvref_t<V>,
58 std::vector<std::int32_t>>
60 : _array(std::forward<U>(data)), _offsets(std::forward<V>(
offsets))
62 _array.reserve(_offsets.back());
63 assert(_offsets.back() == (std::int32_t)_array.size());
74 template <
typename U,
typename V,
typename W>
75 requires std::is_convertible_v<std::remove_cvref_t<U>, std::vector<T>>
76 and std::is_convertible_v<std::remove_cvref_t<V>,
77 std::vector<std::int32_t>>
78 and std::is_convertible_v<std::remove_cvref_t<W>,
79 std::vector<NodeData_t>>
81 : _array(std::forward<U>(data)), _offsets(std::forward<V>(
offsets)),
84 assert(_node_data.has_value()
85 and _node_data->size() == _offsets.size() - 1);
86 _array.reserve(_offsets.back());
87 assert(_offsets.back() == (std::int32_t)_array.size());
99 _offsets.reserve(data.size() + 1);
100 _offsets.push_back(0);
101 for (
auto& row : data)
102 _offsets.push_back(_offsets.back() + row.size());
104 _array.reserve(_offsets.back());
106 _array.insert(_array.end(), e.begin(), e.end());
128 return this->_array == list._array and this->_offsets == list._offsets;
133 std::int32_t
num_nodes()
const {
return _offsets.size() - 1; }
140 assert((node + 1) < _offsets.size());
141 return _offsets[node + 1] - _offsets[node];
148 std::span<T>
links(std::size_t node)
150 return std::span<T>(_array.data() + _offsets[node],
151 _offsets[node + 1] - _offsets[node]);
158 std::span<const T>
links(std::size_t node)
const
160 return std::span<const T>(_array.data() + _offsets[node],
161 _offsets[node + 1] - _offsets[node]);
165 const std::vector<T>&
array()
const {
return _array; }
168 std::vector<T>&
array() {
return _array; }
171 const std::vector<std::int32_t>&
offsets()
const {
return _offsets; }
174 std::vector<std::int32_t>&
offsets() {
return _offsets; }
178 const std::optional<std::vector<NodeData_t>>&
node_data()
const
185 std::optional<std::vector<NodeData_t>>&
node_data() {
return _node_data; }
192 s <<
"<AdjacencyList> with " + std::to_string(this->
num_nodes()) +
" nodes"
194 for (std::size_t e = 0; e < _offsets.size() - 1; ++e)
196 s <<
" " << e <<
": [";
197 for (
auto link : this->
links(e))
199 s <<
"]" << std::endl;
206 std::vector<T> _array;
209 std::vector<std::int32_t> _offsets;
212 std::optional<std::vector<NodeData_t>> _node_data = std::nullopt;
216template <
typename T,
typename U>
217AdjacencyList(T, U) -> AdjacencyList<typename T::value_type, std::nullptr_t>;
220template <
typename T,
typename U,
typename W>
221AdjacencyList(T, U, W)
222 -> AdjacencyList<typename T::value_type, typename W::value_type>;
233 typename std::decay_t<U>::value_type;
234 requires std::convertible_to<
235 U, std::vector<typename std::decay_t<U>::value_type>>;
237AdjacencyList<typename std::decay_t<U>::value_type>
240 if (degree == 0 and !data.empty())
242 throw std::runtime_error(
"Degree is zero but data is not empty for "
243 "constant degree AdjacencyList");
246 if (degree > 0 and data.size() % degree != 0)
248 throw std::runtime_error(
249 "Incompatible data size and degree for constant degree AdjacencyList");
252 std::int32_t num_nodes = degree == 0 ? data.size() : data.size() / degree;
253 std::vector<std::int32_t> offsets(num_nodes + 1, 0);
254 for (std::size_t i = 1; i < offsets.size(); ++i)
255 offsets[i] = offsets[i - 1] + degree;
257 std::forward<U>(data), std::move(offsets));
This class provides a static adjacency list data structure.
Definition AdjacencyList.h:37
int num_links(std::size_t node) const
Number of connections for given node.
Definition AdjacencyList.h:138
std::span< T > links(std::size_t node)
Get the links (edges) for given node.
Definition AdjacencyList.h:148
bool operator==(const AdjacencyList &list) const
Definition AdjacencyList.h:126
std::vector< std::int32_t > & offsets()
Offset for each node in array().
Definition AdjacencyList.h:174
const std::vector< T > & array() const
Return contiguous array of links for all nodes (const version).
Definition AdjacencyList.h:165
AdjacencyList & operator=(AdjacencyList &&list)=default
Move assignment operator.
std::span< const T > links(std::size_t node) const
Get the links (edges) for given node (const version).
Definition AdjacencyList.h:158
std::optional< std::vector< NodeData_t > > & node_data()
Definition AdjacencyList.h:185
AdjacencyList(const std::int32_t n)
Construct trivial adjacency list where each of the n nodes is connected to itself.
Definition AdjacencyList.h:42
AdjacencyList(AdjacencyList &&list)=default
Move constructor.
AdjacencyList & operator=(const AdjacencyList &list)=default
Assignment operator.
AdjacencyList(U &&data, V &&offsets, W &&node_data)
Construct adjacency list from arrays of edge data, offsets, and node data.
Definition AdjacencyList.h:80
const std::optional< std::vector< NodeData_t > > & node_data() const
Definition AdjacencyList.h:178
AdjacencyList(const std::vector< X > &data)
Definition AdjacencyList.h:96
std::int32_t num_nodes() const
Get the number of nodes.
Definition AdjacencyList.h:133
AdjacencyList(const AdjacencyList &list)=default
Copy constructor.
std::vector< T > & array()
Return contiguous array of links for all nodes.
Definition AdjacencyList.h:168
AdjacencyList(U &&data, V &&offsets)
Construct adjacency list from arrays of edge data and offsets.
Definition AdjacencyList.h:59
const std::vector< std::int32_t > & offsets() const
Offset for each node in array() (const version).
Definition AdjacencyList.h:171
std::string str() const
Informal string representation (pretty-print).
Definition AdjacencyList.h:189
~AdjacencyList()=default
Destructor.
Graph data structures and algorithms.
Definition AdjacencyList.h:20
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:238