1 // Copyright (C) 2007 Douglas Gregor
2 // Copyright (C) 2007 Hartmut Kaiser
3
4 // Use, modification and distribution is subject to the Boost Software
5 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
6 // http://www.boost.org/LICENSE_1_0.txt)
7
8 // TODO:
9 // - Cache (some) remote vertex names?
10 #ifndef BOOST_GRAPH_DISTRIBUTED_NAMED_GRAPH_HPP
11 #define BOOST_GRAPH_DISTRIBUTED_NAMED_GRAPH_HPP
12
13 #ifndef BOOST_GRAPH_USE_MPI
14 #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
15 #endif
16
17 #include <boost/assert.hpp>
18 #include <boost/graph/named_graph.hpp>
19 #include <boost/functional/hash.hpp>
20 #include <boost/variant.hpp>
21 #include <boost/graph/parallel/simple_trigger.hpp>
22 #include <boost/graph/parallel/process_group.hpp>
23 #include <boost/graph/parallel/detail/property_holders.hpp>
24
25 namespace boost { namespace graph { namespace distributed {
26
27 using boost::parallel::trigger_receive_context;
28 using boost::detail::parallel::pair_with_property;
29
30 /*******************************************************************
31 * Hashed distribution of named entities *
32 *******************************************************************/
33
34 template<typename T>
35 struct hashed_distribution
36 {
37 template<typename ProcessGroup>
hashed_distributionboost::graph::distributed::hashed_distribution38 hashed_distribution(const ProcessGroup& pg, std::size_t /*num_vertices*/ = 0)
39 : n(num_processes(pg)) { }
40
operator ()boost::graph::distributed::hashed_distribution41 int operator()(const T& value) const
42 {
43 return hasher(value) % n;
44 }
45
46 std::size_t n;
47 hash<T> hasher;
48 };
49
50 /// Specialization for named graphs
51 template <typename InDistribution, typename VertexProperty, typename VertexSize,
52 typename ProcessGroup,
53 typename ExtractName
54 = typename internal_vertex_name<VertexProperty>::type>
55 struct select_distribution
56 {
57 private:
58 /// The type used to name vertices in the graph
59 typedef typename remove_cv<
60 typename remove_reference<
61 typename ExtractName::result_type>::type>::type
62 vertex_name_type;
63
64 public:
65 /**
66 * The @c type field provides a distribution object that maps
67 * vertex names to processors. The distribution object will be
68 * constructed with the process group over which communication will
69 * occur. The distribution object shall also be a function
70 * object mapping from the type of the name to a processor number
71 * in @c [0, @c p) (for @c p processors). By default, the mapping
72 * function uses the @c boost::hash value of the name, modulo @c p.
73 */
74 typedef typename mpl::if_<is_same<InDistribution, defaultS>,
75 hashed_distribution<vertex_name_type>,
76 InDistribution>::type
77 type;
78
79 /// for named graphs the default type is the same as the stored distribution
80 /// type
81 typedef type default_type;
82 };
83
84 /// Specialization for non-named graphs
85 template <typename InDistribution, typename VertexProperty, typename VertexSize,
86 typename ProcessGroup>
87 struct select_distribution<InDistribution, VertexProperty, VertexSize,
88 ProcessGroup, void>
89 {
90 /// the distribution type stored in the graph for non-named graphs should be
91 /// the variant_distribution type
92 typedef typename mpl::if_<is_same<InDistribution, defaultS>,
93 boost::parallel::variant_distribution<ProcessGroup,
94 VertexSize>,
95 InDistribution>::type type;
96
97 /// default_type is used as the distribution functor for the
98 /// adjacency_list, it should be parallel::block by default
99 typedef typename mpl::if_<is_same<InDistribution, defaultS>,
100 boost::parallel::block, type>::type
101 default_type;
102 };
103
104
105 /*******************************************************************
106 * Named graph mixin *
107 *******************************************************************/
108
109 /**
110 * named_graph is a mixin that provides names for the vertices of a
111 * graph, including a mapping from names to vertices. Graph types that
112 * may or may not be have vertex names (depending on the properties
113 * supplied by the user) should use maybe_named_graph.
114 *
115 * Template parameters:
116 *
117 * Graph: the graph type that derives from named_graph
118 *
119 * Vertex: the type of a vertex descriptor in Graph. Note: we cannot
120 * use graph_traits here, because the Graph is not yet defined.
121 *
122 * VertexProperty: the type of the property stored along with the
123 * vertex.
124 *
125 * ProcessGroup: the process group over which the distributed name
126 * graph mixin will communicate.
127 */
128 template<typename Graph, typename Vertex, typename Edge, typename Config>
129 class named_graph
130 {
131 public:
132 /// Messages passed within the distributed named graph
133 enum message_kind {
134 /**
135 * Requests the addition of a vertex on a remote processor. The
136 * message data is a @c vertex_name_type.
137 */
138 msg_add_vertex_name,
139
140 /**
141 * Requests the addition of a vertex on a remote processor. The
142 * message data is a @c vertex_name_type. The remote processor
143 * will send back a @c msg_add_vertex_name_reply message
144 * containing the vertex descriptor.
145 */
146 msg_add_vertex_name_with_reply,
147
148 /**
149 * Requests the vertex descriptor corresponding to the given
150 * vertex name. The remote process will reply with a
151 * @c msg_find_vertex_reply message containing the answer.
152 */
153 msg_find_vertex,
154
155 /**
156 * Requests the addition of an edge on a remote processor. The
157 * data stored in these messages is a @c pair<source, target>@,
158 * where @c source and @c target may be either names (of type @c
159 * vertex_name_type) or vertex descriptors, depending on what
160 * information we have locally.
161 */
162 msg_add_edge_name_name,
163 msg_add_edge_vertex_name,
164 msg_add_edge_name_vertex,
165
166 /**
167 * These messages are identical to msg_add_edge_*_*, except that
168 * the process actually adding the edge will send back a @c
169 * pair<edge_descriptor,bool>
170 */
171 msg_add_edge_name_name_with_reply,
172 msg_add_edge_vertex_name_with_reply,
173 msg_add_edge_name_vertex_with_reply,
174
175 /**
176 * Requests the addition of an edge with a property on a remote
177 * processor. The data stored in these messages is a @c
178 * pair<vertex_property_type, pair<source, target>>@, where @c
179 * source and @c target may be either names (of type @c
180 * vertex_name_type) or vertex descriptors, depending on what
181 * information we have locally.
182 */
183 msg_add_edge_name_name_with_property,
184 msg_add_edge_vertex_name_with_property,
185 msg_add_edge_name_vertex_with_property,
186
187 /**
188 * These messages are identical to msg_add_edge_*_*_with_property,
189 * except that the process actually adding the edge will send back
190 * a @c pair<edge_descriptor,bool>.
191 */
192 msg_add_edge_name_name_with_reply_and_property,
193 msg_add_edge_vertex_name_with_reply_and_property,
194 msg_add_edge_name_vertex_with_reply_and_property
195 };
196
197 /// The vertex descriptor type
198 typedef Vertex vertex_descriptor;
199
200 /// The edge descriptor type
201 typedef Edge edge_descriptor;
202
203 /// The vertex property type
204 typedef typename Config::vertex_property_type vertex_property_type;
205
206 /// The vertex property type
207 typedef typename Config::edge_property_type edge_property_type;
208
209 /// The type used to extract names from the property structure
210 typedef typename internal_vertex_name<vertex_property_type>::type
211 extract_name_type;
212
213 /// The type used to name vertices in the graph
214 typedef typename remove_cv<
215 typename remove_reference<
216 typename extract_name_type::result_type>::type>::type
217 vertex_name_type;
218
219 /// The type used to distribute named vertices in the graph
220 typedef typename Config::distribution_type distribution_type;
221 typedef typename Config::base_distribution_type base_distribution_type;
222
223 /// The type used for communication in the distributed structure
224 typedef typename Config::process_group_type process_group_type;
225
226 /// Type used to identify processes
227 typedef typename process_group_type::process_id_type process_id_type;
228
229 /// a reference to this class, which is used for disambiguation of the
230 // add_vertex function
231 typedef named_graph named_graph_type;
232
233 /// Structure returned when adding a vertex by vertex name
234 struct lazy_add_vertex;
235 friend struct lazy_add_vertex;
236
237 /// Structure returned when adding an edge by vertex name
238 struct lazy_add_edge;
239 friend struct lazy_add_edge;
240
241 /// Structure returned when adding an edge by vertex name with a property
242 struct lazy_add_edge_with_property;
243 friend struct lazy_add_edge_with_property;
244
245 explicit named_graph(const process_group_type& pg);
246
247 named_graph(const process_group_type& pg, const base_distribution_type& distribution);
248
249 /// Set up triggers, but only for the BSP process group
250 void setup_triggers();
251
252 /// Retrieve the derived instance
derived()253 Graph& derived() { return static_cast<Graph&>(*this); }
derived() const254 const Graph& derived() const { return static_cast<const Graph&>(*this); }
255
256 /// Retrieve the process group
process_group()257 process_group_type& process_group() { return process_group_; }
process_group() const258 const process_group_type& process_group() const { return process_group_; }
259
260 // Retrieve the named distribution
named_distribution()261 distribution_type& named_distribution() { return distribution_; }
named_distribution() const262 const distribution_type& named_distribution() const { return distribution_; }
263
264 /// Notify the named_graph that we have added the given vertex. This
265 /// is a no-op.
added_vertex(Vertex)266 void added_vertex(Vertex) { }
267
268 /// Notify the named_graph that we are removing the given
269 /// vertex. This is a no-op.
270 template <typename VertexIterStability>
removing_vertex(Vertex,VertexIterStability)271 void removing_vertex(Vertex, VertexIterStability) { }
272
273 /// Notify the named_graph that we are clearing the graph
clearing_graph()274 void clearing_graph() { }
275
276 /// Retrieve the owner of a given vertex based on the properties
277 /// associated with that vertex. This operation just returns the
278 /// number of the local processor, adding all vertices locally.
279 process_id_type owner_by_property(const vertex_property_type&);
280
281 protected:
282 void
283 handle_add_vertex_name(int source, int tag, const vertex_name_type& msg,
284 trigger_receive_context);
285
286 vertex_descriptor
287 handle_add_vertex_name_with_reply(int source, int tag,
288 const vertex_name_type& msg,
289 trigger_receive_context);
290
291 boost::parallel::detail::untracked_pair<vertex_descriptor, bool>
292 handle_find_vertex(int source, int tag, const vertex_name_type& msg,
293 trigger_receive_context);
294
295 template<typename U, typename V>
296 void handle_add_edge(int source, int tag, const boost::parallel::detail::untracked_pair<U, V>& msg,
297 trigger_receive_context);
298
299 template<typename U, typename V>
300 boost::parallel::detail::untracked_pair<edge_descriptor, bool>
301 handle_add_edge_with_reply(int source, int tag, const boost::parallel::detail::untracked_pair<U, V>& msg,
302 trigger_receive_context);
303
304 template<typename U, typename V>
305 void
306 handle_add_edge_with_property
307 (int source, int tag,
308 const pair_with_property<U, V, edge_property_type>& msg,
309 trigger_receive_context);
310
311 template<typename U, typename V>
312 boost::parallel::detail::untracked_pair<edge_descriptor, bool>
313 handle_add_edge_with_reply_and_property
314 (int source, int tag,
315 const pair_with_property<U, V, edge_property_type>& msg,
316 trigger_receive_context);
317
318 /// The process group for this distributed data structure
319 process_group_type process_group_;
320
321 /// The distribution we will use to map names to processors
322 distribution_type distribution_;
323 };
324
325 /// Helper macro containing the template parameters of named_graph
326 #define BGL_NAMED_GRAPH_PARAMS \
327 typename Graph, typename Vertex, typename Edge, typename Config
328 /// Helper macro containing the named_graph<...> instantiation
329 #define BGL_NAMED_GRAPH \
330 named_graph<Graph, Vertex, Edge, Config>
331
332 /**
333 * Data structure returned from add_vertex that will "lazily" add the
334 * vertex, either when it is converted to a @c vertex_descriptor or
335 * when the most recent copy has been destroyed.
336 */
337 template<BGL_NAMED_GRAPH_PARAMS>
338 struct BGL_NAMED_GRAPH::lazy_add_vertex
339 {
340 /// Construct a new lazyily-added vertex
lazy_add_vertexboost::graph::distributed::BGL_NAMED_GRAPH::lazy_add_vertex341 lazy_add_vertex(named_graph& self, const vertex_name_type& name)
342 : self(self), name(name), committed(false) { }
343
344 /// Transfer responsibility for adding the vertex from the source of
345 /// the copy to the newly-constructed opbject.
lazy_add_vertexboost::graph::distributed::BGL_NAMED_GRAPH::lazy_add_vertex346 lazy_add_vertex(const lazy_add_vertex& other)
347 : self(other.self), name(other.name), committed(other.committed)
348 {
349 other.committed = true;
350 }
351
352 /// If the vertex has not been added yet, add it
353 ~lazy_add_vertex();
354
355 /// Add the vertex and return its descriptor. This conversion can
356 /// only occur once, and only when this object is responsible for
357 /// creating the vertex.
operator vertex_descriptorboost::graph::distributed::BGL_NAMED_GRAPH::lazy_add_vertex358 operator vertex_descriptor() const { return commit(); }
359
360 /// Add the vertex and return its descriptor. This can only be
361 /// called once, and only when this object is responsible for
362 /// creating the vertex.
363 vertex_descriptor commit() const;
364
365 protected:
366 named_graph& self;
367 vertex_name_type name;
368 mutable bool committed;
369 };
370
371 template<BGL_NAMED_GRAPH_PARAMS>
~lazy_add_vertex()372 BGL_NAMED_GRAPH::lazy_add_vertex::~lazy_add_vertex()
373 {
374 typedef typename BGL_NAMED_GRAPH::process_id_type process_id_type;
375
376 /// If this vertex has already been created or will be created by
377 /// someone else, or if someone threw an exception, we will not
378 /// create the vertex now.
379 if (committed || std::uncaught_exception())
380 return;
381
382 committed = true;
383
384 process_id_type owner = self.named_distribution()(name);
385 if (owner == process_id(self.process_group()))
386 /// Add the vertex locally
387 add_vertex(self.derived().base().vertex_constructor(name), self.derived());
388 else
389 /// Ask the owner of the vertex to add a vertex with this name
390 send(self.process_group(), owner, msg_add_vertex_name, name);
391 }
392
393 template<BGL_NAMED_GRAPH_PARAMS>
394 typename BGL_NAMED_GRAPH::vertex_descriptor
commit() const395 BGL_NAMED_GRAPH::lazy_add_vertex::commit() const
396 {
397 typedef typename BGL_NAMED_GRAPH::process_id_type process_id_type;
398 BOOST_ASSERT (!committed);
399 committed = true;
400
401 process_id_type owner = self.named_distribution()(name);
402 if (owner == process_id(self.process_group()))
403 /// Add the vertex locally
404 return add_vertex(self.derived().base().vertex_constructor(name),
405 self.derived());
406 else {
407 /// Ask the owner of the vertex to add a vertex with this name
408 vertex_descriptor result;
409 send_oob_with_reply(self.process_group(), owner,
410 msg_add_vertex_name_with_reply, name, result);
411 return result;
412 }
413 }
414
415 /**
416 * Data structure returned from add_edge that will "lazily" add the
417 * edge, either when it is converted to a @c
418 * pair<edge_descriptor,bool> or when the most recent copy has been
419 * destroyed.
420 */
421 template<BGL_NAMED_GRAPH_PARAMS>
422 struct BGL_NAMED_GRAPH::lazy_add_edge
423 {
424 /// The graph's edge descriptor
425 typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
426
427 /// Add an edge for the edge (u, v) based on vertex names
lazy_add_edgeboost::graph::distributed::BGL_NAMED_GRAPH::lazy_add_edge428 lazy_add_edge(BGL_NAMED_GRAPH& self,
429 const vertex_name_type& u_name,
430 const vertex_name_type& v_name)
431 : self(self), u(u_name), v(v_name), committed(false) { }
432
433 /// Add an edge for the edge (u, v) based on a vertex descriptor and name
lazy_add_edgeboost::graph::distributed::BGL_NAMED_GRAPH::lazy_add_edge434 lazy_add_edge(BGL_NAMED_GRAPH& self,
435 vertex_descriptor u,
436 const vertex_name_type& v_name)
437 : self(self), u(u), v(v_name), committed(false) { }
438
439 /// Add an edge for the edge (u, v) based on a vertex name and descriptor
lazy_add_edgeboost::graph::distributed::BGL_NAMED_GRAPH::lazy_add_edge440 lazy_add_edge(BGL_NAMED_GRAPH& self,
441 const vertex_name_type& u_name,
442 vertex_descriptor v)
443 : self(self), u(u_name), v(v), committed(false) { }
444
445 /// Add an edge for the edge (u, v) based on vertex descriptors
lazy_add_edgeboost::graph::distributed::BGL_NAMED_GRAPH::lazy_add_edge446 lazy_add_edge(BGL_NAMED_GRAPH& self,
447 vertex_descriptor u,
448 vertex_descriptor v)
449 : self(self), u(u), v(v), committed(false) { }
450
451 /// Copy a lazy_add_edge structure, which transfers responsibility
452 /// for adding the edge to the newly-constructed object.
lazy_add_edgeboost::graph::distributed::BGL_NAMED_GRAPH::lazy_add_edge453 lazy_add_edge(const lazy_add_edge& other)
454 : self(other.self), u(other.u), v(other.v), committed(other.committed)
455 {
456 other.committed = true;
457 }
458
459 /// If the edge has not yet been added, add the edge but don't wait
460 /// for a reply.
461 ~lazy_add_edge();
462
463 /// Returns commit().
operator std::pair<edge_descriptor,bool>boost::graph::distributed::BGL_NAMED_GRAPH::lazy_add_edge464 operator std::pair<edge_descriptor, bool>() const { return commit(); }
465
466 // Add the edge. This operation will block if a remote edge is
467 // being added.
468 std::pair<edge_descriptor, bool> commit() const;
469
470 protected:
471 BGL_NAMED_GRAPH& self;
472 mutable variant<vertex_descriptor, vertex_name_type> u;
473 mutable variant<vertex_descriptor, vertex_name_type> v;
474 mutable bool committed;
475
476 private:
477 // No copy-assignment semantics
478 void operator=(lazy_add_edge&);
479 };
480
481 template<BGL_NAMED_GRAPH_PARAMS>
~lazy_add_edge()482 BGL_NAMED_GRAPH::lazy_add_edge::~lazy_add_edge()
483 {
484 using boost::parallel::detail::make_untracked_pair;
485
486 /// If this edge has already been created or will be created by
487 /// someone else, or if someone threw an exception, we will not
488 /// create the edge now.
489 if (committed || std::uncaught_exception())
490 return;
491
492 committed = true;
493
494 if (vertex_name_type* v_name = boost::get<vertex_name_type>(&v)) {
495 // We haven't resolved the target vertex to a descriptor yet, so
496 // it must not be local. Send a message to the owner of the target
497 // of the edge. If the owner of the target does not happen to own
498 // the source, it will resolve the target to a vertex descriptor
499 // and pass the message along to the owner of the source.
500 if (vertex_name_type* u_name = boost::get<vertex_name_type>(&u))
501 send(self.process_group(), self.distribution_(*v_name),
502 BGL_NAMED_GRAPH::msg_add_edge_name_name,
503 make_untracked_pair(*u_name, *v_name));
504 else
505 send(self.process_group(), self.distribution_(*v_name),
506 BGL_NAMED_GRAPH::msg_add_edge_vertex_name,
507 make_untracked_pair(boost::get<vertex_descriptor>(u), *v_name));
508 } else {
509 if (vertex_name_type* u_name = boost::get<vertex_name_type>(&u))
510 // We haven't resolved the source vertex to a descriptor yet, so
511 // it must not be local. Send a message to the owner of the
512 // source vertex requesting the edge addition.
513 send(self.process_group(), self.distribution_(*u_name),
514 BGL_NAMED_GRAPH::msg_add_edge_name_vertex,
515 make_untracked_pair(*u_name, boost::get<vertex_descriptor>(v)));
516 else
517 // We have descriptors for both of the vertices, either of which
518 // may be remote or local. Tell the owner of the source vertex
519 // to add the edge (it may be us!).
520 add_edge(boost::get<vertex_descriptor>(u),
521 boost::get<vertex_descriptor>(v),
522 self.derived());
523 }
524 }
525
526 template<BGL_NAMED_GRAPH_PARAMS>
527 std::pair<typename graph_traits<Graph>::edge_descriptor, bool>
commit() const528 BGL_NAMED_GRAPH::lazy_add_edge::commit() const
529 {
530 typedef typename BGL_NAMED_GRAPH::process_id_type process_id_type;
531 using boost::parallel::detail::make_untracked_pair;
532
533 BOOST_ASSERT(!committed);
534 committed = true;
535
536 /// The result we will return, if we are sending a message to
537 /// request that someone else add the edge.
538 boost::parallel::detail::untracked_pair<edge_descriptor, bool> result;
539
540 /// The owner of the vertex "u"
541 process_id_type u_owner;
542
543 process_id_type rank = process_id(self.process_group());
544 if (const vertex_name_type* u_name = boost::get<vertex_name_type>(&u)) {
545 /// We haven't resolved the source vertex to a descriptor yet, so
546 /// it must not be local.
547 u_owner = self.named_distribution()(*u_name);
548
549 /// Send a message to the remote vertex requesting that it add the
550 /// edge. The message differs depending on whether we have a
551 /// vertex name or a vertex descriptor for the target.
552 if (const vertex_name_type* v_name = boost::get<vertex_name_type>(&v))
553 send_oob_with_reply(self.process_group(), u_owner,
554 BGL_NAMED_GRAPH::msg_add_edge_name_name_with_reply,
555 make_untracked_pair(*u_name, *v_name), result);
556 else
557 send_oob_with_reply(self.process_group(), u_owner,
558 BGL_NAMED_GRAPH::msg_add_edge_name_vertex_with_reply,
559 make_untracked_pair(*u_name,
560 boost::get<vertex_descriptor>(v)),
561 result);
562 } else {
563 /// We have resolved the source vertex to a descriptor, which may
564 /// either be local or remote.
565 u_owner
566 = get(vertex_owner, self.derived(),
567 boost::get<vertex_descriptor>(u));
568 if (u_owner == rank) {
569 /// The source is local. If we need to, resolve the target vertex.
570 if (const vertex_name_type* v_name = boost::get<vertex_name_type>(&v))
571 v = add_vertex(*v_name, self.derived());
572
573 /// Add the edge using vertex descriptors
574 return add_edge(boost::get<vertex_descriptor>(u),
575 boost::get<vertex_descriptor>(v),
576 self.derived());
577 } else {
578 /// The source is remote. Just send a message to its owner
579 /// requesting that the owner add the new edge, either directly
580 /// or via the derived class's add_edge function.
581 if (const vertex_name_type* v_name = boost::get<vertex_name_type>(&v))
582 send_oob_with_reply
583 (self.process_group(), u_owner,
584 BGL_NAMED_GRAPH::msg_add_edge_vertex_name_with_reply,
585 make_untracked_pair(boost::get<vertex_descriptor>(u), *v_name),
586 result);
587 else
588 return add_edge(boost::get<vertex_descriptor>(u),
589 boost::get<vertex_descriptor>(v),
590 self.derived());
591 }
592 }
593
594 // If we get here, the edge has been added remotely and "result"
595 // contains the result of that edge addition.
596 return result;
597 }
598
599 /**
600 * Data structure returned from add_edge that will "lazily" add the
601 * edge with a property, either when it is converted to a @c
602 * pair<edge_descriptor,bool> or when the most recent copy has been
603 * destroyed.
604 */
605 template<BGL_NAMED_GRAPH_PARAMS>
606 struct BGL_NAMED_GRAPH::lazy_add_edge_with_property
607 {
608 /// The graph's edge descriptor
609 typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
610
611 /// The Edge property type for our graph
612 typedef typename Config::edge_property_type edge_property_type;
613
614 /// Add an edge for the edge (u, v) based on vertex names
lazy_add_edge_with_propertyboost::graph::distributed::BGL_NAMED_GRAPH::lazy_add_edge_with_property615 lazy_add_edge_with_property(BGL_NAMED_GRAPH& self,
616 const vertex_name_type& u_name,
617 const vertex_name_type& v_name,
618 const edge_property_type& property)
619 : self(self), u(u_name), v(v_name), property(property), committed(false)
620 {
621 }
622
623 /// Add an edge for the edge (u, v) based on a vertex descriptor and name
lazy_add_edge_with_propertyboost::graph::distributed::BGL_NAMED_GRAPH::lazy_add_edge_with_property624 lazy_add_edge_with_property(BGL_NAMED_GRAPH& self,
625 vertex_descriptor u,
626 const vertex_name_type& v_name,
627 const edge_property_type& property)
628 : self(self), u(u), v(v_name), property(property), committed(false) { }
629
630 /// Add an edge for the edge (u, v) based on a vertex name and descriptor
lazy_add_edge_with_propertyboost::graph::distributed::BGL_NAMED_GRAPH::lazy_add_edge_with_property631 lazy_add_edge_with_property(BGL_NAMED_GRAPH& self,
632 const vertex_name_type& u_name,
633 vertex_descriptor v,
634 const edge_property_type& property)
635 : self(self), u(u_name), v(v), property(property), committed(false) { }
636
637 /// Add an edge for the edge (u, v) based on vertex descriptors
lazy_add_edge_with_propertyboost::graph::distributed::BGL_NAMED_GRAPH::lazy_add_edge_with_property638 lazy_add_edge_with_property(BGL_NAMED_GRAPH& self,
639 vertex_descriptor u,
640 vertex_descriptor v,
641 const edge_property_type& property)
642 : self(self), u(u), v(v), property(property), committed(false) { }
643
644 /// Copy a lazy_add_edge_with_property structure, which transfers
645 /// responsibility for adding the edge to the newly-constructed
646 /// object.
lazy_add_edge_with_propertyboost::graph::distributed::BGL_NAMED_GRAPH::lazy_add_edge_with_property647 lazy_add_edge_with_property(const lazy_add_edge_with_property& other)
648 : self(other.self), u(other.u), v(other.v), property(other.property),
649 committed(other.committed)
650 {
651 other.committed = true;
652 }
653
654 /// If the edge has not yet been added, add the edge but don't wait
655 /// for a reply.
656 ~lazy_add_edge_with_property();
657
658 /// Returns commit().
operator std::pair<edge_descriptor,bool>boost::graph::distributed::BGL_NAMED_GRAPH::lazy_add_edge_with_property659 operator std::pair<edge_descriptor, bool>() const { return commit(); }
660
661 // Add the edge. This operation will block if a remote edge is
662 // being added.
663 std::pair<edge_descriptor, bool> commit() const;
664
665 protected:
666 BGL_NAMED_GRAPH& self;
667 mutable variant<vertex_descriptor, vertex_name_type> u;
668 mutable variant<vertex_descriptor, vertex_name_type> v;
669 edge_property_type property;
670 mutable bool committed;
671
672 private:
673 // No copy-assignment semantics
674 void operator=(lazy_add_edge_with_property&);
675 };
676
677 template<BGL_NAMED_GRAPH_PARAMS>
~lazy_add_edge_with_property()678 BGL_NAMED_GRAPH::lazy_add_edge_with_property::~lazy_add_edge_with_property()
679 {
680 using boost::detail::parallel::make_pair_with_property;
681
682 /// If this edge has already been created or will be created by
683 /// someone else, or if someone threw an exception, we will not
684 /// create the edge now.
685 if (committed || std::uncaught_exception())
686 return;
687
688 committed = true;
689
690 if (vertex_name_type* v_name = boost::get<vertex_name_type>(&v)) {
691 // We haven't resolved the target vertex to a descriptor yet, so
692 // it must not be local. Send a message to the owner of the target
693 // of the edge. If the owner of the target does not happen to own
694 // the source, it will resolve the target to a vertex descriptor
695 // and pass the message along to the owner of the source.
696 if (vertex_name_type* u_name = boost::get<vertex_name_type>(&u))
697 send(self.process_group(), self.distribution_(*v_name),
698 BGL_NAMED_GRAPH::msg_add_edge_name_name_with_property,
699 make_pair_with_property(*u_name, *v_name, property));
700 else
701 send(self.process_group(), self.distribution_(*v_name),
702 BGL_NAMED_GRAPH::msg_add_edge_vertex_name_with_property,
703 make_pair_with_property(boost::get<vertex_descriptor>(u), *v_name,
704 property));
705 } else {
706 if (vertex_name_type* u_name = boost::get<vertex_name_type>(&u))
707 // We haven't resolved the source vertex to a descriptor yet, so
708 // it must not be local. Send a message to the owner of the
709 // source vertex requesting the edge addition.
710 send(self.process_group(), self.distribution_(*u_name),
711 BGL_NAMED_GRAPH::msg_add_edge_name_vertex_with_property,
712 make_pair_with_property(*u_name, boost::get<vertex_descriptor>(v),
713 property));
714 else
715 // We have descriptors for both of the vertices, either of which
716 // may be remote or local. Tell the owner of the source vertex
717 // to add the edge (it may be us!).
718 add_edge(boost::get<vertex_descriptor>(u),
719 boost::get<vertex_descriptor>(v),
720 property,
721 self.derived());
722 }
723 }
724
725 template<BGL_NAMED_GRAPH_PARAMS>
726 std::pair<typename graph_traits<Graph>::edge_descriptor, bool>
commit() const727 BGL_NAMED_GRAPH::lazy_add_edge_with_property::commit() const
728 {
729 using boost::detail::parallel::make_pair_with_property;
730 typedef typename BGL_NAMED_GRAPH::process_id_type process_id_type;
731 BOOST_ASSERT(!committed);
732 committed = true;
733
734 /// The result we will return, if we are sending a message to
735 /// request that someone else add the edge.
736 boost::parallel::detail::untracked_pair<edge_descriptor, bool> result;
737
738 /// The owner of the vertex "u"
739 process_id_type u_owner;
740
741 process_id_type rank = process_id(self.process_group());
742 if (const vertex_name_type* u_name = boost::get<vertex_name_type>(&u)) {
743 /// We haven't resolved the source vertex to a descriptor yet, so
744 /// it must not be local.
745 u_owner = self.named_distribution()(*u_name);
746
747 /// Send a message to the remote vertex requesting that it add the
748 /// edge. The message differs depending on whether we have a
749 /// vertex name or a vertex descriptor for the target.
750 if (const vertex_name_type* v_name = boost::get<vertex_name_type>(&v))
751 send_oob_with_reply
752 (self.process_group(), u_owner,
753 BGL_NAMED_GRAPH::msg_add_edge_name_name_with_reply_and_property,
754 make_pair_with_property(*u_name, *v_name, property),
755 result);
756 else
757 send_oob_with_reply
758 (self.process_group(), u_owner,
759 BGL_NAMED_GRAPH::msg_add_edge_name_vertex_with_reply_and_property,
760 make_pair_with_property(*u_name,
761 boost::get<vertex_descriptor>(v),
762 property),
763 result);
764 } else {
765 /// We have resolved the source vertex to a descriptor, which may
766 /// either be local or remote.
767 u_owner
768 = get(vertex_owner, self.derived(),
769 boost::get<vertex_descriptor>(u));
770 if (u_owner == rank) {
771 /// The source is local. If we need to, resolve the target vertex.
772 if (const vertex_name_type* v_name = boost::get<vertex_name_type>(&v))
773 v = add_vertex(*v_name, self.derived());
774
775 /// Add the edge using vertex descriptors
776 return add_edge(boost::get<vertex_descriptor>(u),
777 boost::get<vertex_descriptor>(v),
778 property,
779 self.derived());
780 } else {
781 /// The source is remote. Just send a message to its owner
782 /// requesting that the owner add the new edge, either directly
783 /// or via the derived class's add_edge function.
784 if (const vertex_name_type* v_name = boost::get<vertex_name_type>(&v))
785 send_oob_with_reply
786 (self.process_group(), u_owner,
787 BGL_NAMED_GRAPH::msg_add_edge_vertex_name_with_reply_and_property,
788 make_pair_with_property(boost::get<vertex_descriptor>(u), *v_name,
789 property),
790 result);
791 else
792 return add_edge(boost::get<vertex_descriptor>(u),
793 boost::get<vertex_descriptor>(v),
794 property,
795 self.derived());
796 }
797 }
798
799 // If we get here, the edge has been added remotely and "result"
800 // contains the result of that edge addition.
801 return result;
802 }
803
804 /// Construct the named_graph with a particular process group
805 template<BGL_NAMED_GRAPH_PARAMS>
named_graph(const process_group_type & pg)806 BGL_NAMED_GRAPH::named_graph(const process_group_type& pg)
807 : process_group_(pg, boost::parallel::attach_distributed_object()),
808 distribution_(pg)
809 {
810 setup_triggers();
811 }
812
813 /// Construct the named_graph mixin with a particular process group
814 /// and distribution function
815 template<BGL_NAMED_GRAPH_PARAMS>
named_graph(const process_group_type & pg,const base_distribution_type & distribution)816 BGL_NAMED_GRAPH::named_graph(const process_group_type& pg,
817 const base_distribution_type& distribution)
818 : process_group_(pg, boost::parallel::attach_distributed_object()),
819 distribution_(pg, distribution)
820 {
821 setup_triggers();
822 }
823
824 template<BGL_NAMED_GRAPH_PARAMS>
825 void
setup_triggers()826 BGL_NAMED_GRAPH::setup_triggers()
827 {
828 using boost::graph::parallel::simple_trigger;
829
830 simple_trigger(process_group_, msg_add_vertex_name, this,
831 &named_graph::handle_add_vertex_name);
832 simple_trigger(process_group_, msg_add_vertex_name_with_reply, this,
833 &named_graph::handle_add_vertex_name_with_reply);
834 simple_trigger(process_group_, msg_find_vertex, this,
835 &named_graph::handle_find_vertex);
836 simple_trigger(process_group_, msg_add_edge_name_name, this,
837 &named_graph::template handle_add_edge<vertex_name_type,
838 vertex_name_type>);
839 simple_trigger(process_group_, msg_add_edge_name_name_with_reply, this,
840 &named_graph::template handle_add_edge_with_reply
841 <vertex_name_type, vertex_name_type>);
842 simple_trigger(process_group_, msg_add_edge_name_vertex, this,
843 &named_graph::template handle_add_edge<vertex_name_type,
844 vertex_descriptor>);
845 simple_trigger(process_group_, msg_add_edge_name_vertex_with_reply, this,
846 &named_graph::template handle_add_edge_with_reply
847 <vertex_name_type, vertex_descriptor>);
848 simple_trigger(process_group_, msg_add_edge_vertex_name, this,
849 &named_graph::template handle_add_edge<vertex_descriptor,
850 vertex_name_type>);
851 simple_trigger(process_group_, msg_add_edge_vertex_name_with_reply, this,
852 &named_graph::template handle_add_edge_with_reply
853 <vertex_descriptor, vertex_name_type>);
854 simple_trigger(process_group_, msg_add_edge_name_name_with_property, this,
855 &named_graph::
856 template handle_add_edge_with_property<vertex_name_type,
857 vertex_name_type>);
858 simple_trigger(process_group_,
859 msg_add_edge_name_name_with_reply_and_property, this,
860 &named_graph::template handle_add_edge_with_reply_and_property
861 <vertex_name_type, vertex_name_type>);
862 simple_trigger(process_group_, msg_add_edge_name_vertex_with_property, this,
863 &named_graph::
864 template handle_add_edge_with_property<vertex_name_type,
865 vertex_descriptor>);
866 simple_trigger(process_group_,
867 msg_add_edge_name_vertex_with_reply_and_property, this,
868 &named_graph::template handle_add_edge_with_reply_and_property
869 <vertex_name_type, vertex_descriptor>);
870 simple_trigger(process_group_, msg_add_edge_vertex_name_with_property, this,
871 &named_graph::
872 template handle_add_edge_with_property<vertex_descriptor,
873 vertex_name_type>);
874 simple_trigger(process_group_,
875 msg_add_edge_vertex_name_with_reply_and_property, this,
876 &named_graph::template handle_add_edge_with_reply_and_property
877 <vertex_descriptor, vertex_name_type>);
878 }
879
880 /// Retrieve the vertex associated with the given name
881 template<BGL_NAMED_GRAPH_PARAMS>
882 optional<Vertex>
find_vertex(typename BGL_NAMED_GRAPH::vertex_name_type const & name,const BGL_NAMED_GRAPH & g)883 find_vertex(typename BGL_NAMED_GRAPH::vertex_name_type const& name,
884 const BGL_NAMED_GRAPH& g)
885 {
886 typedef typename Graph::local_vertex_descriptor local_vertex_descriptor;
887 typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
888
889 // Determine the owner of this name
890 typename BGL_NAMED_GRAPH::process_id_type owner
891 = g.named_distribution()(name);
892
893 if (owner == process_id(g.process_group())) {
894 // The vertex is local, so search for a mapping here
895 optional<local_vertex_descriptor> result
896 = find_vertex(name, g.derived().base());
897 if (result)
898 return Vertex(owner, *result);
899 else
900 return optional<Vertex>();
901 }
902 else {
903 // Ask the ownering process for the name of this vertex
904 boost::parallel::detail::untracked_pair<vertex_descriptor, bool> result;
905 send_oob_with_reply(g.process_group(), owner,
906 BGL_NAMED_GRAPH::msg_find_vertex, name, result);
907 if (result.second)
908 return result.first;
909 else
910 return optional<Vertex>();
911 }
912 }
913
914 /// meta-function helping in figuring out if the given VertextProerty belongs to
915 /// a named graph
916 template<typename VertexProperty>
917 struct not_is_named_graph
918 : is_same<typename internal_vertex_name<VertexProperty>::type, void>
919 {};
920
921 /// Retrieve the vertex associated with the given name
922 template<typename Graph>
923 typename Graph::named_graph_type::lazy_add_vertex
add_vertex(typename Graph::vertex_name_type const & name,Graph & g,typename disable_if<not_is_named_graph<typename Graph::vertex_property_type>,void * >::type=0)924 add_vertex(typename Graph::vertex_name_type const& name,
925 Graph& g,
926 typename disable_if<
927 not_is_named_graph<typename Graph::vertex_property_type>,
928 void*>::type = 0)
929 {
930 return typename Graph::named_graph_type::lazy_add_vertex(g, name);
931 }
932
933 /// Add an edge using vertex names to refer to the vertices
934 template<BGL_NAMED_GRAPH_PARAMS>
935 typename BGL_NAMED_GRAPH::lazy_add_edge
add_edge(typename BGL_NAMED_GRAPH::vertex_name_type const & u_name,typename BGL_NAMED_GRAPH::vertex_name_type const & v_name,BGL_NAMED_GRAPH & g)936 add_edge(typename BGL_NAMED_GRAPH::vertex_name_type const& u_name,
937 typename BGL_NAMED_GRAPH::vertex_name_type const& v_name,
938 BGL_NAMED_GRAPH& g)
939 {
940 typedef typename BGL_NAMED_GRAPH::lazy_add_edge lazy_add_edge;
941 typedef typename BGL_NAMED_GRAPH::process_id_type process_id_type;
942
943 process_id_type rank = process_id(g.process_group());
944 process_id_type u_owner = g.named_distribution()(u_name);
945 process_id_type v_owner = g.named_distribution()(v_name);
946
947 // Resolve local vertex names before building the "lazy" edge
948 // addition structure.
949 if (u_owner == rank && v_owner == rank)
950 return lazy_add_edge(g, add_vertex(u_name, g), add_vertex(v_name, g));
951 else if (u_owner == rank && v_owner != rank)
952 return lazy_add_edge(g, add_vertex(u_name, g), v_name);
953 else if (u_owner != rank && v_owner == rank)
954 return lazy_add_edge(g, u_name, add_vertex(v_name, g));
955 else
956 return lazy_add_edge(g, u_name, v_name);
957 }
958
959 template<BGL_NAMED_GRAPH_PARAMS>
960 typename BGL_NAMED_GRAPH::lazy_add_edge
add_edge(typename BGL_NAMED_GRAPH::vertex_name_type const & u_name,typename BGL_NAMED_GRAPH::vertex_descriptor const & v,BGL_NAMED_GRAPH & g)961 add_edge(typename BGL_NAMED_GRAPH::vertex_name_type const& u_name,
962 typename BGL_NAMED_GRAPH::vertex_descriptor const& v,
963 BGL_NAMED_GRAPH& g)
964 {
965 // Resolve local vertex names before building the "lazy" edge
966 // addition structure.
967 typedef typename BGL_NAMED_GRAPH::lazy_add_edge lazy_add_edge;
968 if (g.named_distribution()(u_name) == process_id(g.process_group()))
969 return lazy_add_edge(g, add_vertex(u_name, g), v);
970 else
971 return lazy_add_edge(g, u_name, v);
972 }
973
974 template<BGL_NAMED_GRAPH_PARAMS>
975 typename BGL_NAMED_GRAPH::lazy_add_edge
add_edge(typename BGL_NAMED_GRAPH::vertex_descriptor const & u,typename BGL_NAMED_GRAPH::vertex_name_type const & v_name,BGL_NAMED_GRAPH & g)976 add_edge(typename BGL_NAMED_GRAPH::vertex_descriptor const& u,
977 typename BGL_NAMED_GRAPH::vertex_name_type const& v_name,
978 BGL_NAMED_GRAPH& g)
979 {
980 // Resolve local vertex names before building the "lazy" edge
981 // addition structure.
982 typedef typename BGL_NAMED_GRAPH::lazy_add_edge lazy_add_edge;
983 if (g.named_distribution()(v_name) == process_id(g.process_group()))
984 return lazy_add_edge(g, u, add_vertex(v_name, g));
985 else
986 return lazy_add_edge(g, u, v_name);
987 }
988
989 /// Add an edge using vertex names to refer to the vertices
990 template<BGL_NAMED_GRAPH_PARAMS>
991 typename BGL_NAMED_GRAPH::lazy_add_edge_with_property
add_edge(typename BGL_NAMED_GRAPH::vertex_name_type const & u_name,typename BGL_NAMED_GRAPH::vertex_name_type const & v_name,typename Graph::edge_property_type const & property,BGL_NAMED_GRAPH & g)992 add_edge(typename BGL_NAMED_GRAPH::vertex_name_type const& u_name,
993 typename BGL_NAMED_GRAPH::vertex_name_type const& v_name,
994 typename Graph::edge_property_type const& property,
995 BGL_NAMED_GRAPH& g)
996 {
997 typedef typename BGL_NAMED_GRAPH::lazy_add_edge_with_property lazy_add_edge;
998 typedef typename BGL_NAMED_GRAPH::process_id_type process_id_type;
999
1000 process_id_type rank = process_id(g.process_group());
1001 process_id_type u_owner = g.named_distribution()(u_name);
1002 process_id_type v_owner = g.named_distribution()(v_name);
1003
1004 // Resolve local vertex names before building the "lazy" edge
1005 // addition structure.
1006 if (u_owner == rank && v_owner == rank)
1007 return lazy_add_edge(g, add_vertex(u_name, g), add_vertex(v_name, g),
1008 property);
1009 else if (u_owner == rank && v_owner != rank)
1010 return lazy_add_edge(g, add_vertex(u_name, g), v_name, property);
1011 else if (u_owner != rank && v_owner == rank)
1012 return lazy_add_edge(g, u_name, add_vertex(v_name, g), property);
1013 else
1014 return lazy_add_edge(g, u_name, v_name, property);
1015 }
1016
1017 template<BGL_NAMED_GRAPH_PARAMS>
1018 typename BGL_NAMED_GRAPH::lazy_add_edge_with_property
add_edge(typename BGL_NAMED_GRAPH::vertex_name_type const & u_name,typename BGL_NAMED_GRAPH::vertex_descriptor const & v,typename Graph::edge_property_type const & property,BGL_NAMED_GRAPH & g)1019 add_edge(typename BGL_NAMED_GRAPH::vertex_name_type const& u_name,
1020 typename BGL_NAMED_GRAPH::vertex_descriptor const& v,
1021 typename Graph::edge_property_type const& property,
1022 BGL_NAMED_GRAPH& g)
1023 {
1024 // Resolve local vertex names before building the "lazy" edge
1025 // addition structure.
1026 typedef typename BGL_NAMED_GRAPH::lazy_add_edge_with_property lazy_add_edge;
1027 if (g.named_distribution()(u_name) == process_id(g.process_group()))
1028 return lazy_add_edge(g, add_vertex(u_name, g), v, property);
1029 else
1030 return lazy_add_edge(g, u_name, v, property);
1031 }
1032
1033 template<BGL_NAMED_GRAPH_PARAMS>
1034 typename BGL_NAMED_GRAPH::lazy_add_edge_with_property
add_edge(typename BGL_NAMED_GRAPH::vertex_descriptor const & u,typename BGL_NAMED_GRAPH::vertex_name_type const & v_name,typename Graph::edge_property_type const & property,BGL_NAMED_GRAPH & g)1035 add_edge(typename BGL_NAMED_GRAPH::vertex_descriptor const& u,
1036 typename BGL_NAMED_GRAPH::vertex_name_type const& v_name,
1037 typename Graph::edge_property_type const& property,
1038 BGL_NAMED_GRAPH& g)
1039 {
1040 // Resolve local vertex names before building the "lazy" edge
1041 // addition structure.
1042 typedef typename BGL_NAMED_GRAPH::lazy_add_edge_with_property lazy_add_edge;
1043 if (g.named_distribution()(v_name) == process_id(g.process_group()))
1044 return lazy_add_edge(g, u, add_vertex(v_name, g), property);
1045 else
1046 return lazy_add_edge(g, u, v_name, property);
1047 }
1048
1049 template<BGL_NAMED_GRAPH_PARAMS>
1050 typename BGL_NAMED_GRAPH::process_id_type
owner_by_property(const vertex_property_type & property)1051 BGL_NAMED_GRAPH::owner_by_property(const vertex_property_type& property)
1052 {
1053 return distribution_(derived().base().extract_name(property));
1054 }
1055
1056
1057 /*******************************************************************
1058 * Message handlers *
1059 *******************************************************************/
1060
1061 template<BGL_NAMED_GRAPH_PARAMS>
1062 void
1063 BGL_NAMED_GRAPH::
handle_add_vertex_name(int,int,const vertex_name_type & msg,trigger_receive_context)1064 handle_add_vertex_name(int /*source*/, int /*tag*/,
1065 const vertex_name_type& msg, trigger_receive_context)
1066 {
1067 add_vertex(msg, derived());
1068 }
1069
1070 template<BGL_NAMED_GRAPH_PARAMS>
1071 typename BGL_NAMED_GRAPH::vertex_descriptor
1072 BGL_NAMED_GRAPH::
handle_add_vertex_name_with_reply(int source,int,const vertex_name_type & msg,trigger_receive_context)1073 handle_add_vertex_name_with_reply(int source, int /*tag*/,
1074 const vertex_name_type& msg,
1075 trigger_receive_context)
1076 {
1077 return add_vertex(msg, derived());
1078 }
1079
1080 template<BGL_NAMED_GRAPH_PARAMS>
1081 boost::parallel::detail::untracked_pair<typename BGL_NAMED_GRAPH::vertex_descriptor, bool>
1082 BGL_NAMED_GRAPH::
handle_find_vertex(int source,int,const vertex_name_type & msg,trigger_receive_context)1083 handle_find_vertex(int source, int /*tag*/, const vertex_name_type& msg,
1084 trigger_receive_context)
1085 {
1086 using boost::parallel::detail::make_untracked_pair;
1087
1088 optional<vertex_descriptor> v = find_vertex(msg, derived());
1089 if (v)
1090 return make_untracked_pair(*v, true);
1091 else
1092 return make_untracked_pair(graph_traits<Graph>::null_vertex(), false);
1093 }
1094
1095 template<BGL_NAMED_GRAPH_PARAMS>
1096 template<typename U, typename V>
1097 void
1098 BGL_NAMED_GRAPH::
handle_add_edge(int source,int,const boost::parallel::detail::untracked_pair<U,V> & msg,trigger_receive_context)1099 handle_add_edge(int source, int /*tag*/, const boost::parallel::detail::untracked_pair<U, V>& msg,
1100 trigger_receive_context)
1101 {
1102 add_edge(msg.first, msg.second, derived());
1103 }
1104
1105 template<BGL_NAMED_GRAPH_PARAMS>
1106 template<typename U, typename V>
1107 boost::parallel::detail::untracked_pair<typename BGL_NAMED_GRAPH::edge_descriptor, bool>
1108 BGL_NAMED_GRAPH::
handle_add_edge_with_reply(int source,int,const boost::parallel::detail::untracked_pair<U,V> & msg,trigger_receive_context)1109 handle_add_edge_with_reply(int source, int /*tag*/, const boost::parallel::detail::untracked_pair<U, V>& msg,
1110 trigger_receive_context)
1111 {
1112 std::pair<typename BGL_NAMED_GRAPH::edge_descriptor, bool> p =
1113 add_edge(msg.first, msg.second, derived());
1114 return p;
1115 }
1116
1117 template<BGL_NAMED_GRAPH_PARAMS>
1118 template<typename U, typename V>
1119 void
1120 BGL_NAMED_GRAPH::
handle_add_edge_with_property(int source,int tag,const pair_with_property<U,V,edge_property_type> & msg,trigger_receive_context)1121 handle_add_edge_with_property
1122 (int source, int tag,
1123 const pair_with_property<U, V, edge_property_type>& msg,
1124 trigger_receive_context)
1125 {
1126 add_edge(msg.first, msg.second, msg.get_property(), derived());
1127 }
1128
1129 template<BGL_NAMED_GRAPH_PARAMS>
1130 template<typename U, typename V>
1131 boost::parallel::detail::untracked_pair<typename BGL_NAMED_GRAPH::edge_descriptor, bool>
1132 BGL_NAMED_GRAPH::
handle_add_edge_with_reply_and_property(int source,int tag,const pair_with_property<U,V,edge_property_type> & msg,trigger_receive_context)1133 handle_add_edge_with_reply_and_property
1134 (int source, int tag,
1135 const pair_with_property<U, V, edge_property_type>& msg,
1136 trigger_receive_context)
1137 {
1138 std:: pair<typename BGL_NAMED_GRAPH::edge_descriptor, bool> p =
1139 add_edge(msg.first, msg.second, msg.get_property(), derived());
1140 return p;
1141 }
1142
1143 #undef BGL_NAMED_GRAPH
1144 #undef BGL_NAMED_GRAPH_PARAMS
1145
1146 /*******************************************************************
1147 * Maybe named graph mixin *
1148 *******************************************************************/
1149
1150 /**
1151 * A graph mixin that can provide a mapping from names to vertices,
1152 * and use that mapping to simplify creation and manipulation of
1153 * graphs.
1154 */
1155 template<typename Graph, typename Vertex, typename Edge, typename Config,
1156 typename ExtractName
1157 = typename internal_vertex_name<typename Config::vertex_property_type>::type>
1158 struct maybe_named_graph
1159 : public named_graph<Graph, Vertex, Edge, Config>
1160 {
1161 private:
1162 typedef named_graph<Graph, Vertex, Edge, Config> inherited;
1163 typedef typename Config::process_group_type process_group_type;
1164
1165 public:
1166 /// The type used to distribute named vertices in the graph
1167 typedef typename Config::distribution_type distribution_type;
1168 typedef typename Config::base_distribution_type base_distribution_type;
1169
maybe_named_graphboost::graph::distributed::maybe_named_graph1170 explicit maybe_named_graph(const process_group_type& pg) : inherited(pg) { }
1171
maybe_named_graphboost::graph::distributed::maybe_named_graph1172 maybe_named_graph(const process_group_type& pg,
1173 const base_distribution_type& distribution)
1174 : inherited(pg, distribution) { }
1175
distributionboost::graph::distributed::maybe_named_graph1176 distribution_type& distribution() { return this->distribution_; }
distributionboost::graph::distributed::maybe_named_graph1177 const distribution_type& distribution() const { return this->distribution_; }
1178 };
1179
1180 /**
1181 * A graph mixin that can provide a mapping from names to vertices,
1182 * and use that mapping to simplify creation and manipulation of
1183 * graphs. This partial specialization turns off this functionality
1184 * when the @c VertexProperty does not have an internal vertex name.
1185 */
1186 template<typename Graph, typename Vertex, typename Edge, typename Config>
1187 struct maybe_named_graph<Graph, Vertex, Edge, Config, void>
1188 {
1189 private:
1190 typedef typename Config::process_group_type process_group_type;
1191 typedef typename Config::vertex_property_type vertex_property_type;
1192
1193 public:
1194 typedef typename process_group_type::process_id_type process_id_type;
1195
1196 /// The type used to distribute named vertices in the graph
1197 typedef typename Config::distribution_type distribution_type;
1198 typedef typename Config::base_distribution_type base_distribution_type;
1199
maybe_named_graphboost::graph::distributed::maybe_named_graph1200 explicit maybe_named_graph(const process_group_type&) { }
1201
maybe_named_graphboost::graph::distributed::maybe_named_graph1202 maybe_named_graph(const process_group_type& pg,
1203 const base_distribution_type& distribution)
1204 : distribution_(pg, distribution) { }
1205
1206 /// Notify the named_graph that we have added the given vertex. This
1207 /// is a no-op.
added_vertexboost::graph::distributed::maybe_named_graph1208 void added_vertex(Vertex) { }
1209
1210 /// Notify the named_graph that we are removing the given
1211 /// vertex. This is a no-op.
1212 template <typename VertexIterStability>
removing_vertexboost::graph::distributed::maybe_named_graph1213 void removing_vertex(Vertex, VertexIterStability) { }
1214
1215 /// Notify the named_graph that we are clearing the graph
clearing_graphboost::graph::distributed::maybe_named_graph1216 void clearing_graph() { }
1217
1218 /// Retrieve the owner of a given vertex based on the properties
1219 /// associated with that vertex. This operation just returns the
1220 /// number of the local processor, adding all vertices locally.
owner_by_propertyboost::graph::distributed::maybe_named_graph1221 process_id_type owner_by_property(const vertex_property_type&)
1222 {
1223 return process_id(pg);
1224 }
1225
distributionboost::graph::distributed::maybe_named_graph1226 distribution_type& distribution() { return distribution_; }
distributionboost::graph::distributed::maybe_named_graph1227 const distribution_type& distribution() const { return distribution_; }
1228
1229 protected:
1230 /// The process group of the graph
1231 process_group_type pg;
1232
1233 /// The distribution used for the graph
1234 distribution_type distribution_;
1235 };
1236
1237 } } } // end namespace boost::graph::distributed
1238
1239 #endif // BOOST_GRAPH_DISTRIBUTED_NAMED_GRAPH_HPP
1240