1 // Copyright (C) 2007 Trustees of Indiana University
3 // Authors: Douglas Gregor
6 // Use, modification and distribution is subject to the Boost Software
7 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
8 // http://www.boost.org/LICENSE_1_0.txt)
10 /** @file graph_communicator.hpp
12 * This header defines facilities to support MPI communicators with
13 * graph topologies, using the graph interface defined by the Boost
14 * Graph Library. One can construct a communicator whose topology is
15 * described by any graph meeting the requirements of the Boost Graph
16 * Library's graph concepts. Likewise, any communicator that has a
17 * graph topology can be viewed as a graph by the Boost Graph
18 * Library, permitting one to use the BGL's graph algorithms on the
21 #ifndef BOOST_MPI_GRAPH_COMMUNICATOR_HPP
22 #define BOOST_MPI_GRAPH_COMMUNICATOR_HPP
24 #include <boost/mpi/communicator.hpp>
28 // Headers required to implement graph topologies
29 #include <boost/graph/graph_traits.hpp>
30 #include <boost/graph/properties.hpp>
31 #include <boost/property_map/property_map.hpp>
32 #include <boost/iterator/counting_iterator.hpp>
33 #include <boost/graph/iteration_macros.hpp>
34 #include <boost/shared_array.hpp>
35 #include <boost/assert.hpp>
37 namespace boost { namespace mpi {
40 * @brief An MPI communicator with a graph topology.
42 * A @c graph_communicator is a communicator whose topology is
43 * expressed as a graph. Graph communicators have the same
44 * functionality as (intra)communicators, but also allow one to query
45 * the relationships among processes. Those relationships are
46 * expressed via a graph, using the interface defined by the Boost
47 * Graph Library. The @c graph_communicator class meets the
48 * requirements of the BGL Graph, Incidence Graph, Adjacency Graph,
49 * Vertex List Graph, and Edge List Graph concepts.
51 class BOOST_MPI_DECL graph_communicator : public communicator
53 friend class communicator;
58 * Construct a graph communicator given a shared pointer to the
59 * underlying MPI_Comm. This operation is used for "casting" from a
60 * communicator to a graph communicator.
62 explicit graph_communicator(const shared_ptr<MPI_Comm>& comm_ptr)
64 #ifndef BOOST_DISABLE_ASSERTS
66 BOOST_MPI_CHECK_RESULT(MPI_Topo_test, ((MPI_Comm)*this, &status));
67 BOOST_ASSERT(status == MPI_GRAPH);
69 this->comm_ptr = comm_ptr;
74 * Build a new Boost.MPI graph communicator based on the MPI
75 * communicator @p comm with graph topology.
77 * @p comm may be any valid MPI communicator. If @p comm is
78 * MPI_COMM_NULL, an empty communicator (that cannot be used for
79 * communication) is created and the @p kind parameter is
80 * ignored. Otherwise, the @p kind parameter determines how the
81 * Boost.MPI communicator will be related to @p comm:
83 * - If @p kind is @c comm_duplicate, duplicate @c comm to create
84 * a new communicator. This new communicator will be freed when
85 * the Boost.MPI communicator (and all copies of it) is
86 * destroyed. This option is only permitted if the underlying MPI
87 * implementation supports MPI 2.0; duplication of
88 * intercommunicators is not available in MPI 1.x.
90 * - If @p kind is @c comm_take_ownership, take ownership of @c
91 * comm. It will be freed automatically when all of the Boost.MPI
92 * communicators go out of scope.
94 * - If @p kind is @c comm_attach, this Boost.MPI communicator
95 * will reference the existing MPI communicator @p comm but will
96 * not free @p comm when the Boost.MPI communicator goes out of
97 * scope. This option should only be used when the communicator is
98 * managed by the user.
100 graph_communicator(const MPI_Comm& comm, comm_create_kind kind)
101 : communicator(comm, kind)
103 #ifndef BOOST_DISABLE_ASSERTS
105 BOOST_MPI_CHECK_RESULT(MPI_Topo_test, ((MPI_Comm)*this, &status));
106 BOOST_ASSERT(status == MPI_GRAPH);
111 * Create a new communicator whose topology is described by the
112 * given graph. The indices of the vertices in the graph will be
113 * assumed to be the ranks of the processes within the
114 * communicator. There may be fewer vertices in the graph than
115 * there are processes in the communicator; in this case, the
116 * resulting communicator will be a NULL communicator.
118 * @param comm The communicator that the new, graph communicator
121 * @param graph Any type that meets the requirements of the
122 * Incidence Graph and Vertex List Graph concepts from the Boost Graph
123 * Library. This structure of this graph will become the topology
124 * of the communicator that is returned.
126 * @param reorder Whether MPI is permitted to re-order the process
127 * ranks within the returned communicator, to better optimize
128 * communication. If false, the ranks of each process in the
129 * returned process will match precisely the rank of that process
130 * within the original communicator.
132 template<typename Graph>
134 graph_communicator(const communicator& comm, const Graph& graph,
135 bool reorder = false);
138 * Create a new communicator whose topology is described by the
139 * given graph. The rank map (@p rank) gives the mapping from
140 * vertices in the graph to ranks within the communicator. There
141 * may be fewer vertices in the graph than there are processes in
142 * the communicator; in this case, the resulting communicator will
143 * be a NULL communicator.
145 * @param comm The communicator that the new, graph communicator
146 * will be based on. The ranks in @c rank refer to the processes in
149 * @param graph Any type that meets the requirements of the
150 * Incidence Graph and Vertex List Graph concepts from the Boost Graph
151 * Library. This structure of this graph will become the topology
152 * of the communicator that is returned.
154 * @param rank This map translates vertices in the @c graph into
155 * ranks within the current communicator. It must be a Readable
156 * Property Map (see the Boost Property Map library) whose key type
157 * is the vertex type of the @p graph and whose value type is @c
160 * @param reorder Whether MPI is permitted to re-order the process
161 * ranks within the returned communicator, to better optimize
162 * communication. If false, the ranks of each process in the
163 * returned process will match precisely the rank of that process
164 * within the original communicator.
166 template<typename Graph, typename RankMap>
168 graph_communicator(const communicator& comm, const Graph& graph,
169 RankMap rank, bool reorder = false);
175 * Used by the constructors to create the new communicator with a
178 template<typename Graph, typename RankMap>
180 setup_graph(const communicator& comm, const Graph& graph, RankMap rank,
184 /****************************************************************************
185 * Implementation Details *
186 ****************************************************************************/
188 template<typename Graph>
189 graph_communicator::graph_communicator(const communicator& comm,
193 this->setup_graph(comm, graph, get(vertex_index, graph), reorder);
196 template<typename Graph, typename RankMap>
197 graph_communicator::graph_communicator(const communicator& comm,
199 RankMap rank, bool reorder)
201 this->setup_graph(comm, graph, rank, reorder);
205 template<typename Graph, typename RankMap>
207 graph_communicator::setup_graph(const communicator& comm, const Graph& graph,
208 RankMap rank, bool reorder)
210 typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
212 // Build a mapping from ranks to vertices
213 std::vector<vertex_descriptor> vertex_with_rank(num_vertices(graph));
214 if (vertex_with_rank.empty())
217 BGL_FORALL_VERTICES_T(v, graph, Graph)
218 vertex_with_rank[get(rank, v)] = v;
220 // Build the representation of the graph required by
222 std::vector<int> indices(num_vertices(graph));
223 std::vector<int> edges;
224 int nvertices = indices.size();
225 for (int vertex_index = 0; vertex_index < nvertices; ++vertex_index) {
226 vertex_descriptor v = vertex_with_rank[vertex_index];
228 BGL_FORALL_OUTEDGES_T(v, e, graph, Graph)
229 edges.push_back(get(rank, target(e, graph)));
231 indices[vertex_index] = edges.size();
234 // Create the new communicator
236 BOOST_MPI_CHECK_RESULT(MPI_Graph_create,
240 edges.empty()? (int*)0 : &edges[0],
243 this->comm_ptr.reset(new MPI_Comm(newcomm), comm_free());
246 /****************************************************************************
247 * Communicator with Graph Topology as BGL Graph *
248 ****************************************************************************/
253 * The iterator used to access the outgoing edges within a
254 * communicator's graph topology.
256 class comm_out_edge_iterator
257 : public iterator_facade<comm_out_edge_iterator,
259 random_access_traversal_tag,
260 const std::pair<int, int>&,
264 comm_out_edge_iterator() { }
266 comm_out_edge_iterator(int source, shared_array<int> neighbors, int index)
267 : edge(source, -1), neighbors(neighbors), index(index) { }
270 friend class boost::iterator_core_access;
272 const std::pair<int, int>& dereference() const
274 edge.second = neighbors[index];
278 bool equal(const comm_out_edge_iterator& other) const
280 return (edge.first == other.edge.first
281 && index == other.index);
284 void increment() { ++index; }
286 void decrement() { --index; }
288 void advance(int n) { index += n; }
290 int distance_to(const comm_out_edge_iterator& other) const
292 return other.index - index;
295 mutable std::pair<int, int> edge;
296 shared_array<int> neighbors;
303 * The iterator used to access the adjacent vertices within a
304 * communicator's graph topology.
306 class comm_adj_iterator
307 : public iterator_facade<comm_adj_iterator,
309 random_access_traversal_tag,
314 comm_adj_iterator() { }
316 comm_adj_iterator(shared_array<int> neighbors, int index)
317 : neighbors(neighbors), index(index) { }
320 friend class boost::iterator_core_access;
322 int dereference() const { return neighbors[index]; }
324 bool equal(const comm_adj_iterator& other) const
326 return (neighbors == other.neighbors
327 && index == other.index);
330 void increment() { ++index; }
332 void decrement() { --index; }
334 void advance(int n) { index += n; }
336 int distance_to(const comm_adj_iterator& other) const
338 return other.index - index;
341 shared_array<int> neighbors;
348 * The iterator used to access the edges in a communicator's graph
351 class comm_edge_iterator
352 : public iterator_facade<comm_edge_iterator,
354 forward_traversal_tag,
355 const std::pair<int, int>&,
359 comm_edge_iterator() { }
361 /// Constructor for a past-the-end iterator
362 comm_edge_iterator(int nedges) : edge_index(nedges) { }
364 comm_edge_iterator(shared_array<int> indices, shared_array<int> edges)
365 : indices(indices), edges(edges), edge_index(0), edge(0, 0)
369 friend class boost::iterator_core_access;
371 const std::pair<int, int>& dereference() const
373 while (edge_index == indices[edge.first])
375 edge.second = edges[edge_index];
379 bool equal(const comm_edge_iterator& other) const
381 return edge_index == other.edge_index;
389 shared_array<int> indices;
390 shared_array<int> edges;
392 mutable std::pair<int, int> edge;
395 } // end namespace detail
397 // Incidence Graph requirements
400 * @brief Returns the source vertex from an edge in the graph topology
403 inline int source(const std::pair<int, int>& edge, const graph_communicator&)
409 * @brief Returns the target vertex from an edge in the graph topology
412 inline int target(const std::pair<int, int>& edge, const graph_communicator&)
418 * @brief Returns an iterator range containing all of the edges
419 * outgoing from the given vertex in a graph topology of a
422 std::pair<detail::comm_out_edge_iterator, detail::comm_out_edge_iterator>
423 out_edges(int vertex, const graph_communicator& comm);
427 * @brief Returns the out-degree of a vertex in the graph topology of
430 int out_degree(int vertex, const graph_communicator& comm);
432 // Adjacency Graph requirements
435 * @brief Returns an iterator range containing all of the neighbors of
436 * the given vertex in the communicator's graph topology.
438 std::pair<detail::comm_adj_iterator, detail::comm_adj_iterator>
439 adjacent_vertices(int vertex, const graph_communicator& comm);
441 // Vertex List Graph requirements
444 * @brief Returns an iterator range that contains all of the vertices
445 * with the communicator's graph topology, i.e., all of the process
446 * ranks in the communicator.
448 inline std::pair<counting_iterator<int>, counting_iterator<int> >
449 vertices(const graph_communicator& comm)
451 return std::make_pair(counting_iterator<int>(0),
452 counting_iterator<int>(comm.size()));
456 * @brief Returns the number of vertices within the graph topology of
457 * the communicator, i.e., the number of processes in the
460 inline int num_vertices(const graph_communicator& comm) { return comm.size(); }
462 // Edge List Graph requirements
465 * @brief Returns an iterator range that contains all of the edges
466 * with the communicator's graph topology.
468 std::pair<detail::comm_edge_iterator, detail::comm_edge_iterator>
469 edges(const graph_communicator& comm);
472 * @brief Returns the number of edges in the communicator's graph
475 int num_edges(const graph_communicator& comm);
477 // Property Graph requirements
480 * @brief Returns a property map that maps from vertices in a
481 * communicator's graph topology to their index values.
483 * Since the vertices are ranks in the communicator, the returned
484 * property map is the identity property map.
486 inline identity_property_map get(vertex_index_t, const graph_communicator&)
488 return identity_property_map();
492 * @brief Returns the index of a vertex in the communicator's graph
495 * Since the vertices are ranks in the communicator, this is the
498 inline int get(vertex_index_t, const graph_communicator&, int vertex)
503 } } // end namespace boost::mpi
508 * @brief Traits structure that allows a communicator with graph
509 * topology to be view as a graph by the Boost Graph Library.
511 * The specialization of @c graph_traits for an MPI communicator
512 * allows a communicator with graph topology to be viewed as a
513 * graph. An MPI communicator with graph topology meets the
514 * requirements of the Graph, Incidence Graph, Adjacency Graph, Vertex
515 * List Graph, and Edge List Graph concepts from the Boost Graph
519 struct graph_traits<mpi::graph_communicator> {
520 // Graph concept requirements
521 typedef int vertex_descriptor;
522 typedef std::pair<int, int> edge_descriptor;
523 typedef directed_tag directed_category;
524 typedef disallow_parallel_edge_tag edge_parallel_category;
529 struct traversal_category
530 : incidence_graph_tag,
532 vertex_list_graph_tag,
538 * @brief Returns a vertex descriptor that can never refer to any
541 static vertex_descriptor null_vertex() { return -1; }
543 // Incidence Graph requirements
544 typedef mpi::detail::comm_out_edge_iterator out_edge_iterator;
545 typedef int degree_size_type;
547 // Adjacency Graph requirements
548 typedef mpi::detail::comm_adj_iterator adjacency_iterator;
550 // Vertex List Graph requirements
551 typedef counting_iterator<int> vertex_iterator;
552 typedef int vertices_size_type;
554 // Edge List Graph requirements
555 typedef mpi::detail::comm_edge_iterator edge_iterator;
556 typedef int edges_size_type;
559 // Property Graph requirements
565 struct property_map<mpi::graph_communicator, vertex_index_t>
567 typedef identity_property_map type;
568 typedef identity_property_map const_type;
571 } // end namespace boost
575 #endif // BOOST_MPI_GRAPH_COMMUNICATOR_HPP