DOLFINx
DOLFINx C++ interface
AdjacencyList.h
1// Copyright (C) 2019-2021 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 <numeric>
11#include <sstream>
12#include <utility>
13#include <vector>
14#include <xtensor/xtensor.hpp>
15#include <xtl/xspan.hpp>
16
17namespace dolfinx::graph
18{
19
25template <typename T>
26auto create_adjacency_data(const xt::xtensor<T, 2>& array)
27{
28 std::vector<T> data(array.shape(0) * array.shape(1));
29 std::vector<std::int32_t> offset(array.shape(0) + 1, 0);
30 for (std::size_t i = 0; i < array.shape(0); ++i)
31 {
32 for (std::size_t j = 0; j < array.shape(1); ++j)
33 data[i * array.shape(1) + j] = array(i, j);
34 offset[i + 1] = offset[i] + array.shape(1);
35 }
36 return std::pair(std::move(data), std::move(offset));
37}
38
44template <typename T>
46{
47public:
51 explicit AdjacencyList(const std::int32_t n) : _array(n), _offsets(n + 1)
52 {
53 std::iota(_array.begin(), _array.end(), 0);
54 std::iota(_offsets.begin(), _offsets.end(), 0);
55 }
56
61 template <
62 typename U, typename V,
63 typename = std::enable_if_t<
64 std::is_same<std::vector<T>, std::decay_t<U>>::value
65 && std::is_same<std::vector<std::int32_t>, std::decay_t<V>>::value>>
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
78 template <typename X>
79 explicit AdjacencyList(const std::vector<X>& data)
80 {
81 // Initialize offsets and compute total size
82 _offsets.reserve(data.size() + 1);
83 _offsets.push_back(0);
84 for (auto row = data.begin(); row != data.end(); ++row)
85 _offsets.push_back(_offsets.back() + row->size());
86
87 _array.reserve(_offsets.back());
88 for (auto e = data.begin(); e != data.end(); ++e)
89 _array.insert(_array.end(), e->begin(), e->end());
90 }
91
93 AdjacencyList(const AdjacencyList& list) = default;
94
96 AdjacencyList(AdjacencyList&& list) = default;
97
99 ~AdjacencyList() = default;
100
102 AdjacencyList& operator=(const AdjacencyList& list) = default;
103
106
109 bool operator==(const AdjacencyList& list) const
110 {
111 return this->_array == list._array and this->_offsets == list._offsets;
112 }
113
116 std::int32_t num_nodes() const { return _offsets.size() - 1; }
117
121 int num_links(int node) const
122 {
123 assert((node + 1) < (int)_offsets.size());
124 return _offsets[node + 1] - _offsets[node];
125 }
126
131 xtl::span<T> links(int node)
132 {
133 return xtl::span<T>(_array.data() + _offsets[node],
134 _offsets[node + 1] - _offsets[node]);
135 }
136
141 xtl::span<const T> links(int node) const
142 {
143 return xtl::span<const T>(_array.data() + _offsets[node],
144 _offsets[node + 1] - _offsets[node]);
145 }
146
148 const std::vector<T>& array() const { return _array; }
149
151 std::vector<T>& array() { return _array; }
152
154 const std::vector<std::int32_t>& offsets() const { return _offsets; }
155
157 std::vector<std::int32_t>& offsets() { return _offsets; }
158
161 std::string str() const
162 {
163 std::stringstream s;
164 s << "<AdjacencyList> with " + std::to_string(this->num_nodes()) + " nodes"
165 << std::endl;
166 for (std::size_t e = 0; e < _offsets.size() - 1; ++e)
167 {
168 s << " " << e << ": [";
169 for (auto link : this->links(e))
170 s << link << " ";
171 s << "]" << std::endl;
172 }
173 return s.str();
174 }
175
176private:
177 // Connections for all entities stored as a contiguous array
178 std::vector<T> _array;
179
180 // Position of first connection for each entity (using local index)
181 std::vector<std::int32_t> _offsets;
182};
183
190template <typename U>
192 int degree)
193{
194 if (degree == 0 and !data.empty())
195 {
196 throw std::runtime_error("Degree is zero but data is not empty for "
197 "constant degree AdjacencyList");
198 }
199
200 if (degree > 0 and data.size() % degree != 0)
201 {
202 throw std::runtime_error(
203 "Incompatible data size and degree for constant degree AdjacencyList");
204 }
205
206 std::int32_t num_nodes = degree == 0 ? data.size() : data.size() / degree;
207 std::vector<std::int32_t> offsets(num_nodes + 1, 0);
208 for (std::size_t i = 1; i < offsets.size(); ++i)
209 offsets[i] = offsets[i - 1] + degree;
210 return AdjacencyList<typename U::value_type>(std::forward<U>(data),
211 std::move(offsets));
212}
213
214} // namespace dolfinx::graph
This class provides a static adjacency list data structure. It is commonly used to store directed gra...
Definition: AdjacencyList.h:46
bool operator==(const AdjacencyList &list) const
Equality operator.
Definition: AdjacencyList.h:109
std::vector< std::int32_t > & offsets()
Offset for each node in array()
Definition: AdjacencyList.h:157
const std::vector< T > & array() const
Return contiguous array of links for all nodes (const version)
Definition: AdjacencyList.h:148
AdjacencyList & operator=(AdjacencyList &&list)=default
Move assignment operator.
int num_links(int node) const
Number of connections for given node.
Definition: AdjacencyList.h:121
AdjacencyList(const std::int32_t n)
Construct trivial adjacency list where each of the n nodes is connected to itself.
Definition: AdjacencyList.h:51
AdjacencyList(AdjacencyList &&list)=default
Move constructor.
AdjacencyList & operator=(const AdjacencyList &list)=default
Assignment operator.
xtl::span< T > links(int node)
Get the links (edges) for given node.
Definition: AdjacencyList.h:131
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:79
xtl::span< const T > links(int node) const
Get the links (edges) for given node (const version)
Definition: AdjacencyList.h:141
std::int32_t num_nodes() const
Get the number of nodes.
Definition: AdjacencyList.h:116
AdjacencyList(const AdjacencyList &list)=default
Copy constructor.
AdjacencyList(U &&data, V &&offsets)
Construct adjacency list from arrays of data.
Definition: AdjacencyList.h:66
std::vector< T > & array()
Return contiguous array of links for all nodes.
Definition: AdjacencyList.h:151
const std::vector< std::int32_t > & offsets() const
Offset for each node in array() (const version)
Definition: AdjacencyList.h:154
std::string str() const
Informal string representation (pretty-print)
Definition: AdjacencyList.h:161
~AdjacencyList()=default
Destructor.
Graph data structures and algorithms.
Definition: dofmapbuilder.h:25
auto create_adjacency_data(const xt::xtensor< T, 2 > &array)
Construct adjacency list data for a problem with a fixed number of links (edges) for each node.
Definition: AdjacencyList.h:26
AdjacencyList< typename U::value_type > regular_adjacency_list(U &&data, int degree)
Construct a constant degree (valency) adjacency list.
Definition: AdjacencyList.h:191