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/iterator/counting_iterator.hpp>
32 #include <boost/graph/iteration_macros.hpp>
33 #include <boost/shared_array.hpp>
34 #include <boost/assert.hpp>
36 namespace boost { namespace mpi {
39 * @brief An MPI communicator with a graph topology.
41 * A @c graph_communicator is a communicator whose topology is
42 * expressed as a graph. Graph communicators have the same
43 * functionality as (intra)communicators, but also allow one to query
44 * the relationships among processes. Those relationships are
45 * expressed via a graph, using the interface defined by the Boost
46 * Graph Library. The @c graph_communicator class meets the
47 * requirements of the BGL Graph, Incidence Graph, Adjacency Graph,
48 * Vertex List Graph, and Edge List Graph concepts.
50 class BOOST_MPI_DECL graph_communicator : public communicator
52 friend class communicator;
57 * Construct a graph communicator given a shared pointer to the
58 * underlying MPI_Comm. This operation is used for "casting" from a
59 * communicator to a graph communicator.
61 explicit graph_communicator(const shared_ptr<MPI_Comm>& comm_ptr)
63 #ifndef BOOST_DISABLE_ASSERTS
65 BOOST_MPI_CHECK_RESULT(MPI_Topo_test, ((MPI_Comm)*this, &status));
66 BOOST_ASSERT(status == MPI_GRAPH);
68 this->comm_ptr = comm_ptr;
73 * Build a new Boost.MPI graph communicator based on the MPI
74 * communicator @p comm with graph topology.
76 * @p comm may be any valid MPI communicator. If @p comm is
77 * MPI_COMM_NULL, an empty communicator (that cannot be used for
78 * communication) is created and the @p kind parameter is
79 * ignored. Otherwise, the @p kind parameter determines how the
80 * Boost.MPI communicator will be related to @p comm:
82 * - If @p kind is @c comm_duplicate, duplicate @c comm to create
83 * a new communicator. This new communicator will be freed when
84 * the Boost.MPI communicator (and all copies of it) is
85 * destroyed. This option is only permitted if the underlying MPI
86 * implementation supports MPI 2.0; duplication of
87 * intercommunicators is not available in MPI 1.x.
89 * - If @p kind is @c comm_take_ownership, take ownership of @c
90 * comm. It will be freed automatically when all of the Boost.MPI
91 * communicators go out of scope.
93 * - If @p kind is @c comm_attach, this Boost.MPI communicator
94 * will reference the existing MPI communicator @p comm but will
95 * not free @p comm when the Boost.MPI communicator goes out of
96 * scope. This option should only be used when the communicator is
97 * managed by the user.
99 graph_communicator(const MPI_Comm& comm, comm_create_kind kind)
100 : communicator(comm, kind)
102 #ifndef BOOST_DISABLE_ASSERTS
104 BOOST_MPI_CHECK_RESULT(MPI_Topo_test, ((MPI_Comm)*this, &status));
105 BOOST_ASSERT(status == MPI_GRAPH);
110 * Create a new communicator whose topology is described by the
111 * given graph. The indices of the vertices in the graph will be
112 * assumed to be the ranks of the processes within the
113 * communicator. There may be fewer vertices in the graph than
114 * there are processes in the communicator; in this case, the
115 * resulting communicator will be a NULL communicator.
117 * @param comm The communicator that the new, graph communicator
120 * @param graph Any type that meets the requirements of the
121 * Incidence Graph and Vertex List Graph concepts from the Boost Graph
122 * Library. This structure of this graph will become the topology
123 * of the communicator that is returned.
125 * @param reorder Whether MPI is permitted to re-order the process
126 * ranks within the returned communicator, to better optimize
127 * communication. If false, the ranks of each process in the
128 * returned process will match precisely the rank of that process
129 * within the original communicator.
131 template<typename Graph>
133 graph_communicator(const communicator& comm, const Graph& graph,
134 bool reorder = false);
137 * Create a new communicator whose topology is described by the
138 * given graph. The rank map (@p rank) gives the mapping from
139 * vertices in the graph to ranks within the communicator. There
140 * may be fewer vertices in the graph than there are processes in
141 * the communicator; in this case, the resulting communicator will
142 * be a NULL communicator.
144 * @param comm The communicator that the new, graph communicator
145 * will be based on. The ranks in @c rank refer to the processes in
148 * @param graph Any type that meets the requirements of the
149 * Incidence Graph and Vertex List Graph concepts from the Boost Graph
150 * Library. This structure of this graph will become the topology
151 * of the communicator that is returned.
153 * @param rank This map translates vertices in the @c graph into
154 * ranks within the current communicator. It must be a Readable
155 * Property Map (see the Boost Property Map library) whose key type
156 * is the vertex type of the @p graph and whose value type is @c
159 * @param reorder Whether MPI is permitted to re-order the process
160 * ranks within the returned communicator, to better optimize
161 * communication. If false, the ranks of each process in the
162 * returned process will match precisely the rank of that process
163 * within the original communicator.
165 template<typename Graph, typename RankMap>
167 graph_communicator(const communicator& comm, const Graph& graph,
168 RankMap rank, bool reorder = false);
174 * Used by the constructors to create the new communicator with a
177 template<typename Graph, typename RankMap>
179 setup_graph(const communicator& comm, const Graph& graph, RankMap rank,
183 /****************************************************************************
184 * Implementation Details *
185 ****************************************************************************/
187 template<typename Graph>
188 graph_communicator::graph_communicator(const communicator& comm,
192 this->setup_graph(comm, graph, get(vertex_index, graph), reorder);
195 template<typename Graph, typename RankMap>
196 graph_communicator::graph_communicator(const communicator& comm,
198 RankMap rank, bool reorder)
200 this->setup_graph(comm, graph, rank, reorder);
204 template<typename Graph, typename RankMap>
206 graph_communicator::setup_graph(const communicator& comm, const Graph& graph,
207 RankMap rank, bool reorder)
209 typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
211 // Build a mapping from ranks to vertices
212 std::vector<vertex_descriptor> vertex_with_rank(num_vertices(graph));
213 if (vertex_with_rank.empty())
216 BGL_FORALL_VERTICES_T(v, graph, Graph)
217 vertex_with_rank[get(rank, v)] = v;
219 // Build the representation of the graph required by
221 std::vector<int> indices(num_vertices(graph));
222 std::vector<int> edges;
223 int nvertices = indices.size();
224 for (int vertex_index = 0; vertex_index < nvertices; ++vertex_index) {
225 vertex_descriptor v = vertex_with_rank[vertex_index];
227 BGL_FORALL_OUTEDGES_T(v, e, graph, Graph)
228 edges.push_back(get(rank, target(e, graph)));
230 indices[vertex_index] = edges.size();
233 // Create the new communicator
235 BOOST_MPI_CHECK_RESULT(MPI_Graph_create,
238 detail::c_data(indices),
239 detail::c_data(edges),
242 this->comm_ptr.reset(new MPI_Comm(newcomm), comm_free());
245 /****************************************************************************
246 * Communicator with Graph Topology as BGL Graph *
247 ****************************************************************************/
252 * The iterator used to access the outgoing edges within a
253 * communicator's graph topology.
255 class comm_out_edge_iterator
256 : public iterator_facade<comm_out_edge_iterator,
258 random_access_traversal_tag,
259 const std::pair<int, int>&,
263 comm_out_edge_iterator() { }
265 comm_out_edge_iterator(int source, shared_array<int> neighbors, int index)
266 : edge(source, -1), neighbors(neighbors), index(index) { }
269 friend class boost::iterator_core_access;
271 const std::pair<int, int>& dereference() const
273 edge.second = neighbors[index];
277 bool equal(const comm_out_edge_iterator& other) const
279 return (edge.first == other.edge.first
280 && index == other.index);
283 void increment() { ++index; }
285 void decrement() { --index; }
287 void advance(int n) { index += n; }
289 int distance_to(const comm_out_edge_iterator& other) const
291 return other.index - index;
294 mutable std::pair<int, int> edge;
295 shared_array<int> neighbors;
302 * The iterator used to access the adjacent vertices within a
303 * communicator's graph topology.
305 class comm_adj_iterator
306 : public iterator_facade<comm_adj_iterator,
308 random_access_traversal_tag,
313 comm_adj_iterator() { }
315 comm_adj_iterator(shared_array<int> neighbors, int index)
316 : neighbors(neighbors), index(index) { }
319 friend class boost::iterator_core_access;
321 int dereference() const { return neighbors[index]; }
323 bool equal(const comm_adj_iterator& other) const
325 return (neighbors == other.neighbors
326 && index == other.index);
329 void increment() { ++index; }
331 void decrement() { --index; }
333 void advance(int n) { index += n; }
335 int distance_to(const comm_adj_iterator& other) const
337 return other.index - index;
340 shared_array<int> neighbors;
347 * The iterator used to access the edges in a communicator's graph
350 class comm_edge_iterator
351 : public iterator_facade<comm_edge_iterator,
353 forward_traversal_tag,
354 const std::pair<int, int>&,
358 comm_edge_iterator() { }
360 /// Constructor for a past-the-end iterator
361 comm_edge_iterator(int nedges) : edge_index(nedges) { }
363 comm_edge_iterator(shared_array<int> indices, shared_array<int> edges)
364 : indices(indices), edges(edges), edge_index(0), edge(0, 0)
368 friend class boost::iterator_core_access;
370 const std::pair<int, int>& dereference() const
372 while (edge_index == indices[edge.first])
374 edge.second = edges[edge_index];
378 bool equal(const comm_edge_iterator& other) const
380 return edge_index == other.edge_index;
388 shared_array<int> indices;
389 shared_array<int> edges;
391 mutable std::pair<int, int> edge;
394 } // end namespace detail
396 // Incidence Graph requirements
399 * @brief Returns the source vertex from an edge in the graph topology
402 inline int source(const std::pair<int, int>& edge, const graph_communicator&)
408 * @brief Returns the target vertex from an edge in the graph topology
411 inline int target(const std::pair<int, int>& edge, const graph_communicator&)
417 * @brief Returns an iterator range containing all of the edges
418 * outgoing from the given vertex in a graph topology of a
421 std::pair<detail::comm_out_edge_iterator, detail::comm_out_edge_iterator>
422 out_edges(int vertex, const graph_communicator& comm);
426 * @brief Returns the out-degree of a vertex in the graph topology of
429 int out_degree(int vertex, const graph_communicator& comm);
431 // Adjacency Graph requirements
434 * @brief Returns an iterator range containing all of the neighbors of
435 * the given vertex in the communicator's graph topology.
437 std::pair<detail::comm_adj_iterator, detail::comm_adj_iterator>
438 adjacent_vertices(int vertex, const graph_communicator& comm);
440 // Vertex List Graph requirements
443 * @brief Returns an iterator range that contains all of the vertices
444 * with the communicator's graph topology, i.e., all of the process
445 * ranks in the communicator.
447 inline std::pair<counting_iterator<int>, counting_iterator<int> >
448 vertices(const graph_communicator& comm)
450 return std::make_pair(counting_iterator<int>(0),
451 counting_iterator<int>(comm.size()));
455 * @brief Returns the number of vertices within the graph topology of
456 * the communicator, i.e., the number of processes in the
459 inline int num_vertices(const graph_communicator& comm) { return comm.size(); }
461 // Edge List Graph requirements
464 * @brief Returns an iterator range that contains all of the edges
465 * with the communicator's graph topology.
467 std::pair<detail::comm_edge_iterator, detail::comm_edge_iterator>
468 edges(const graph_communicator& comm);
471 * @brief Returns the number of edges in the communicator's graph
474 int num_edges(const graph_communicator& comm);
476 // Property Graph requirements
479 * @brief Returns a property map that maps from vertices in a
480 * communicator's graph topology to their index values.
482 * Since the vertices are ranks in the communicator, the returned
483 * property map is the identity property map.
485 inline identity_property_map get(vertex_index_t, const graph_communicator&)
487 return identity_property_map();
491 * @brief Returns the index of a vertex in the communicator's graph
494 * Since the vertices are ranks in the communicator, this is the
497 inline int get(vertex_index_t, const graph_communicator&, int vertex)
502 } } // end namespace boost::mpi
507 * @brief Traits structure that allows a communicator with graph
508 * topology to be view as a graph by the Boost Graph Library.
510 * The specialization of @c graph_traits for an MPI communicator
511 * allows a communicator with graph topology to be viewed as a
512 * graph. An MPI communicator with graph topology meets the
513 * requirements of the Graph, Incidence Graph, Adjacency Graph, Vertex
514 * List Graph, and Edge List Graph concepts from the Boost Graph
518 struct graph_traits<mpi::graph_communicator> {
519 // Graph concept requirements
520 typedef int vertex_descriptor;
521 typedef std::pair<int, int> edge_descriptor;
522 typedef directed_tag directed_category;
523 typedef disallow_parallel_edge_tag edge_parallel_category;
528 struct traversal_category
529 : incidence_graph_tag,
531 vertex_list_graph_tag,
537 * @brief Returns a vertex descriptor that can never refer to any
540 static vertex_descriptor null_vertex() { return -1; }
542 // Incidence Graph requirements
543 typedef mpi::detail::comm_out_edge_iterator out_edge_iterator;
544 typedef int degree_size_type;
546 // Adjacency Graph requirements
547 typedef mpi::detail::comm_adj_iterator adjacency_iterator;
549 // Vertex List Graph requirements
550 typedef counting_iterator<int> vertex_iterator;
551 typedef int vertices_size_type;
553 // Edge List Graph requirements
554 typedef mpi::detail::comm_edge_iterator edge_iterator;
555 typedef int edges_size_type;
558 // Property Graph requirements
564 struct property_map<mpi::graph_communicator, vertex_index_t>
566 typedef identity_property_map type;
567 typedef identity_property_map const_type;
570 } // end namespace boost
574 #endif // BOOST_MPI_GRAPH_COMMUNICATOR_HPP