boost/mpi/graph_communicator.hpp

// Copyright (C) 2007 Trustees of Indiana University

// Authors: Douglas Gregor
//          Andrew Lumsdaine

// Use, modification and distribution is subject to the Boost Software
// License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)

/** @file graph_communicator.hpp
 *
 *  This header defines facilities to support MPI communicators with
 *  graph topologies, using the graph interface defined by the Boost
 *  Graph Library. One can construct a communicator whose topology is
 *  described by any graph meeting the requirements of the Boost Graph
 *  Library's graph concepts. Likewise, any communicator that has a
 *  graph topology can be viewed as a graph by the Boost Graph
 *  Library, permitting one to use the BGL's graph algorithms on the
 *  process topology.
 */
#ifndef BOOST_MPI_GRAPH_COMMUNICATOR_HPP
#define BOOST_MPI_GRAPH_COMMUNICATOR_HPP

#include <boost/mpi/communicator.hpp>
#include <vector>
#include <utility>

// Headers required to implement graph topologies
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/properties.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/iterator/counting_iterator.hpp>
#include <boost/graph/iteration_macros.hpp>
#include <boost/shared_array.hpp>
#include <boost/assert.hpp>

namespace boost { namespace mpi {

/**
 * @brief An MPI communicator with a graph topology.
 *
 * A @c graph_communicator is a communicator whose topology is
 * expressed as a graph. Graph communicators have the same
 * functionality as (intra)communicators, but also allow one to query
 * the relationships among processes. Those relationships are
 * expressed via a graph, using the interface defined by the Boost
 * Graph Library. The @c graph_communicator class meets the
 * requirements of the BGL Graph, Incidence Graph, Adjacency Graph,
 * Vertex List Graph, and Edge List Graph concepts.
 */
class BOOST_MPI_DECL graph_communicator : public communicator
{
  friend class communicator;

  /**
   * INTERNAL ONLY
   *
   * Construct a graph communicator given a shared pointer to the
   * underlying MPI_Comm. This operation is used for "casting" from a
   * communicator to a graph communicator.
   */
  explicit graph_communicator(const shared_ptr<MPI_Comm>& comm_ptr)
  {
#ifndef BOOST_DISABLE_ASSERTS
    int status;
    BOOST_MPI_CHECK_RESULT(MPI_Topo_test, ((MPI_Comm)*this, &status));
    BOOST_ASSERT(status == MPI_GRAPH);
#endif
    this->comm_ptr = comm_ptr;
  }

public:
  /**
   * Build a new Boost.MPI graph communicator based on the MPI
   * communicator @p comm with graph topology.
   *
   * @p comm may be any valid MPI communicator. If @p comm is
   * MPI_COMM_NULL, an empty communicator (that cannot be used for
   * communication) is created and the @p kind parameter is
   * ignored. Otherwise, the @p kind parameter determines how the
   * Boost.MPI communicator will be related to @p comm:
   *
   *   - If @p kind is @c comm_duplicate, duplicate @c comm to create
   *   a new communicator. This new communicator will be freed when
   *   the Boost.MPI communicator (and all copies of it) is
   *   destroyed. This option is only permitted if the underlying MPI
   *   implementation supports MPI 2.0; duplication of
   *   intercommunicators is not available in MPI 1.x.
   *
   *   - If @p kind is @c comm_take_ownership, take ownership of @c
   *   comm. It will be freed automatically when all of the Boost.MPI
   *   communicators go out of scope.
   *
   *   - If @p kind is @c comm_attach, this Boost.MPI communicator
   *   will reference the existing MPI communicator @p comm but will
   *   not free @p comm when the Boost.MPI communicator goes out of
   *   scope. This option should only be used when the communicator is
   *   managed by the user.
   */
  graph_communicator(const MPI_Comm& comm, comm_create_kind kind)
    : communicator(comm, kind)
  {
#ifndef BOOST_DISABLE_ASSERTS
    int status;
    BOOST_MPI_CHECK_RESULT(MPI_Topo_test, ((MPI_Comm)*this, &status));
    BOOST_ASSERT(status == MPI_GRAPH);
#endif
  }

  /**
   *  Create a new communicator whose topology is described by the
   *  given graph. The indices of the vertices in the graph will be
   *  assumed to be the ranks of the processes within the
   *  communicator. There may be fewer vertices in the graph than
   *  there are processes in the communicator; in this case, the
   *  resulting communicator will be a NULL communicator.
   *
   *  @param comm The communicator that the new, graph communicator
   *  will be based on.
   *
   *  @param graph Any type that meets the requirements of the
   *  Incidence Graph and Vertex List Graph concepts from the Boost Graph
   *  Library. This structure of this graph will become the topology
   *  of the communicator that is returned.
   *
   *  @param reorder Whether MPI is permitted to re-order the process
   *  ranks within the returned communicator, to better optimize
   *  communication. If false, the ranks of each process in the
   *  returned process will match precisely the rank of that process
   *  within the original communicator.
   */
  template<typename Graph>
  explicit
  graph_communicator(const communicator& comm, const Graph& graph,
                     bool reorder = false);

  /**
   *  Create a new communicator whose topology is described by the
   *  given graph. The rank map (@p rank) gives the mapping from
   *  vertices in the graph to ranks within the communicator. There
   *  may be fewer vertices in the graph than there are processes in
   *  the communicator; in this case, the resulting communicator will
   *  be a NULL communicator.
   *
   *  @param comm The communicator that the new, graph communicator
   *  will be based on. The ranks in @c rank refer to the processes in
   *  this communicator.
   *
   *  @param graph Any type that meets the requirements of the
   *  Incidence Graph and Vertex List Graph concepts from the Boost Graph
   *  Library. This structure of this graph will become the topology
   *  of the communicator that is returned.
   *
   *  @param rank This map translates vertices in the @c graph into
   *  ranks within the current communicator. It must be a Readable
   *  Property Map (see the Boost Property Map library) whose key type
   *  is the vertex type of the @p graph and whose value type is @c
   *  int.
   *
   *  @param reorder Whether MPI is permitted to re-order the process
   *  ranks within the returned communicator, to better optimize
   *  communication. If false, the ranks of each process in the
   *  returned process will match precisely the rank of that process
   *  within the original communicator.
   */
  template<typename Graph, typename RankMap>
  explicit
  graph_communicator(const communicator& comm, const Graph& graph,
                     RankMap rank, bool reorder = false);

protected:
  /**
   * INTERNAL ONLY
   *
   * Used by the constructors to create the new communicator with a
   * graph topology.
   */
  template<typename Graph, typename RankMap>
  void
  setup_graph(const communicator& comm, const Graph& graph, RankMap rank,
              bool reorder);
};

/****************************************************************************
 *  Implementation Details                                                  *
 ****************************************************************************/

template<typename Graph>
graph_communicator::graph_communicator(const communicator& comm,
                                       const Graph& graph,
                                       bool reorder)
{
  this->setup_graph(comm, graph, get(vertex_index, graph), reorder);
}

template<typename Graph, typename RankMap>
graph_communicator::graph_communicator(const communicator& comm,
                                       const Graph& graph,
                                       RankMap rank, bool reorder)
{
  this->setup_graph(comm, graph, rank, reorder);
}


template<typename Graph, typename RankMap>
void
graph_communicator::setup_graph(const communicator& comm, const Graph& graph,
                                RankMap rank, bool reorder)
{
  typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;

  // Build a mapping from ranks to vertices
  std::vector<vertex_descriptor> vertex_with_rank(num_vertices(graph));
  if (vertex_with_rank.empty())
    return;

  BGL_FORALL_VERTICES_T(v, graph, Graph)
    vertex_with_rank[get(rank, v)] = v;

  // Build the representation of the graph required by
  // MPI_Graph_create.
  std::vector<int> indices(num_vertices(graph));
  std::vector<int> edges;
  int nvertices = indices.size();
  for (int vertex_index = 0; vertex_index < nvertices; ++vertex_index) {
    vertex_descriptor v = vertex_with_rank[vertex_index];

    BGL_FORALL_OUTEDGES_T(v, e, graph, Graph)
      edges.push_back(get(rank, target(e, graph)));

    indices[vertex_index] = edges.size();
  }

  // Create the new communicator
  MPI_Comm newcomm;
  BOOST_MPI_CHECK_RESULT(MPI_Graph_create,
                         ((MPI_Comm)comm,
                          nvertices,
                          &indices[0],
                          edges.empty()? (int*)0 : &edges[0],
                          reorder,
                          &newcomm));
  this->comm_ptr.reset(new MPI_Comm(newcomm), comm_free());
}

/****************************************************************************
 *  Communicator with Graph Topology as BGL Graph                           *
 ****************************************************************************/
namespace detail {
  /**
   *  INTERNAL ONLY
   *
   *  The iterator used to access the outgoing edges within a
   *  communicator's graph topology.
   */
  class comm_out_edge_iterator
    : public iterator_facade<comm_out_edge_iterator,
                             std::pair<int, int>,
                             random_access_traversal_tag,
                             const std::pair<int, int>&,
                             int>
  {
  public:
    comm_out_edge_iterator() { }

    comm_out_edge_iterator(int source, shared_array<int> neighbors, int index)
      : edge(source, -1), neighbors(neighbors), index(index) { }

  protected:
    friend class boost::iterator_core_access;

    const std::pair<int, int>& dereference() const
    {
      edge.second = neighbors[index];
      return edge;
    }

    bool equal(const comm_out_edge_iterator& other) const
    {
      return (edge.first == other.edge.first
              && index == other.index);
    }

    void increment() { ++index; }

    void decrement() { --index; }

    void advance(int n) { index += n; }

    int distance_to(const comm_out_edge_iterator& other) const
    {
      return other.index - index;
    }

    mutable std::pair<int, int> edge;
    shared_array<int> neighbors;
    int index;
  };

  /**
   *  INTERNAL ONLY
   *
   *  The iterator used to access the adjacent vertices within a
   *  communicator's graph topology.
   */
  class comm_adj_iterator
    : public iterator_facade<comm_adj_iterator,
                             int,
                             random_access_traversal_tag,
                             int,
                             int>
  {
  public:
    comm_adj_iterator() { }

    comm_adj_iterator(shared_array<int> neighbors, int index)
      : neighbors(neighbors), index(index) { }

  protected:
    friend class boost::iterator_core_access;

    int dereference() const { return neighbors[index]; }

    bool equal(const comm_adj_iterator& other) const
    {
      return (neighbors == other.neighbors
              && index == other.index);
    }

    void increment() { ++index; }

    void decrement() { --index; }

    void advance(int n) { index += n; }

    int distance_to(const comm_adj_iterator& other) const
    {
      return other.index - index;
    }

    shared_array<int> neighbors;
    int index;
  };

  /**
   *  INTERNAL ONLY
   *
   *  The iterator used to access the edges in a communicator's graph
   *  topology.
   */
  class comm_edge_iterator
    : public iterator_facade<comm_edge_iterator,
                             std::pair<int, int>,
                             forward_traversal_tag,
                             const std::pair<int, int>&,
                             int>
  {
  public:
    comm_edge_iterator() { }

    /// Constructor for a past-the-end iterator
    comm_edge_iterator(int nedges) : edge_index(nedges) { }

    comm_edge_iterator(shared_array<int> indices, shared_array<int> edges)
      : indices(indices), edges(edges), edge_index(0), edge(0, 0)
    { }

  protected:
    friend class boost::iterator_core_access;

    const std::pair<int, int>& dereference() const
    {
      while (edge_index == indices[edge.first])
        ++edge.first;
      edge.second = edges[edge_index];
      return edge;
    }

    bool equal(const comm_edge_iterator& other) const
    {
      return edge_index == other.edge_index;
    }

    void increment()
    {
      ++edge_index;
    }

    shared_array<int> indices;
    shared_array<int> edges;
    int edge_index;
    mutable std::pair<int, int> edge;
  };

} // end namespace detail

// Incidence Graph requirements

/**
 * @brief Returns the source vertex from an edge in the graph topology
 * of a communicator.
 */
inline int source(const std::pair<int, int>& edge, const graph_communicator&)
{
  return edge.first;
}

/**
 * @brief Returns the target vertex from an edge in the graph topology
 * of a communicator.
 */
inline int target(const std::pair<int, int>& edge, const graph_communicator&)
{
  return edge.second;
}

/**
 * @brief Returns an iterator range containing all of the edges
 * outgoing from the given vertex in a graph topology of a
 * communicator.
 */
std::pair<detail::comm_out_edge_iterator, detail::comm_out_edge_iterator>
out_edges(int vertex, const graph_communicator& comm);


/**
 * @brief Returns the out-degree of a vertex in the graph topology of
 * a communicator.
 */
int out_degree(int vertex, const graph_communicator& comm);

// Adjacency Graph requirements

/**
 * @brief Returns an iterator range containing all of the neighbors of
 * the given vertex in the communicator's graph topology.
 */
std::pair<detail::comm_adj_iterator, detail::comm_adj_iterator>
adjacent_vertices(int vertex, const graph_communicator& comm);

// Vertex List Graph requirements

/**
 * @brief Returns an iterator range that contains all of the vertices
 * with the communicator's graph topology, i.e., all of the process
 * ranks in the communicator.
 */
inline std::pair<counting_iterator<int>, counting_iterator<int> >
vertices(const graph_communicator& comm)
{
  return std::make_pair(counting_iterator<int>(0),
                        counting_iterator<int>(comm.size()));
}

/**
 *  @brief Returns the number of vertices within the graph topology of
 *  the communicator, i.e., the number of processes in the
 *  communicator.
 */
inline int num_vertices(const graph_communicator& comm) { return comm.size(); }

// Edge List Graph requirements

/**
 * @brief Returns an iterator range that contains all of the edges
 * with the communicator's graph topology.
 */
std::pair<detail::comm_edge_iterator, detail::comm_edge_iterator>
edges(const graph_communicator& comm);

/**
 * @brief Returns the number of edges in the communicator's graph
 * topology.
 */
int num_edges(const graph_communicator& comm);

// Property Graph requirements

/**
 *  @brief Returns a property map that maps from vertices in a
 *  communicator's graph topology to their index values.
 *
 *  Since the vertices are ranks in the communicator, the returned
 *  property map is the identity property map.
 */
inline identity_property_map get(vertex_index_t, const graph_communicator&)
{
  return identity_property_map();
}

/**
 * @brief Returns the index of a vertex in the communicator's graph
 * topology.
 *
 * Since the vertices are ranks in the communicator, this is the
 *  identity function.
 */
inline int get(vertex_index_t, const graph_communicator&, int vertex)
{
  return vertex;
}

} } // end namespace boost::mpi

namespace boost {

/**
 * @brief Traits structure that allows a communicator with graph
 * topology to be view as a graph by the Boost Graph Library.
 *
 * The specialization of @c graph_traits for an MPI communicator
 * allows a communicator with graph topology to be viewed as a
 * graph. An MPI communicator with graph topology meets the
 * requirements of the Graph, Incidence Graph, Adjacency Graph, Vertex
 * List Graph, and Edge List Graph concepts from the Boost Graph
 * Library.
 */
template<>
struct graph_traits<mpi::graph_communicator> {
  // Graph concept requirements
  typedef int                        vertex_descriptor;
  typedef std::pair<int, int>        edge_descriptor;
  typedef directed_tag               directed_category;
  typedef disallow_parallel_edge_tag edge_parallel_category;

  /**
   * INTERNAL ONLY
   */
  struct traversal_category
    : incidence_graph_tag,
      adjacency_graph_tag,
      vertex_list_graph_tag,
      edge_list_graph_tag
  {
  };

  /**
   * @brief Returns a vertex descriptor that can never refer to any
   * valid vertex.
   */
  static vertex_descriptor null_vertex() { return -1; }

  // Incidence Graph requirements
  typedef mpi::detail::comm_out_edge_iterator out_edge_iterator;
  typedef int degree_size_type;

  // Adjacency Graph requirements
  typedef mpi::detail::comm_adj_iterator adjacency_iterator;

  // Vertex List Graph requirements
  typedef counting_iterator<int> vertex_iterator;
  typedef int                    vertices_size_type;

  // Edge List Graph requirements
  typedef mpi::detail::comm_edge_iterator edge_iterator;
  typedef int                             edges_size_type;
};

// Property Graph requirements

/**
 * INTERNAL ONLY
 */
template<>
struct property_map<mpi::graph_communicator, vertex_index_t>
{
  typedef identity_property_map type;
  typedef identity_property_map const_type;
};

} // end namespace boost


#endif // BOOST_MPI_GRAPH_COMMUNICATOR_HPP