Loading...
Searching...
No Matches
CSRGraph.h
// Copyright (C) 2014 Chris Richardson
//
// This file is part of DOLFIN.
//
// DOLFIN is free software: you can redistribute it and/or modify
// it under the terms of the GNU Lesser General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// DOLFIN is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public License
// along with DOLFIN. If not, see <http://www.gnu.org/licenses/>.
//
// First added:
// Last changed:
#ifndef __CSRGRAPH_H
#define __CSRGRAPH_H
#include <vector>
#include <dolfin/common/MPI.h>
namespace dolfin
{
template<typename T> class CSRGraph
{
public:
class node
{
public:
node(const typename std::vector<T>::const_iterator& begin_it,
const typename std::vector<T>::const_iterator& end_it)
: begin_edge(begin_it), end_edge(end_it) {}
typename std::vector<T>::const_iterator begin() const
{ return begin_edge; }
typename std::vector<T>::const_iterator end() const
{ return end_edge; }
std::size_t size() const
{ return (end_edge - begin_edge); }
const T& operator[](std::size_t i) const
{ return *(begin_edge + i); }
private:
typename std::vector<T>::const_iterator begin_edge;
typename std::vector<T>::const_iterator end_edge;
};
CSRGraph() = delete;
template<typename X>
CSRGraph(MPI_Comm mpi_comm, const std::vector<X>& graph)
: _node_offsets(1, 0), _mpi_comm(mpi_comm)
{
// Count number of outgoing edges (to pre-allocate memory)
std::size_t num_edges = 0;
for (auto const &edges : graph)
num_edges += edges.size();
// Reserve memory
_node_offsets.reserve(graph.size());
_edges.reserve(num_edges);
// Node-by-node, add outgoing edges
for (auto const &node_edges : graph)
{
_edges.insert(_edges.end(), node_edges.begin(), node_edges.end());
_node_offsets.push_back(_node_offsets.back() + node_edges.size());
}
// Compute node offsets
calculate_node_distribution();
}
CSRGraph(MPI_Comm mpi_comm, const T* xadj, const T* adjncy,
std::size_t n) : _mpi_comm(mpi_comm)
{
_node_offsets.assign(xadj, xadj + n + 1);
_edges.assign(adjncy, adjncy + xadj[n]);
// Compute node offsets
calculate_node_distribution();
}
~CSRGraph() {}
const std::vector<T>& edges() const
{ return _edges; }
std::vector<T>& edges()
{ return _edges; }
const node operator[](std::size_t i) const
{
return node(_edges.begin() + _node_offsets[i],
_edges.begin() + _node_offsets[i + 1]);
}
const std::vector<T>& nodes() const
{ return _node_offsets; }
std::vector<T>& nodes()
{ return _node_offsets; }
std::size_t num_edges() const
{ return _edges.size(); }
std::size_t num_edges(std::size_t i) const
{
dolfin_assert(i < size());
return (_node_offsets[i + 1] - _node_offsets[i]);
}
std::size_t size() const
{ return _node_offsets.size() - 1; }
T size_global() const
{ return _node_distribution.back(); }
const std::vector<T>& node_distribution() const
{ return _node_distribution; }
std::vector<T>& node_distribution()
{ return _node_distribution; }
private:
// Compute offset of number of nodes on each process
void calculate_node_distribution()
{
// Communicate number of nodes between all processors
const T num_nodes = size();
MPI::all_gather(_mpi_comm.comm(), num_nodes, _node_distribution);
_node_distribution.insert(_node_distribution.begin(), 0);
for (std::size_t i = 1; i != _node_distribution.size(); ++i)
_node_distribution[i] += _node_distribution[i - 1];
}
// Edges in compressed form. Edges for node i are stored in
// _edges[_node_offsets[i]:_node_offsets[i + 1]]
std::vector<T> _edges;
// Offsets of each node into edges (see above) corresponding to
// the nodes on this process (see below)
std::vector<T> _node_offsets;
// Distribution of nodes across processes in parallel i.e. the
// range of nodes stored on process j is
// _node_distribution[j]:_node_distribution[j+1]
std::vector<T> _node_distribution;
// MPI communicator attached to graph
dolfin::MPI::Comm _mpi_comm;
};
}
#endif
dolfin::CSRGraph::node
Definition CSRGraph.h:52
dolfin::CSRGraph::node::node
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
dolfin::CSRGraph::node::begin
std::vector< T >::const_iterator begin() const
Iterator pointing to beginning of edges.
Definition CSRGraph.h:61
dolfin::CSRGraph::node::end
std::vector< T >::const_iterator end() const
Iterator pointing to beyond end of edges.
Definition CSRGraph.h:65
dolfin::CSRGraph::node::size
std::size_t size() const
Number of outgoing edges for this node.
Definition CSRGraph.h:69
dolfin::CSRGraph::node::operator[]
const T & operator[](std::size_t i) const
Access outgoing edge i of this node.
Definition CSRGraph.h:73
dolfin::CSRGraph::num_edges
std::size_t num_edges(std::size_t i) const
Number of edges from node i.
Definition CSRGraph.h:161
dolfin::CSRGraph::edges
std::vector< T > & edges()
Definition CSRGraph.h:133
dolfin::CSRGraph::CSRGraph
CSRGraph()=delete
Empty CSR Graph.
dolfin::CSRGraph::nodes
const std::vector< T > & nodes() const
Definition CSRGraph.h:148
dolfin::CSRGraph::num_edges
std::size_t num_edges() const
Number of local edges in graph.
Definition CSRGraph.h:157
dolfin::CSRGraph::CSRGraph
CSRGraph(MPI_Comm mpi_comm, const std::vector< X > &graph)
Definition CSRGraph.h:89
dolfin::CSRGraph::operator[]
const node operator[](std::size_t i) const
Definition CSRGraph.h:139
dolfin::CSRGraph::~CSRGraph
~CSRGraph()
Destructor.
Definition CSRGraph.h:124
dolfin::CSRGraph::nodes
std::vector< T > & nodes()
Definition CSRGraph.h:153
dolfin::CSRGraph::CSRGraph
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
dolfin::CSRGraph::node_distribution
const std::vector< T > & node_distribution() const
Return number of nodes (offset) on each process.
Definition CSRGraph.h:176
dolfin::CSRGraph::edges
const std::vector< T > & edges() const
Definition CSRGraph.h:128
dolfin::CSRGraph::size
std::size_t size() const
Number of local nodes in graph.
Definition CSRGraph.h:168
dolfin::CSRGraph::size_global
T size_global() const
Total (global) number of nodes in parallel graph.
Definition CSRGraph.h:172
dolfin::CSRGraph::node_distribution
std::vector< T > & node_distribution()
Return number of nodes (offset) on each process (non-const).
Definition CSRGraph.h:180
dolfin::MPI::Comm
Definition MPI.h:77
dolfin::MPI::Comm::comm
MPI_Comm comm() const
Return the underlying MPI_Comm object.
Definition MPI.cpp:117
dolfin::MPI::all_gather
static void all_gather(MPI_Comm comm, const std::vector< T > &in_values, std::vector< T > &out_values)
Definition MPI.h:708
dolfin
Definition adapt.h:30