DOLFINx 0.10.0.0
DOLFINx C++ interface
Loading...
Searching...
No Matches
AdjacencyList.h
1// Copyright (C) 2019-2025 Garth N. Wells
2//
3// This file is part of DOLFINx (https://www.fenicsproject.org)
4//
5// SPDX-License-Identifier: LGPL-3.0-or-later
6
7#pragma once
8
9#include <cassert>
10#include <concepts>
11#include <cstdint>
12#include <numeric>
13#include <optional>
14#include <span>
15#include <sstream>
16#include <utility>
17#include <vector>
18
20{
36template <typename LinkData, typename NodeData = std::nullptr_t>
38{
39public:
41 using link_type = LinkData;
43 using node_data_type = NodeData;
44
48 explicit AdjacencyList(const std::int32_t n) : _array(n), _offsets(n + 1)
49 {
50 std::iota(_array.begin(), _array.end(), 0);
51 std::iota(_offsets.begin(), _offsets.end(), 0);
52 }
53
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>>
66 AdjacencyList(U&& data, V&& offsets)
67 : _array(std::forward<U>(data)), _offsets(std::forward<V>(offsets))
68 {
69 _array.reserve(_offsets.back());
70 assert(_offsets.back() == (std::int32_t)_array.size());
71 }
72
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>>
88 AdjacencyList(U&& data, V&& offsets, W&& node_data)
89 : _array(std::forward<U>(data)), _offsets(std::forward<V>(offsets)),
90 _node_data(std::forward<W>(node_data))
91 {
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());
96 }
97
103 template <typename X>
104 explicit AdjacencyList(const std::vector<X>& data)
105 {
106 // Initialize offsets and compute total size
107 _offsets.reserve(data.size() + 1);
108 _offsets.push_back(0);
109 for (auto& row : data)
110 _offsets.push_back(_offsets.back() + row.size());
111
112 _array.reserve(_offsets.back());
113 for (auto& e : data)
114 _array.insert(_array.end(), e.begin(), e.end());
115 }
116
118 AdjacencyList(const AdjacencyList& list) = default;
119
121 AdjacencyList(AdjacencyList&& list) = default;
122
124 ~AdjacencyList() = default;
125
127 AdjacencyList& operator=(const AdjacencyList& list) = default;
128
131
134 bool operator==(const AdjacencyList& list) const
135 {
136 return this->_array == list._array and this->_offsets == list._offsets;
137 }
138
141 std::int32_t num_nodes() const { return _offsets.size() - 1; }
142
146 int num_links(std::size_t node) const
147 {
148 assert((node + 1) < _offsets.size());
149 return _offsets[node + 1] - _offsets[node];
150 }
151
156 std::span<LinkData> links(std::size_t node)
157 {
158 return std::span<LinkData>(_array.data() + _offsets[node],
159 _offsets[node + 1] - _offsets[node]);
160 }
161
166 std::span<const LinkData> links(std::size_t node) const
167 {
168 return std::span<const LinkData>(_array.data() + _offsets[node],
169 _offsets[node + 1] - _offsets[node]);
170 }
171
173 const std::vector<LinkData>& array() const { return _array; }
174
176 std::vector<LinkData>& array() { return _array; }
177
179 const std::vector<std::int32_t>& offsets() const { return _offsets; }
180
182 std::vector<std::int32_t>& offsets() { return _offsets; }
183
186 const std::optional<std::vector<NodeData>>& node_data() const
187 {
188 return _node_data;
189 }
190
193 std::optional<std::vector<NodeData>>& node_data() { return _node_data; }
194
197 std::string str() const
198 {
199 std::stringstream s;
200 s << "<AdjacencyList> with " + std::to_string(this->num_nodes()) + " nodes"
201 << std::endl;
202 for (std::size_t e = 0; e < _offsets.size() - 1; ++e)
203 {
204 s << " " << e << ": [";
205 for (auto link : this->links(e))
206 s << link << " ";
207 s << "]" << '\n';
208 }
209 return s.str();
210 }
211
212private:
213 // Connections (links/edges) for all entities stored as a contiguous
214 // array
215 std::vector<LinkData> _array;
216
217 // Position of first connection for each entity (using local index)
218 std::vector<std::int32_t> _offsets;
219
220 // Node data, where _node_data[i] is the data associated with node `i`
221 std::optional<std::vector<NodeData>> _node_data = std::nullopt;
222};
223
225template <typename T, typename U>
226AdjacencyList(T, U) -> AdjacencyList<typename T::value_type, std::nullptr_t>;
227
229template <typename T, typename U, typename W>
230AdjacencyList(T, U, W)
231 -> AdjacencyList<typename T::value_type, typename W::value_type>;
232
241template <typename V = std::nullptr_t, typename U>
242 requires requires {
243 typename std::decay_t<U>::value_type;
244 requires std::convertible_to<
245 U, std::vector<typename std::decay_t<U>::value_type>>;
246 }
247AdjacencyList<typename std::decay_t<U>::value_type, V>
248regular_adjacency_list(U&& data, int degree)
249{
250 if (degree == 0 and !data.empty())
251 {
252 throw std::runtime_error("Degree is zero but data is not empty for "
253 "constant degree AdjacencyList");
254 }
255
256 if (degree > 0 and data.size() % degree != 0)
257 {
258 throw std::runtime_error(
259 "Incompatible data size and degree for constant degree AdjacencyList");
260 }
261
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));
268}
269
270} // namespace dolfinx::graph
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