10 #include <dolfinx/common/array2d.h>
11 #include <dolfinx/common/span.hpp>
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)
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];
36 return std::pair(std::move(data), std::move(offset));
44 template <
typename Container>
47 using T =
typename Container::value_type;
49 std::vector<T> data(matrix.size());
50 std::vector<std::int32_t> offset(matrix.rows() + 1, 0);
52 for (std::size_t i = 0; i < std::size_t(matrix.rows()); ++i)
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();
58 return std::pair(std::move(data), std::move(offset));
73 explicit AdjacencyList(
const std::int32_t n) : _array(n), _offsets(n + 1)
75 std::iota(_array.begin(), _array.end(), 0);
76 std::iota(_offsets.begin(), _offsets.end(), 0);
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>>
89 : _array(std::forward<U>(data)), _offsets(std::forward<V>(
offsets))
91 _array.reserve(_offsets.back());
92 assert(_offsets.back() == (std::int32_t)_array.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());
108 _array.reserve(_offsets.back());
109 for (
auto e = data.begin(); e != data.end(); ++e)
110 _array.insert(_array.end(), e->begin(), e->end());
131 return this->_array == list._array and this->_offsets == list._offsets;
136 std::int32_t
num_nodes()
const {
return _offsets.size() - 1; }
143 assert((node + 1) < (
int)_offsets.size());
144 return _offsets[node + 1] - _offsets[node];
153 return tcb::span(_array.data() + _offsets[node],
154 _offsets[node + 1] - _offsets[node]);
161 tcb::span<const T>
links(
int node)
const
163 return tcb::span(_array.data() + _offsets[node],
164 _offsets[node + 1] - _offsets[node]);
168 const std::vector<T>&
array()
const {
return _array; }
171 std::vector<T>&
array() {
return _array; }
174 const std::vector<std::int32_t>&
offsets()
const {
return _offsets; }
178 template <
typename X>
183 #ifdef __INTEL_COMPILER
184 #pragma warning(disable : 1011)
187 if constexpr (std::is_same<X, T>::value)
192 std::vector<X>(_array.begin(), _array.end()), this->_offsets);
200 s <<
"<AdjacencyList> with " + std::to_string(this->
num_nodes()) +
" nodes"
202 for (std::size_t e = 0; e < _offsets.size() - 1; ++e)
204 s <<
" " << e <<
": [";
205 for (
auto link : this->
links(e))
207 s <<
"]" << std::endl;
214 std::vector<T> _array;
217 std::vector<std::int32_t> _offsets;
226 template <
typename T,
typename U>
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;
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