Chris@16
|
1 // Copyright (C) 2007 Trustees of Indiana University
|
Chris@16
|
2
|
Chris@16
|
3 // Authors: Douglas Gregor
|
Chris@16
|
4 // Andrew Lumsdaine
|
Chris@16
|
5
|
Chris@16
|
6 // Use, modification and distribution is subject to the Boost Software
|
Chris@16
|
7 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
|
Chris@16
|
8 // http://www.boost.org/LICENSE_1_0.txt)
|
Chris@16
|
9
|
Chris@16
|
10 /** @file graph_communicator.hpp
|
Chris@16
|
11 *
|
Chris@16
|
12 * This header defines facilities to support MPI communicators with
|
Chris@16
|
13 * graph topologies, using the graph interface defined by the Boost
|
Chris@16
|
14 * Graph Library. One can construct a communicator whose topology is
|
Chris@16
|
15 * described by any graph meeting the requirements of the Boost Graph
|
Chris@16
|
16 * Library's graph concepts. Likewise, any communicator that has a
|
Chris@16
|
17 * graph topology can be viewed as a graph by the Boost Graph
|
Chris@16
|
18 * Library, permitting one to use the BGL's graph algorithms on the
|
Chris@16
|
19 * process topology.
|
Chris@16
|
20 */
|
Chris@16
|
21 #ifndef BOOST_MPI_GRAPH_COMMUNICATOR_HPP
|
Chris@16
|
22 #define BOOST_MPI_GRAPH_COMMUNICATOR_HPP
|
Chris@16
|
23
|
Chris@16
|
24 #include <boost/mpi/communicator.hpp>
|
Chris@16
|
25 #include <vector>
|
Chris@16
|
26 #include <utility>
|
Chris@16
|
27
|
Chris@16
|
28 // Headers required to implement graph topologies
|
Chris@16
|
29 #include <boost/graph/graph_traits.hpp>
|
Chris@16
|
30 #include <boost/graph/properties.hpp>
|
Chris@16
|
31 #include <boost/property_map/property_map.hpp>
|
Chris@16
|
32 #include <boost/iterator/counting_iterator.hpp>
|
Chris@16
|
33 #include <boost/graph/iteration_macros.hpp>
|
Chris@16
|
34 #include <boost/shared_array.hpp>
|
Chris@16
|
35 #include <boost/assert.hpp>
|
Chris@16
|
36
|
Chris@16
|
37 namespace boost { namespace mpi {
|
Chris@16
|
38
|
Chris@16
|
39 /**
|
Chris@16
|
40 * @brief An MPI communicator with a graph topology.
|
Chris@16
|
41 *
|
Chris@16
|
42 * A @c graph_communicator is a communicator whose topology is
|
Chris@16
|
43 * expressed as a graph. Graph communicators have the same
|
Chris@16
|
44 * functionality as (intra)communicators, but also allow one to query
|
Chris@16
|
45 * the relationships among processes. Those relationships are
|
Chris@16
|
46 * expressed via a graph, using the interface defined by the Boost
|
Chris@16
|
47 * Graph Library. The @c graph_communicator class meets the
|
Chris@16
|
48 * requirements of the BGL Graph, Incidence Graph, Adjacency Graph,
|
Chris@16
|
49 * Vertex List Graph, and Edge List Graph concepts.
|
Chris@16
|
50 */
|
Chris@16
|
51 class BOOST_MPI_DECL graph_communicator : public communicator
|
Chris@16
|
52 {
|
Chris@16
|
53 friend class communicator;
|
Chris@16
|
54
|
Chris@16
|
55 /**
|
Chris@16
|
56 * INTERNAL ONLY
|
Chris@16
|
57 *
|
Chris@16
|
58 * Construct a graph communicator given a shared pointer to the
|
Chris@16
|
59 * underlying MPI_Comm. This operation is used for "casting" from a
|
Chris@16
|
60 * communicator to a graph communicator.
|
Chris@16
|
61 */
|
Chris@16
|
62 explicit graph_communicator(const shared_ptr<MPI_Comm>& comm_ptr)
|
Chris@16
|
63 {
|
Chris@16
|
64 #ifndef BOOST_DISABLE_ASSERTS
|
Chris@16
|
65 int status;
|
Chris@16
|
66 BOOST_MPI_CHECK_RESULT(MPI_Topo_test, ((MPI_Comm)*this, &status));
|
Chris@16
|
67 BOOST_ASSERT(status == MPI_GRAPH);
|
Chris@16
|
68 #endif
|
Chris@16
|
69 this->comm_ptr = comm_ptr;
|
Chris@16
|
70 }
|
Chris@16
|
71
|
Chris@16
|
72 public:
|
Chris@16
|
73 /**
|
Chris@16
|
74 * Build a new Boost.MPI graph communicator based on the MPI
|
Chris@16
|
75 * communicator @p comm with graph topology.
|
Chris@16
|
76 *
|
Chris@16
|
77 * @p comm may be any valid MPI communicator. If @p comm is
|
Chris@16
|
78 * MPI_COMM_NULL, an empty communicator (that cannot be used for
|
Chris@16
|
79 * communication) is created and the @p kind parameter is
|
Chris@16
|
80 * ignored. Otherwise, the @p kind parameter determines how the
|
Chris@16
|
81 * Boost.MPI communicator will be related to @p comm:
|
Chris@16
|
82 *
|
Chris@16
|
83 * - If @p kind is @c comm_duplicate, duplicate @c comm to create
|
Chris@16
|
84 * a new communicator. This new communicator will be freed when
|
Chris@16
|
85 * the Boost.MPI communicator (and all copies of it) is
|
Chris@16
|
86 * destroyed. This option is only permitted if the underlying MPI
|
Chris@16
|
87 * implementation supports MPI 2.0; duplication of
|
Chris@16
|
88 * intercommunicators is not available in MPI 1.x.
|
Chris@16
|
89 *
|
Chris@16
|
90 * - If @p kind is @c comm_take_ownership, take ownership of @c
|
Chris@16
|
91 * comm. It will be freed automatically when all of the Boost.MPI
|
Chris@16
|
92 * communicators go out of scope.
|
Chris@16
|
93 *
|
Chris@16
|
94 * - If @p kind is @c comm_attach, this Boost.MPI communicator
|
Chris@16
|
95 * will reference the existing MPI communicator @p comm but will
|
Chris@16
|
96 * not free @p comm when the Boost.MPI communicator goes out of
|
Chris@16
|
97 * scope. This option should only be used when the communicator is
|
Chris@16
|
98 * managed by the user.
|
Chris@16
|
99 */
|
Chris@16
|
100 graph_communicator(const MPI_Comm& comm, comm_create_kind kind)
|
Chris@16
|
101 : communicator(comm, kind)
|
Chris@16
|
102 {
|
Chris@16
|
103 #ifndef BOOST_DISABLE_ASSERTS
|
Chris@16
|
104 int status;
|
Chris@16
|
105 BOOST_MPI_CHECK_RESULT(MPI_Topo_test, ((MPI_Comm)*this, &status));
|
Chris@16
|
106 BOOST_ASSERT(status == MPI_GRAPH);
|
Chris@16
|
107 #endif
|
Chris@16
|
108 }
|
Chris@16
|
109
|
Chris@16
|
110 /**
|
Chris@16
|
111 * Create a new communicator whose topology is described by the
|
Chris@16
|
112 * given graph. The indices of the vertices in the graph will be
|
Chris@16
|
113 * assumed to be the ranks of the processes within the
|
Chris@16
|
114 * communicator. There may be fewer vertices in the graph than
|
Chris@16
|
115 * there are processes in the communicator; in this case, the
|
Chris@16
|
116 * resulting communicator will be a NULL communicator.
|
Chris@16
|
117 *
|
Chris@16
|
118 * @param comm The communicator that the new, graph communicator
|
Chris@16
|
119 * will be based on.
|
Chris@16
|
120 *
|
Chris@16
|
121 * @param graph Any type that meets the requirements of the
|
Chris@16
|
122 * Incidence Graph and Vertex List Graph concepts from the Boost Graph
|
Chris@16
|
123 * Library. This structure of this graph will become the topology
|
Chris@16
|
124 * of the communicator that is returned.
|
Chris@16
|
125 *
|
Chris@16
|
126 * @param reorder Whether MPI is permitted to re-order the process
|
Chris@16
|
127 * ranks within the returned communicator, to better optimize
|
Chris@16
|
128 * communication. If false, the ranks of each process in the
|
Chris@16
|
129 * returned process will match precisely the rank of that process
|
Chris@16
|
130 * within the original communicator.
|
Chris@16
|
131 */
|
Chris@16
|
132 template<typename Graph>
|
Chris@16
|
133 explicit
|
Chris@16
|
134 graph_communicator(const communicator& comm, const Graph& graph,
|
Chris@16
|
135 bool reorder = false);
|
Chris@16
|
136
|
Chris@16
|
137 /**
|
Chris@16
|
138 * Create a new communicator whose topology is described by the
|
Chris@16
|
139 * given graph. The rank map (@p rank) gives the mapping from
|
Chris@16
|
140 * vertices in the graph to ranks within the communicator. There
|
Chris@16
|
141 * may be fewer vertices in the graph than there are processes in
|
Chris@16
|
142 * the communicator; in this case, the resulting communicator will
|
Chris@16
|
143 * be a NULL communicator.
|
Chris@16
|
144 *
|
Chris@16
|
145 * @param comm The communicator that the new, graph communicator
|
Chris@16
|
146 * will be based on. The ranks in @c rank refer to the processes in
|
Chris@16
|
147 * this communicator.
|
Chris@16
|
148 *
|
Chris@16
|
149 * @param graph Any type that meets the requirements of the
|
Chris@16
|
150 * Incidence Graph and Vertex List Graph concepts from the Boost Graph
|
Chris@16
|
151 * Library. This structure of this graph will become the topology
|
Chris@16
|
152 * of the communicator that is returned.
|
Chris@16
|
153 *
|
Chris@16
|
154 * @param rank This map translates vertices in the @c graph into
|
Chris@16
|
155 * ranks within the current communicator. It must be a Readable
|
Chris@16
|
156 * Property Map (see the Boost Property Map library) whose key type
|
Chris@16
|
157 * is the vertex type of the @p graph and whose value type is @c
|
Chris@16
|
158 * int.
|
Chris@16
|
159 *
|
Chris@16
|
160 * @param reorder Whether MPI is permitted to re-order the process
|
Chris@16
|
161 * ranks within the returned communicator, to better optimize
|
Chris@16
|
162 * communication. If false, the ranks of each process in the
|
Chris@16
|
163 * returned process will match precisely the rank of that process
|
Chris@16
|
164 * within the original communicator.
|
Chris@16
|
165 */
|
Chris@16
|
166 template<typename Graph, typename RankMap>
|
Chris@16
|
167 explicit
|
Chris@16
|
168 graph_communicator(const communicator& comm, const Graph& graph,
|
Chris@16
|
169 RankMap rank, bool reorder = false);
|
Chris@16
|
170
|
Chris@16
|
171 protected:
|
Chris@16
|
172 /**
|
Chris@16
|
173 * INTERNAL ONLY
|
Chris@16
|
174 *
|
Chris@16
|
175 * Used by the constructors to create the new communicator with a
|
Chris@16
|
176 * graph topology.
|
Chris@16
|
177 */
|
Chris@16
|
178 template<typename Graph, typename RankMap>
|
Chris@16
|
179 void
|
Chris@16
|
180 setup_graph(const communicator& comm, const Graph& graph, RankMap rank,
|
Chris@16
|
181 bool reorder);
|
Chris@16
|
182 };
|
Chris@16
|
183
|
Chris@16
|
184 /****************************************************************************
|
Chris@16
|
185 * Implementation Details *
|
Chris@16
|
186 ****************************************************************************/
|
Chris@16
|
187
|
Chris@16
|
188 template<typename Graph>
|
Chris@16
|
189 graph_communicator::graph_communicator(const communicator& comm,
|
Chris@16
|
190 const Graph& graph,
|
Chris@16
|
191 bool reorder)
|
Chris@16
|
192 {
|
Chris@16
|
193 this->setup_graph(comm, graph, get(vertex_index, graph), reorder);
|
Chris@16
|
194 }
|
Chris@16
|
195
|
Chris@16
|
196 template<typename Graph, typename RankMap>
|
Chris@16
|
197 graph_communicator::graph_communicator(const communicator& comm,
|
Chris@16
|
198 const Graph& graph,
|
Chris@16
|
199 RankMap rank, bool reorder)
|
Chris@16
|
200 {
|
Chris@16
|
201 this->setup_graph(comm, graph, rank, reorder);
|
Chris@16
|
202 }
|
Chris@16
|
203
|
Chris@16
|
204
|
Chris@16
|
205 template<typename Graph, typename RankMap>
|
Chris@16
|
206 void
|
Chris@16
|
207 graph_communicator::setup_graph(const communicator& comm, const Graph& graph,
|
Chris@16
|
208 RankMap rank, bool reorder)
|
Chris@16
|
209 {
|
Chris@16
|
210 typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
|
Chris@16
|
211
|
Chris@16
|
212 // Build a mapping from ranks to vertices
|
Chris@16
|
213 std::vector<vertex_descriptor> vertex_with_rank(num_vertices(graph));
|
Chris@16
|
214 if (vertex_with_rank.empty())
|
Chris@16
|
215 return;
|
Chris@16
|
216
|
Chris@16
|
217 BGL_FORALL_VERTICES_T(v, graph, Graph)
|
Chris@16
|
218 vertex_with_rank[get(rank, v)] = v;
|
Chris@16
|
219
|
Chris@16
|
220 // Build the representation of the graph required by
|
Chris@16
|
221 // MPI_Graph_create.
|
Chris@16
|
222 std::vector<int> indices(num_vertices(graph));
|
Chris@16
|
223 std::vector<int> edges;
|
Chris@16
|
224 int nvertices = indices.size();
|
Chris@16
|
225 for (int vertex_index = 0; vertex_index < nvertices; ++vertex_index) {
|
Chris@16
|
226 vertex_descriptor v = vertex_with_rank[vertex_index];
|
Chris@16
|
227
|
Chris@16
|
228 BGL_FORALL_OUTEDGES_T(v, e, graph, Graph)
|
Chris@16
|
229 edges.push_back(get(rank, target(e, graph)));
|
Chris@16
|
230
|
Chris@16
|
231 indices[vertex_index] = edges.size();
|
Chris@16
|
232 }
|
Chris@16
|
233
|
Chris@16
|
234 // Create the new communicator
|
Chris@16
|
235 MPI_Comm newcomm;
|
Chris@16
|
236 BOOST_MPI_CHECK_RESULT(MPI_Graph_create,
|
Chris@16
|
237 ((MPI_Comm)comm,
|
Chris@16
|
238 nvertices,
|
Chris@16
|
239 &indices[0],
|
Chris@16
|
240 edges.empty()? (int*)0 : &edges[0],
|
Chris@16
|
241 reorder,
|
Chris@16
|
242 &newcomm));
|
Chris@16
|
243 this->comm_ptr.reset(new MPI_Comm(newcomm), comm_free());
|
Chris@16
|
244 }
|
Chris@16
|
245
|
Chris@16
|
246 /****************************************************************************
|
Chris@16
|
247 * Communicator with Graph Topology as BGL Graph *
|
Chris@16
|
248 ****************************************************************************/
|
Chris@16
|
249 namespace detail {
|
Chris@16
|
250 /**
|
Chris@16
|
251 * INTERNAL ONLY
|
Chris@16
|
252 *
|
Chris@16
|
253 * The iterator used to access the outgoing edges within a
|
Chris@16
|
254 * communicator's graph topology.
|
Chris@16
|
255 */
|
Chris@16
|
256 class comm_out_edge_iterator
|
Chris@16
|
257 : public iterator_facade<comm_out_edge_iterator,
|
Chris@16
|
258 std::pair<int, int>,
|
Chris@16
|
259 random_access_traversal_tag,
|
Chris@16
|
260 const std::pair<int, int>&,
|
Chris@16
|
261 int>
|
Chris@16
|
262 {
|
Chris@16
|
263 public:
|
Chris@16
|
264 comm_out_edge_iterator() { }
|
Chris@16
|
265
|
Chris@16
|
266 comm_out_edge_iterator(int source, shared_array<int> neighbors, int index)
|
Chris@16
|
267 : edge(source, -1), neighbors(neighbors), index(index) { }
|
Chris@16
|
268
|
Chris@16
|
269 protected:
|
Chris@16
|
270 friend class boost::iterator_core_access;
|
Chris@16
|
271
|
Chris@16
|
272 const std::pair<int, int>& dereference() const
|
Chris@16
|
273 {
|
Chris@16
|
274 edge.second = neighbors[index];
|
Chris@16
|
275 return edge;
|
Chris@16
|
276 }
|
Chris@16
|
277
|
Chris@16
|
278 bool equal(const comm_out_edge_iterator& other) const
|
Chris@16
|
279 {
|
Chris@16
|
280 return (edge.first == other.edge.first
|
Chris@16
|
281 && index == other.index);
|
Chris@16
|
282 }
|
Chris@16
|
283
|
Chris@16
|
284 void increment() { ++index; }
|
Chris@16
|
285
|
Chris@16
|
286 void decrement() { --index; }
|
Chris@16
|
287
|
Chris@16
|
288 void advance(int n) { index += n; }
|
Chris@16
|
289
|
Chris@16
|
290 int distance_to(const comm_out_edge_iterator& other) const
|
Chris@16
|
291 {
|
Chris@16
|
292 return other.index - index;
|
Chris@16
|
293 }
|
Chris@16
|
294
|
Chris@16
|
295 mutable std::pair<int, int> edge;
|
Chris@16
|
296 shared_array<int> neighbors;
|
Chris@16
|
297 int index;
|
Chris@16
|
298 };
|
Chris@16
|
299
|
Chris@16
|
300 /**
|
Chris@16
|
301 * INTERNAL ONLY
|
Chris@16
|
302 *
|
Chris@16
|
303 * The iterator used to access the adjacent vertices within a
|
Chris@16
|
304 * communicator's graph topology.
|
Chris@16
|
305 */
|
Chris@16
|
306 class comm_adj_iterator
|
Chris@16
|
307 : public iterator_facade<comm_adj_iterator,
|
Chris@16
|
308 int,
|
Chris@16
|
309 random_access_traversal_tag,
|
Chris@16
|
310 int,
|
Chris@16
|
311 int>
|
Chris@16
|
312 {
|
Chris@16
|
313 public:
|
Chris@16
|
314 comm_adj_iterator() { }
|
Chris@16
|
315
|
Chris@16
|
316 comm_adj_iterator(shared_array<int> neighbors, int index)
|
Chris@16
|
317 : neighbors(neighbors), index(index) { }
|
Chris@16
|
318
|
Chris@16
|
319 protected:
|
Chris@16
|
320 friend class boost::iterator_core_access;
|
Chris@16
|
321
|
Chris@16
|
322 int dereference() const { return neighbors[index]; }
|
Chris@16
|
323
|
Chris@16
|
324 bool equal(const comm_adj_iterator& other) const
|
Chris@16
|
325 {
|
Chris@16
|
326 return (neighbors == other.neighbors
|
Chris@16
|
327 && index == other.index);
|
Chris@16
|
328 }
|
Chris@16
|
329
|
Chris@16
|
330 void increment() { ++index; }
|
Chris@16
|
331
|
Chris@16
|
332 void decrement() { --index; }
|
Chris@16
|
333
|
Chris@16
|
334 void advance(int n) { index += n; }
|
Chris@16
|
335
|
Chris@16
|
336 int distance_to(const comm_adj_iterator& other) const
|
Chris@16
|
337 {
|
Chris@16
|
338 return other.index - index;
|
Chris@16
|
339 }
|
Chris@16
|
340
|
Chris@16
|
341 shared_array<int> neighbors;
|
Chris@16
|
342 int index;
|
Chris@16
|
343 };
|
Chris@16
|
344
|
Chris@16
|
345 /**
|
Chris@16
|
346 * INTERNAL ONLY
|
Chris@16
|
347 *
|
Chris@16
|
348 * The iterator used to access the edges in a communicator's graph
|
Chris@16
|
349 * topology.
|
Chris@16
|
350 */
|
Chris@16
|
351 class comm_edge_iterator
|
Chris@16
|
352 : public iterator_facade<comm_edge_iterator,
|
Chris@16
|
353 std::pair<int, int>,
|
Chris@16
|
354 forward_traversal_tag,
|
Chris@16
|
355 const std::pair<int, int>&,
|
Chris@16
|
356 int>
|
Chris@16
|
357 {
|
Chris@16
|
358 public:
|
Chris@16
|
359 comm_edge_iterator() { }
|
Chris@16
|
360
|
Chris@16
|
361 /// Constructor for a past-the-end iterator
|
Chris@16
|
362 comm_edge_iterator(int nedges) : edge_index(nedges) { }
|
Chris@16
|
363
|
Chris@16
|
364 comm_edge_iterator(shared_array<int> indices, shared_array<int> edges)
|
Chris@16
|
365 : indices(indices), edges(edges), edge_index(0), edge(0, 0)
|
Chris@16
|
366 { }
|
Chris@16
|
367
|
Chris@16
|
368 protected:
|
Chris@16
|
369 friend class boost::iterator_core_access;
|
Chris@16
|
370
|
Chris@16
|
371 const std::pair<int, int>& dereference() const
|
Chris@16
|
372 {
|
Chris@16
|
373 while (edge_index == indices[edge.first])
|
Chris@16
|
374 ++edge.first;
|
Chris@16
|
375 edge.second = edges[edge_index];
|
Chris@16
|
376 return edge;
|
Chris@16
|
377 }
|
Chris@16
|
378
|
Chris@16
|
379 bool equal(const comm_edge_iterator& other) const
|
Chris@16
|
380 {
|
Chris@16
|
381 return edge_index == other.edge_index;
|
Chris@16
|
382 }
|
Chris@16
|
383
|
Chris@16
|
384 void increment()
|
Chris@16
|
385 {
|
Chris@16
|
386 ++edge_index;
|
Chris@16
|
387 }
|
Chris@16
|
388
|
Chris@16
|
389 shared_array<int> indices;
|
Chris@16
|
390 shared_array<int> edges;
|
Chris@16
|
391 int edge_index;
|
Chris@16
|
392 mutable std::pair<int, int> edge;
|
Chris@16
|
393 };
|
Chris@16
|
394
|
Chris@16
|
395 } // end namespace detail
|
Chris@16
|
396
|
Chris@16
|
397 // Incidence Graph requirements
|
Chris@16
|
398
|
Chris@16
|
399 /**
|
Chris@16
|
400 * @brief Returns the source vertex from an edge in the graph topology
|
Chris@16
|
401 * of a communicator.
|
Chris@16
|
402 */
|
Chris@16
|
403 inline int source(const std::pair<int, int>& edge, const graph_communicator&)
|
Chris@16
|
404 {
|
Chris@16
|
405 return edge.first;
|
Chris@16
|
406 }
|
Chris@16
|
407
|
Chris@16
|
408 /**
|
Chris@16
|
409 * @brief Returns the target vertex from an edge in the graph topology
|
Chris@16
|
410 * of a communicator.
|
Chris@16
|
411 */
|
Chris@16
|
412 inline int target(const std::pair<int, int>& edge, const graph_communicator&)
|
Chris@16
|
413 {
|
Chris@16
|
414 return edge.second;
|
Chris@16
|
415 }
|
Chris@16
|
416
|
Chris@16
|
417 /**
|
Chris@16
|
418 * @brief Returns an iterator range containing all of the edges
|
Chris@16
|
419 * outgoing from the given vertex in a graph topology of a
|
Chris@16
|
420 * communicator.
|
Chris@16
|
421 */
|
Chris@16
|
422 std::pair<detail::comm_out_edge_iterator, detail::comm_out_edge_iterator>
|
Chris@16
|
423 out_edges(int vertex, const graph_communicator& comm);
|
Chris@16
|
424
|
Chris@16
|
425
|
Chris@16
|
426 /**
|
Chris@16
|
427 * @brief Returns the out-degree of a vertex in the graph topology of
|
Chris@16
|
428 * a communicator.
|
Chris@16
|
429 */
|
Chris@16
|
430 int out_degree(int vertex, const graph_communicator& comm);
|
Chris@16
|
431
|
Chris@16
|
432 // Adjacency Graph requirements
|
Chris@16
|
433
|
Chris@16
|
434 /**
|
Chris@16
|
435 * @brief Returns an iterator range containing all of the neighbors of
|
Chris@16
|
436 * the given vertex in the communicator's graph topology.
|
Chris@16
|
437 */
|
Chris@16
|
438 std::pair<detail::comm_adj_iterator, detail::comm_adj_iterator>
|
Chris@16
|
439 adjacent_vertices(int vertex, const graph_communicator& comm);
|
Chris@16
|
440
|
Chris@16
|
441 // Vertex List Graph requirements
|
Chris@16
|
442
|
Chris@16
|
443 /**
|
Chris@16
|
444 * @brief Returns an iterator range that contains all of the vertices
|
Chris@16
|
445 * with the communicator's graph topology, i.e., all of the process
|
Chris@16
|
446 * ranks in the communicator.
|
Chris@16
|
447 */
|
Chris@16
|
448 inline std::pair<counting_iterator<int>, counting_iterator<int> >
|
Chris@16
|
449 vertices(const graph_communicator& comm)
|
Chris@16
|
450 {
|
Chris@16
|
451 return std::make_pair(counting_iterator<int>(0),
|
Chris@16
|
452 counting_iterator<int>(comm.size()));
|
Chris@16
|
453 }
|
Chris@16
|
454
|
Chris@16
|
455 /**
|
Chris@16
|
456 * @brief Returns the number of vertices within the graph topology of
|
Chris@16
|
457 * the communicator, i.e., the number of processes in the
|
Chris@16
|
458 * communicator.
|
Chris@16
|
459 */
|
Chris@16
|
460 inline int num_vertices(const graph_communicator& comm) { return comm.size(); }
|
Chris@16
|
461
|
Chris@16
|
462 // Edge List Graph requirements
|
Chris@16
|
463
|
Chris@16
|
464 /**
|
Chris@16
|
465 * @brief Returns an iterator range that contains all of the edges
|
Chris@16
|
466 * with the communicator's graph topology.
|
Chris@16
|
467 */
|
Chris@16
|
468 std::pair<detail::comm_edge_iterator, detail::comm_edge_iterator>
|
Chris@16
|
469 edges(const graph_communicator& comm);
|
Chris@16
|
470
|
Chris@16
|
471 /**
|
Chris@16
|
472 * @brief Returns the number of edges in the communicator's graph
|
Chris@16
|
473 * topology.
|
Chris@16
|
474 */
|
Chris@16
|
475 int num_edges(const graph_communicator& comm);
|
Chris@16
|
476
|
Chris@16
|
477 // Property Graph requirements
|
Chris@16
|
478
|
Chris@16
|
479 /**
|
Chris@16
|
480 * @brief Returns a property map that maps from vertices in a
|
Chris@16
|
481 * communicator's graph topology to their index values.
|
Chris@16
|
482 *
|
Chris@16
|
483 * Since the vertices are ranks in the communicator, the returned
|
Chris@16
|
484 * property map is the identity property map.
|
Chris@16
|
485 */
|
Chris@16
|
486 inline identity_property_map get(vertex_index_t, const graph_communicator&)
|
Chris@16
|
487 {
|
Chris@16
|
488 return identity_property_map();
|
Chris@16
|
489 }
|
Chris@16
|
490
|
Chris@16
|
491 /**
|
Chris@16
|
492 * @brief Returns the index of a vertex in the communicator's graph
|
Chris@16
|
493 * topology.
|
Chris@16
|
494 *
|
Chris@16
|
495 * Since the vertices are ranks in the communicator, this is the
|
Chris@16
|
496 * identity function.
|
Chris@16
|
497 */
|
Chris@16
|
498 inline int get(vertex_index_t, const graph_communicator&, int vertex)
|
Chris@16
|
499 {
|
Chris@16
|
500 return vertex;
|
Chris@16
|
501 }
|
Chris@16
|
502
|
Chris@16
|
503 } } // end namespace boost::mpi
|
Chris@16
|
504
|
Chris@16
|
505 namespace boost {
|
Chris@16
|
506
|
Chris@16
|
507 /**
|
Chris@16
|
508 * @brief Traits structure that allows a communicator with graph
|
Chris@16
|
509 * topology to be view as a graph by the Boost Graph Library.
|
Chris@16
|
510 *
|
Chris@16
|
511 * The specialization of @c graph_traits for an MPI communicator
|
Chris@16
|
512 * allows a communicator with graph topology to be viewed as a
|
Chris@16
|
513 * graph. An MPI communicator with graph topology meets the
|
Chris@16
|
514 * requirements of the Graph, Incidence Graph, Adjacency Graph, Vertex
|
Chris@16
|
515 * List Graph, and Edge List Graph concepts from the Boost Graph
|
Chris@16
|
516 * Library.
|
Chris@16
|
517 */
|
Chris@16
|
518 template<>
|
Chris@16
|
519 struct graph_traits<mpi::graph_communicator> {
|
Chris@16
|
520 // Graph concept requirements
|
Chris@16
|
521 typedef int vertex_descriptor;
|
Chris@16
|
522 typedef std::pair<int, int> edge_descriptor;
|
Chris@16
|
523 typedef directed_tag directed_category;
|
Chris@16
|
524 typedef disallow_parallel_edge_tag edge_parallel_category;
|
Chris@16
|
525
|
Chris@16
|
526 /**
|
Chris@16
|
527 * INTERNAL ONLY
|
Chris@16
|
528 */
|
Chris@16
|
529 struct traversal_category
|
Chris@16
|
530 : incidence_graph_tag,
|
Chris@16
|
531 adjacency_graph_tag,
|
Chris@16
|
532 vertex_list_graph_tag,
|
Chris@16
|
533 edge_list_graph_tag
|
Chris@16
|
534 {
|
Chris@16
|
535 };
|
Chris@16
|
536
|
Chris@16
|
537 /**
|
Chris@16
|
538 * @brief Returns a vertex descriptor that can never refer to any
|
Chris@16
|
539 * valid vertex.
|
Chris@16
|
540 */
|
Chris@16
|
541 static vertex_descriptor null_vertex() { return -1; }
|
Chris@16
|
542
|
Chris@16
|
543 // Incidence Graph requirements
|
Chris@16
|
544 typedef mpi::detail::comm_out_edge_iterator out_edge_iterator;
|
Chris@16
|
545 typedef int degree_size_type;
|
Chris@16
|
546
|
Chris@16
|
547 // Adjacency Graph requirements
|
Chris@16
|
548 typedef mpi::detail::comm_adj_iterator adjacency_iterator;
|
Chris@16
|
549
|
Chris@16
|
550 // Vertex List Graph requirements
|
Chris@16
|
551 typedef counting_iterator<int> vertex_iterator;
|
Chris@16
|
552 typedef int vertices_size_type;
|
Chris@16
|
553
|
Chris@16
|
554 // Edge List Graph requirements
|
Chris@16
|
555 typedef mpi::detail::comm_edge_iterator edge_iterator;
|
Chris@16
|
556 typedef int edges_size_type;
|
Chris@16
|
557 };
|
Chris@16
|
558
|
Chris@16
|
559 // Property Graph requirements
|
Chris@16
|
560
|
Chris@16
|
561 /**
|
Chris@16
|
562 * INTERNAL ONLY
|
Chris@16
|
563 */
|
Chris@16
|
564 template<>
|
Chris@16
|
565 struct property_map<mpi::graph_communicator, vertex_index_t>
|
Chris@16
|
566 {
|
Chris@16
|
567 typedef identity_property_map type;
|
Chris@16
|
568 typedef identity_property_map const_type;
|
Chris@16
|
569 };
|
Chris@16
|
570
|
Chris@16
|
571 } // end namespace boost
|
Chris@16
|
572
|
Chris@16
|
573
|
Chris@16
|
574
|
Chris@16
|
575 #endif // BOOST_MPI_GRAPH_COMMUNICATOR_HPP
|