graph/distributed/named_graph.hpp

0001 // Copyright (C) 2007 Douglas Gregor
0002 // Copyright (C) 2007 Hartmut Kaiser
0003
0004 // Use, modification and distribution is subject to the Boost Software
0005 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0006 // http://www.boost.org/LICENSE_1_0.txt)
0007
0008 // TODO:
0009 //   - Cache (some) remote vertex names?
0010 #ifndef BOOST_GRAPH_DISTRIBUTED_NAMED_GRAPH_HPP
0011 #define BOOST_GRAPH_DISTRIBUTED_NAMED_GRAPH_HPP
0012
0013 #ifndef BOOST_GRAPH_USE_MPI
0014 #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
0015 #endif
0016
0017 #include <boost/assert.hpp>
0018 #include <boost/core/uncaught_exceptions.hpp>
0019 #include <boost/graph/named_graph.hpp>
0020 #include <boost/functional/hash.hpp>
0021 #include <boost/variant.hpp>
0022 #include <boost/graph/parallel/simple_trigger.hpp>
0023 #include <boost/graph/parallel/process_group.hpp>
0024 #include <boost/graph/parallel/detail/property_holders.hpp>
0025
0026 namespace boost { namespace graph { namespace distributed {
0027
0028 using boost::parallel::trigger_receive_context;
0029 using boost::detail::parallel::pair_with_property;
0030
0031 /*******************************************************************
0032  * Hashed distribution of named entities                           *
0033  *******************************************************************/
0034
0035 template<typename T>
0036 struct hashed_distribution
0037 {
0038   template<typename ProcessGroup>
0039   hashed_distribution(const ProcessGroup& pg, std::size_t /*num_vertices*/ = 0)
0040     : n(num_processes(pg)) { }
0041
0042   int operator()(const T& value) const
0043   {
0044     return hasher(value) % n;
0045   }
0046
0047   std::size_t n;
0048   hash<T> hasher;
0049 };
0050
0051 /// Specialization for named graphs
0052 template <typename InDistribution, typename VertexProperty, typename VertexSize,
0053           typename ProcessGroup,
0054           typename ExtractName
0055             = typename internal_vertex_name<VertexProperty>::type>
0056 struct select_distribution
0057 {
0058 private:
0059   /// The type used to name vertices in the graph
0060   typedef typename remove_cv<
0061             typename remove_reference<
0062               typename ExtractName::result_type>::type>::type
0063     vertex_name_type;
0064
0065 public:
0066   /**
0067    *  The @c type field provides a distribution object that maps
0068    *  vertex names to processors. The distribution object will be
0069    *  constructed with the process group over which communication will
0070    *  occur. The distribution object shall also be a function
0071    *  object mapping from the type of the name to a processor number
0072    *  in @c [0, @c p) (for @c p processors). By default, the mapping
0073    *  function uses the @c boost::hash value of the name, modulo @c p.
0074    */
0075   typedef typename mpl::if_<is_same<InDistribution, defaultS>,
0076                             hashed_distribution<vertex_name_type>,
0077                             InDistribution>::type
0078     type;
0079
0080   /// for named graphs the default type is the same as the stored distribution
0081   /// type
0082   typedef type default_type;
0083 };
0084
0085 /// Specialization for non-named graphs
0086 template <typename InDistribution, typename VertexProperty, typename VertexSize,
0087           typename ProcessGroup>
0088 struct select_distribution<InDistribution, VertexProperty, VertexSize,
0089                            ProcessGroup, void>
0090 {
0091   /// the distribution type stored in the graph for non-named graphs should be
0092   /// the variant_distribution type
0093   typedef typename mpl::if_<is_same<InDistribution, defaultS>,
0094                             boost::parallel::variant_distribution<ProcessGroup,
0095                                                                   VertexSize>,
0096                             InDistribution>::type type;
0097
0098   /// default_type is used as the distribution functor for the
0099   /// adjacency_list, it should be parallel::block by default
0100   typedef typename mpl::if_<is_same<InDistribution, defaultS>,
0101                             boost::parallel::block, type>::type
0102     default_type;
0103 };
0104
0105
0106 /*******************************************************************
0107  * Named graph mixin                                               *
0108  *******************************************************************/
0109
0110 /**
0111  * named_graph is a mixin that provides names for the vertices of a
0112  * graph, including a mapping from names to vertices. Graph types that
0113  * may or may not be have vertex names (depending on the properties
0114  * supplied by the user) should use maybe_named_graph.
0115  *
0116  * Template parameters:
0117  *
0118  *   Graph: the graph type that derives from named_graph
0119  *
0120  *   Vertex: the type of a vertex descriptor in Graph. Note: we cannot
0121  *   use graph_traits here, because the Graph is not yet defined.
0122  *
0123  *   VertexProperty: the type of the property stored along with the
0124  *   vertex.
0125  *
0126  *   ProcessGroup: the process group over which the distributed name
0127  *   graph mixin will communicate.
0128  */
0129 template<typename Graph, typename Vertex, typename Edge, typename Config>
0130 class named_graph
0131 {
0132 public:
0133   /// Messages passed within the distributed named graph
0134   enum message_kind {
0135     /**
0136      * Requests the addition of a vertex on a remote processor. The
0137      * message data is a @c vertex_name_type.
0138      */
0139     msg_add_vertex_name,
0140
0141     /**
0142      * Requests the addition of a vertex on a remote processor. The
0143      * message data is a @c vertex_name_type. The remote processor
0144      * will send back a @c msg_add_vertex_name_reply message
0145      * containing the vertex descriptor.
0146      */
0147     msg_add_vertex_name_with_reply,
0148
0149     /**
0150      * Requests the vertex descriptor corresponding to the given
0151      * vertex name. The remote process will reply with a
0152      * @c msg_find_vertex_reply message containing the answer.
0153      */
0154     msg_find_vertex,
0155
0156     /**
0157      * Requests the addition of an edge on a remote processor. The
0158      * data stored in these messages is a @c pair<source, target>@,
0159      * where @c source and @c target may be either names (of type @c
0160      * vertex_name_type) or vertex descriptors, depending on what
0161      * information we have locally.
0162      */
0163     msg_add_edge_name_name,
0164     msg_add_edge_vertex_name,
0165     msg_add_edge_name_vertex,
0166
0167     /**
0168      * These messages are identical to msg_add_edge_*_*, except that
0169      * the process actually adding the edge will send back a @c
0170      * pair<edge_descriptor,bool>
0171      */
0172     msg_add_edge_name_name_with_reply,
0173     msg_add_edge_vertex_name_with_reply,
0174     msg_add_edge_name_vertex_with_reply,
0175
0176     /**
0177      * Requests the addition of an edge with a property on a remote
0178      * processor. The data stored in these messages is a @c
0179      * pair<vertex_property_type, pair<source, target>>@, where @c
0180      * source and @c target may be either names (of type @c
0181      * vertex_name_type) or vertex descriptors, depending on what
0182      * information we have locally.
0183      */
0184     msg_add_edge_name_name_with_property,
0185     msg_add_edge_vertex_name_with_property,
0186     msg_add_edge_name_vertex_with_property,
0187
0188     /**
0189      * These messages are identical to msg_add_edge_*_*_with_property,
0190      * except that the process actually adding the edge will send back
0191      * a @c pair<edge_descriptor,bool>.
0192      */
0193     msg_add_edge_name_name_with_reply_and_property,
0194     msg_add_edge_vertex_name_with_reply_and_property,
0195     msg_add_edge_name_vertex_with_reply_and_property
0196   };
0197
0198   /// The vertex descriptor type
0199   typedef Vertex vertex_descriptor;
0200
0201   /// The edge descriptor type
0202   typedef Edge edge_descriptor;
0203
0204   /// The vertex property type
0205   typedef typename Config::vertex_property_type vertex_property_type;
0206
0207   /// The vertex property type
0208   typedef typename Config::edge_property_type edge_property_type;
0209
0210   /// The type used to extract names from the property structure
0211   typedef typename internal_vertex_name<vertex_property_type>::type
0212     extract_name_type;
0213
0214   /// The type used to name vertices in the graph
0215   typedef typename remove_cv<
0216             typename remove_reference<
0217               typename extract_name_type::result_type>::type>::type
0218     vertex_name_type;
0219
0220   /// The type used to distribute named vertices in the graph
0221   typedef typename Config::distribution_type distribution_type;
0222   typedef typename Config::base_distribution_type base_distribution_type;
0223
0224   /// The type used for communication in the distributed structure
0225   typedef typename Config::process_group_type process_group_type;
0226
0227   /// Type used to identify processes
0228   typedef typename process_group_type::process_id_type process_id_type;
0229
0230   /// a reference to this class, which is used for disambiguation of the
0231   //  add_vertex function
0232   typedef named_graph named_graph_type;
0233
0234   /// Structure returned when adding a vertex by vertex name
0235   struct lazy_add_vertex;
0236   friend struct lazy_add_vertex;
0237
0238   /// Structure returned when adding an edge by vertex name
0239   struct lazy_add_edge;
0240   friend struct lazy_add_edge;
0241
0242   /// Structure returned when adding an edge by vertex name with a property
0243   struct lazy_add_edge_with_property;
0244   friend struct lazy_add_edge_with_property;
0245
0246   explicit named_graph(const process_group_type& pg);
0247
0248   named_graph(const process_group_type& pg, const base_distribution_type& distribution);
0249
0250   /// Set up triggers, but only for the BSP process group
0251   void setup_triggers();
0252
0253   /// Retrieve the derived instance
0254   Graph&       derived()       { return static_cast<Graph&>(*this); }
0255   const Graph& derived() const { return static_cast<const Graph&>(*this); }
0256
0257   /// Retrieve the process group
0258   process_group_type&       process_group()       { return process_group_; }
0259   const process_group_type& process_group() const { return process_group_; }
0260
0261   // Retrieve the named distribution
0262   distribution_type&       named_distribution()       { return distribution_; }
0263   const distribution_type& named_distribution() const { return distribution_; }
0264
0265   /// Notify the named_graph that we have added the given vertex. This
0266   /// is a no-op.
0267   void added_vertex(Vertex) { }
0268
0269   /// Notify the named_graph that we are removing the given
0270   /// vertex. This is a no-op.
0271   template <typename VertexIterStability>
0272   void removing_vertex(Vertex, VertexIterStability) { }
0273
0274   /// Notify the named_graph that we are clearing the graph
0275   void clearing_graph() { }
0276
0277   /// Retrieve the owner of a given vertex based on the properties
0278   /// associated with that vertex. This operation just returns the
0279   /// number of the local processor, adding all vertices locally.
0280   process_id_type owner_by_property(const vertex_property_type&);
0281
0282 protected:
0283   void
0284   handle_add_vertex_name(int source, int tag, const vertex_name_type& msg,
0285                          trigger_receive_context);
0286
0287   vertex_descriptor
0288   handle_add_vertex_name_with_reply(int source, int tag,
0289                                     const vertex_name_type& msg,
0290                                     trigger_receive_context);
0291
0292   boost::parallel::detail::untracked_pair<vertex_descriptor, bool>
0293   handle_find_vertex(int source, int tag, const vertex_name_type& msg,
0294                      trigger_receive_context);
0295
0296   template<typename U, typename V>
0297   void handle_add_edge(int source, int tag, const boost::parallel::detail::untracked_pair<U, V>& msg,
0298                        trigger_receive_context);
0299
0300   template<typename U, typename V>
0301   boost::parallel::detail::untracked_pair<edge_descriptor, bool>
0302   handle_add_edge_with_reply(int source, int tag, const boost::parallel::detail::untracked_pair<U, V>& msg,
0303                              trigger_receive_context);
0304
0305   template<typename U, typename V>
0306   void
0307   handle_add_edge_with_property
0308     (int source, int tag,
0309      const pair_with_property<U, V, edge_property_type>& msg,
0310      trigger_receive_context);
0311
0312   template<typename U, typename V>
0313   boost::parallel::detail::untracked_pair<edge_descriptor, bool>
0314   handle_add_edge_with_reply_and_property
0315     (int source, int tag,
0316      const pair_with_property<U, V, edge_property_type>& msg,
0317      trigger_receive_context);
0318
0319   /// The process group for this distributed data structure
0320   process_group_type process_group_;
0321
0322   /// The distribution we will use to map names to processors
0323   distribution_type distribution_;
0324 };
0325
0326 /// Helper macro containing the template parameters of named_graph
0327 #define BGL_NAMED_GRAPH_PARAMS \
0328   typename Graph, typename Vertex, typename Edge, typename Config
0329 /// Helper macro containing the named_graph<...> instantiation
0330 #define BGL_NAMED_GRAPH \
0331   named_graph<Graph, Vertex, Edge, Config>
0332
0333 /**
0334  * Data structure returned from add_vertex that will "lazily" add the
0335  * vertex, either when it is converted to a @c vertex_descriptor or
0336  * when the most recent copy has been destroyed.
0337  */
0338 template<BGL_NAMED_GRAPH_PARAMS>
0339 struct BGL_NAMED_GRAPH::lazy_add_vertex
0340 {
0341   /// Construct a new lazyily-added vertex
0342   lazy_add_vertex(named_graph& self, const vertex_name_type& name)
0343     : self(self), name(name), committed(false) { }
0344
0345   /// Transfer responsibility for adding the vertex from the source of
0346   /// the copy to the newly-constructed opbject.
0347   lazy_add_vertex(const lazy_add_vertex& other)
0348     : self(other.self), name(other.name), committed(other.committed)
0349   {
0350     other.committed = true;
0351   }
0352
0353   /// If the vertex has not been added yet, add it
0354   ~lazy_add_vertex();
0355
0356   /// Add the vertex and return its descriptor. This conversion can
0357   /// only occur once, and only when this object is responsible for
0358   /// creating the vertex.
0359   operator vertex_descriptor() const { return commit(); }
0360
0361   /// Add the vertex and return its descriptor. This can only be
0362   /// called once, and only when this object is responsible for
0363   /// creating the vertex.
0364   vertex_descriptor commit() const;
0365
0366 protected:
0367   named_graph&     self;
0368   vertex_name_type name;
0369   mutable bool     committed;
0370 };
0371
0372 template<BGL_NAMED_GRAPH_PARAMS>
0373 BGL_NAMED_GRAPH::lazy_add_vertex::~lazy_add_vertex()
0374 {
0375   typedef typename BGL_NAMED_GRAPH::process_id_type process_id_type;
0376
0377   /// If this vertex has already been created or will be created by
0378   /// someone else, or if someone threw an exception, we will not
0379   /// create the vertex now.
0380   if (committed || boost::core::uncaught_exceptions() > 0)
0381     return;
0382
0383   committed = true;
0384
0385   process_id_type owner = self.named_distribution()(name);
0386   if (owner == process_id(self.process_group()))
0387     /// Add the vertex locally
0388     add_vertex(self.derived().base().vertex_constructor(name), self.derived());
0389   else
0390     /// Ask the owner of the vertex to add a vertex with this name
0391     send(self.process_group(), owner, msg_add_vertex_name, name);
0392 }
0393
0394 template<BGL_NAMED_GRAPH_PARAMS>
0395 typename BGL_NAMED_GRAPH::vertex_descriptor
0396 BGL_NAMED_GRAPH::lazy_add_vertex::commit() const
0397 {
0398   typedef typename BGL_NAMED_GRAPH::process_id_type process_id_type;
0399   BOOST_ASSERT (!committed);
0400   committed = true;
0401
0402   process_id_type owner = self.named_distribution()(name);
0403   if (owner == process_id(self.process_group()))
0404     /// Add the vertex locally
0405     return add_vertex(self.derived().base().vertex_constructor(name),
0406                       self.derived());
0407   else {
0408     /// Ask the owner of the vertex to add a vertex with this name
0409     vertex_descriptor result;
0410     send_oob_with_reply(self.process_group(), owner,
0411                         msg_add_vertex_name_with_reply, name, result);
0412     return result;
0413   }
0414 }
0415
0416 /**
0417  * Data structure returned from add_edge that will "lazily" add the
0418  * edge, either when it is converted to a @c
0419  * pair<edge_descriptor,bool> or when the most recent copy has been
0420  * destroyed.
0421  */
0422 template<BGL_NAMED_GRAPH_PARAMS>
0423 struct BGL_NAMED_GRAPH::lazy_add_edge
0424 {
0425   /// The graph's edge descriptor
0426   typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
0427
0428   /// Add an edge for the edge (u, v) based on vertex names
0429   lazy_add_edge(BGL_NAMED_GRAPH& self,
0430                 const vertex_name_type& u_name,
0431                 const vertex_name_type& v_name)
0432     : self(self), u(u_name), v(v_name), committed(false) { }
0433
0434   /// Add an edge for the edge (u, v) based on a vertex descriptor and name
0435   lazy_add_edge(BGL_NAMED_GRAPH& self,
0436                 vertex_descriptor u,
0437                 const vertex_name_type& v_name)
0438     : self(self), u(u), v(v_name), committed(false) { }
0439
0440   /// Add an edge for the edge (u, v) based on a vertex name and descriptor
0441   lazy_add_edge(BGL_NAMED_GRAPH& self,
0442                 const vertex_name_type& u_name,
0443                 vertex_descriptor v)
0444     : self(self), u(u_name), v(v), committed(false) { }
0445
0446   /// Add an edge for the edge (u, v) based on vertex descriptors
0447   lazy_add_edge(BGL_NAMED_GRAPH& self,
0448                 vertex_descriptor u,
0449                 vertex_descriptor v)
0450     : self(self), u(u), v(v), committed(false) { }
0451
0452   /// Copy a lazy_add_edge structure, which transfers responsibility
0453   /// for adding the edge to the newly-constructed object.
0454   lazy_add_edge(const lazy_add_edge& other)
0455     : self(other.self), u(other.u), v(other.v), committed(other.committed)
0456   {
0457     other.committed = true;
0458   }
0459
0460   /// If the edge has not yet been added, add the edge but don't wait
0461   /// for a reply.
0462   ~lazy_add_edge();
0463
0464   /// Returns commit().
0465   operator std::pair<edge_descriptor, bool>() const { return commit(); }
0466
0467   // Add the edge. This operation will block if a remote edge is
0468   // being added.
0469   std::pair<edge_descriptor, bool> commit() const;
0470
0471 protected:
0472   BGL_NAMED_GRAPH& self;
0473   mutable variant<vertex_descriptor, vertex_name_type> u;
0474   mutable variant<vertex_descriptor, vertex_name_type> v;
0475   mutable bool committed;
0476
0477 private:
0478   // No copy-assignment semantics
0479   void operator=(lazy_add_edge&);
0480 };
0481
0482 template<BGL_NAMED_GRAPH_PARAMS>
0483 BGL_NAMED_GRAPH::lazy_add_edge::~lazy_add_edge()
0484 {
0485   using boost::parallel::detail::make_untracked_pair;
0486
0487   /// If this edge has already been created or will be created by
0488   /// someone else, or if someone threw an exception, we will not
0489   /// create the edge now.
0490   if (committed || boost::core::uncaught_exceptions() > 0)
0491     return;
0492
0493   committed = true;
0494
0495   if (vertex_name_type* v_name = boost::get<vertex_name_type>(&v)) {
0496     // We haven't resolved the target vertex to a descriptor yet, so
0497     // it must not be local. Send a message to the owner of the target
0498     // of the edge. If the owner of the target does not happen to own
0499     // the source, it will resolve the target to a vertex descriptor
0500     // and pass the message along to the owner of the source.
0501     if (vertex_name_type* u_name = boost::get<vertex_name_type>(&u))
0502       send(self.process_group(), self.distribution_(*v_name),
0503            BGL_NAMED_GRAPH::msg_add_edge_name_name,
0504            make_untracked_pair(*u_name, *v_name));
0505     else
0506       send(self.process_group(), self.distribution_(*v_name),
0507            BGL_NAMED_GRAPH::msg_add_edge_vertex_name,
0508            make_untracked_pair(boost::get<vertex_descriptor>(u), *v_name));
0509   } else {
0510     if (vertex_name_type* u_name = boost::get<vertex_name_type>(&u))
0511       // We haven't resolved the source vertex to a descriptor yet, so
0512       // it must not be local. Send a message to the owner of the
0513       // source vertex requesting the edge addition.
0514       send(self.process_group(), self.distribution_(*u_name),
0515            BGL_NAMED_GRAPH::msg_add_edge_name_vertex,
0516            make_untracked_pair(*u_name, boost::get<vertex_descriptor>(v)));
0517     else
0518       // We have descriptors for both of the vertices, either of which
0519       // may be remote or local. Tell the owner of the source vertex
0520       // to add the edge (it may be us!).
0521       add_edge(boost::get<vertex_descriptor>(u),
0522                boost::get<vertex_descriptor>(v),
0523                self.derived());
0524   }
0525 }
0526
0527 template<BGL_NAMED_GRAPH_PARAMS>
0528 std::pair<typename graph_traits<Graph>::edge_descriptor, bool>
0529 BGL_NAMED_GRAPH::lazy_add_edge::commit() const
0530 {
0531   typedef typename BGL_NAMED_GRAPH::process_id_type process_id_type;
0532   using boost::parallel::detail::make_untracked_pair;
0533
0534   BOOST_ASSERT(!committed);
0535   committed = true;
0536
0537   /// The result we will return, if we are sending a message to
0538   /// request that someone else add the edge.
0539   boost::parallel::detail::untracked_pair<edge_descriptor, bool> result;
0540
0541   /// The owner of the vertex "u"
0542   process_id_type u_owner;
0543
0544   process_id_type rank = process_id(self.process_group());
0545   if (const vertex_name_type* u_name = boost::get<vertex_name_type>(&u)) {
0546     /// We haven't resolved the source vertex to a descriptor yet, so
0547     /// it must not be local.
0548     u_owner = self.named_distribution()(*u_name);
0549
0550     /// Send a message to the remote vertex requesting that it add the
0551     /// edge. The message differs depending on whether we have a
0552     /// vertex name or a vertex descriptor for the target.
0553     if (const vertex_name_type* v_name = boost::get<vertex_name_type>(&v))
0554       send_oob_with_reply(self.process_group(), u_owner,
0555                           BGL_NAMED_GRAPH::msg_add_edge_name_name_with_reply,
0556                           make_untracked_pair(*u_name, *v_name), result);
0557     else
0558       send_oob_with_reply(self.process_group(), u_owner,
0559                           BGL_NAMED_GRAPH::msg_add_edge_name_vertex_with_reply,
0560                           make_untracked_pair(*u_name,
0561                                          boost::get<vertex_descriptor>(v)),
0562                           result);
0563   } else {
0564     /// We have resolved the source vertex to a descriptor, which may
0565     /// either be local or remote.
0566     u_owner
0567       = get(vertex_owner, self.derived(),
0568             boost::get<vertex_descriptor>(u));
0569     if (u_owner == rank) {
0570       /// The source is local. If we need to, resolve the target vertex.
0571       if (const vertex_name_type* v_name = boost::get<vertex_name_type>(&v))
0572         v = add_vertex(*v_name, self.derived());
0573
0574       /// Add the edge using vertex descriptors
0575       return add_edge(boost::get<vertex_descriptor>(u),
0576                       boost::get<vertex_descriptor>(v),
0577                       self.derived());
0578     } else {
0579       /// The source is remote. Just send a message to its owner
0580       /// requesting that the owner add the new edge, either directly
0581       /// or via the derived class's add_edge function.
0582       if (const vertex_name_type* v_name = boost::get<vertex_name_type>(&v))
0583         send_oob_with_reply
0584           (self.process_group(), u_owner,
0585            BGL_NAMED_GRAPH::msg_add_edge_vertex_name_with_reply,
0586            make_untracked_pair(boost::get<vertex_descriptor>(u), *v_name),
0587            result);
0588       else
0589         return add_edge(boost::get<vertex_descriptor>(u),
0590                         boost::get<vertex_descriptor>(v),
0591                         self.derived());
0592     }
0593   }
0594
0595   // If we get here, the edge has been added remotely and "result"
0596   // contains the result of that edge addition.
0597   return result;
0598 }
0599
0600 /**
0601  * Data structure returned from add_edge that will "lazily" add the
0602  * edge with a property, either when it is converted to a @c
0603  * pair<edge_descriptor,bool> or when the most recent copy has been
0604  * destroyed.
0605  */
0606 template<BGL_NAMED_GRAPH_PARAMS>
0607 struct BGL_NAMED_GRAPH::lazy_add_edge_with_property
0608 {
0609   /// The graph's edge descriptor
0610   typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
0611
0612   /// The Edge property type for our graph
0613   typedef typename Config::edge_property_type edge_property_type;
0614
0615   /// Add an edge for the edge (u, v) based on vertex names
0616   lazy_add_edge_with_property(BGL_NAMED_GRAPH& self,
0617                               const vertex_name_type& u_name,
0618                               const vertex_name_type& v_name,
0619                               const edge_property_type& property)
0620     : self(self), u(u_name), v(v_name), property(property), committed(false)
0621   {
0622   }
0623
0624   /// Add an edge for the edge (u, v) based on a vertex descriptor and name
0625   lazy_add_edge_with_property(BGL_NAMED_GRAPH& self,
0626                 vertex_descriptor u,
0627                 const vertex_name_type& v_name,
0628                                   const edge_property_type& property)
0629     : self(self), u(u), v(v_name), property(property), committed(false) { }
0630
0631   /// Add an edge for the edge (u, v) based on a vertex name and descriptor
0632   lazy_add_edge_with_property(BGL_NAMED_GRAPH& self,
0633                               const vertex_name_type& u_name,
0634                               vertex_descriptor v,
0635                               const edge_property_type& property)
0636     : self(self), u(u_name), v(v), property(property), committed(false) { }
0637
0638   /// Add an edge for the edge (u, v) based on vertex descriptors
0639   lazy_add_edge_with_property(BGL_NAMED_GRAPH& self,
0640                               vertex_descriptor u,
0641                               vertex_descriptor v,
0642                               const edge_property_type& property)
0643     : self(self), u(u), v(v), property(property), committed(false) { }
0644
0645   /// Copy a lazy_add_edge_with_property structure, which transfers
0646   /// responsibility for adding the edge to the newly-constructed
0647   /// object.
0648   lazy_add_edge_with_property(const lazy_add_edge_with_property& other)
0649     : self(other.self), u(other.u), v(other.v), property(other.property),
0650       committed(other.committed)
0651   {
0652     other.committed = true;
0653   }
0654
0655   /// If the edge has not yet been added, add the edge but don't wait
0656   /// for a reply.
0657   ~lazy_add_edge_with_property();
0658
0659   /// Returns commit().
0660   operator std::pair<edge_descriptor, bool>() const { return commit(); }
0661
0662   // Add the edge. This operation will block if a remote edge is
0663   // being added.
0664   std::pair<edge_descriptor, bool> commit() const;
0665
0666 protected:
0667   BGL_NAMED_GRAPH& self;
0668   mutable variant<vertex_descriptor, vertex_name_type> u;
0669   mutable variant<vertex_descriptor, vertex_name_type> v;
0670   edge_property_type property;
0671   mutable bool committed;
0672
0673 private:
0674   // No copy-assignment semantics
0675   void operator=(lazy_add_edge_with_property&);
0676 };
0677
0678 template<BGL_NAMED_GRAPH_PARAMS>
0679 BGL_NAMED_GRAPH::lazy_add_edge_with_property::~lazy_add_edge_with_property()
0680 {
0681   using boost::detail::parallel::make_pair_with_property;
0682
0683   /// If this edge has already been created or will be created by
0684   /// someone else, or if someone threw an exception, we will not
0685   /// create the edge now.
0686   if (committed || boost::core::uncaught_exceptions() > 0)
0687     return;
0688
0689   committed = true;
0690
0691   if (vertex_name_type* v_name = boost::get<vertex_name_type>(&v)) {
0692     // We haven't resolved the target vertex to a descriptor yet, so
0693     // it must not be local. Send a message to the owner of the target
0694     // of the edge. If the owner of the target does not happen to own
0695     // the source, it will resolve the target to a vertex descriptor
0696     // and pass the message along to the owner of the source.
0697     if (vertex_name_type* u_name = boost::get<vertex_name_type>(&u))
0698       send(self.process_group(), self.distribution_(*v_name),
0699            BGL_NAMED_GRAPH::msg_add_edge_name_name_with_property,
0700            make_pair_with_property(*u_name, *v_name, property));
0701     else
0702       send(self.process_group(), self.distribution_(*v_name),
0703            BGL_NAMED_GRAPH::msg_add_edge_vertex_name_with_property,
0704            make_pair_with_property(boost::get<vertex_descriptor>(u), *v_name,
0705                                    property));
0706   } else {
0707     if (vertex_name_type* u_name = boost::get<vertex_name_type>(&u))
0708       // We haven't resolved the source vertex to a descriptor yet, so
0709       // it must not be local. Send a message to the owner of the
0710       // source vertex requesting the edge addition.
0711       send(self.process_group(), self.distribution_(*u_name),
0712            BGL_NAMED_GRAPH::msg_add_edge_name_vertex_with_property,
0713            make_pair_with_property(*u_name, boost::get<vertex_descriptor>(v),
0714                                    property));
0715     else
0716       // We have descriptors for both of the vertices, either of which
0717       // may be remote or local. Tell the owner of the source vertex
0718       // to add the edge (it may be us!).
0719       add_edge(boost::get<vertex_descriptor>(u),
0720                boost::get<vertex_descriptor>(v),
0721                property,
0722                self.derived());
0723   }
0724 }
0725
0726 template<BGL_NAMED_GRAPH_PARAMS>
0727 std::pair<typename graph_traits<Graph>::edge_descriptor, bool>
0728 BGL_NAMED_GRAPH::lazy_add_edge_with_property::commit() const
0729 {
0730   using boost::detail::parallel::make_pair_with_property;
0731   typedef typename BGL_NAMED_GRAPH::process_id_type process_id_type;
0732   BOOST_ASSERT(!committed);
0733   committed = true;
0734
0735   /// The result we will return, if we are sending a message to
0736   /// request that someone else add the edge.
0737   boost::parallel::detail::untracked_pair<edge_descriptor, bool> result;
0738
0739   /// The owner of the vertex "u"
0740   process_id_type u_owner;
0741
0742   process_id_type rank = process_id(self.process_group());
0743   if (const vertex_name_type* u_name = boost::get<vertex_name_type>(&u)) {
0744     /// We haven't resolved the source vertex to a descriptor yet, so
0745     /// it must not be local.
0746     u_owner = self.named_distribution()(*u_name);
0747
0748     /// Send a message to the remote vertex requesting that it add the
0749     /// edge. The message differs depending on whether we have a
0750     /// vertex name or a vertex descriptor for the target.
0751     if (const vertex_name_type* v_name = boost::get<vertex_name_type>(&v))
0752       send_oob_with_reply
0753         (self.process_group(), u_owner,
0754          BGL_NAMED_GRAPH::msg_add_edge_name_name_with_reply_and_property,
0755          make_pair_with_property(*u_name, *v_name, property),
0756          result);
0757     else
0758       send_oob_with_reply
0759         (self.process_group(), u_owner,
0760          BGL_NAMED_GRAPH::msg_add_edge_name_vertex_with_reply_and_property,
0761          make_pair_with_property(*u_name,
0762                                  boost::get<vertex_descriptor>(v),
0763                                  property),
0764          result);
0765   } else {
0766     /// We have resolved the source vertex to a descriptor, which may
0767     /// either be local or remote.
0768     u_owner
0769       = get(vertex_owner, self.derived(),
0770             boost::get<vertex_descriptor>(u));
0771     if (u_owner == rank) {
0772       /// The source is local. If we need to, resolve the target vertex.
0773       if (const vertex_name_type* v_name = boost::get<vertex_name_type>(&v))
0774         v = add_vertex(*v_name, self.derived());
0775
0776       /// Add the edge using vertex descriptors
0777       return add_edge(boost::get<vertex_descriptor>(u),
0778                       boost::get<vertex_descriptor>(v),
0779                       property,
0780                       self.derived());
0781     } else {
0782       /// The source is remote. Just send a message to its owner
0783       /// requesting that the owner add the new edge, either directly
0784       /// or via the derived class's add_edge function.
0785       if (const vertex_name_type* v_name = boost::get<vertex_name_type>(&v))
0786         send_oob_with_reply
0787           (self.process_group(), u_owner,
0788            BGL_NAMED_GRAPH::msg_add_edge_vertex_name_with_reply_and_property,
0789            make_pair_with_property(boost::get<vertex_descriptor>(u), *v_name,
0790                                    property),
0791            result);
0792       else
0793         return add_edge(boost::get<vertex_descriptor>(u),
0794                         boost::get<vertex_descriptor>(v),
0795                         property,
0796                         self.derived());
0797     }
0798   }
0799
0800   // If we get here, the edge has been added remotely and "result"
0801   // contains the result of that edge addition.
0802   return result;
0803 }
0804
0805 /// Construct the named_graph with a particular process group
0806 template<BGL_NAMED_GRAPH_PARAMS>
0807 BGL_NAMED_GRAPH::named_graph(const process_group_type& pg)
0808   : process_group_(pg, boost::parallel::attach_distributed_object()),
0809     distribution_(pg)
0810 {
0811   setup_triggers();
0812 }
0813
0814 /// Construct the named_graph mixin with a particular process group
0815 /// and distribution function
0816 template<BGL_NAMED_GRAPH_PARAMS>
0817 BGL_NAMED_GRAPH::named_graph(const process_group_type& pg,
0818                              const base_distribution_type& distribution)
0819   : process_group_(pg, boost::parallel::attach_distributed_object()),
0820     distribution_(pg, distribution)
0821 {
0822   setup_triggers();
0823 }
0824
0825 template<BGL_NAMED_GRAPH_PARAMS>
0826 void
0827 BGL_NAMED_GRAPH::setup_triggers()
0828 {
0829   using boost::graph::parallel::simple_trigger;
0830
0831   simple_trigger(process_group_, msg_add_vertex_name, this,
0832                  &named_graph::handle_add_vertex_name);
0833   simple_trigger(process_group_, msg_add_vertex_name_with_reply, this,
0834                  &named_graph::handle_add_vertex_name_with_reply);
0835   simple_trigger(process_group_, msg_find_vertex, this,
0836                  &named_graph::handle_find_vertex);
0837   simple_trigger(process_group_, msg_add_edge_name_name, this,
0838                  &named_graph::template handle_add_edge<vertex_name_type,
0839                                                         vertex_name_type>);
0840   simple_trigger(process_group_, msg_add_edge_name_name_with_reply, this,
0841                  &named_graph::template handle_add_edge_with_reply
0842                    <vertex_name_type, vertex_name_type>);
0843   simple_trigger(process_group_, msg_add_edge_name_vertex, this,
0844                  &named_graph::template handle_add_edge<vertex_name_type,
0845                                                         vertex_descriptor>);
0846   simple_trigger(process_group_, msg_add_edge_name_vertex_with_reply, this,
0847                  &named_graph::template handle_add_edge_with_reply
0848                    <vertex_name_type, vertex_descriptor>);
0849   simple_trigger(process_group_, msg_add_edge_vertex_name, this,
0850                  &named_graph::template handle_add_edge<vertex_descriptor,
0851                                                         vertex_name_type>);
0852   simple_trigger(process_group_, msg_add_edge_vertex_name_with_reply, this,
0853                  &named_graph::template handle_add_edge_with_reply
0854                    <vertex_descriptor, vertex_name_type>);
0855   simple_trigger(process_group_, msg_add_edge_name_name_with_property, this,
0856                  &named_graph::
0857                    template handle_add_edge_with_property<vertex_name_type,
0858                                                           vertex_name_type>);
0859   simple_trigger(process_group_,
0860                  msg_add_edge_name_name_with_reply_and_property, this,
0861                  &named_graph::template handle_add_edge_with_reply_and_property
0862                    <vertex_name_type, vertex_name_type>);
0863   simple_trigger(process_group_, msg_add_edge_name_vertex_with_property, this,
0864                  &named_graph::
0865                    template handle_add_edge_with_property<vertex_name_type,
0866                                                           vertex_descriptor>);
0867   simple_trigger(process_group_,
0868                  msg_add_edge_name_vertex_with_reply_and_property, this,
0869                  &named_graph::template handle_add_edge_with_reply_and_property
0870                    <vertex_name_type, vertex_descriptor>);
0871   simple_trigger(process_group_, msg_add_edge_vertex_name_with_property, this,
0872                  &named_graph::
0873                    template handle_add_edge_with_property<vertex_descriptor,
0874                                                           vertex_name_type>);
0875   simple_trigger(process_group_,
0876                  msg_add_edge_vertex_name_with_reply_and_property, this,
0877                  &named_graph::template handle_add_edge_with_reply_and_property
0878                    <vertex_descriptor, vertex_name_type>);
0879 }
0880
0881 /// Retrieve the vertex associated with the given name
0882 template<BGL_NAMED_GRAPH_PARAMS>
0883 optional<Vertex>
0884 find_vertex(typename BGL_NAMED_GRAPH::vertex_name_type const& name,
0885             const BGL_NAMED_GRAPH& g)
0886 {
0887   typedef typename Graph::local_vertex_descriptor local_vertex_descriptor;
0888   typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
0889
0890   // Determine the owner of this name
0891   typename BGL_NAMED_GRAPH::process_id_type owner
0892     = g.named_distribution()(name);
0893
0894   if (owner == process_id(g.process_group())) {
0895     // The vertex is local, so search for a mapping here
0896     optional<local_vertex_descriptor> result
0897       = find_vertex(name, g.derived().base());
0898     if (result)
0899       return Vertex(owner, *result);
0900     else
0901       return optional<Vertex>();
0902   }
0903   else {
0904     // Ask the ownering process for the name of this vertex
0905     boost::parallel::detail::untracked_pair<vertex_descriptor, bool> result;
0906     send_oob_with_reply(g.process_group(), owner,
0907                         BGL_NAMED_GRAPH::msg_find_vertex, name, result);
0908     if (result.second)
0909       return result.first;
0910     else
0911       return optional<Vertex>();
0912   }
0913 }
0914
0915 /// meta-function helping in figuring out if the given VertextProerty belongs to
0916 /// a named graph
0917 template<typename VertexProperty>
0918 struct not_is_named_graph
0919   : is_same<typename internal_vertex_name<VertexProperty>::type, void>
0920 {};
0921
0922 /// Retrieve the vertex associated with the given name
0923 template<typename Graph>
0924 typename Graph::named_graph_type::lazy_add_vertex
0925 add_vertex(typename Graph::vertex_name_type const& name,
0926            Graph& g,
0927            typename disable_if<
0928               not_is_named_graph<typename Graph::vertex_property_type>,
0929               void*>::type = 0)
0930 {
0931   return typename Graph::named_graph_type::lazy_add_vertex(g, name);
0932 }
0933
0934 /// Add an edge using vertex names to refer to the vertices
0935 template<BGL_NAMED_GRAPH_PARAMS>
0936 typename BGL_NAMED_GRAPH::lazy_add_edge
0937 add_edge(typename BGL_NAMED_GRAPH::vertex_name_type const& u_name,
0938          typename BGL_NAMED_GRAPH::vertex_name_type const& v_name,
0939          BGL_NAMED_GRAPH& g)
0940 {
0941   typedef typename BGL_NAMED_GRAPH::lazy_add_edge lazy_add_edge;
0942   typedef typename BGL_NAMED_GRAPH::process_id_type process_id_type;
0943
0944   process_id_type rank = process_id(g.process_group());
0945   process_id_type u_owner = g.named_distribution()(u_name);
0946   process_id_type v_owner = g.named_distribution()(v_name);
0947
0948   // Resolve local vertex names before building the "lazy" edge
0949   // addition structure.
0950   if (u_owner == rank && v_owner == rank)
0951     return lazy_add_edge(g, add_vertex(u_name, g), add_vertex(v_name, g));
0952   else if (u_owner == rank && v_owner != rank)
0953     return lazy_add_edge(g, add_vertex(u_name, g), v_name);
0954   else if (u_owner != rank && v_owner == rank)
0955     return lazy_add_edge(g, u_name, add_vertex(v_name, g));
0956   else
0957     return lazy_add_edge(g, u_name, v_name);
0958 }
0959
0960 template<BGL_NAMED_GRAPH_PARAMS>
0961 typename BGL_NAMED_GRAPH::lazy_add_edge
0962 add_edge(typename BGL_NAMED_GRAPH::vertex_name_type const& u_name,
0963          typename BGL_NAMED_GRAPH::vertex_descriptor const& v,
0964          BGL_NAMED_GRAPH& g)
0965 {
0966   // Resolve local vertex names before building the "lazy" edge
0967   // addition structure.
0968   typedef typename BGL_NAMED_GRAPH::lazy_add_edge lazy_add_edge;
0969   if (g.named_distribution()(u_name) == process_id(g.process_group()))
0970     return lazy_add_edge(g, add_vertex(u_name, g), v);
0971   else
0972     return lazy_add_edge(g, u_name, v);
0973 }
0974
0975 template<BGL_NAMED_GRAPH_PARAMS>
0976 typename BGL_NAMED_GRAPH::lazy_add_edge
0977 add_edge(typename BGL_NAMED_GRAPH::vertex_descriptor const& u,
0978          typename BGL_NAMED_GRAPH::vertex_name_type const& v_name,
0979          BGL_NAMED_GRAPH& g)
0980 {
0981   // Resolve local vertex names before building the "lazy" edge
0982   // addition structure.
0983   typedef typename BGL_NAMED_GRAPH::lazy_add_edge lazy_add_edge;
0984   if (g.named_distribution()(v_name) == process_id(g.process_group()))
0985     return lazy_add_edge(g, u, add_vertex(v_name, g));
0986   else
0987     return lazy_add_edge(g, u, v_name);
0988 }
0989
0990 /// Add an edge using vertex names to refer to the vertices
0991 template<BGL_NAMED_GRAPH_PARAMS>
0992 typename BGL_NAMED_GRAPH::lazy_add_edge_with_property
0993 add_edge(typename BGL_NAMED_GRAPH::vertex_name_type const& u_name,
0994          typename BGL_NAMED_GRAPH::vertex_name_type const& v_name,
0995          typename Graph::edge_property_type const& property,
0996          BGL_NAMED_GRAPH& g)
0997 {
0998   typedef typename BGL_NAMED_GRAPH::lazy_add_edge_with_property lazy_add_edge;
0999   typedef typename BGL_NAMED_GRAPH::process_id_type process_id_type;
1000
1001   process_id_type rank = process_id(g.process_group());
1002   process_id_type u_owner = g.named_distribution()(u_name);
1003   process_id_type v_owner = g.named_distribution()(v_name);
1004
1005   // Resolve local vertex names before building the "lazy" edge
1006   // addition structure.
1007   if (u_owner == rank && v_owner == rank)
1008     return lazy_add_edge(g, add_vertex(u_name, g), add_vertex(v_name, g),
1009                          property);
1010   else if (u_owner == rank && v_owner != rank)
1011     return lazy_add_edge(g, add_vertex(u_name, g), v_name, property);
1012   else if (u_owner != rank && v_owner == rank)
1013     return lazy_add_edge(g, u_name, add_vertex(v_name, g), property);
1014   else
1015     return lazy_add_edge(g, u_name, v_name, property);
1016 }
1017
1018 template<BGL_NAMED_GRAPH_PARAMS>
1019 typename BGL_NAMED_GRAPH::lazy_add_edge_with_property
1020 add_edge(typename BGL_NAMED_GRAPH::vertex_name_type const& u_name,
1021          typename BGL_NAMED_GRAPH::vertex_descriptor const& v,
1022          typename Graph::edge_property_type const& property,
1023          BGL_NAMED_GRAPH& g)
1024 {
1025   // Resolve local vertex names before building the "lazy" edge
1026   // addition structure.
1027   typedef typename BGL_NAMED_GRAPH::lazy_add_edge_with_property lazy_add_edge;
1028   if (g.named_distribution()(u_name) == process_id(g.process_group()))
1029     return lazy_add_edge(g, add_vertex(u_name, g), v, property);
1030   else
1031     return lazy_add_edge(g, u_name, v, property);
1032 }
1033
1034 template<BGL_NAMED_GRAPH_PARAMS>
1035 typename BGL_NAMED_GRAPH::lazy_add_edge_with_property
1036 add_edge(typename BGL_NAMED_GRAPH::vertex_descriptor const& u,
1037          typename BGL_NAMED_GRAPH::vertex_name_type const& v_name,
1038          typename Graph::edge_property_type const& property,
1039          BGL_NAMED_GRAPH& g)
1040 {
1041   // Resolve local vertex names before building the "lazy" edge
1042   // addition structure.
1043   typedef typename BGL_NAMED_GRAPH::lazy_add_edge_with_property lazy_add_edge;
1044   if (g.named_distribution()(v_name) == process_id(g.process_group()))
1045     return lazy_add_edge(g, u, add_vertex(v_name, g), property);
1046   else
1047     return lazy_add_edge(g, u, v_name, property);
1048 }
1049
1050 template<BGL_NAMED_GRAPH_PARAMS>
1051 typename BGL_NAMED_GRAPH::process_id_type
1052 BGL_NAMED_GRAPH::owner_by_property(const vertex_property_type& property)
1053 {
1054   return distribution_(derived().base().extract_name(property));
1055 }
1056
1057
1058 /*******************************************************************
1059  * Message handlers                                                *
1060  *******************************************************************/
1061
1062 template<BGL_NAMED_GRAPH_PARAMS>
1063 void
1064 BGL_NAMED_GRAPH::
1065 handle_add_vertex_name(int /*source*/, int /*tag*/,
1066                        const vertex_name_type& msg, trigger_receive_context)
1067 {
1068   add_vertex(msg, derived());
1069 }
1070
1071 template<BGL_NAMED_GRAPH_PARAMS>
1072 typename BGL_NAMED_GRAPH::vertex_descriptor
1073 BGL_NAMED_GRAPH::
1074 handle_add_vertex_name_with_reply(int source, int /*tag*/,
1075                                   const vertex_name_type& msg,
1076                                   trigger_receive_context)
1077 {
1078   return add_vertex(msg, derived());
1079 }
1080
1081 template<BGL_NAMED_GRAPH_PARAMS>
1082 boost::parallel::detail::untracked_pair<typename BGL_NAMED_GRAPH::vertex_descriptor, bool>
1083 BGL_NAMED_GRAPH::
1084 handle_find_vertex(int source, int /*tag*/, const vertex_name_type& msg,
1085                    trigger_receive_context)
1086 {
1087   using boost::parallel::detail::make_untracked_pair;
1088
1089   optional<vertex_descriptor> v = find_vertex(msg, derived());
1090   if (v)
1091     return make_untracked_pair(*v, true);
1092   else
1093     return make_untracked_pair(graph_traits<Graph>::null_vertex(), false);
1094 }
1095
1096 template<BGL_NAMED_GRAPH_PARAMS>
1097 template<typename U, typename V>
1098 void
1099 BGL_NAMED_GRAPH::
1100 handle_add_edge(int source, int /*tag*/, const boost::parallel::detail::untracked_pair<U, V>& msg,
1101                 trigger_receive_context)
1102 {
1103   add_edge(msg.first, msg.second, derived());
1104 }
1105
1106 template<BGL_NAMED_GRAPH_PARAMS>
1107 template<typename U, typename V>
1108 boost::parallel::detail::untracked_pair<typename BGL_NAMED_GRAPH::edge_descriptor, bool>
1109 BGL_NAMED_GRAPH::
1110 handle_add_edge_with_reply(int source, int /*tag*/, const boost::parallel::detail::untracked_pair<U, V>& msg,
1111                            trigger_receive_context)
1112 {
1113   std::pair<typename BGL_NAMED_GRAPH::edge_descriptor, bool> p =
1114     add_edge(msg.first, msg.second, derived());
1115    return p;
1116 }
1117
1118 template<BGL_NAMED_GRAPH_PARAMS>
1119 template<typename U, typename V>
1120 void
1121 BGL_NAMED_GRAPH::
1122 handle_add_edge_with_property
1123   (int source, int tag,
1124    const pair_with_property<U, V, edge_property_type>& msg,
1125    trigger_receive_context)
1126 {
1127   add_edge(msg.first, msg.second, msg.get_property(), derived());
1128 }
1129
1130 template<BGL_NAMED_GRAPH_PARAMS>
1131 template<typename U, typename V>
1132 boost::parallel::detail::untracked_pair<typename BGL_NAMED_GRAPH::edge_descriptor, bool>
1133 BGL_NAMED_GRAPH::
1134 handle_add_edge_with_reply_and_property
1135   (int source, int tag,
1136    const pair_with_property<U, V, edge_property_type>& msg,
1137    trigger_receive_context)
1138 {
1139   std:: pair<typename BGL_NAMED_GRAPH::edge_descriptor, bool> p =
1140     add_edge(msg.first, msg.second, msg.get_property(), derived());
1141   return p;
1142 }
1143
1144 #undef BGL_NAMED_GRAPH
1145 #undef BGL_NAMED_GRAPH_PARAMS
1146
1147 /*******************************************************************
1148  * Maybe named graph mixin                                         *
1149  *******************************************************************/
1150
1151 /**
1152  * A graph mixin that can provide a mapping from names to vertices,
1153  * and use that mapping to simplify creation and manipulation of
1154  * graphs.
1155  */
1156 template<typename Graph, typename Vertex, typename Edge, typename Config,
1157   typename ExtractName
1158     = typename internal_vertex_name<typename Config::vertex_property_type>::type>
1159 struct maybe_named_graph
1160   : public named_graph<Graph, Vertex, Edge, Config>
1161 {
1162 private:
1163   typedef named_graph<Graph, Vertex, Edge, Config> inherited;
1164   typedef typename Config::process_group_type process_group_type;
1165
1166 public:
1167   /// The type used to distribute named vertices in the graph
1168   typedef typename Config::distribution_type distribution_type;
1169   typedef typename Config::base_distribution_type base_distribution_type;
1170
1171   explicit maybe_named_graph(const process_group_type& pg) : inherited(pg) { }
1172
1173   maybe_named_graph(const process_group_type& pg,
1174                     const base_distribution_type& distribution)
1175     : inherited(pg, distribution) { }
1176
1177   distribution_type&       distribution()       { return this->distribution_; }
1178   const distribution_type& distribution() const { return this->distribution_; }
1179 };
1180
1181 /**
1182  * A graph mixin that can provide a mapping from names to vertices,
1183  * and use that mapping to simplify creation and manipulation of
1184  * graphs. This partial specialization turns off this functionality
1185  * when the @c VertexProperty does not have an internal vertex name.
1186  */
1187 template<typename Graph, typename Vertex, typename Edge, typename Config>
1188 struct maybe_named_graph<Graph, Vertex, Edge, Config, void>
1189 {
1190 private:
1191   typedef typename Config::process_group_type process_group_type;
1192   typedef typename Config::vertex_property_type vertex_property_type;
1193
1194 public:
1195   typedef typename process_group_type::process_id_type process_id_type;
1196
1197   /// The type used to distribute named vertices in the graph
1198   typedef typename Config::distribution_type distribution_type;
1199   typedef typename Config::base_distribution_type base_distribution_type;
1200
1201   explicit maybe_named_graph(const process_group_type&)  { }
1202
1203   maybe_named_graph(const process_group_type& pg,
1204                     const base_distribution_type& distribution)
1205     : distribution_(pg, distribution) { }
1206
1207   /// Notify the named_graph that we have added the given vertex. This
1208   /// is a no-op.
1209   void added_vertex(Vertex) { }
1210
1211   /// Notify the named_graph that we are removing the given
1212   /// vertex. This is a no-op.
1213   template <typename VertexIterStability>
1214   void removing_vertex(Vertex, VertexIterStability) { }
1215
1216   /// Notify the named_graph that we are clearing the graph
1217   void clearing_graph() { }
1218
1219   /// Retrieve the owner of a given vertex based on the properties
1220   /// associated with that vertex. This operation just returns the
1221   /// number of the local processor, adding all vertices locally.
1222   process_id_type owner_by_property(const vertex_property_type&)
1223   {
1224     return process_id(pg);
1225   }
1226
1227   distribution_type&       distribution()       { return distribution_; }
1228   const distribution_type& distribution() const { return distribution_; }
1229
1230 protected:
1231   /// The process group of the graph
1232   process_group_type pg;
1233
1234   /// The distribution used for the graph
1235   distribution_type distribution_;
1236 };
1237
1238 } } } // end namespace boost::graph::distributed
1239
1240 #endif // BOOST_GRAPH_DISTRIBUTED_NAMED_GRAPH_HPP