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{
35template <typename T, typename NodeData_t = std::nullptr_t>
37{
38public:
42 explicit AdjacencyList(const std::int32_t n) : _array(n), _offsets(n + 1)
43 {
44 std::iota(_array.begin(), _array.end(), 0);
45 std::iota(_offsets.begin(), _offsets.end(), 0);
46 }
47
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>>
59 AdjacencyList(U&& data, V&& offsets)
60 : _array(std::forward<U>(data)), _offsets(std::forward<V>(offsets))
61 {
62 _array.reserve(_offsets.back());
63 assert(_offsets.back() == (std::int32_t)_array.size());
64 }
65
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>>
80 AdjacencyList(U&& data, V&& offsets, W&& node_data)
81 : _array(std::forward<U>(data)), _offsets(std::forward<V>(offsets)),
82 _node_data(std::forward<W>(node_data))
83 {
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());
88 }
89
95 template <typename X>
96 explicit AdjacencyList(const std::vector<X>& data)
97 {
98 // Initialize offsets and compute total 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());
103
104 _array.reserve(_offsets.back());
105 for (auto& e : data)
106 _array.insert(_array.end(), e.begin(), e.end());
107 }
108
110 AdjacencyList(const AdjacencyList& list) = default;
111
113 AdjacencyList(AdjacencyList&& list) = default;
114
116 ~AdjacencyList() = default;
117
119 AdjacencyList& operator=(const AdjacencyList& list) = default;
120
123
126 bool operator==(const AdjacencyList& list) const
127 {
128 return this->_array == list._array and this->_offsets == list._offsets;
129 }
130
133 std::int32_t num_nodes() const { return _offsets.size() - 1; }
134
138 int num_links(std::size_t node) const
139 {
140 assert((node + 1) < _offsets.size());
141 return _offsets[node + 1] - _offsets[node];
142 }
143
148 std::span<T> links(std::size_t node)
149 {
150 return std::span<T>(_array.data() + _offsets[node],
151 _offsets[node + 1] - _offsets[node]);
152 }
153
158 std::span<const T> links(std::size_t node) const
159 {
160 return std::span<const T>(_array.data() + _offsets[node],
161 _offsets[node + 1] - _offsets[node]);
162 }
163
165 const std::vector<T>& array() const { return _array; }
166
168 std::vector<T>& array() { return _array; }
169
171 const std::vector<std::int32_t>& offsets() const { return _offsets; }
172
174 std::vector<std::int32_t>& offsets() { return _offsets; }
175
178 const std::optional<std::vector<NodeData_t>>& node_data() const
179 {
180 return _node_data;
181 }
182
185 std::optional<std::vector<NodeData_t>>& node_data() { return _node_data; }
186
189 std::string str() const
190 {
191 std::stringstream s;
192 s << "<AdjacencyList> with " + std::to_string(this->num_nodes()) + " nodes"
193 << std::endl;
194 for (std::size_t e = 0; e < _offsets.size() - 1; ++e)
195 {
196 s << " " << e << ": [";
197 for (auto link : this->links(e))
198 s << link << " ";
199 s << "]" << std::endl;
200 }
201 return s.str();
202 }
203
204private:
205 // Connections for all entities stored as a contiguous array
206 std::vector<T> _array;
207
208 // Position of first connection for each entity (using local index)
209 std::vector<std::int32_t> _offsets;
210
211 // Node data, where _node_data[i] is the data associated with node `i`
212 std::optional<std::vector<NodeData_t>> _node_data = std::nullopt;
213};
214
216template <typename T, typename U>
217AdjacencyList(T, U) -> AdjacencyList<typename T::value_type, std::nullptr_t>;
218
220template <typename T, typename U, typename W>
221AdjacencyList(T, U, W)
222 -> AdjacencyList<typename T::value_type, typename W::value_type>;
223
231template <typename U>
232 requires requires {
233 typename std::decay_t<U>::value_type;
234 requires std::convertible_to<
235 U, std::vector<typename std::decay_t<U>::value_type>>;
236 }
237AdjacencyList<typename std::decay_t<U>::value_type>
238regular_adjacency_list(U&& data, int degree)
239{
240 if (degree == 0 and !data.empty())
241 {
242 throw std::runtime_error("Degree is zero but data is not empty for "
243 "constant degree AdjacencyList");
244 }
245
246 if (degree > 0 and data.size() % degree != 0)
247 {
248 throw std::runtime_error(
249 "Incompatible data size and degree for constant degree AdjacencyList");
250 }
251
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));
258}
259
260} // namespace dolfinx::graph
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