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