DOLFIN
DOLFIN C++ interface
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 
27 namespace 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
const std::vector< T > & nodes() const
Definition: CSRGraph.h:148
std::size_t size() const
Number of local nodes in graph.
Definition: CSRGraph.h:168
std::size_t num_edges() const
Number of local edges in graph.
Definition: CSRGraph.h:157
const std::vector< T > & edges() const
Definition: CSRGraph.h:128
std::vector< T > & node_distribution()
Return number of nodes (offset) on each process (non-const)
Definition: CSRGraph.h:180
Definition: adapt.h:29
std::vector< T > & edges()
Definition: CSRGraph.h:133
std::vector< T >::const_iterator begin() const
Iterator pointing to beginning of edges.
Definition: CSRGraph.h:61
CSRGraph()=delete
Empty CSR Graph.
~CSRGraph()
Destructor.
Definition: CSRGraph.h:124
std::size_t size() const
Number of outgoing edges for this node.
Definition: CSRGraph.h:69
std::vector< T > & nodes()
Definition: CSRGraph.h:153
const std::vector< T > & node_distribution() const
Return number of nodes (offset) on each process.
Definition: CSRGraph.h:176
Definition: CSRGraph.h:51
T size_global() const
Total (global) number of nodes in parallel graph.
Definition: CSRGraph.h:172
std::size_t num_edges(std::size_t i) const
Number of edges from node i.
Definition: CSRGraph.h:161
static void all_gather(MPI_Comm comm, const std::vector< T > &in_values, std::vector< T > &out_values)
Definition: MPI.h:708
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
const T & operator[](std::size_t i) const
Access outgoing edge i of this node.
Definition: CSRGraph.h:73
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(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
Compressed Sparse Row graph.
Definition: CSRGraph.h:44
std::vector< T >::const_iterator end() const
Iterator pointing to beyond end of edges.
Definition: CSRGraph.h:65
Definition: MPI.h:76