DOLFIN
DOLFIN C++ interface
Loading...
Searching...
No Matches
CSRGraph.h
1// Copyright (C) 2014 Chris Richardson
2//
3// This file is part of DOLFIN.
4//
5// DOLFIN is free software: you can redistribute it and/or modify
6// it under the terms of the GNU Lesser General Public License as published by
7// the Free Software Foundation, either version 3 of the License, or
8// (at your option) any later version.
9//
10// DOLFIN is distributed in the hope that it will be useful,
11// but WITHOUT ANY WARRANTY; without even the implied warranty of
12// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13// GNU Lesser General Public License for more details.
14//
15// You should have received a copy of the GNU Lesser General Public License
16// along with DOLFIN. If not, see <http://www.gnu.org/licenses/>.
17//
18// First added:
19// Last changed:
20
21#ifndef __CSRGRAPH_H
22#define __CSRGRAPH_H
23
24#include <vector>
25#include <dolfin/common/MPI.h>
26
27namespace dolfin
28{
30
43
44 template<typename T> class CSRGraph
45 {
46
47 public:
48
51 class node
52 {
53 public:
54
56 node(const typename std::vector<T>::const_iterator& begin_it,
57 const typename std::vector<T>::const_iterator& end_it)
58 : begin_edge(begin_it), end_edge(end_it) {}
59
61 typename std::vector<T>::const_iterator begin() const
62 { return begin_edge; }
63
65 typename std::vector<T>::const_iterator end() const
66 { return end_edge; }
67
69 std::size_t size() const
70 { return (end_edge - begin_edge); }
71
73 const T& operator[](std::size_t i) const
74 { return *(begin_edge + i); }
75
76 private:
77
78 typename std::vector<T>::const_iterator begin_edge;
79 typename std::vector<T>::const_iterator end_edge;
80 };
81
83 CSRGraph() = delete;
84
88 template<typename X>
89 CSRGraph(MPI_Comm mpi_comm, const std::vector<X>& graph)
90 : _node_offsets(1, 0), _mpi_comm(mpi_comm)
91 {
92 // Count number of outgoing edges (to pre-allocate memory)
93 std::size_t num_edges = 0;
94 for (auto const &edges : graph)
95 num_edges += edges.size();
96
97 // Reserve memory
98 _node_offsets.reserve(graph.size());
99 _edges.reserve(num_edges);
100
101 // Node-by-node, add outgoing edges
102 for (auto const &node_edges : graph)
103 {
104 _edges.insert(_edges.end(), node_edges.begin(), node_edges.end());
105 _node_offsets.push_back(_node_offsets.back() + node_edges.size());
106 }
107
108 // Compute node offsets
109 calculate_node_distribution();
110 }
111
113 CSRGraph(MPI_Comm mpi_comm, const T* xadj, const T* adjncy,
114 std::size_t n) : _mpi_comm(mpi_comm)
115 {
116 _node_offsets.assign(xadj, xadj + n + 1);
117 _edges.assign(adjncy, adjncy + xadj[n]);
118
119 // Compute node offsets
120 calculate_node_distribution();
121 }
122
125
128 const std::vector<T>& edges() const
129 { return _edges; }
130
133 std::vector<T>& edges()
134 { return _edges; }
135
139 const node operator[](std::size_t i) const
140 {
141 return node(_edges.begin() + _node_offsets[i],
142 _edges.begin() + _node_offsets[i + 1]);
143 }
144
145
148 const std::vector<T>& nodes() const
149 { return _node_offsets; }
150
153 std::vector<T>& nodes()
154 { return _node_offsets; }
155
157 std::size_t num_edges() const
158 { return _edges.size(); }
159
161 std::size_t num_edges(std::size_t i) const
162 {
163 dolfin_assert(i < size());
164 return (_node_offsets[i + 1] - _node_offsets[i]);
165 }
166
168 std::size_t size() const
169 { return _node_offsets.size() - 1; }
170
172 T size_global() const
173 { return _node_distribution.back(); }
174
176 const std::vector<T>& node_distribution() const
177 { return _node_distribution; }
178
180 std::vector<T>& node_distribution()
181 { return _node_distribution; }
182
183 private:
184
185 // Compute offset of number of nodes on each process
186 void calculate_node_distribution()
187 {
188 // Communicate number of nodes between all processors
189 const T num_nodes = size();
190 MPI::all_gather(_mpi_comm.comm(), num_nodes, _node_distribution);
191
192 _node_distribution.insert(_node_distribution.begin(), 0);
193 for (std::size_t i = 1; i != _node_distribution.size(); ++i)
194 _node_distribution[i] += _node_distribution[i - 1];
195 }
196
197 // Edges in compressed form. Edges for node i are stored in
198 // _edges[_node_offsets[i]:_node_offsets[i + 1]]
199 std::vector<T> _edges;
200
201 // Offsets of each node into edges (see above) corresponding to
202 // the nodes on this process (see below)
203 std::vector<T> _node_offsets;
204
205 // Distribution of nodes across processes in parallel i.e. the
206 // range of nodes stored on process j is
207 // _node_distribution[j]:_node_distribution[j+1]
208 std::vector<T> _node_distribution;
209
210 // MPI communicator attached to graph
211 dolfin::MPI::Comm _mpi_comm;
212
213 };
214
215}
216#endif
Definition CSRGraph.h:52
node(const typename std::vector< T >::const_iterator &begin_it, const typename std::vector< T >::const_iterator &end_it)
Node object, listing a set of outgoing edges.
Definition CSRGraph.h:56
std::vector< T >::const_iterator begin() const
Iterator pointing to beginning of edges.
Definition CSRGraph.h:61
std::vector< T >::const_iterator end() const
Iterator pointing to beyond end of edges.
Definition CSRGraph.h:65
std::size_t size() const
Number of outgoing edges for this node.
Definition CSRGraph.h:69
const T & operator[](std::size_t i) const
Access outgoing edge i of this node.
Definition CSRGraph.h:73
Compressed Sparse Row graph.
Definition CSRGraph.h:45
std::size_t num_edges(std::size_t i) const
Number of edges from node i.
Definition CSRGraph.h:161
std::vector< T > & edges()
Definition CSRGraph.h:133
CSRGraph()=delete
Empty CSR Graph.
const std::vector< T > & nodes() const
Definition CSRGraph.h:148
std::size_t num_edges() const
Number of local edges in graph.
Definition CSRGraph.h:157
CSRGraph(MPI_Comm mpi_comm, const std::vector< X > &graph)
Definition CSRGraph.h:89
const node operator[](std::size_t i) const
Definition CSRGraph.h:139
~CSRGraph()
Destructor.
Definition CSRGraph.h:124
std::vector< T > & nodes()
Definition CSRGraph.h:153
CSRGraph(MPI_Comm mpi_comm, const T *xadj, const T *adjncy, std::size_t n)
Create a CSR Graph from ParMETIS style adjacency lists.
Definition CSRGraph.h:113
const std::vector< T > & node_distribution() const
Return number of nodes (offset) on each process.
Definition CSRGraph.h:176
const std::vector< T > & edges() const
Definition CSRGraph.h:128
std::size_t size() const
Number of local nodes in graph.
Definition CSRGraph.h:168
T size_global() const
Total (global) number of nodes in parallel graph.
Definition CSRGraph.h:172
std::vector< T > & node_distribution()
Return number of nodes (offset) on each process (non-const)
Definition CSRGraph.h:180
Definition MPI.h:77
MPI_Comm comm() const
Return the underlying MPI_Comm object.
Definition MPI.cpp:117
static void all_gather(MPI_Comm comm, const std::vector< T > &in_values, std::vector< T > &out_values)
Definition MPI.h:708
Definition adapt.h:30