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/Dense>
10 #include <boost/functional/hash.hpp>
11 #include <cassert>
12 #include <numeric>
13 #include <sstream>
14 #include <type_traits>
15 #include <vector>
16 
17 namespace dolfinx::graph
18 {
19 
25 
26 template <typename T>
28 {
29 public:
33  explicit AdjacencyList(const std::int32_t n) : _array(n), _offsets(n + 1)
34  {
35  std::iota(_array.data(), _array.data() + n, 0);
36  std::iota(_offsets.data(), _offsets.data() + n + 1, 0);
37  }
38 
43  template <typename U, typename V,
44  std::enable_if_t<std::is_base_of<Eigen::EigenBase<std::decay_t<V>>,
45  std::decay_t<V>>::value,
46  int> = 0>
47  AdjacencyList(U&& data, V&& offsets)
48  : _array(std::forward<U>(data)), _offsets(std::forward<V>(offsets))
49  {
50  // Do nothing
51  }
52 
58  template <typename U, typename V,
59  std::enable_if_t<!std::is_base_of<Eigen::EigenBase<std::decay_t<V>>,
60  std::decay_t<V>>::value,
61  int> = 0>
62  AdjacencyList(U&& data, V&& offsets)
63  : _array(data.size()), _offsets(offsets.size())
64  {
65  assert(offsets.back() == (std::int32_t)data.size());
66  std::copy(data.begin(), data.end(), _array.data());
67  std::copy(offsets.begin(), offsets.end(), _offsets.data());
68  }
69 
74  explicit AdjacencyList(
75  const Eigen::Ref<const Eigen::Array<T, Eigen::Dynamic, Eigen::Dynamic,
76  Eigen::RowMajor>>& matrix)
77  : _array(matrix.rows() * matrix.cols()), _offsets(matrix.rows() + 1)
78  {
79  const std::int32_t num_links = matrix.cols();
80  for (Eigen::Index e = 0; e < _offsets.rows(); e++)
81  _offsets[e] = e * num_links;
82 
83  // NOTE: Do not directly copy data from matrix because it may be a
84  // view into a larger array
85  for (Eigen::Index i = 0; i < matrix.rows(); ++i)
86  _array.segment(_offsets(i), num_links) = matrix.row(i);
87  }
88 
93  template <typename X>
94  explicit AdjacencyList(const std::vector<X>& data) : _offsets(data.size() + 1)
95  {
96  // Initialize offsets and compute total size
97  std::int32_t size = 0;
98  for (std::size_t e = 0; e < data.size(); e++)
99  {
100  _offsets[e] = size;
101  size += data[e].size();
102  }
103  _offsets[data.size()] = size;
104 
105  std::vector<T> c;
106  c.reserve(size);
107  for (auto e = data.begin(); e != data.end(); ++e)
108  c.insert(c.end(), e->begin(), e->end());
109 
110  _array = Eigen::Array<T, Eigen::Dynamic, 1>(c.size());
111  std::copy(c.begin(), c.end(), _array.data());
112  }
113 
115  AdjacencyList(const AdjacencyList& list) = default;
116 
118  AdjacencyList(AdjacencyList&& list) = default;
119 
121  ~AdjacencyList() = default;
122 
124  AdjacencyList& operator=(const AdjacencyList& list) = default;
125 
127  AdjacencyList& operator=(AdjacencyList&& list) = default;
128 
130  bool operator==(const AdjacencyList& list) const
131  {
132  return (this->_array == list._array).all()
133  and (this->_offsets == list._offsets).all();
134  }
135 
138  std::int32_t num_nodes() const { return _offsets.rows() - 1; }
139 
143  int num_links(int node) const
144  {
145  assert((node + 1) < _offsets.rows());
146  return _offsets[node + 1] - _offsets[node];
147  }
148 
153  typename Eigen::Array<T, Eigen::Dynamic, 1>::SegmentReturnType links(int node)
154  {
155  return _array.segment(_offsets[node], _offsets[node + 1] - _offsets[node]);
156  }
157 
162  typename Eigen::Array<T, Eigen::Dynamic, 1>::ConstSegmentReturnType
163  links(int node) const
164  {
165  return _array.segment(_offsets[node], _offsets[node + 1] - _offsets[node]);
166  }
167 
169  const std::int32_t* links_ptr(int node) const
170  {
171  return &_array[_offsets[node]];
172  }
173 
175  const Eigen::Array<T, Eigen::Dynamic, 1>& array() const { return _array; }
176 
178  const Eigen::Array<std::int32_t, Eigen::Dynamic, 1>& offsets() const
179  {
180  return _offsets;
181  }
182 
184  std::size_t hash() const
185  {
186  return boost::hash_range(_array.data(), _array.data() + _array.size());
187  }
188 
190  std::string str() const
191  {
192  std::stringstream s;
193  s << "<AdjacencyList> with " + std::to_string(this->num_nodes()) + " nodes"
194  << std::endl;
195  for (Eigen::Index e = 0; e < _offsets.size() - 1; e++)
196  s << " " << e << ": " << this->links(e).transpose() << std::endl;
197  return s.str();
198  }
199 
200 private:
201  // Connections for all entities stored as a contiguous array
202  Eigen::Array<T, Eigen::Dynamic, 1> _array;
203 
204  // Position of first connection for each entity (using local index)
205  Eigen::Array<std::int32_t, Eigen::Dynamic, 1> _offsets;
206 }; // namespace graph
207 } // namespace dolfinx::graph
dolfinx::graph::AdjacencyList::num_links
int num_links(int node) const
Number of connections for given node.
Definition: AdjacencyList.h:143
dolfinx::graph::AdjacencyList::num_nodes
std::int32_t num_nodes() const
Number of nodes.
Definition: AdjacencyList.h:138
dolfinx::graph
Graph data structures and algorithms.
Definition: AdjacencyList.h:17
dolfinx::graph::AdjacencyList::links
Eigen::Array< T, Eigen::Dynamic, 1 >::SegmentReturnType links(int node)
Links (edges) for given node.
Definition: AdjacencyList.h:153
dolfinx::graph::AdjacencyList::AdjacencyList
AdjacencyList(const Eigen::Ref< const Eigen::Array< T, Eigen::Dynamic, Eigen::Dynamic, Eigen::RowMajor >> &matrix)
Construct adjacency list for a problem with a fixed number of links (edges) for each node.
Definition: AdjacencyList.h:74
dolfinx::graph::AdjacencyList::AdjacencyList
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:94
dolfinx::graph::AdjacencyList::array
const Eigen::Array< T, Eigen::Dynamic, 1 > & array() const
Return contiguous array of links for all nodes (const version)
Definition: AdjacencyList.h:175
dolfinx::graph::AdjacencyList
This class provides a static adjacency list data structure. It is commonly used to store directed gra...
Definition: AdjacencyList.h:27
dolfinx::graph::AdjacencyList::offsets
const Eigen::Array< std::int32_t, Eigen::Dynamic, 1 > & offsets() const
Offset for each node in array() (const version)
Definition: AdjacencyList.h:178
dolfinx::graph::AdjacencyList::AdjacencyList
AdjacencyList(const std::int32_t n)
Construct trivial adjacency list where each of the n nodes is connected to itself.
Definition: AdjacencyList.h:33
dolfinx::graph::AdjacencyList::str
std::string str() const
Return informal string representation (pretty-print)
Definition: AdjacencyList.h:190
dolfinx::graph::AdjacencyList::operator=
AdjacencyList & operator=(const AdjacencyList &list)=default
Assignment.
dolfinx::graph::AdjacencyList::links_ptr
const std::int32_t * links_ptr(int node) const
TODO: attempt to remove.
Definition: AdjacencyList.h:169
dolfinx::graph::AdjacencyList::AdjacencyList
AdjacencyList(U &&data, V &&offsets)
Construct adjacency list from arrays of data (Eigen data types)
Definition: AdjacencyList.h:47
dolfinx::graph::AdjacencyList::~AdjacencyList
~AdjacencyList()=default
Destructor.
dolfinx::graph::AdjacencyList::links
Eigen::Array< T, Eigen::Dynamic, 1 >::ConstSegmentReturnType links(int node) const
Links (edges) for given node (const version)
Definition: AdjacencyList.h:163
dolfinx::graph::AdjacencyList::hash
std::size_t hash() const
Hash of graph.
Definition: AdjacencyList.h:184
dolfinx::graph::AdjacencyList::operator==
bool operator==(const AdjacencyList &list) const
Equality operator.
Definition: AdjacencyList.h:130