DOLFIN-X
DOLFIN-X C++ interface
AdjacencyList.h
1 // Copyright (C) 2006-2019 Anders Logg and 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 <dolfinx/common/array2d.h>
11 #include <dolfinx/common/span.hpp>
12 #include <numeric>
13 #include <sstream>
14 #include <utility>
15 #include <vector>
16 
17 namespace dolfinx::graph
18 {
19 
25 template <typename T>
27 {
28  std::vector<T> data(array.size());
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 
44 template <typename Container>
45 auto create_adjacency_data(const Container& matrix)
46 {
47  using T = typename Container::value_type;
48 
49  std::vector<T> data(matrix.size());
50  std::vector<std::int32_t> offset(matrix.rows() + 1, 0);
51 
52  for (std::size_t i = 0; i < std::size_t(matrix.rows()); ++i)
53  {
54  for (std::size_t j = 0; j < std::size_t(matrix.cols()); ++j)
55  data[i * matrix.cols() + j] = matrix(i, j);
56  offset[i + 1] = offset[i] + matrix.cols();
57  }
58  return std::pair(std::move(data), std::move(offset));
59 }
60 
66 template <typename T>
68 {
69 public:
73  explicit AdjacencyList(const std::int32_t n) : _array(n), _offsets(n + 1)
74  {
75  std::iota(_array.begin(), _array.end(), 0);
76  std::iota(_offsets.begin(), _offsets.end(), 0);
77  }
78 
83  template <
84  typename U, typename V,
85  typename = std::enable_if_t<
86  std::is_same<std::vector<T>, std::decay_t<U>>::value
87  && std::is_same<std::vector<std::int32_t>, std::decay_t<V>>::value>>
88  AdjacencyList(U&& data, V&& offsets)
89  : _array(std::forward<U>(data)), _offsets(std::forward<V>(offsets))
90  {
91  _array.reserve(_offsets.back());
92  assert(_offsets.back() == (std::int32_t)_array.size());
93  }
94 
99  template <typename X>
100  explicit AdjacencyList(const std::vector<X>& data)
101  {
102  // Initialize offsets and compute total size
103  _offsets.reserve(data.size() + 1);
104  _offsets.push_back(0);
105  for (auto row = data.begin(); row != data.end(); ++row)
106  _offsets.push_back(_offsets.back() + row->size());
107 
108  _array.reserve(_offsets.back());
109  for (auto e = data.begin(); e != data.end(); ++e)
110  _array.insert(_array.end(), e->begin(), e->end());
111  }
112 
114  AdjacencyList(const AdjacencyList& list) = default;
115 
117  AdjacencyList(AdjacencyList&& list) = default;
118 
120  ~AdjacencyList() = default;
121 
123  AdjacencyList& operator=(const AdjacencyList& list) = default;
124 
127 
129  bool operator==(const AdjacencyList& list) const
130  {
131  return this->_array == list._array and this->_offsets == list._offsets;
132  }
133 
136  std::int32_t num_nodes() const { return _offsets.size() - 1; }
137 
141  int num_links(int node) const
142  {
143  assert((node + 1) < (int)_offsets.size());
144  return _offsets[node + 1] - _offsets[node];
145  }
146 
151  tcb::span<T> links(int node)
152  {
153  return tcb::span(_array.data() + _offsets[node],
154  _offsets[node + 1] - _offsets[node]);
155  }
156 
161  tcb::span<const T> links(int node) const
162  {
163  return tcb::span(_array.data() + _offsets[node],
164  _offsets[node + 1] - _offsets[node]);
165  }
166 
168  const std::vector<T>& array() const { return _array; }
169 
171  std::vector<T>& array() { return _array; }
172 
174  const std::vector<std::int32_t>& offsets() const { return _offsets; }
175 
178  template <typename X>
179  decltype(auto) as_type() const
180  {
181 // Workaround for Intel compler bug, see
182 // https://community.intel.com/t5/Intel-C-Compiler/quot-if-constexpr-quot-and-quot-missing-return-statement-quot-in/td-p/1154551
183 #ifdef __INTEL_COMPILER
184 #pragma warning(disable : 1011)
185 #endif
186 
187  if constexpr (std::is_same<X, T>::value)
188  return *this;
189  else
190  {
192  std::vector<X>(_array.begin(), _array.end()), this->_offsets);
193  }
194  }
195 
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 << "]" << std::endl;
208  }
209  return s.str();
210  }
211 
212 private:
213  // Connections for all entities stored as a contiguous array
214  std::vector<T> _array;
215 
216  // Position of first connection for each entity (using local index)
217  std::vector<std::int32_t> _offsets;
218 };
219 
226 template <typename T, typename U>
228 {
229  // using T = typename U::value_type;
230  assert(data.size() % degree == 0);
231  std::vector<std::int32_t> offsets(data.size() / degree + 1, 0);
232  for (std::size_t i = 1; i < offsets.size(); ++i)
233  offsets[i] = offsets[i - 1] + degree;
234  return AdjacencyList<T>(std::forward<U>(data), std::move(offsets));
235 }
236 
237 } // namespace dolfinx::graph
This class provides a dynamic 2-dimensional row-wise array data structure.
Definition: array2d.h:21
std::array< size_type, 2 > shape
The shape of the array.
Definition: array2d.h:157
constexpr size_type size() const noexcept
Returns the number of elements in the array.
Definition: array2d.h:144
This class provides a static adjacency list data structure. It is commonly used to store directed gra...
Definition: AdjacencyList.h:68
tcb::span< const T > links(int node) const
Get the links (edges) for given node (const version)
Definition: AdjacencyList.h:161
bool operator==(const AdjacencyList &list) const
Equality operator.
Definition: AdjacencyList.h:129
std::string str() const
Return informal string representation (pretty-print)
Definition: AdjacencyList.h:197
AdjacencyList & operator=(AdjacencyList &&list)=default
Move assignment.
~AdjacencyList()=default
Destructor.
AdjacencyList(const AdjacencyList &list)=default
Copy constructor.
AdjacencyList(const std::int32_t n)
Construct trivial adjacency list where each of the n nodes is connected to itself.
Definition: AdjacencyList.h:73
const std::vector< std::int32_t > & offsets() const
Offset for each node in array() (const version)
Definition: AdjacencyList.h:174
tcb::span< T > links(int node)
Get the links (edges) for given node.
Definition: AdjacencyList.h:151
std::int32_t num_nodes() const
Get the number of nodes.
Definition: AdjacencyList.h:136
AdjacencyList(AdjacencyList &&list)=default
Move constructor.
decltype(auto) as_type() const
Copy of the Adjacency List if the specified type is different from the current type,...
Definition: AdjacencyList.h:179
std::vector< T > & array()
Return contiguous array of links for all nodes.
Definition: AdjacencyList.h:171
AdjacencyList(U &&data, V &&offsets)
Construct adjacency list from arrays of data.
Definition: AdjacencyList.h:88
const std::vector< T > & array() const
Return contiguous array of links for all nodes (const version)
Definition: AdjacencyList.h:168
int num_links(int node) const
Number of connections for given node.
Definition: AdjacencyList.h:141
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:100
AdjacencyList & operator=(const AdjacencyList &list)=default
Assignment.
Graph data structures and algorithms.
Definition: AdjacencyList.h:18
AdjacencyList< T > build_adjacency_list(U &&data, int degree)
Construct an adjacency list from array of data for a graph with constant degree (valency)....
Definition: AdjacencyList.h:227
auto create_adjacency_data(const array2d< T > &array)
Construct adjacency list data for a problem with a fixed number of links (edges) for each node.
Definition: AdjacencyList.h:26