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 <Eigen/Core>
10 #include <cassert>
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>
26 auto create_adjacency_data(const Eigen::DenseBase<T>& matrix)
27 {
28  std::vector<typename T::Scalar> data(matrix.rows() * matrix.cols());
29  std::vector<std::int32_t> offset(matrix.rows() + 1, 0);
30  for (Eigen::Index i = 0; i < matrix.rows(); ++i)
31  {
32  for (Eigen::Index j = 0; j < matrix.cols(); ++j)
33  data[i * matrix.cols() + j] = matrix(i, j);
34  offset[i + 1] = offset[i] + matrix.cols();
35  }
36  return std::pair(std::move(data), std::move(offset));
37 }
38 
44 template <typename T>
46 {
47 public:
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  assert(_offsets.back() == (std::int32_t)_array.size());
70  }
71 
76  template <typename X>
77  explicit AdjacencyList(const std::vector<X>& data)
78  {
79  // Initialize offsets and compute total size
80  _offsets.reserve(data.size() + 1);
81  _offsets.push_back(0);
82  for (auto row = data.begin(); row != data.end(); ++row)
83  _offsets.push_back(_offsets.back() + row->size());
84 
85  _array.reserve(_offsets.back());
86  for (auto e = data.begin(); e != data.end(); ++e)
87  _array.insert(_array.end(), e->begin(), e->end());
88  }
89 
91  AdjacencyList(const AdjacencyList& list) = default;
92 
94  AdjacencyList(AdjacencyList&& list) = default;
95 
97  ~AdjacencyList() = default;
98 
100  AdjacencyList& operator=(const AdjacencyList& list) = default;
101 
104 
106  bool operator==(const AdjacencyList& list) const
107  {
108  return this->_array == list._array and this->_offsets == list._offsets;
109  }
110 
113  std::int32_t num_nodes() const { return _offsets.size() - 1; }
114 
118  int num_links(int node) const
119  {
120  assert((node + 1) < (int)_offsets.size());
121  return _offsets[node + 1] - _offsets[node];
122  }
123 
128  tcb::span<T> links(int node)
129  {
130  return tcb::span(_array.data() + _offsets[node],
131  _offsets[node + 1] - _offsets[node]);
132  }
133 
138  tcb::span<const T> links(int node) const
139  {
140  return tcb::span(_array.data() + _offsets[node],
141  _offsets[node + 1] - _offsets[node]);
142  }
143 
145  const std::vector<T>& array() const { return _array; }
146 
148  std::vector<T>& array() { return _array; }
149 
151  const std::vector<std::int32_t>& offsets() const { return _offsets; }
152 
155  template <typename X>
156  decltype(auto) as_type() const
157  {
158 // Workaround for Intel compler bug, see
159 // https://community.intel.com/t5/Intel-C-Compiler/quot-if-constexpr-quot-and-quot-missing-return-statement-quot-in/td-p/1154551
160 #ifdef __INTEL_COMPILER
161 #pragma warning(disable : 1011)
162 #endif
163 
164  if constexpr (std::is_same<X, T>::value)
165  return *this;
166  else
167  {
169  std::vector<X>(_array.begin(), _array.end()), this->_offsets);
170  }
171  }
172 
174  std::string str() const
175  {
176  std::stringstream s;
177  s << "<AdjacencyList> with " + std::to_string(this->num_nodes()) + " nodes"
178  << std::endl;
179  for (std::size_t e = 0; e < _offsets.size() - 1; ++e)
180  {
181  s << " " << e << ": [";
182  for (auto link : this->links(e))
183  s << link << " ";
184  s << "]" << std::endl;
185  }
186  return s.str();
187  }
188 
189 private:
190  // Connections for all entities stored as a contiguous array
191  std::vector<T> _array;
192 
193  // Position of first connection for each entity (using local index)
194  std::vector<std::int32_t> _offsets;
195 };
196 
203 template <typename T, typename U>
205 {
206  // using T = typename U::value_type;
207  assert(data.size() % degree == 0);
208  std::vector<std::int32_t> offsets(data.size() / degree + 1, 0);
209  for (std::size_t i = 1; i < offsets.size(); ++i)
210  offsets[i] = offsets[i - 1] + degree;
211  return AdjacencyList<T>(std::forward<U>(data), 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
tcb::span< const T > links(int node) const
Get the links (edges) for given node (const version)
Definition: AdjacencyList.h:138
bool operator==(const AdjacencyList &list) const
Equality operator.
Definition: AdjacencyList.h:106
std::string str() const
Return informal string representation (pretty-print)
Definition: AdjacencyList.h:174
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:51
const std::vector< std::int32_t > & offsets() const
Offset for each node in array() (const version)
Definition: AdjacencyList.h:151
tcb::span< T > links(int node)
Get the links (edges) for given node.
Definition: AdjacencyList.h:128
std::int32_t num_nodes() const
Get the number of nodes.
Definition: AdjacencyList.h:113
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:156
std::vector< T > & array()
Return contiguous array of links for all nodes.
Definition: AdjacencyList.h:148
AdjacencyList(U &&data, V &&offsets)
Construct adjacency list from arrays of data.
Definition: AdjacencyList.h:66
const std::vector< T > & array() const
Return contiguous array of links for all nodes (const version)
Definition: AdjacencyList.h:145
int num_links(int node) const
Number of connections for given node.
Definition: AdjacencyList.h:118
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:77
AdjacencyList & operator=(const AdjacencyList &list)=default
Assignment.
Graph data structures and algorithms.
Definition: AdjacencyList.h:18
auto create_adjacency_data(const Eigen::DenseBase< T > &matrix)
Construct adjacency list data for a problem with a fixed number of links (edges) for each node.
Definition: AdjacencyList.h:26
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:204