Chris@16: // Copyright (C) 2007 Douglas Gregor 
Chris@16: // Copyright (C) 2007 Hartmut Kaiser
Chris@16: 
Chris@16: // Use, modification and distribution is subject to the Boost Software
Chris@16: // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: // TODO:
Chris@16: //   - Cache (some) remote vertex names?
Chris@16: #ifndef BOOST_GRAPH_DISTRIBUTED_NAMED_GRAPH_HPP
Chris@16: #define BOOST_GRAPH_DISTRIBUTED_NAMED_GRAPH_HPP
Chris@16: 
Chris@16: #ifndef BOOST_GRAPH_USE_MPI
Chris@16: #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
Chris@16: #endif
Chris@16: 
Chris@16: #include <boost/assert.hpp>
Chris@16: #include <boost/graph/named_graph.hpp>
Chris@16: #include <boost/functional/hash.hpp>
Chris@16: #include <boost/variant.hpp>
Chris@16: #include <boost/graph/parallel/simple_trigger.hpp>
Chris@16: #include <boost/graph/parallel/process_group.hpp>
Chris@16: #include <boost/graph/parallel/detail/property_holders.hpp>
Chris@16: 
Chris@16: namespace boost { namespace graph { namespace distributed {
Chris@16: 
Chris@16: using boost::parallel::trigger_receive_context;
Chris@16: using boost::detail::parallel::pair_with_property;
Chris@16: 
Chris@16: /*******************************************************************
Chris@16:  * Hashed distribution of named entities                           *
Chris@16:  *******************************************************************/
Chris@16: 
Chris@16: template<typename T>
Chris@16: struct hashed_distribution
Chris@16: {
Chris@16:   template<typename ProcessGroup>
Chris@16:   hashed_distribution(const ProcessGroup& pg, std::size_t /*num_vertices*/ = 0)
Chris@16:     : n(num_processes(pg)) { }
Chris@16: 
Chris@16:   int operator()(const T& value) const 
Chris@16:   {
Chris@16:     return hasher(value) % n;
Chris@16:   }
Chris@16: 
Chris@16:   std::size_t n;
Chris@16:   hash<T> hasher;
Chris@16: };
Chris@16: 
Chris@16: /// Specialization for named graphs
Chris@16: template <typename InDistribution, typename VertexProperty, typename VertexSize,
Chris@16:           typename ProcessGroup,
Chris@16:           typename ExtractName 
Chris@16:             = typename internal_vertex_name<VertexProperty>::type>
Chris@16: struct select_distribution
Chris@16: {
Chris@16: private:
Chris@16:   /// The type used to name vertices in the graph
Chris@16:   typedef typename remove_cv<
Chris@16:             typename remove_reference<
Chris@16:               typename ExtractName::result_type>::type>::type
Chris@16:     vertex_name_type;
Chris@16: 
Chris@16: public:
Chris@16:   /**
Chris@16:    *  The @c type field provides a distribution object that maps
Chris@16:    *  vertex names to processors. The distribution object will be
Chris@16:    *  constructed with the process group over which communication will
Chris@16:    *  occur. The distribution object shall also be a function
Chris@16:    *  object mapping from the type of the name to a processor number
Chris@16:    *  in @c [0, @c p) (for @c p processors). By default, the mapping
Chris@16:    *  function uses the @c boost::hash value of the name, modulo @c p.
Chris@16:    */
Chris@16:   typedef typename mpl::if_<is_same<InDistribution, defaultS>,
Chris@16:                             hashed_distribution<vertex_name_type>,
Chris@16:                             InDistribution>::type 
Chris@16:     type;
Chris@16: 
Chris@16:   /// for named graphs the default type is the same as the stored distribution 
Chris@16:   /// type
Chris@16:   typedef type default_type;
Chris@16: };
Chris@16: 
Chris@16: /// Specialization for non-named graphs
Chris@16: template <typename InDistribution, typename VertexProperty, typename VertexSize,
Chris@16:           typename ProcessGroup>
Chris@16: struct select_distribution<InDistribution, VertexProperty, VertexSize, 
Chris@16:                            ProcessGroup, void>
Chris@16: {
Chris@16:   /// the distribution type stored in the graph for non-named graphs should be
Chris@16:   /// the variant_distribution type
Chris@16:   typedef typename mpl::if_<is_same<InDistribution, defaultS>,
Chris@16:                             boost::parallel::variant_distribution<ProcessGroup, 
Chris@16:                                                                   VertexSize>,
Chris@16:                             InDistribution>::type type;
Chris@16: 
Chris@16:   /// default_type is used as the distribution functor for the
Chris@16:   /// adjacency_list, it should be parallel::block by default
Chris@16:   typedef typename mpl::if_<is_same<InDistribution, defaultS>,
Chris@16:                             boost::parallel::block, type>::type
Chris@16:     default_type;
Chris@16: };
Chris@16: 
Chris@16: 
Chris@16: /*******************************************************************
Chris@16:  * Named graph mixin                                               *
Chris@16:  *******************************************************************/
Chris@16: 
Chris@16: /**
Chris@16:  * named_graph is a mixin that provides names for the vertices of a
Chris@16:  * graph, including a mapping from names to vertices. Graph types that
Chris@16:  * may or may not be have vertex names (depending on the properties
Chris@16:  * supplied by the user) should use maybe_named_graph.
Chris@16:  *
Chris@16:  * Template parameters:
Chris@16:  *
Chris@16:  *   Graph: the graph type that derives from named_graph
Chris@16:  *
Chris@16:  *   Vertex: the type of a vertex descriptor in Graph. Note: we cannot
Chris@16:  *   use graph_traits here, because the Graph is not yet defined.
Chris@16:  *
Chris@16:  *   VertexProperty: the type of the property stored along with the
Chris@16:  *   vertex.
Chris@16:  *
Chris@16:  *   ProcessGroup: the process group over which the distributed name
Chris@16:  *   graph mixin will communicate.
Chris@16:  */
Chris@16: template<typename Graph, typename Vertex, typename Edge, typename Config>
Chris@16: class named_graph
Chris@16: {
Chris@16: public:
Chris@16:   /// Messages passed within the distributed named graph
Chris@16:   enum message_kind {
Chris@16:     /**
Chris@16:      * Requests the addition of a vertex on a remote processor. The
Chris@16:      * message data is a @c vertex_name_type.
Chris@16:      */
Chris@16:     msg_add_vertex_name,
Chris@16: 
Chris@16:     /**
Chris@16:      * Requests the addition of a vertex on a remote processor. The
Chris@16:      * message data is a @c vertex_name_type. The remote processor
Chris@16:      * will send back a @c msg_add_vertex_name_reply message
Chris@16:      * containing the vertex descriptor.
Chris@16:      */
Chris@16:     msg_add_vertex_name_with_reply,
Chris@16: 
Chris@16:     /**
Chris@16:      * Requests the vertex descriptor corresponding to the given
Chris@16:      * vertex name. The remote process will reply with a 
Chris@16:      * @c msg_find_vertex_reply message containing the answer.
Chris@16:      */
Chris@16:     msg_find_vertex,
Chris@16: 
Chris@16:     /**
Chris@16:      * Requests the addition of an edge on a remote processor. The
Chris@16:      * data stored in these messages is a @c pair<source, target>@,
Chris@16:      * where @c source and @c target may be either names (of type @c
Chris@16:      * vertex_name_type) or vertex descriptors, depending on what
Chris@16:      * information we have locally.  
Chris@16:      */
Chris@16:     msg_add_edge_name_name,
Chris@16:     msg_add_edge_vertex_name,
Chris@16:     msg_add_edge_name_vertex,
Chris@16: 
Chris@16:     /**
Chris@16:      * These messages are identical to msg_add_edge_*_*, except that
Chris@16:      * the process actually adding the edge will send back a @c
Chris@16:      * pair<edge_descriptor,bool>
Chris@16:      */
Chris@16:     msg_add_edge_name_name_with_reply,
Chris@16:     msg_add_edge_vertex_name_with_reply,
Chris@16:     msg_add_edge_name_vertex_with_reply,
Chris@16: 
Chris@16:     /**
Chris@16:      * Requests the addition of an edge with a property on a remote
Chris@16:      * processor. The data stored in these messages is a @c
Chris@16:      * pair<vertex_property_type, pair<source, target>>@, where @c
Chris@16:      * source and @c target may be either names (of type @c
Chris@16:      * vertex_name_type) or vertex descriptors, depending on what
Chris@16:      * information we have locally.
Chris@16:      */
Chris@16:     msg_add_edge_name_name_with_property,
Chris@16:     msg_add_edge_vertex_name_with_property,
Chris@16:     msg_add_edge_name_vertex_with_property,
Chris@16: 
Chris@16:     /**
Chris@16:      * These messages are identical to msg_add_edge_*_*_with_property,
Chris@16:      * except that the process actually adding the edge will send back
Chris@16:      * a @c pair<edge_descriptor,bool>.
Chris@16:      */
Chris@16:     msg_add_edge_name_name_with_reply_and_property,
Chris@16:     msg_add_edge_vertex_name_with_reply_and_property,
Chris@16:     msg_add_edge_name_vertex_with_reply_and_property
Chris@16:   };
Chris@16: 
Chris@16:   /// The vertex descriptor type
Chris@16:   typedef Vertex vertex_descriptor;
Chris@16:   
Chris@16:   /// The edge descriptor type
Chris@16:   typedef Edge edge_descriptor;
Chris@16: 
Chris@16:   /// The vertex property type
Chris@16:   typedef typename Config::vertex_property_type vertex_property_type;
Chris@16:   
Chris@16:   /// The vertex property type
Chris@16:   typedef typename Config::edge_property_type edge_property_type;
Chris@16:   
Chris@16:   /// The type used to extract names from the property structure
Chris@16:   typedef typename internal_vertex_name<vertex_property_type>::type
Chris@16:     extract_name_type;
Chris@16: 
Chris@16:   /// The type used to name vertices in the graph
Chris@16:   typedef typename remove_cv<
Chris@16:             typename remove_reference<
Chris@16:               typename extract_name_type::result_type>::type>::type
Chris@16:     vertex_name_type;
Chris@16: 
Chris@16:   /// The type used to distribute named vertices in the graph
Chris@16:   typedef typename Config::distribution_type distribution_type;
Chris@16:   typedef typename Config::base_distribution_type base_distribution_type;
Chris@16: 
Chris@16:   /// The type used for communication in the distributed structure
Chris@16:   typedef typename Config::process_group_type process_group_type;
Chris@16: 
Chris@16:   /// Type used to identify processes
Chris@16:   typedef typename process_group_type::process_id_type process_id_type;
Chris@16: 
Chris@16:   /// a reference to this class, which is used for disambiguation of the 
Chris@16:   //  add_vertex function
Chris@16:   typedef named_graph named_graph_type;
Chris@16:   
Chris@16:   /// Structure returned when adding a vertex by vertex name
Chris@16:   struct lazy_add_vertex;
Chris@16:   friend struct lazy_add_vertex;
Chris@16: 
Chris@16:   /// Structure returned when adding an edge by vertex name
Chris@16:   struct lazy_add_edge;
Chris@16:   friend struct lazy_add_edge;
Chris@16: 
Chris@16:   /// Structure returned when adding an edge by vertex name with a property
Chris@16:   struct lazy_add_edge_with_property;
Chris@16:   friend struct lazy_add_edge_with_property;
Chris@16: 
Chris@16:   explicit named_graph(const process_group_type& pg);
Chris@16: 
Chris@16:   named_graph(const process_group_type& pg, const base_distribution_type& distribution);
Chris@16: 
Chris@16:   /// Set up triggers, but only for the BSP process group
Chris@16:   void setup_triggers();
Chris@16: 
Chris@16:   /// Retrieve the derived instance
Chris@16:   Graph&       derived()       { return static_cast<Graph&>(*this); }
Chris@16:   const Graph& derived() const { return static_cast<const Graph&>(*this); }
Chris@16: 
Chris@16:   /// Retrieve the process group
Chris@16:   process_group_type&       process_group()       { return process_group_; }
Chris@16:   const process_group_type& process_group() const { return process_group_; }
Chris@16: 
Chris@16:   // Retrieve the named distribution
Chris@16:   distribution_type&       named_distribution()       { return distribution_; }
Chris@16:   const distribution_type& named_distribution() const { return distribution_; }
Chris@16: 
Chris@16:   /// Notify the named_graph that we have added the given vertex. This
Chris@16:   /// is a no-op.
Chris@16:   void added_vertex(Vertex) { }
Chris@16: 
Chris@16:   /// Notify the named_graph that we are removing the given
Chris@16:   /// vertex. This is a no-op.
Chris@16:   template <typename VertexIterStability>
Chris@16:   void removing_vertex(Vertex, VertexIterStability) { }
Chris@16: 
Chris@16:   /// Notify the named_graph that we are clearing the graph
Chris@16:   void clearing_graph() { }
Chris@16: 
Chris@16:   /// Retrieve the owner of a given vertex based on the properties
Chris@16:   /// associated with that vertex. This operation just returns the
Chris@16:   /// number of the local processor, adding all vertices locally.
Chris@16:   process_id_type owner_by_property(const vertex_property_type&);
Chris@16: 
Chris@16: protected:
Chris@16:   void 
Chris@16:   handle_add_vertex_name(int source, int tag, const vertex_name_type& msg,
Chris@16:                          trigger_receive_context);
Chris@16: 
Chris@16:   vertex_descriptor 
Chris@16:   handle_add_vertex_name_with_reply(int source, int tag, 
Chris@16:                                     const vertex_name_type& msg,
Chris@16:                                     trigger_receive_context);
Chris@16: 
Chris@16:   boost::parallel::detail::untracked_pair<vertex_descriptor, bool>
Chris@16:   handle_find_vertex(int source, int tag, const vertex_name_type& msg,
Chris@16:                      trigger_receive_context);
Chris@16: 
Chris@16:   template<typename U, typename V>
Chris@16:   void handle_add_edge(int source, int tag, const boost::parallel::detail::untracked_pair<U, V>& msg,
Chris@16:                        trigger_receive_context);
Chris@16: 
Chris@16:   template<typename U, typename V>
Chris@16:   boost::parallel::detail::untracked_pair<edge_descriptor, bool> 
Chris@16:   handle_add_edge_with_reply(int source, int tag, const boost::parallel::detail::untracked_pair<U, V>& msg,
Chris@16:                              trigger_receive_context);
Chris@16: 
Chris@16:   template<typename U, typename V>
Chris@16:   void 
Chris@16:   handle_add_edge_with_property
Chris@16:     (int source, int tag, 
Chris@16:      const pair_with_property<U, V, edge_property_type>& msg,
Chris@16:      trigger_receive_context);
Chris@16: 
Chris@16:   template<typename U, typename V>
Chris@16:   boost::parallel::detail::untracked_pair<edge_descriptor, bool> 
Chris@16:   handle_add_edge_with_reply_and_property
Chris@16:     (int source, int tag, 
Chris@16:      const pair_with_property<U, V, edge_property_type>& msg,
Chris@16:      trigger_receive_context);
Chris@16: 
Chris@16:   /// The process group for this distributed data structure
Chris@16:   process_group_type process_group_;
Chris@16: 
Chris@16:   /// The distribution we will use to map names to processors
Chris@16:   distribution_type distribution_;
Chris@16: };
Chris@16: 
Chris@16: /// Helper macro containing the template parameters of named_graph
Chris@16: #define BGL_NAMED_GRAPH_PARAMS \
Chris@16:   typename Graph, typename Vertex, typename Edge, typename Config
Chris@16: /// Helper macro containing the named_graph<...> instantiation
Chris@16: #define BGL_NAMED_GRAPH \
Chris@16:   named_graph<Graph, Vertex, Edge, Config>
Chris@16: 
Chris@16: /**
Chris@16:  * Data structure returned from add_vertex that will "lazily" add the
Chris@16:  * vertex, either when it is converted to a @c vertex_descriptor or
Chris@16:  * when the most recent copy has been destroyed.
Chris@16:  */
Chris@16: template<BGL_NAMED_GRAPH_PARAMS>
Chris@16: struct BGL_NAMED_GRAPH::lazy_add_vertex
Chris@16: {
Chris@16:   /// Construct a new lazyily-added vertex
Chris@16:   lazy_add_vertex(named_graph& self, const vertex_name_type& name)
Chris@16:     : self(self), name(name), committed(false) { }
Chris@16: 
Chris@16:   /// Transfer responsibility for adding the vertex from the source of
Chris@16:   /// the copy to the newly-constructed opbject.
Chris@16:   lazy_add_vertex(const lazy_add_vertex& other)
Chris@101:     : self(other.self), name(other.name), committed(other.committed)
Chris@16:   {
Chris@16:     other.committed = true;
Chris@16:   }
Chris@16: 
Chris@16:   /// If the vertex has not been added yet, add it
Chris@16:   ~lazy_add_vertex();
Chris@16: 
Chris@16:   /// Add the vertex and return its descriptor. This conversion can
Chris@16:   /// only occur once, and only when this object is responsible for
Chris@16:   /// creating the vertex.
Chris@16:   operator vertex_descriptor() const { return commit(); }
Chris@16: 
Chris@16:   /// Add the vertex and return its descriptor. This can only be
Chris@16:   /// called once, and only when this object is responsible for
Chris@16:   /// creating the vertex.
Chris@16:   vertex_descriptor commit() const;
Chris@16: 
Chris@16: protected:
Chris@16:   named_graph&     self;
Chris@16:   vertex_name_type name;
Chris@16:   mutable bool     committed;
Chris@16: };
Chris@16: 
Chris@16: template<BGL_NAMED_GRAPH_PARAMS>
Chris@16: BGL_NAMED_GRAPH::lazy_add_vertex::~lazy_add_vertex()
Chris@16: {
Chris@16:   typedef typename BGL_NAMED_GRAPH::process_id_type process_id_type;
Chris@16: 
Chris@16:   /// If this vertex has already been created or will be created by
Chris@16:   /// someone else, or if someone threw an exception, we will not
Chris@16:   /// create the vertex now.
Chris@16:   if (committed || std::uncaught_exception())
Chris@16:     return;
Chris@16: 
Chris@16:   committed = true;
Chris@16: 
Chris@16:   process_id_type owner = self.named_distribution()(name);
Chris@16:   if (owner == process_id(self.process_group()))
Chris@16:     /// Add the vertex locally
Chris@16:     add_vertex(self.derived().base().vertex_constructor(name), self.derived()); 
Chris@16:   else
Chris@16:     /// Ask the owner of the vertex to add a vertex with this name
Chris@16:     send(self.process_group(), owner, msg_add_vertex_name, name);
Chris@16: }
Chris@16: 
Chris@16: template<BGL_NAMED_GRAPH_PARAMS>
Chris@16: typename BGL_NAMED_GRAPH::vertex_descriptor
Chris@16: BGL_NAMED_GRAPH::lazy_add_vertex::commit() const
Chris@16: {
Chris@16:   typedef typename BGL_NAMED_GRAPH::process_id_type process_id_type;
Chris@16:   BOOST_ASSERT (!committed);
Chris@16:   committed = true;
Chris@16: 
Chris@16:   process_id_type owner = self.named_distribution()(name);
Chris@16:   if (owner == process_id(self.process_group()))
Chris@16:     /// Add the vertex locally
Chris@16:     return add_vertex(self.derived().base().vertex_constructor(name),
Chris@16:                       self.derived()); 
Chris@16:   else {
Chris@16:     /// Ask the owner of the vertex to add a vertex with this name
Chris@16:     vertex_descriptor result;
Chris@16:     send_oob_with_reply(self.process_group(), owner, 
Chris@16:                         msg_add_vertex_name_with_reply, name, result);
Chris@16:     return result;
Chris@16:   }
Chris@16: }
Chris@16: 
Chris@16: /**
Chris@16:  * Data structure returned from add_edge that will "lazily" add the
Chris@16:  * edge, either when it is converted to a @c
Chris@16:  * pair<edge_descriptor,bool> or when the most recent copy has been
Chris@16:  * destroyed.
Chris@16:  */
Chris@16: template<BGL_NAMED_GRAPH_PARAMS>
Chris@16: struct BGL_NAMED_GRAPH::lazy_add_edge 
Chris@16: {
Chris@16:   /// The graph's edge descriptor
Chris@16:   typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
Chris@16: 
Chris@16:   /// Add an edge for the edge (u, v) based on vertex names
Chris@16:   lazy_add_edge(BGL_NAMED_GRAPH& self, 
Chris@16:                 const vertex_name_type& u_name,
Chris@16:                 const vertex_name_type& v_name) 
Chris@16:     : self(self), u(u_name), v(v_name), committed(false) { }
Chris@16: 
Chris@16:   /// Add an edge for the edge (u, v) based on a vertex descriptor and name
Chris@16:   lazy_add_edge(BGL_NAMED_GRAPH& self,
Chris@16:                 vertex_descriptor u,
Chris@16:                 const vertex_name_type& v_name)
Chris@16:     : self(self), u(u), v(v_name), committed(false) { }
Chris@16: 
Chris@16:   /// Add an edge for the edge (u, v) based on a vertex name and descriptor
Chris@16:   lazy_add_edge(BGL_NAMED_GRAPH& self,
Chris@16:                 const vertex_name_type& u_name,
Chris@16:                 vertex_descriptor v)
Chris@16:     : self(self), u(u_name), v(v), committed(false) { }
Chris@16: 
Chris@16:   /// Add an edge for the edge (u, v) based on vertex descriptors
Chris@16:   lazy_add_edge(BGL_NAMED_GRAPH& self,
Chris@16:                 vertex_descriptor u,
Chris@16:                 vertex_descriptor v)
Chris@16:     : self(self), u(u), v(v), committed(false) { }
Chris@16: 
Chris@16:   /// Copy a lazy_add_edge structure, which transfers responsibility
Chris@16:   /// for adding the edge to the newly-constructed object.
Chris@16:   lazy_add_edge(const lazy_add_edge& other)
Chris@16:     : self(other.self), u(other.u), v(other.v), committed(other.committed)
Chris@16:   {
Chris@16:     other.committed = true;
Chris@16:   }
Chris@16: 
Chris@16:   /// If the edge has not yet been added, add the edge but don't wait
Chris@16:   /// for a reply.
Chris@16:   ~lazy_add_edge();
Chris@16: 
Chris@16:   /// Returns commit().
Chris@16:   operator std::pair<edge_descriptor, bool>() const { return commit(); }
Chris@16: 
Chris@16:   // Add the edge. This operation will block if a remote edge is
Chris@16:   // being added.
Chris@16:   std::pair<edge_descriptor, bool> commit() const;
Chris@16: 
Chris@16: protected:
Chris@16:   BGL_NAMED_GRAPH& self;
Chris@16:   mutable variant<vertex_descriptor, vertex_name_type> u;
Chris@16:   mutable variant<vertex_descriptor, vertex_name_type> v;
Chris@16:   mutable bool committed;
Chris@16: 
Chris@16: private:
Chris@16:   // No copy-assignment semantics
Chris@16:   void operator=(lazy_add_edge&);
Chris@16: };
Chris@16: 
Chris@16: template<BGL_NAMED_GRAPH_PARAMS>
Chris@16: BGL_NAMED_GRAPH::lazy_add_edge::~lazy_add_edge()
Chris@16: {
Chris@16:   using boost::parallel::detail::make_untracked_pair;
Chris@16: 
Chris@16:   /// If this edge has already been created or will be created by
Chris@16:   /// someone else, or if someone threw an exception, we will not
Chris@16:   /// create the edge now.
Chris@16:   if (committed || std::uncaught_exception())
Chris@16:     return;
Chris@16: 
Chris@16:   committed = true;
Chris@16: 
Chris@16:   if (vertex_name_type* v_name = boost::get<vertex_name_type>(&v)) {
Chris@16:     // We haven't resolved the target vertex to a descriptor yet, so
Chris@16:     // it must not be local. Send a message to the owner of the target
Chris@16:     // of the edge. If the owner of the target does not happen to own
Chris@16:     // the source, it will resolve the target to a vertex descriptor
Chris@16:     // and pass the message along to the owner of the source. 
Chris@16:     if (vertex_name_type* u_name = boost::get<vertex_name_type>(&u))
Chris@16:       send(self.process_group(), self.distribution_(*v_name),
Chris@16:            BGL_NAMED_GRAPH::msg_add_edge_name_name,
Chris@16:            make_untracked_pair(*u_name, *v_name));
Chris@16:     else
Chris@16:       send(self.process_group(), self.distribution_(*v_name),
Chris@16:            BGL_NAMED_GRAPH::msg_add_edge_vertex_name,
Chris@16:            make_untracked_pair(boost::get<vertex_descriptor>(u), *v_name));
Chris@16:   } else {
Chris@16:     if (vertex_name_type* u_name = boost::get<vertex_name_type>(&u))
Chris@16:       // We haven't resolved the source vertex to a descriptor yet, so
Chris@16:       // it must not be local. Send a message to the owner of the
Chris@16:       // source vertex requesting the edge addition.
Chris@16:       send(self.process_group(), self.distribution_(*u_name),
Chris@16:            BGL_NAMED_GRAPH::msg_add_edge_name_vertex,
Chris@16:            make_untracked_pair(*u_name, boost::get<vertex_descriptor>(v)));
Chris@16:     else
Chris@16:       // We have descriptors for both of the vertices, either of which
Chris@16:       // may be remote or local. Tell the owner of the source vertex
Chris@16:       // to add the edge (it may be us!).
Chris@16:       add_edge(boost::get<vertex_descriptor>(u), 
Chris@16:                boost::get<vertex_descriptor>(v), 
Chris@16:                self.derived());
Chris@16:   }
Chris@16: }
Chris@16: 
Chris@16: template<BGL_NAMED_GRAPH_PARAMS>
Chris@16: std::pair<typename graph_traits<Graph>::edge_descriptor, bool>
Chris@16: BGL_NAMED_GRAPH::lazy_add_edge::commit() const
Chris@16: {
Chris@16:   typedef typename BGL_NAMED_GRAPH::process_id_type process_id_type;
Chris@16:   using boost::parallel::detail::make_untracked_pair;
Chris@16: 
Chris@16:   BOOST_ASSERT(!committed);
Chris@16:   committed = true;
Chris@16: 
Chris@16:   /// The result we will return, if we are sending a message to
Chris@16:   /// request that someone else add the edge.
Chris@16:   boost::parallel::detail::untracked_pair<edge_descriptor, bool> result;
Chris@16: 
Chris@16:   /// The owner of the vertex "u"
Chris@16:   process_id_type u_owner;
Chris@16: 
Chris@16:   process_id_type rank = process_id(self.process_group());
Chris@16:   if (const vertex_name_type* u_name = boost::get<vertex_name_type>(&u)) {
Chris@16:     /// We haven't resolved the source vertex to a descriptor yet, so
Chris@16:     /// it must not be local. 
Chris@16:     u_owner = self.named_distribution()(*u_name);
Chris@16: 
Chris@16:     /// Send a message to the remote vertex requesting that it add the
Chris@16:     /// edge. The message differs depending on whether we have a
Chris@16:     /// vertex name or a vertex descriptor for the target.
Chris@16:     if (const vertex_name_type* v_name = boost::get<vertex_name_type>(&v))
Chris@16:       send_oob_with_reply(self.process_group(), u_owner,
Chris@16:                           BGL_NAMED_GRAPH::msg_add_edge_name_name_with_reply,
Chris@16:                           make_untracked_pair(*u_name, *v_name), result);
Chris@16:     else
Chris@16:       send_oob_with_reply(self.process_group(), u_owner,
Chris@16:                           BGL_NAMED_GRAPH::msg_add_edge_name_vertex_with_reply,
Chris@16:                           make_untracked_pair(*u_name, 
Chris@16:                                          boost::get<vertex_descriptor>(v)),
Chris@16:                           result);
Chris@16:   } else {
Chris@16:     /// We have resolved the source vertex to a descriptor, which may
Chris@16:     /// either be local or remote.
Chris@16:     u_owner 
Chris@16:       = get(vertex_owner, self.derived(),
Chris@16:             boost::get<vertex_descriptor>(u));
Chris@16:     if (u_owner == rank) {
Chris@16:       /// The source is local. If we need to, resolve the target vertex.
Chris@16:       if (const vertex_name_type* v_name = boost::get<vertex_name_type>(&v))
Chris@16:         v = add_vertex(*v_name, self.derived());
Chris@16: 
Chris@16:       /// Add the edge using vertex descriptors
Chris@16:       return add_edge(boost::get<vertex_descriptor>(u), 
Chris@16:                       boost::get<vertex_descriptor>(v), 
Chris@16:                       self.derived());
Chris@16:     } else {
Chris@16:       /// The source is remote. Just send a message to its owner
Chris@16:       /// requesting that the owner add the new edge, either directly
Chris@16:       /// or via the derived class's add_edge function.
Chris@16:       if (const vertex_name_type* v_name = boost::get<vertex_name_type>(&v))
Chris@16:         send_oob_with_reply
Chris@16:           (self.process_group(), u_owner,
Chris@16:            BGL_NAMED_GRAPH::msg_add_edge_vertex_name_with_reply,
Chris@16:            make_untracked_pair(boost::get<vertex_descriptor>(u), *v_name),
Chris@16:            result);
Chris@16:       else
Chris@16:         return add_edge(boost::get<vertex_descriptor>(u), 
Chris@16:                         boost::get<vertex_descriptor>(v), 
Chris@16:                         self.derived());
Chris@16:     }
Chris@16:   }
Chris@16: 
Chris@16:   // If we get here, the edge has been added remotely and "result"
Chris@16:   // contains the result of that edge addition.
Chris@16:   return result;
Chris@16: }
Chris@16: 
Chris@16: /**
Chris@16:  * Data structure returned from add_edge that will "lazily" add the
Chris@16:  * edge with a property, either when it is converted to a @c
Chris@16:  * pair<edge_descriptor,bool> or when the most recent copy has been
Chris@16:  * destroyed.
Chris@16:  */
Chris@16: template<BGL_NAMED_GRAPH_PARAMS>
Chris@16: struct BGL_NAMED_GRAPH::lazy_add_edge_with_property 
Chris@16: {
Chris@16:   /// The graph's edge descriptor
Chris@16:   typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
Chris@16: 
Chris@16:   /// The Edge property type for our graph
Chris@16:   typedef typename Config::edge_property_type edge_property_type;
Chris@16:   
Chris@16:   /// Add an edge for the edge (u, v) based on vertex names
Chris@16:   lazy_add_edge_with_property(BGL_NAMED_GRAPH& self, 
Chris@16:                               const vertex_name_type& u_name,
Chris@16:                               const vertex_name_type& v_name,
Chris@16:                               const edge_property_type& property) 
Chris@16:     : self(self), u(u_name), v(v_name), property(property), committed(false)
Chris@16:   { 
Chris@16:   }
Chris@16: 
Chris@16:   /// Add an edge for the edge (u, v) based on a vertex descriptor and name
Chris@16:   lazy_add_edge_with_property(BGL_NAMED_GRAPH& self,
Chris@16:                 vertex_descriptor u,
Chris@16:                 const vertex_name_type& v_name,
Chris@16:                                   const edge_property_type& property)
Chris@16:     : self(self), u(u), v(v_name), property(property), committed(false) { }
Chris@16: 
Chris@16:   /// Add an edge for the edge (u, v) based on a vertex name and descriptor
Chris@16:   lazy_add_edge_with_property(BGL_NAMED_GRAPH& self,
Chris@16:                               const vertex_name_type& u_name,
Chris@16:                               vertex_descriptor v,
Chris@16:                               const edge_property_type& property)
Chris@16:     : self(self), u(u_name), v(v), property(property), committed(false) { }
Chris@16: 
Chris@16:   /// Add an edge for the edge (u, v) based on vertex descriptors
Chris@16:   lazy_add_edge_with_property(BGL_NAMED_GRAPH& self,
Chris@16:                               vertex_descriptor u,
Chris@16:                               vertex_descriptor v,
Chris@16:                               const edge_property_type& property)
Chris@16:     : self(self), u(u), v(v), property(property), committed(false) { }
Chris@16: 
Chris@16:   /// Copy a lazy_add_edge_with_property structure, which transfers
Chris@16:   /// responsibility for adding the edge to the newly-constructed
Chris@16:   /// object.
Chris@16:   lazy_add_edge_with_property(const lazy_add_edge_with_property& other)
Chris@16:     : self(other.self), u(other.u), v(other.v), property(other.property), 
Chris@16:       committed(other.committed)
Chris@16:   {
Chris@16:     other.committed = true;
Chris@16:   }
Chris@16: 
Chris@16:   /// If the edge has not yet been added, add the edge but don't wait
Chris@16:   /// for a reply.
Chris@16:   ~lazy_add_edge_with_property();
Chris@16: 
Chris@16:   /// Returns commit().
Chris@16:   operator std::pair<edge_descriptor, bool>() const { return commit(); }
Chris@16: 
Chris@16:   // Add the edge. This operation will block if a remote edge is
Chris@16:   // being added.
Chris@16:   std::pair<edge_descriptor, bool> commit() const;
Chris@16: 
Chris@16: protected:
Chris@16:   BGL_NAMED_GRAPH& self;
Chris@16:   mutable variant<vertex_descriptor, vertex_name_type> u;
Chris@16:   mutable variant<vertex_descriptor, vertex_name_type> v;
Chris@16:   edge_property_type property;
Chris@16:   mutable bool committed;
Chris@16: 
Chris@16: private:
Chris@16:   // No copy-assignment semantics
Chris@16:   void operator=(lazy_add_edge_with_property&);
Chris@16: };
Chris@16: 
Chris@16: template<BGL_NAMED_GRAPH_PARAMS>
Chris@16: BGL_NAMED_GRAPH::lazy_add_edge_with_property::~lazy_add_edge_with_property()
Chris@16: {
Chris@16:   using boost::detail::parallel::make_pair_with_property;
Chris@16: 
Chris@16:   /// If this edge has already been created or will be created by
Chris@16:   /// someone else, or if someone threw an exception, we will not
Chris@16:   /// create the edge now.
Chris@16:   if (committed || std::uncaught_exception())
Chris@16:     return;
Chris@16: 
Chris@16:   committed = true;
Chris@16: 
Chris@16:   if (vertex_name_type* v_name = boost::get<vertex_name_type>(&v)) {
Chris@16:     // We haven't resolved the target vertex to a descriptor yet, so
Chris@16:     // it must not be local. Send a message to the owner of the target
Chris@16:     // of the edge. If the owner of the target does not happen to own
Chris@16:     // the source, it will resolve the target to a vertex descriptor
Chris@16:     // and pass the message along to the owner of the source. 
Chris@16:     if (vertex_name_type* u_name = boost::get<vertex_name_type>(&u))
Chris@16:       send(self.process_group(), self.distribution_(*v_name),
Chris@16:            BGL_NAMED_GRAPH::msg_add_edge_name_name_with_property,
Chris@16:            make_pair_with_property(*u_name, *v_name, property));
Chris@16:     else
Chris@16:       send(self.process_group(), self.distribution_(*v_name),
Chris@16:            BGL_NAMED_GRAPH::msg_add_edge_vertex_name_with_property,
Chris@16:            make_pair_with_property(boost::get<vertex_descriptor>(u), *v_name, 
Chris@16:                                    property));
Chris@16:   } else {
Chris@16:     if (vertex_name_type* u_name = boost::get<vertex_name_type>(&u))
Chris@16:       // We haven't resolved the source vertex to a descriptor yet, so
Chris@16:       // it must not be local. Send a message to the owner of the
Chris@16:       // source vertex requesting the edge addition.
Chris@16:       send(self.process_group(), self.distribution_(*u_name),
Chris@16:            BGL_NAMED_GRAPH::msg_add_edge_name_vertex_with_property,
Chris@16:            make_pair_with_property(*u_name, boost::get<vertex_descriptor>(v), 
Chris@16:                                    property));
Chris@16:     else
Chris@16:       // We have descriptors for both of the vertices, either of which
Chris@16:       // may be remote or local. Tell the owner of the source vertex
Chris@16:       // to add the edge (it may be us!).
Chris@16:       add_edge(boost::get<vertex_descriptor>(u), 
Chris@16:                boost::get<vertex_descriptor>(v), 
Chris@16:                property,
Chris@16:                self.derived());
Chris@16:   }
Chris@16: }
Chris@16: 
Chris@16: template<BGL_NAMED_GRAPH_PARAMS>
Chris@16: std::pair<typename graph_traits<Graph>::edge_descriptor, bool>
Chris@16: BGL_NAMED_GRAPH::lazy_add_edge_with_property::commit() const
Chris@16: {
Chris@16:   using boost::detail::parallel::make_pair_with_property;
Chris@16:   typedef typename BGL_NAMED_GRAPH::process_id_type process_id_type;
Chris@16:   BOOST_ASSERT(!committed);
Chris@16:   committed = true;
Chris@16: 
Chris@16:   /// The result we will return, if we are sending a message to
Chris@16:   /// request that someone else add the edge.
Chris@16:   boost::parallel::detail::untracked_pair<edge_descriptor, bool> result;
Chris@16: 
Chris@16:   /// The owner of the vertex "u"
Chris@16:   process_id_type u_owner;
Chris@16: 
Chris@16:   process_id_type rank = process_id(self.process_group());
Chris@16:   if (const vertex_name_type* u_name = boost::get<vertex_name_type>(&u)) {
Chris@16:     /// We haven't resolved the source vertex to a descriptor yet, so
Chris@16:     /// it must not be local. 
Chris@16:     u_owner = self.named_distribution()(*u_name);
Chris@16: 
Chris@16:     /// Send a message to the remote vertex requesting that it add the
Chris@16:     /// edge. The message differs depending on whether we have a
Chris@16:     /// vertex name or a vertex descriptor for the target.
Chris@16:     if (const vertex_name_type* v_name = boost::get<vertex_name_type>(&v))
Chris@16:       send_oob_with_reply
Chris@16:         (self.process_group(), u_owner,
Chris@16:          BGL_NAMED_GRAPH::msg_add_edge_name_name_with_reply_and_property,
Chris@16:          make_pair_with_property(*u_name, *v_name, property),
Chris@16:          result);
Chris@16:     else
Chris@16:       send_oob_with_reply
Chris@16:         (self.process_group(), u_owner,
Chris@16:          BGL_NAMED_GRAPH::msg_add_edge_name_vertex_with_reply_and_property,
Chris@16:          make_pair_with_property(*u_name, 
Chris@16:                                  boost::get<vertex_descriptor>(v),
Chris@16:                                  property),
Chris@16:          result);
Chris@16:   } else {
Chris@16:     /// We have resolved the source vertex to a descriptor, which may
Chris@16:     /// either be local or remote.
Chris@16:     u_owner 
Chris@16:       = get(vertex_owner, self.derived(),
Chris@16:             boost::get<vertex_descriptor>(u));
Chris@16:     if (u_owner == rank) {
Chris@16:       /// The source is local. If we need to, resolve the target vertex.
Chris@16:       if (const vertex_name_type* v_name = boost::get<vertex_name_type>(&v))
Chris@16:         v = add_vertex(*v_name, self.derived());
Chris@16: 
Chris@16:       /// Add the edge using vertex descriptors
Chris@16:       return add_edge(boost::get<vertex_descriptor>(u), 
Chris@16:                       boost::get<vertex_descriptor>(v), 
Chris@16:                       property,
Chris@16:                       self.derived());
Chris@16:     } else {
Chris@16:       /// The source is remote. Just send a message to its owner
Chris@16:       /// requesting that the owner add the new edge, either directly
Chris@16:       /// or via the derived class's add_edge function.
Chris@16:       if (const vertex_name_type* v_name = boost::get<vertex_name_type>(&v))
Chris@16:         send_oob_with_reply
Chris@16:           (self.process_group(), u_owner,
Chris@16:            BGL_NAMED_GRAPH::msg_add_edge_vertex_name_with_reply_and_property,
Chris@16:            make_pair_with_property(boost::get<vertex_descriptor>(u), *v_name,
Chris@16:                                    property),
Chris@16:            result);
Chris@16:       else
Chris@16:         return add_edge(boost::get<vertex_descriptor>(u), 
Chris@16:                         boost::get<vertex_descriptor>(v), 
Chris@16:                         property,
Chris@16:                         self.derived());
Chris@16:     }
Chris@16:   }
Chris@16: 
Chris@16:   // If we get here, the edge has been added remotely and "result"
Chris@16:   // contains the result of that edge addition.
Chris@16:   return result;
Chris@16: }
Chris@16: 
Chris@16: /// Construct the named_graph with a particular process group
Chris@16: template<BGL_NAMED_GRAPH_PARAMS>
Chris@16: BGL_NAMED_GRAPH::named_graph(const process_group_type& pg)
Chris@101:   : process_group_(pg, boost::parallel::attach_distributed_object()),
Chris@16:     distribution_(pg)
Chris@16: {
Chris@16:   setup_triggers();
Chris@16: }
Chris@16: 
Chris@16: /// Construct the named_graph mixin with a particular process group
Chris@16: /// and distribution function
Chris@16: template<BGL_NAMED_GRAPH_PARAMS>
Chris@16: BGL_NAMED_GRAPH::named_graph(const process_group_type& pg,
Chris@16:                              const base_distribution_type& distribution)
Chris@101:   : process_group_(pg, boost::parallel::attach_distributed_object()),
Chris@16:     distribution_(pg, distribution)
Chris@16: {
Chris@16:   setup_triggers();
Chris@16: }
Chris@16: 
Chris@16: template<BGL_NAMED_GRAPH_PARAMS>
Chris@16: void
Chris@16: BGL_NAMED_GRAPH::setup_triggers()
Chris@16: {
Chris@16:   using boost::graph::parallel::simple_trigger;
Chris@16: 
Chris@16:   simple_trigger(process_group_, msg_add_vertex_name, this,
Chris@16:                  &named_graph::handle_add_vertex_name);
Chris@16:   simple_trigger(process_group_, msg_add_vertex_name_with_reply, this,
Chris@16:                  &named_graph::handle_add_vertex_name_with_reply);
Chris@16:   simple_trigger(process_group_, msg_find_vertex, this, 
Chris@16:                  &named_graph::handle_find_vertex);
Chris@16:   simple_trigger(process_group_, msg_add_edge_name_name, this, 
Chris@16:                  &named_graph::template handle_add_edge<vertex_name_type, 
Chris@16:                                                         vertex_name_type>);
Chris@16:   simple_trigger(process_group_, msg_add_edge_name_name_with_reply, this,
Chris@16:                  &named_graph::template handle_add_edge_with_reply
Chris@16:                    <vertex_name_type, vertex_name_type>);
Chris@16:   simple_trigger(process_group_, msg_add_edge_name_vertex, this,
Chris@16:                  &named_graph::template handle_add_edge<vertex_name_type, 
Chris@16:                                                         vertex_descriptor>);
Chris@16:   simple_trigger(process_group_, msg_add_edge_name_vertex_with_reply, this,
Chris@16:                  &named_graph::template handle_add_edge_with_reply
Chris@16:                    <vertex_name_type, vertex_descriptor>);
Chris@16:   simple_trigger(process_group_, msg_add_edge_vertex_name, this,
Chris@16:                  &named_graph::template handle_add_edge<vertex_descriptor, 
Chris@16:                                                         vertex_name_type>);
Chris@16:   simple_trigger(process_group_, msg_add_edge_vertex_name_with_reply, this,
Chris@16:                  &named_graph::template handle_add_edge_with_reply
Chris@16:                    <vertex_descriptor, vertex_name_type>);
Chris@16:   simple_trigger(process_group_, msg_add_edge_name_name_with_property, this, 
Chris@16:                  &named_graph::
Chris@16:                    template handle_add_edge_with_property<vertex_name_type, 
Chris@16:                                                           vertex_name_type>);
Chris@16:   simple_trigger(process_group_, 
Chris@16:                  msg_add_edge_name_name_with_reply_and_property, this,
Chris@16:                  &named_graph::template handle_add_edge_with_reply_and_property
Chris@16:                    <vertex_name_type, vertex_name_type>);
Chris@16:   simple_trigger(process_group_, msg_add_edge_name_vertex_with_property, this,
Chris@16:                  &named_graph::
Chris@16:                    template handle_add_edge_with_property<vertex_name_type, 
Chris@16:                                                           vertex_descriptor>);
Chris@16:   simple_trigger(process_group_, 
Chris@16:                  msg_add_edge_name_vertex_with_reply_and_property, this,
Chris@16:                  &named_graph::template handle_add_edge_with_reply_and_property
Chris@16:                    <vertex_name_type, vertex_descriptor>);
Chris@16:   simple_trigger(process_group_, msg_add_edge_vertex_name_with_property, this,
Chris@16:                  &named_graph::
Chris@16:                    template handle_add_edge_with_property<vertex_descriptor, 
Chris@16:                                                           vertex_name_type>);
Chris@16:   simple_trigger(process_group_, 
Chris@16:                  msg_add_edge_vertex_name_with_reply_and_property, this,
Chris@16:                  &named_graph::template handle_add_edge_with_reply_and_property
Chris@16:                    <vertex_descriptor, vertex_name_type>);
Chris@16: }
Chris@16: 
Chris@16: /// Retrieve the vertex associated with the given name
Chris@16: template<BGL_NAMED_GRAPH_PARAMS>
Chris@16: optional<Vertex> 
Chris@16: find_vertex(typename BGL_NAMED_GRAPH::vertex_name_type const& name,
Chris@16:             const BGL_NAMED_GRAPH& g)
Chris@16: {
Chris@16:   typedef typename Graph::local_vertex_descriptor local_vertex_descriptor;
Chris@16:   typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
Chris@16: 
Chris@16:   // Determine the owner of this name
Chris@16:   typename BGL_NAMED_GRAPH::process_id_type owner 
Chris@16:     = g.named_distribution()(name);
Chris@16: 
Chris@16:   if (owner == process_id(g.process_group())) {
Chris@16:     // The vertex is local, so search for a mapping here
Chris@16:     optional<local_vertex_descriptor> result 
Chris@16:       = find_vertex(name, g.derived().base());
Chris@16:     if (result)
Chris@16:       return Vertex(owner, *result);
Chris@16:     else
Chris@16:       return optional<Vertex>();
Chris@16:   }
Chris@16:   else {
Chris@16:     // Ask the ownering process for the name of this vertex
Chris@16:     boost::parallel::detail::untracked_pair<vertex_descriptor, bool> result;
Chris@16:     send_oob_with_reply(g.process_group(), owner, 
Chris@16:                         BGL_NAMED_GRAPH::msg_find_vertex, name, result);
Chris@16:     if (result.second)
Chris@16:       return result.first;
Chris@16:     else
Chris@16:       return optional<Vertex>();
Chris@16:   }
Chris@16: }
Chris@16: 
Chris@16: /// meta-function helping in figuring out if the given VertextProerty belongs to 
Chris@16: /// a named graph
Chris@16: template<typename VertexProperty>
Chris@16: struct not_is_named_graph
Chris@16:   : is_same<typename internal_vertex_name<VertexProperty>::type, void>
Chris@16: {};
Chris@16: 
Chris@16: /// Retrieve the vertex associated with the given name
Chris@16: template<typename Graph>
Chris@16: typename Graph::named_graph_type::lazy_add_vertex
Chris@16: add_vertex(typename Graph::vertex_name_type const& name,
Chris@16:            Graph& g, 
Chris@16:            typename disable_if<
Chris@16:               not_is_named_graph<typename Graph::vertex_property_type>, 
Chris@16:               void*>::type = 0)
Chris@16: {
Chris@16:   return typename Graph::named_graph_type::lazy_add_vertex(g, name);
Chris@16: }
Chris@16: 
Chris@16: /// Add an edge using vertex names to refer to the vertices
Chris@16: template<BGL_NAMED_GRAPH_PARAMS>
Chris@16: typename BGL_NAMED_GRAPH::lazy_add_edge
Chris@16: add_edge(typename BGL_NAMED_GRAPH::vertex_name_type const& u_name,
Chris@16:          typename BGL_NAMED_GRAPH::vertex_name_type const& v_name,
Chris@16:          BGL_NAMED_GRAPH& g)
Chris@16: {
Chris@16:   typedef typename BGL_NAMED_GRAPH::lazy_add_edge lazy_add_edge;
Chris@16:   typedef typename BGL_NAMED_GRAPH::process_id_type process_id_type;
Chris@16: 
Chris@16:   process_id_type rank = process_id(g.process_group());
Chris@16:   process_id_type u_owner = g.named_distribution()(u_name);
Chris@16:   process_id_type v_owner = g.named_distribution()(v_name);
Chris@16: 
Chris@16:   // Resolve local vertex names before building the "lazy" edge
Chris@16:   // addition structure.
Chris@16:   if (u_owner == rank && v_owner == rank)
Chris@16:     return lazy_add_edge(g, add_vertex(u_name, g), add_vertex(v_name, g));
Chris@16:   else if (u_owner == rank && v_owner != rank)
Chris@16:     return lazy_add_edge(g, add_vertex(u_name, g), v_name);
Chris@16:   else if (u_owner != rank && v_owner == rank)
Chris@16:     return lazy_add_edge(g, u_name, add_vertex(v_name, g));
Chris@16:   else
Chris@16:     return lazy_add_edge(g, u_name, v_name);
Chris@16: }
Chris@16: 
Chris@16: template<BGL_NAMED_GRAPH_PARAMS>
Chris@16: typename BGL_NAMED_GRAPH::lazy_add_edge
Chris@16: add_edge(typename BGL_NAMED_GRAPH::vertex_name_type const& u_name,
Chris@16:          typename BGL_NAMED_GRAPH::vertex_descriptor const& v,
Chris@16:          BGL_NAMED_GRAPH& g)
Chris@16: {
Chris@16:   // Resolve local vertex names before building the "lazy" edge
Chris@16:   // addition structure.
Chris@16:   typedef typename BGL_NAMED_GRAPH::lazy_add_edge lazy_add_edge;
Chris@16:   if (g.named_distribution()(u_name) == process_id(g.process_group()))
Chris@16:     return lazy_add_edge(g, add_vertex(u_name, g), v);
Chris@16:   else
Chris@16:     return lazy_add_edge(g, u_name, v);
Chris@16: }
Chris@16: 
Chris@16: template<BGL_NAMED_GRAPH_PARAMS>
Chris@16: typename BGL_NAMED_GRAPH::lazy_add_edge
Chris@16: add_edge(typename BGL_NAMED_GRAPH::vertex_descriptor const& u,
Chris@16:          typename BGL_NAMED_GRAPH::vertex_name_type const& v_name,
Chris@16:          BGL_NAMED_GRAPH& g)
Chris@16: {
Chris@16:   // Resolve local vertex names before building the "lazy" edge
Chris@16:   // addition structure.
Chris@16:   typedef typename BGL_NAMED_GRAPH::lazy_add_edge lazy_add_edge;
Chris@16:   if (g.named_distribution()(v_name) == process_id(g.process_group()))
Chris@16:     return lazy_add_edge(g, u, add_vertex(v_name, g));
Chris@16:   else
Chris@16:     return lazy_add_edge(g, u, v_name);
Chris@16: }
Chris@16: 
Chris@16: /// Add an edge using vertex names to refer to the vertices
Chris@16: template<BGL_NAMED_GRAPH_PARAMS>
Chris@16: typename BGL_NAMED_GRAPH::lazy_add_edge_with_property
Chris@16: add_edge(typename BGL_NAMED_GRAPH::vertex_name_type const& u_name,
Chris@16:          typename BGL_NAMED_GRAPH::vertex_name_type const& v_name,
Chris@16:          typename Graph::edge_property_type const& property,
Chris@16:          BGL_NAMED_GRAPH& g)
Chris@16: {
Chris@16:   typedef typename BGL_NAMED_GRAPH::lazy_add_edge_with_property lazy_add_edge;
Chris@16:   typedef typename BGL_NAMED_GRAPH::process_id_type process_id_type;
Chris@16: 
Chris@16:   process_id_type rank = process_id(g.process_group());
Chris@16:   process_id_type u_owner = g.named_distribution()(u_name);
Chris@16:   process_id_type v_owner = g.named_distribution()(v_name);
Chris@16: 
Chris@16:   // Resolve local vertex names before building the "lazy" edge
Chris@16:   // addition structure.
Chris@16:   if (u_owner == rank && v_owner == rank)
Chris@16:     return lazy_add_edge(g, add_vertex(u_name, g), add_vertex(v_name, g), 
Chris@16:                          property);
Chris@16:   else if (u_owner == rank && v_owner != rank)
Chris@16:     return lazy_add_edge(g, add_vertex(u_name, g), v_name, property);
Chris@16:   else if (u_owner != rank && v_owner == rank)
Chris@16:     return lazy_add_edge(g, u_name, add_vertex(v_name, g), property);
Chris@16:   else
Chris@16:     return lazy_add_edge(g, u_name, v_name, property);
Chris@16: }
Chris@16: 
Chris@16: template<BGL_NAMED_GRAPH_PARAMS>
Chris@16: typename BGL_NAMED_GRAPH::lazy_add_edge_with_property
Chris@16: add_edge(typename BGL_NAMED_GRAPH::vertex_name_type const& u_name,
Chris@16:          typename BGL_NAMED_GRAPH::vertex_descriptor const& v,
Chris@16:          typename Graph::edge_property_type const& property,
Chris@16:          BGL_NAMED_GRAPH& g)
Chris@16: {
Chris@16:   // Resolve local vertex names before building the "lazy" edge
Chris@16:   // addition structure.
Chris@16:   typedef typename BGL_NAMED_GRAPH::lazy_add_edge_with_property lazy_add_edge;
Chris@16:   if (g.named_distribution()(u_name) == process_id(g.process_group()))
Chris@16:     return lazy_add_edge(g, add_vertex(u_name, g), v, property);
Chris@16:   else
Chris@16:     return lazy_add_edge(g, u_name, v, property);
Chris@16: }
Chris@16: 
Chris@16: template<BGL_NAMED_GRAPH_PARAMS>
Chris@16: typename BGL_NAMED_GRAPH::lazy_add_edge_with_property
Chris@16: add_edge(typename BGL_NAMED_GRAPH::vertex_descriptor const& u,
Chris@16:          typename BGL_NAMED_GRAPH::vertex_name_type const& v_name,
Chris@16:          typename Graph::edge_property_type const& property,
Chris@16:          BGL_NAMED_GRAPH& g)
Chris@16: {
Chris@16:   // Resolve local vertex names before building the "lazy" edge
Chris@16:   // addition structure.
Chris@16:   typedef typename BGL_NAMED_GRAPH::lazy_add_edge_with_property lazy_add_edge;
Chris@16:   if (g.named_distribution()(v_name) == process_id(g.process_group()))
Chris@16:     return lazy_add_edge(g, u, add_vertex(v_name, g), property);
Chris@16:   else
Chris@16:     return lazy_add_edge(g, u, v_name, property);
Chris@16: }
Chris@16: 
Chris@16: template<BGL_NAMED_GRAPH_PARAMS>
Chris@16: typename BGL_NAMED_GRAPH::process_id_type 
Chris@16: BGL_NAMED_GRAPH::owner_by_property(const vertex_property_type& property)
Chris@16: {
Chris@16:   return distribution_(derived().base().extract_name(property));
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: /*******************************************************************
Chris@16:  * Message handlers                                                *
Chris@16:  *******************************************************************/
Chris@16: 
Chris@16: template<BGL_NAMED_GRAPH_PARAMS>
Chris@16: void 
Chris@16: BGL_NAMED_GRAPH::
Chris@16: handle_add_vertex_name(int /*source*/, int /*tag*/, 
Chris@16:                        const vertex_name_type& msg, trigger_receive_context)
Chris@16: {
Chris@16:   add_vertex(msg, derived());
Chris@16: }
Chris@16: 
Chris@16: template<BGL_NAMED_GRAPH_PARAMS>
Chris@16: typename BGL_NAMED_GRAPH::vertex_descriptor
Chris@16: BGL_NAMED_GRAPH::
Chris@16: handle_add_vertex_name_with_reply(int source, int /*tag*/, 
Chris@16:                                   const vertex_name_type& msg, 
Chris@16:                                   trigger_receive_context)
Chris@16: {
Chris@16:   return add_vertex(msg, derived());
Chris@16: }
Chris@16: 
Chris@16: template<BGL_NAMED_GRAPH_PARAMS>
Chris@16: boost::parallel::detail::untracked_pair<typename BGL_NAMED_GRAPH::vertex_descriptor, bool>
Chris@16: BGL_NAMED_GRAPH::
Chris@16: handle_find_vertex(int source, int /*tag*/, const vertex_name_type& msg, 
Chris@16:                    trigger_receive_context)
Chris@16: {
Chris@16:   using boost::parallel::detail::make_untracked_pair;
Chris@16: 
Chris@16:   optional<vertex_descriptor> v = find_vertex(msg, derived());
Chris@16:   if (v)
Chris@16:     return make_untracked_pair(*v, true);
Chris@16:   else
Chris@16:     return make_untracked_pair(graph_traits<Graph>::null_vertex(), false);
Chris@16: }
Chris@16: 
Chris@16: template<BGL_NAMED_GRAPH_PARAMS>
Chris@16: template<typename U, typename V>
Chris@16: void
Chris@16: BGL_NAMED_GRAPH::
Chris@16: handle_add_edge(int source, int /*tag*/, const boost::parallel::detail::untracked_pair<U, V>& msg, 
Chris@16:                 trigger_receive_context)
Chris@16: {
Chris@16:   add_edge(msg.first, msg.second, derived());
Chris@16: }
Chris@16: 
Chris@16: template<BGL_NAMED_GRAPH_PARAMS>
Chris@16: template<typename U, typename V>
Chris@16: boost::parallel::detail::untracked_pair<typename BGL_NAMED_GRAPH::edge_descriptor, bool>
Chris@16: BGL_NAMED_GRAPH::
Chris@16: handle_add_edge_with_reply(int source, int /*tag*/, const boost::parallel::detail::untracked_pair<U, V>& msg,
Chris@16:                            trigger_receive_context)
Chris@16: {
Chris@16:   std::pair<typename BGL_NAMED_GRAPH::edge_descriptor, bool> p =
Chris@16:     add_edge(msg.first, msg.second, derived());
Chris@16:    return p;
Chris@16: }
Chris@16: 
Chris@16: template<BGL_NAMED_GRAPH_PARAMS>
Chris@16: template<typename U, typename V>
Chris@16: void 
Chris@16: BGL_NAMED_GRAPH::
Chris@16: handle_add_edge_with_property
Chris@16:   (int source, int tag, 
Chris@16:    const pair_with_property<U, V, edge_property_type>& msg,
Chris@16:    trigger_receive_context)
Chris@16: {
Chris@16:   add_edge(msg.first, msg.second, msg.get_property(), derived());
Chris@16: }
Chris@16: 
Chris@16: template<BGL_NAMED_GRAPH_PARAMS>
Chris@16: template<typename U, typename V>
Chris@16: boost::parallel::detail::untracked_pair<typename BGL_NAMED_GRAPH::edge_descriptor, bool>
Chris@16: BGL_NAMED_GRAPH::
Chris@16: handle_add_edge_with_reply_and_property
Chris@16:   (int source, int tag, 
Chris@16:    const pair_with_property<U, V, edge_property_type>& msg,
Chris@16:    trigger_receive_context)
Chris@16: {
Chris@16:   std:: pair<typename BGL_NAMED_GRAPH::edge_descriptor, bool> p =
Chris@16:     add_edge(msg.first, msg.second, msg.get_property(), derived());
Chris@16:   return p;
Chris@16: }
Chris@16: 
Chris@16: #undef BGL_NAMED_GRAPH
Chris@16: #undef BGL_NAMED_GRAPH_PARAMS
Chris@16: 
Chris@16: /*******************************************************************
Chris@16:  * Maybe named graph mixin                                         *
Chris@16:  *******************************************************************/
Chris@16: 
Chris@16: /**
Chris@16:  * A graph mixin that can provide a mapping from names to vertices,
Chris@16:  * and use that mapping to simplify creation and manipulation of
Chris@16:  * graphs. 
Chris@16:  */
Chris@16: template<typename Graph, typename Vertex, typename Edge, typename Config, 
Chris@16:   typename ExtractName 
Chris@16:     = typename internal_vertex_name<typename Config::vertex_property_type>::type>
Chris@16: struct maybe_named_graph 
Chris@16:   : public named_graph<Graph, Vertex, Edge, Config> 
Chris@16: {
Chris@16: private:
Chris@16:   typedef named_graph<Graph, Vertex, Edge, Config> inherited;
Chris@16:   typedef typename Config::process_group_type process_group_type;
Chris@16:   
Chris@16: public:
Chris@16:   /// The type used to distribute named vertices in the graph
Chris@16:   typedef typename Config::distribution_type distribution_type;
Chris@16:   typedef typename Config::base_distribution_type base_distribution_type;
Chris@16:   
Chris@16:   explicit maybe_named_graph(const process_group_type& pg) : inherited(pg) { }
Chris@16: 
Chris@16:   maybe_named_graph(const process_group_type& pg, 
Chris@16:                     const base_distribution_type& distribution)
Chris@16:     : inherited(pg, distribution) { }  
Chris@16: 
Chris@16:   distribution_type&       distribution()       { return this->distribution_; }
Chris@16:   const distribution_type& distribution() const { return this->distribution_; }
Chris@16: };
Chris@16: 
Chris@16: /**
Chris@16:  * A graph mixin that can provide a mapping from names to vertices,
Chris@16:  * and use that mapping to simplify creation and manipulation of
Chris@16:  * graphs. This partial specialization turns off this functionality
Chris@16:  * when the @c VertexProperty does not have an internal vertex name.
Chris@16:  */
Chris@16: template<typename Graph, typename Vertex, typename Edge, typename Config>
Chris@16: struct maybe_named_graph<Graph, Vertex, Edge, Config, void> 
Chris@16: { 
Chris@16: private:
Chris@16:   typedef typename Config::process_group_type process_group_type;
Chris@16:   typedef typename Config::vertex_property_type vertex_property_type;
Chris@16:   
Chris@16: public:
Chris@16:   typedef typename process_group_type::process_id_type process_id_type;
Chris@16: 
Chris@16:   /// The type used to distribute named vertices in the graph
Chris@16:   typedef typename Config::distribution_type distribution_type;
Chris@16:   typedef typename Config::base_distribution_type base_distribution_type;
Chris@16: 
Chris@16:   explicit maybe_named_graph(const process_group_type&)  { }
Chris@16: 
Chris@16:   maybe_named_graph(const process_group_type& pg, 
Chris@16:                     const base_distribution_type& distribution) 
Chris@16:     : distribution_(pg, distribution) { }
Chris@16: 
Chris@16:   /// Notify the named_graph that we have added the given vertex. This
Chris@16:   /// is a no-op.
Chris@16:   void added_vertex(Vertex) { }
Chris@16: 
Chris@16:   /// Notify the named_graph that we are removing the given
Chris@16:   /// vertex. This is a no-op.
Chris@16:   template <typename VertexIterStability>
Chris@16:   void removing_vertex(Vertex, VertexIterStability) { }
Chris@16: 
Chris@16:   /// Notify the named_graph that we are clearing the graph
Chris@16:   void clearing_graph() { }
Chris@16: 
Chris@16:   /// Retrieve the owner of a given vertex based on the properties
Chris@16:   /// associated with that vertex. This operation just returns the
Chris@16:   /// number of the local processor, adding all vertices locally.
Chris@16:   process_id_type owner_by_property(const vertex_property_type&)
Chris@16:   {
Chris@16:     return process_id(pg);
Chris@16:   }
Chris@16: 
Chris@16:   distribution_type&       distribution()       { return distribution_; }
Chris@16:   const distribution_type& distribution() const { return distribution_; }
Chris@16: 
Chris@16: protected:
Chris@16:   /// The process group of the graph
Chris@16:   process_group_type pg;
Chris@16:   
Chris@16:   /// The distribution used for the graph
Chris@16:   distribution_type distribution_;
Chris@16: };
Chris@16: 
Chris@16: } } } // end namespace boost::graph::distributed
Chris@16: 
Chris@16: #endif // BOOST_GRAPH_DISTRIBUTED_NAMED_GRAPH_HPP