1 // Copyright (C) 2007 Douglas Gregor
2 // Copyright (C) 2007 Hartmut Kaiser
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)
9 // - Cache (some) remote vertex names?
10 #ifndef BOOST_GRAPH_DISTRIBUTED_NAMED_GRAPH_HPP
11 #define BOOST_GRAPH_DISTRIBUTED_NAMED_GRAPH_HPP
13 #ifndef BOOST_GRAPH_USE_MPI
14 #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
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>
25 namespace boost { namespace graph { namespace distributed {
27 using boost::parallel::trigger_receive_context;
28 using boost::detail::parallel::pair_with_property;
30 /*******************************************************************
31 * Hashed distribution of named entities *
32 *******************************************************************/
35 struct hashed_distribution
37 template<typename ProcessGroup>
38 hashed_distribution(const ProcessGroup& pg, std::size_t /*num_vertices*/ = 0)
39 : n(num_processes(pg)) { }
41 int operator()(const T& value) const
43 return hasher(value) % n;
50 /// Specialization for named graphs
51 template <typename InDistribution, typename VertexProperty, typename VertexSize,
52 typename ProcessGroup,
54 = typename internal_vertex_name<VertexProperty>::type>
55 struct select_distribution
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
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.
74 typedef typename mpl::if_<is_same<InDistribution, defaultS>,
75 hashed_distribution<vertex_name_type>,
79 /// for named graphs the default type is the same as the stored distribution
81 typedef type default_type;
84 /// Specialization for non-named graphs
85 template <typename InDistribution, typename VertexProperty, typename VertexSize,
86 typename ProcessGroup>
87 struct select_distribution<InDistribution, VertexProperty, VertexSize,
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,
95 InDistribution>::type type;
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
105 /*******************************************************************
106 * Named graph mixin *
107 *******************************************************************/
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.
115 * Template parameters:
117 * Graph: the graph type that derives from named_graph
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.
122 * VertexProperty: the type of the property stored along with the
125 * ProcessGroup: the process group over which the distributed name
126 * graph mixin will communicate.
128 template<typename Graph, typename Vertex, typename Edge, typename Config>
132 /// Messages passed within the distributed named graph
135 * Requests the addition of a vertex on a remote processor. The
136 * message data is a @c vertex_name_type.
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.
146 msg_add_vertex_name_with_reply,
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.
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.
162 msg_add_edge_name_name,
163 msg_add_edge_vertex_name,
164 msg_add_edge_name_vertex,
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>
171 msg_add_edge_name_name_with_reply,
172 msg_add_edge_vertex_name_with_reply,
173 msg_add_edge_name_vertex_with_reply,
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.
183 msg_add_edge_name_name_with_property,
184 msg_add_edge_vertex_name_with_property,
185 msg_add_edge_name_vertex_with_property,
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>.
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
197 /// The vertex descriptor type
198 typedef Vertex vertex_descriptor;
200 /// The edge descriptor type
201 typedef Edge edge_descriptor;
203 /// The vertex property type
204 typedef typename Config::vertex_property_type vertex_property_type;
206 /// The vertex property type
207 typedef typename Config::edge_property_type edge_property_type;
209 /// The type used to extract names from the property structure
210 typedef typename internal_vertex_name<vertex_property_type>::type
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
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;
223 /// The type used for communication in the distributed structure
224 typedef typename Config::process_group_type process_group_type;
226 /// Type used to identify processes
227 typedef typename process_group_type::process_id_type process_id_type;
229 /// a reference to this class, which is used for disambiguation of the
230 // add_vertex function
231 typedef named_graph named_graph_type;
233 /// Structure returned when adding a vertex by vertex name
234 struct lazy_add_vertex;
235 friend struct lazy_add_vertex;
237 /// Structure returned when adding an edge by vertex name
238 struct lazy_add_edge;
239 friend struct lazy_add_edge;
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;
245 explicit named_graph(const process_group_type& pg);
247 named_graph(const process_group_type& pg, const base_distribution_type& distribution);
249 /// Set up triggers, but only for the BSP process group
250 void setup_triggers();
252 /// Retrieve the derived instance
253 Graph& derived() { return static_cast<Graph&>(*this); }
254 const Graph& derived() const { return static_cast<const Graph&>(*this); }
256 /// Retrieve the process group
257 process_group_type& process_group() { return process_group_; }
258 const process_group_type& process_group() const { return process_group_; }
260 // Retrieve the named distribution
261 distribution_type& named_distribution() { return distribution_; }
262 const distribution_type& named_distribution() const { return distribution_; }
264 /// Notify the named_graph that we have added the given vertex. This
266 void added_vertex(Vertex) { }
268 /// Notify the named_graph that we are removing the given
269 /// vertex. This is a no-op.
270 template <typename VertexIterStability>
271 void removing_vertex(Vertex, VertexIterStability) { }
273 /// Notify the named_graph that we are clearing the graph
274 void clearing_graph() { }
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&);
283 handle_add_vertex_name(int source, int tag, const vertex_name_type& msg,
284 trigger_receive_context);
287 handle_add_vertex_name_with_reply(int source, int tag,
288 const vertex_name_type& msg,
289 trigger_receive_context);
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);
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);
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);
304 template<typename U, typename V>
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);
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);
318 /// The process group for this distributed data structure
319 process_group_type process_group_;
321 /// The distribution we will use to map names to processors
322 distribution_type distribution_;
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>
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.
337 template<BGL_NAMED_GRAPH_PARAMS>
338 struct BGL_NAMED_GRAPH::lazy_add_vertex
340 /// Construct a new lazyily-added vertex
341 lazy_add_vertex(named_graph& self, const vertex_name_type& name)
342 : self(self), name(name), committed(false) { }
344 /// Transfer responsibility for adding the vertex from the source of
345 /// the copy to the newly-constructed opbject.
346 lazy_add_vertex(const lazy_add_vertex& other)
347 : self(other.self), name(other.name), committed(other.committed)
349 other.committed = true;
352 /// If the vertex has not been added yet, add it
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.
358 operator vertex_descriptor() const { return commit(); }
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;
367 vertex_name_type name;
368 mutable bool committed;
371 template<BGL_NAMED_GRAPH_PARAMS>
372 BGL_NAMED_GRAPH::lazy_add_vertex::~lazy_add_vertex()
374 typedef typename BGL_NAMED_GRAPH::process_id_type process_id_type;
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())
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());
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);
393 template<BGL_NAMED_GRAPH_PARAMS>
394 typename BGL_NAMED_GRAPH::vertex_descriptor
395 BGL_NAMED_GRAPH::lazy_add_vertex::commit() const
397 typedef typename BGL_NAMED_GRAPH::process_id_type process_id_type;
398 BOOST_ASSERT (!committed);
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),
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);
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
421 template<BGL_NAMED_GRAPH_PARAMS>
422 struct BGL_NAMED_GRAPH::lazy_add_edge
424 /// The graph's edge descriptor
425 typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
427 /// Add an edge for the edge (u, v) based on vertex names
428 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) { }
433 /// Add an edge for the edge (u, v) based on a vertex descriptor and name
434 lazy_add_edge(BGL_NAMED_GRAPH& self,
436 const vertex_name_type& v_name)
437 : self(self), u(u), v(v_name), committed(false) { }
439 /// Add an edge for the edge (u, v) based on a vertex name and descriptor
440 lazy_add_edge(BGL_NAMED_GRAPH& self,
441 const vertex_name_type& u_name,
443 : self(self), u(u_name), v(v), committed(false) { }
445 /// Add an edge for the edge (u, v) based on vertex descriptors
446 lazy_add_edge(BGL_NAMED_GRAPH& self,
449 : self(self), u(u), v(v), committed(false) { }
451 /// Copy a lazy_add_edge structure, which transfers responsibility
452 /// for adding the edge to the newly-constructed object.
453 lazy_add_edge(const lazy_add_edge& other)
454 : self(other.self), u(other.u), v(other.v), committed(other.committed)
456 other.committed = true;
459 /// If the edge has not yet been added, add the edge but don't wait
463 /// Returns commit().
464 operator std::pair<edge_descriptor, bool>() const { return commit(); }
466 // Add the edge. This operation will block if a remote edge is
468 std::pair<edge_descriptor, bool> commit() const;
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;
477 // No copy-assignment semantics
478 void operator=(lazy_add_edge&);
481 template<BGL_NAMED_GRAPH_PARAMS>
482 BGL_NAMED_GRAPH::lazy_add_edge::~lazy_add_edge()
484 using boost::parallel::detail::make_untracked_pair;
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())
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));
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));
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)));
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),
526 template<BGL_NAMED_GRAPH_PARAMS>
527 std::pair<typename graph_traits<Graph>::edge_descriptor, bool>
528 BGL_NAMED_GRAPH::lazy_add_edge::commit() const
530 typedef typename BGL_NAMED_GRAPH::process_id_type process_id_type;
531 using boost::parallel::detail::make_untracked_pair;
533 BOOST_ASSERT(!committed);
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;
540 /// The owner of the vertex "u"
541 process_id_type u_owner;
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);
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);
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)),
563 /// We have resolved the source vertex to a descriptor, which may
564 /// either be local or remote.
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());
573 /// Add the edge using vertex descriptors
574 return add_edge(boost::get<vertex_descriptor>(u),
575 boost::get<vertex_descriptor>(v),
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))
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),
588 return add_edge(boost::get<vertex_descriptor>(u),
589 boost::get<vertex_descriptor>(v),
594 // If we get here, the edge has been added remotely and "result"
595 // contains the result of that edge addition.
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
605 template<BGL_NAMED_GRAPH_PARAMS>
606 struct BGL_NAMED_GRAPH::lazy_add_edge_with_property
608 /// The graph's edge descriptor
609 typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
611 /// The Edge property type for our graph
612 typedef typename Config::edge_property_type edge_property_type;
614 /// Add an edge for the edge (u, v) based on vertex names
615 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)
623 /// Add an edge for the edge (u, v) based on a vertex descriptor and name
624 lazy_add_edge_with_property(BGL_NAMED_GRAPH& self,
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) { }
630 /// Add an edge for the edge (u, v) based on a vertex name and descriptor
631 lazy_add_edge_with_property(BGL_NAMED_GRAPH& self,
632 const vertex_name_type& u_name,
634 const edge_property_type& property)
635 : self(self), u(u_name), v(v), property(property), committed(false) { }
637 /// Add an edge for the edge (u, v) based on vertex descriptors
638 lazy_add_edge_with_property(BGL_NAMED_GRAPH& self,
641 const edge_property_type& property)
642 : self(self), u(u), v(v), property(property), committed(false) { }
644 /// Copy a lazy_add_edge_with_property structure, which transfers
645 /// responsibility for adding the edge to the newly-constructed
647 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)
651 other.committed = true;
654 /// If the edge has not yet been added, add the edge but don't wait
656 ~lazy_add_edge_with_property();
658 /// Returns commit().
659 operator std::pair<edge_descriptor, bool>() const { return commit(); }
661 // Add the edge. This operation will block if a remote edge is
663 std::pair<edge_descriptor, bool> commit() const;
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;
673 // No copy-assignment semantics
674 void operator=(lazy_add_edge_with_property&);
677 template<BGL_NAMED_GRAPH_PARAMS>
678 BGL_NAMED_GRAPH::lazy_add_edge_with_property::~lazy_add_edge_with_property()
680 using boost::detail::parallel::make_pair_with_property;
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())
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));
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,
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),
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),
725 template<BGL_NAMED_GRAPH_PARAMS>
726 std::pair<typename graph_traits<Graph>::edge_descriptor, bool>
727 BGL_NAMED_GRAPH::lazy_add_edge_with_property::commit() const
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);
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;
738 /// The owner of the vertex "u"
739 process_id_type u_owner;
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);
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))
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),
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),
765 /// We have resolved the source vertex to a descriptor, which may
766 /// either be local or remote.
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());
775 /// Add the edge using vertex descriptors
776 return add_edge(boost::get<vertex_descriptor>(u),
777 boost::get<vertex_descriptor>(v),
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))
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,
792 return add_edge(boost::get<vertex_descriptor>(u),
793 boost::get<vertex_descriptor>(v),
799 // If we get here, the edge has been added remotely and "result"
800 // contains the result of that edge addition.
804 /// Construct the named_graph with a particular process group
805 template<BGL_NAMED_GRAPH_PARAMS>
806 BGL_NAMED_GRAPH::named_graph(const process_group_type& pg)
807 : process_group_(pg, boost::parallel::attach_distributed_object()),
813 /// Construct the named_graph mixin with a particular process group
814 /// and distribution function
815 template<BGL_NAMED_GRAPH_PARAMS>
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)
824 template<BGL_NAMED_GRAPH_PARAMS>
826 BGL_NAMED_GRAPH::setup_triggers()
828 using boost::graph::parallel::simple_trigger;
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,
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,
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,
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,
856 template handle_add_edge_with_property<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,
864 template handle_add_edge_with_property<vertex_name_type,
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,
872 template handle_add_edge_with_property<vertex_descriptor,
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>);
880 /// Retrieve the vertex associated with the given name
881 template<BGL_NAMED_GRAPH_PARAMS>
883 find_vertex(typename BGL_NAMED_GRAPH::vertex_name_type const& name,
884 const BGL_NAMED_GRAPH& g)
886 typedef typename Graph::local_vertex_descriptor local_vertex_descriptor;
887 typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
889 // Determine the owner of this name
890 typename BGL_NAMED_GRAPH::process_id_type owner
891 = g.named_distribution()(name);
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());
898 return Vertex(owner, *result);
900 return optional<Vertex>();
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);
910 return optional<Vertex>();
914 /// meta-function helping in figuring out if the given VertextProerty belongs to
916 template<typename VertexProperty>
917 struct not_is_named_graph
918 : is_same<typename internal_vertex_name<VertexProperty>::type, void>
921 /// Retrieve the vertex associated with the given name
922 template<typename Graph>
923 typename Graph::named_graph_type::lazy_add_vertex
924 add_vertex(typename Graph::vertex_name_type const& name,
927 not_is_named_graph<typename Graph::vertex_property_type>,
930 return typename Graph::named_graph_type::lazy_add_vertex(g, name);
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
936 add_edge(typename BGL_NAMED_GRAPH::vertex_name_type const& u_name,
937 typename BGL_NAMED_GRAPH::vertex_name_type const& v_name,
940 typedef typename BGL_NAMED_GRAPH::lazy_add_edge lazy_add_edge;
941 typedef typename BGL_NAMED_GRAPH::process_id_type process_id_type;
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);
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));
956 return lazy_add_edge(g, u_name, v_name);
959 template<BGL_NAMED_GRAPH_PARAMS>
960 typename BGL_NAMED_GRAPH::lazy_add_edge
961 add_edge(typename BGL_NAMED_GRAPH::vertex_name_type const& u_name,
962 typename BGL_NAMED_GRAPH::vertex_descriptor const& v,
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);
971 return lazy_add_edge(g, u_name, v);
974 template<BGL_NAMED_GRAPH_PARAMS>
975 typename BGL_NAMED_GRAPH::lazy_add_edge
976 add_edge(typename BGL_NAMED_GRAPH::vertex_descriptor const& u,
977 typename BGL_NAMED_GRAPH::vertex_name_type const& v_name,
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));
986 return lazy_add_edge(g, u, v_name);
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
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,
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;
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);
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),
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);
1014 return lazy_add_edge(g, u_name, v_name, property);
1017 template<BGL_NAMED_GRAPH_PARAMS>
1018 typename BGL_NAMED_GRAPH::lazy_add_edge_with_property
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,
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);
1030 return lazy_add_edge(g, u_name, v, property);
1033 template<BGL_NAMED_GRAPH_PARAMS>
1034 typename BGL_NAMED_GRAPH::lazy_add_edge_with_property
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,
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);
1046 return lazy_add_edge(g, u, v_name, property);
1049 template<BGL_NAMED_GRAPH_PARAMS>
1050 typename BGL_NAMED_GRAPH::process_id_type
1051 BGL_NAMED_GRAPH::owner_by_property(const vertex_property_type& property)
1053 return distribution_(derived().base().extract_name(property));
1057 /*******************************************************************
1058 * Message handlers *
1059 *******************************************************************/
1061 template<BGL_NAMED_GRAPH_PARAMS>
1064 handle_add_vertex_name(int /*source*/, int /*tag*/,
1065 const vertex_name_type& msg, trigger_receive_context)
1067 add_vertex(msg, derived());
1070 template<BGL_NAMED_GRAPH_PARAMS>
1071 typename BGL_NAMED_GRAPH::vertex_descriptor
1073 handle_add_vertex_name_with_reply(int source, int /*tag*/,
1074 const vertex_name_type& msg,
1075 trigger_receive_context)
1077 return add_vertex(msg, derived());
1080 template<BGL_NAMED_GRAPH_PARAMS>
1081 boost::parallel::detail::untracked_pair<typename BGL_NAMED_GRAPH::vertex_descriptor, bool>
1083 handle_find_vertex(int source, int /*tag*/, const vertex_name_type& msg,
1084 trigger_receive_context)
1086 using boost::parallel::detail::make_untracked_pair;
1088 optional<vertex_descriptor> v = find_vertex(msg, derived());
1090 return make_untracked_pair(*v, true);
1092 return make_untracked_pair(graph_traits<Graph>::null_vertex(), false);
1095 template<BGL_NAMED_GRAPH_PARAMS>
1096 template<typename U, typename V>
1099 handle_add_edge(int source, int /*tag*/, const boost::parallel::detail::untracked_pair<U, V>& msg,
1100 trigger_receive_context)
1102 add_edge(msg.first, msg.second, derived());
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>
1109 handle_add_edge_with_reply(int source, int /*tag*/, const boost::parallel::detail::untracked_pair<U, V>& msg,
1110 trigger_receive_context)
1112 std::pair<typename BGL_NAMED_GRAPH::edge_descriptor, bool> p =
1113 add_edge(msg.first, msg.second, derived());
1117 template<BGL_NAMED_GRAPH_PARAMS>
1118 template<typename U, typename V>
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)
1126 add_edge(msg.first, msg.second, msg.get_property(), derived());
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>
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)
1138 std:: pair<typename BGL_NAMED_GRAPH::edge_descriptor, bool> p =
1139 add_edge(msg.first, msg.second, msg.get_property(), derived());
1143 #undef BGL_NAMED_GRAPH
1144 #undef BGL_NAMED_GRAPH_PARAMS
1146 /*******************************************************************
1147 * Maybe named graph mixin *
1148 *******************************************************************/
1151 * A graph mixin that can provide a mapping from names to vertices,
1152 * and use that mapping to simplify creation and manipulation of
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>
1162 typedef named_graph<Graph, Vertex, Edge, Config> inherited;
1163 typedef typename Config::process_group_type process_group_type;
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;
1170 explicit maybe_named_graph(const process_group_type& pg) : inherited(pg) { }
1172 maybe_named_graph(const process_group_type& pg,
1173 const base_distribution_type& distribution)
1174 : inherited(pg, distribution) { }
1176 distribution_type& distribution() { return this->distribution_; }
1177 const distribution_type& distribution() const { return this->distribution_; }
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.
1186 template<typename Graph, typename Vertex, typename Edge, typename Config>
1187 struct maybe_named_graph<Graph, Vertex, Edge, Config, void>
1190 typedef typename Config::process_group_type process_group_type;
1191 typedef typename Config::vertex_property_type vertex_property_type;
1194 typedef typename process_group_type::process_id_type process_id_type;
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;
1200 explicit maybe_named_graph(const process_group_type&) { }
1202 maybe_named_graph(const process_group_type& pg,
1203 const base_distribution_type& distribution)
1204 : distribution_(pg, distribution) { }
1206 /// Notify the named_graph that we have added the given vertex. This
1208 void added_vertex(Vertex) { }
1210 /// Notify the named_graph that we are removing the given
1211 /// vertex. This is a no-op.
1212 template <typename VertexIterStability>
1213 void removing_vertex(Vertex, VertexIterStability) { }
1215 /// Notify the named_graph that we are clearing the graph
1216 void clearing_graph() { }
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.
1221 process_id_type owner_by_property(const vertex_property_type&)
1223 return process_id(pg);
1226 distribution_type& distribution() { return distribution_; }
1227 const distribution_type& distribution() const { return distribution_; }
1230 /// The process group of the graph
1231 process_group_type pg;
1233 /// The distribution used for the graph
1234 distribution_type distribution_;
1237 } } } // end namespace boost::graph::distributed
1239 #endif // BOOST_GRAPH_DISTRIBUTED_NAMED_GRAPH_HPP