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