DOLFINx
DOLFINx C++ interface
AdjacencyList.h
1// Copyright (C) 2019-2022 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 <span>
14#include <sstream>
15#include <utility>
16#include <vector>
17
18namespace dolfinx::graph
19{
20
26template <typename T>
28{
29public:
33 explicit AdjacencyList(const std::int32_t n) : _array(n), _offsets(n + 1)
34 {
35 std::iota(_array.begin(), _array.end(), 0);
36 std::iota(_offsets.begin(), _offsets.end(), 0);
37 }
38
43 template <std::convertible_to<std::vector<T>> U,
44 std::convertible_to<std::vector<std::int32_t>> V>
45 AdjacencyList(U&& data, V&& offsets)
46 : _array(std::forward<U>(data)), _offsets(std::forward<V>(offsets))
47 {
48 _array.reserve(_offsets.back());
49 assert(_offsets.back() == (std::int32_t)_array.size());
50 }
51
57 template <typename X>
58 explicit AdjacencyList(const std::vector<X>& data)
59 {
60 // Initialize offsets and compute total 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());
65
66 _array.reserve(_offsets.back());
67 for (const auto& e : data)
68 _array.insert(_array.end(), e.begin(), e.end());
69 }
70
72 AdjacencyList(const AdjacencyList& list) = default;
73
75 AdjacencyList(AdjacencyList&& list) = default;
76
78 ~AdjacencyList() = default;
79
81 AdjacencyList& operator=(const AdjacencyList& list) = default;
82
85
88 bool operator==(const AdjacencyList& list) const
89 {
90 return this->_array == list._array and this->_offsets == list._offsets;
91 }
92
95 std::int32_t num_nodes() const { return _offsets.size() - 1; }
96
100 int num_links(int node) const
101 {
102 assert((node + 1) < (int)_offsets.size());
103 return _offsets[node + 1] - _offsets[node];
104 }
105
110 std::span<T> links(int node)
111 {
112 return std::span<T>(_array.data() + _offsets[node],
113 _offsets[node + 1] - _offsets[node]);
114 }
115
120 std::span<const T> links(int node) const
121 {
122 return std::span<const T>(_array.data() + _offsets[node],
123 _offsets[node + 1] - _offsets[node]);
124 }
125
127 const std::vector<T>& array() const { return _array; }
128
130 std::vector<T>& array() { return _array; }
131
133 const std::vector<std::int32_t>& offsets() const { return _offsets; }
134
136 std::vector<std::int32_t>& offsets() { return _offsets; }
137
140 std::string str() const
141 {
142 std::stringstream s;
143 s << "<AdjacencyList> with " + std::to_string(this->num_nodes()) + " nodes"
144 << std::endl;
145 for (std::size_t e = 0; e < _offsets.size() - 1; ++e)
146 {
147 s << " " << e << ": [";
148 for (auto link : this->links(e))
149 s << link << " ";
150 s << "]" << std::endl;
151 }
152 return s.str();
153 }
154
155private:
156 // Connections for all entities stored as a contiguous array
157 std::vector<T> _array;
158
159 // Position of first connection for each entity (using local index)
160 std::vector<std::int32_t> _offsets;
161};
162
170template <typename U>
171 requires requires {
172 typename std::decay_t<U>::value_type;
173 requires std::convertible_to<
174 U, std::vector<typename std::decay_t<U>::value_type>>;
175 }
176AdjacencyList<typename std::decay_t<U>::value_type>
177regular_adjacency_list(U&& data, int degree)
178{
179 if (degree == 0 and !data.empty())
180 {
181 throw std::runtime_error("Degree is zero but data is not empty for "
182 "constant degree AdjacencyList");
183 }
184
185 if (degree > 0 and data.size() % degree != 0)
186 {
187 throw std::runtime_error(
188 "Incompatible data size and degree for constant degree AdjacencyList");
189 }
190
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));
197}
198
199} // namespace dolfinx::graph
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