boost/graph/distributed/adjacency_list.hpp
// Copyright (C) 2004-2006 The Trustees of Indiana University. // Copyright (C) 2007 Douglas Gregor // 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) // Authors: Douglas Gregor // Andrew Lumsdaine #ifndef BOOST_GRAPH_DISTRIBUTED_ADJACENCY_LIST_HPP #define BOOST_GRAPH_DISTRIBUTED_ADJACENCY_LIST_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/core/uncaught_exceptions.hpp> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/properties.hpp> #include <boost/graph/graph_traits.hpp> #include <boost/graph/iteration_macros.hpp> #include <boost/graph/distributed/concepts.hpp> #include <boost/iterator/transform_iterator.hpp> #include <boost/property_map/property_map.hpp> #include <boost/property_map/parallel/parallel_property_maps.hpp> #include <boost/graph/adjacency_iterator.hpp> #include <boost/property_map/parallel/distributed_property_map.hpp> #include <boost/property_map/parallel/local_property_map.hpp> #include <boost/graph/parallel/detail/property_holders.hpp> #include <boost/mpl/if.hpp> #include <boost/type_traits/is_same.hpp> #include <boost/assert.hpp> #include <list> #include <iterator> #include <algorithm> #include <boost/limits.hpp> #include <boost/graph/parallel/properties.hpp> #include <boost/graph/parallel/distribution.hpp> #include <boost/graph/parallel/algorithm.hpp> #include <boost/graph/distributed/selector.hpp> #include <boost/graph/parallel/process_group.hpp> #include <boost/pending/container_traits.hpp> // Callbacks #include <boost/function/function2.hpp> // Serialization #include <boost/serialization/base_object.hpp> #include <boost/mpi/datatype.hpp> #include <boost/pending/property_serialize.hpp> #include <boost/graph/distributed/unsafe_serialize.hpp> // Named vertices #include <boost/graph/distributed/named_graph.hpp> #include <boost/graph/distributed/shuffled_distribution.hpp> namespace boost { /// The type used to store an identifier that uniquely names a processor. // NGE: I doubt we'll be running on more than 32768 procs for the time being typedef /*int*/ short processor_id_type; // Tell which processor the target of an edge resides on (for // directed graphs) or which processor the other end point of the // edge resides on (for undirected graphs). enum edge_target_processor_id_t { edge_target_processor_id }; BOOST_INSTALL_PROPERTY(edge, target_processor_id); // For undirected graphs, tells whether the edge is locally owned. enum edge_locally_owned_t { edge_locally_owned }; BOOST_INSTALL_PROPERTY(edge, locally_owned); // For bidirectional graphs, stores the incoming edges. enum vertex_in_edges_t { vertex_in_edges }; BOOST_INSTALL_PROPERTY(vertex, in_edges); /// Tag class for directed, distributed adjacency list struct directed_distributed_adj_list_tag : public virtual distributed_graph_tag, public virtual distributed_vertex_list_graph_tag, public virtual distributed_edge_list_graph_tag, public virtual incidence_graph_tag, public virtual adjacency_graph_tag {}; /// Tag class for bidirectional, distributed adjacency list struct bidirectional_distributed_adj_list_tag : public virtual distributed_graph_tag, public virtual distributed_vertex_list_graph_tag, public virtual distributed_edge_list_graph_tag, public virtual incidence_graph_tag, public virtual adjacency_graph_tag, public virtual bidirectional_graph_tag {}; /// Tag class for undirected, distributed adjacency list struct undirected_distributed_adj_list_tag : public virtual distributed_graph_tag, public virtual distributed_vertex_list_graph_tag, public virtual distributed_edge_list_graph_tag, public virtual incidence_graph_tag, public virtual adjacency_graph_tag, public virtual bidirectional_graph_tag {}; namespace detail { template<typename Archiver, typename Directed, typename Vertex> void serialize(Archiver& ar, edge_base<Directed, Vertex>& e, const unsigned int /*version*/) { ar & unsafe_serialize(e.m_source) & unsafe_serialize(e.m_target); } template<typename Archiver, typename Directed, typename Vertex> void serialize(Archiver& ar, edge_desc_impl<Directed, Vertex>& e, const unsigned int /*version*/) { ar & boost::serialization::base_object<edge_base<Directed, Vertex> >(e) & unsafe_serialize(e.m_eproperty); } } namespace detail { namespace parallel { /** * A distributed vertex descriptor. These descriptors contain both * the ID of the processor that owns the vertex and a local vertex * descriptor that identifies the particular vertex for that * processor. */ template<typename LocalDescriptor> struct global_descriptor { typedef LocalDescriptor local_descriptor_type; global_descriptor() : owner(), local() { } global_descriptor(processor_id_type owner, LocalDescriptor local) : owner(owner), local(local) { } processor_id_type owner; LocalDescriptor local; /** * A function object that, given a processor ID, generates * distributed vertex descriptors from local vertex * descriptors. This function object is used by the * vertex_iterator of the distributed adjacency list. */ struct generator { typedef global_descriptor<LocalDescriptor> result_type; typedef LocalDescriptor argument_type; generator() {} generator(processor_id_type owner) : owner(owner) {} result_type operator()(argument_type v) const { return result_type(owner, v); } private: processor_id_type owner; }; template<typename Archiver> void serialize(Archiver& ar, const unsigned int /*version*/) { ar & owner & unsafe_serialize(local); } }; /// Determine the process that owns the given descriptor template<typename LocalDescriptor> inline processor_id_type owner(const global_descriptor<LocalDescriptor>& v) { return v.owner; } /// Determine the local portion of the given descriptor template<typename LocalDescriptor> inline LocalDescriptor local(const global_descriptor<LocalDescriptor>& v) { return v.local; } /// Compare distributed vertex descriptors for equality template<typename LocalDescriptor> inline bool operator==(const global_descriptor<LocalDescriptor>& u, const global_descriptor<LocalDescriptor>& v) { return u.owner == v.owner && u.local == v.local; } /// Compare distributed vertex descriptors for inequality template<typename LocalDescriptor> inline bool operator!=(const global_descriptor<LocalDescriptor>& u, const global_descriptor<LocalDescriptor>& v) { return !(u == v); } template<typename LocalDescriptor> inline bool operator<(const global_descriptor<LocalDescriptor>& u, const global_descriptor<LocalDescriptor>& v) { return (u.owner) < v.owner || (u.owner == v.owner && (u.local) < v.local); } template<typename LocalDescriptor> inline bool operator<=(const global_descriptor<LocalDescriptor>& u, const global_descriptor<LocalDescriptor>& v) { return u.owner <= v.owner || (u.owner == v.owner && u.local <= v.local); } template<typename LocalDescriptor> inline bool operator>(const global_descriptor<LocalDescriptor>& u, const global_descriptor<LocalDescriptor>& v) { return v < u; } template<typename LocalDescriptor> inline bool operator>=(const global_descriptor<LocalDescriptor>& u, const global_descriptor<LocalDescriptor>& v) { return v <= u; } // DPG TBD: Add <, <=, >=, > for global descriptors /** * A Readable Property Map that extracts a global descriptor pair * from a global_descriptor. */ template<typename LocalDescriptor> struct global_descriptor_property_map { typedef std::pair<processor_id_type, LocalDescriptor> value_type; typedef value_type reference; typedef global_descriptor<LocalDescriptor> key_type; typedef readable_property_map_tag category; }; template<typename LocalDescriptor> inline std::pair<processor_id_type, LocalDescriptor> get(global_descriptor_property_map<LocalDescriptor>, global_descriptor<LocalDescriptor> x) { return std::pair<processor_id_type, LocalDescriptor>(x.owner, x.local); } /** * A Readable Property Map that extracts the owner of a global * descriptor. */ template<typename LocalDescriptor> struct owner_property_map { typedef processor_id_type value_type; typedef value_type reference; typedef global_descriptor<LocalDescriptor> key_type; typedef readable_property_map_tag category; }; template<typename LocalDescriptor> inline processor_id_type get(owner_property_map<LocalDescriptor>, global_descriptor<LocalDescriptor> x) { return x.owner; } /** * A Readable Property Map that extracts the local descriptor from * a global descriptor. */ template<typename LocalDescriptor> struct local_descriptor_property_map { typedef LocalDescriptor value_type; typedef value_type reference; typedef global_descriptor<LocalDescriptor> key_type; typedef readable_property_map_tag category; }; template<typename LocalDescriptor> inline LocalDescriptor get(local_descriptor_property_map<LocalDescriptor>, global_descriptor<LocalDescriptor> x) { return x.local; } /** * Stores an incoming edge for a bidirectional distributed * adjacency list. The user does not see this type directly, * because it is just an implementation detail. */ template<typename Edge> struct stored_in_edge { stored_in_edge(processor_id_type sp, Edge e) : source_processor(sp), e(e) {} processor_id_type source_processor; Edge e; }; /** * A distributed edge descriptor. These descriptors contain the * underlying edge descriptor, the processor IDs for both the * source and the target of the edge, and a boolean flag that * indicates which of the processors actually owns the edge. */ template<typename Edge> struct edge_descriptor { edge_descriptor(processor_id_type sp = processor_id_type(), processor_id_type tp = processor_id_type(), bool owns = false, Edge ld = Edge()) : source_processor(sp), target_processor(tp), source_owns_edge(owns), local(ld) {} processor_id_type owner() const { return source_owns_edge? source_processor : target_processor; } /// The processor that the source vertex resides on processor_id_type source_processor; /// The processor that the target vertex resides on processor_id_type target_processor; /// True when the source processor owns the edge, false when the /// target processor owns the edge. bool source_owns_edge; /// The local edge descriptor. Edge local; /** * Function object that generates edge descriptors for the * out_edge_iterator of the given distributed adjacency list * from the edge descriptors of the underlying adjacency list. */ template<typename Graph> class out_generator { typedef typename Graph::directed_selector directed_selector; public: typedef edge_descriptor<Edge> result_type; typedef Edge argument_type; out_generator() : g(0) {} explicit out_generator(const Graph& g) : g(&g) {} result_type operator()(argument_type e) const { return map(e, directed_selector()); } private: result_type map(argument_type e, directedS) const { return result_type(g->processor(), get(edge_target_processor_id, g->base(), e), true, e); } result_type map(argument_type e, bidirectionalS) const { return result_type(g->processor(), get(edge_target_processor_id, g->base(), e), true, e); } result_type map(argument_type e, undirectedS) const { return result_type(g->processor(), get(edge_target_processor_id, g->base(), e), get(edge_locally_owned, g->base(), e), e); } const Graph* g; }; /** * Function object that generates edge descriptors for the * in_edge_iterator of the given distributed adjacency list * from the edge descriptors of the underlying adjacency list. */ template<typename Graph> class in_generator { typedef typename Graph::directed_selector DirectedS; public: typedef typename boost::mpl::if_<is_same<DirectedS, bidirectionalS>, stored_in_edge<Edge>, Edge>::type argument_type; typedef edge_descriptor<Edge> result_type; in_generator() : g(0) {} explicit in_generator(const Graph& g) : g(&g) {} result_type operator()(argument_type e) const { return map(e, DirectedS()); } private: /** * For a bidirectional graph, we just generate the appropriate * edge. No tricks. */ result_type map(argument_type e, bidirectionalS) const { return result_type(e.source_processor, g->processor(), true, e.e); } /** * For an undirected graph, we generate descriptors for the * incoming edges by swapping the source/target of the * underlying edge descriptor (a hack). The target processor * ID on the edge is actually the source processor for this * edge, and our processor is the target processor. If the * edge is locally owned, then it is owned by the target (us); * otherwise it is owned by the source. */ result_type map(argument_type e, undirectedS) const { typename Graph::local_edge_descriptor local_edge(e); // TBD: This is a very, VERY lame hack that takes advantage // of our knowledge of the internals of the BGL // adjacency_list. There should be a cleaner way to handle // this... using std::swap; swap(local_edge.m_source, local_edge.m_target); return result_type(get(edge_target_processor_id, g->base(), e), g->processor(), !get(edge_locally_owned, g->base(), e), local_edge); } const Graph* g; }; private: friend class boost::serialization::access; template<typename Archiver> void serialize(Archiver& ar, const unsigned int /*version*/) { ar & source_processor & target_processor & source_owns_edge & local; } }; /// Determine the process that owns this edge template<typename Edge> inline processor_id_type owner(const edge_descriptor<Edge>& e) { return e.source_owns_edge? e.source_processor : e.target_processor; } /// Determine the local descriptor for this edge. template<typename Edge> inline Edge local(const edge_descriptor<Edge>& e) { return e.local; } /** * A Readable Property Map that extracts the owner and local * descriptor of an edge descriptor. */ template<typename Edge> struct edge_global_property_map { typedef std::pair<processor_id_type, Edge> value_type; typedef value_type reference; typedef edge_descriptor<Edge> key_type; typedef readable_property_map_tag category; }; template<typename Edge> inline std::pair<processor_id_type, Edge> get(edge_global_property_map<Edge>, const edge_descriptor<Edge>& e) { typedef std::pair<processor_id_type, Edge> result_type; return result_type(e.source_owns_edge? e.source_processor /* target owns edge*/: e.target_processor, e.local); } /** * A Readable Property Map that extracts the owner of an edge * descriptor. */ template<typename Edge> struct edge_owner_property_map { typedef processor_id_type value_type; typedef value_type reference; typedef edge_descriptor<Edge> key_type; typedef readable_property_map_tag category; }; template<typename Edge> inline processor_id_type get(edge_owner_property_map<Edge>, const edge_descriptor<Edge>& e) { return e.source_owns_edge? e.source_processor : e.target_processor; } /** * A Readable Property Map that extracts the local descriptor from * an edge descriptor. */ template<typename Edge> struct edge_local_property_map { typedef Edge value_type; typedef value_type reference; typedef edge_descriptor<Edge> key_type; typedef readable_property_map_tag category; }; template<typename Edge> inline Edge get(edge_local_property_map<Edge>, const edge_descriptor<Edge>& e) { return e.local; } /** Compare distributed edge descriptors for equality. * * \todo need edge_descriptor to know if it is undirected so we * can compare both ways. */ template<typename Edge> inline bool operator==(const edge_descriptor<Edge>& e1, const edge_descriptor<Edge>& e2) { return (e1.source_processor == e2.source_processor && e1.target_processor == e2.target_processor && e1.local == e2.local); } /// Compare distributed edge descriptors for inequality. template<typename Edge> inline bool operator!=(const edge_descriptor<Edge>& e1, const edge_descriptor<Edge>& e2) { return !(e1 == e2); } /** * Configuration for the distributed adjacency list. We use this * parameter to store all of the configuration details for the * implementation of the distributed adjacency list, which allows us to * get at the distribution type in the maybe_named_graph. */ template<typename OutEdgeListS, typename ProcessGroup, typename InVertexListS, typename InDistribution, typename DirectedS, typename VertexProperty, typename EdgeProperty, typename GraphProperty, typename EdgeListS> struct adjacency_list_config { typedef typename mpl::if_<is_same<InVertexListS, defaultS>, vecS, InVertexListS>::type VertexListS; /// Introduce the target processor ID property for each edge typedef property<edge_target_processor_id_t, processor_id_type, EdgeProperty> edge_property_with_id; /// For undirected graphs, introduce the locally-owned property for edges typedef typename boost::mpl::if_<is_same<DirectedS, undirectedS>, property<edge_locally_owned_t, bool, edge_property_with_id>, edge_property_with_id>::type base_edge_property_type; /// The edge descriptor type for the local subgraph typedef typename adjacency_list_traits<OutEdgeListS, VertexListS, directedS>::edge_descriptor local_edge_descriptor; /// For bidirectional graphs, the type of an incoming stored edge typedef stored_in_edge<local_edge_descriptor> bidir_stored_edge; /// The container type that will store incoming edges for a /// bidirectional graph. typedef typename container_gen<EdgeListS, bidir_stored_edge>::type in_edge_list_type; // Bidirectional graphs have an extra vertex property to store // the incoming edges. typedef typename boost::mpl::if_<is_same<DirectedS, bidirectionalS>, property<vertex_in_edges_t, in_edge_list_type, VertexProperty>, VertexProperty>::type base_vertex_property_type; // The type of the distributed adjacency list typedef adjacency_list<OutEdgeListS, distributedS<ProcessGroup, VertexListS, InDistribution>, DirectedS, VertexProperty, EdgeProperty, GraphProperty, EdgeListS> graph_type; // The type of the underlying adjacency list implementation typedef adjacency_list<OutEdgeListS, VertexListS, directedS, base_vertex_property_type, base_edge_property_type, GraphProperty, EdgeListS> inherited; typedef InDistribution in_distribution_type; typedef typename inherited::vertices_size_type vertices_size_type; typedef typename ::boost::graph::distributed::select_distribution< in_distribution_type, VertexProperty, vertices_size_type, ProcessGroup>::type base_distribution_type; typedef ::boost::graph::distributed::shuffled_distribution< base_distribution_type> distribution_type; typedef VertexProperty vertex_property_type; typedef EdgeProperty edge_property_type; typedef ProcessGroup process_group_type; typedef VertexListS vertex_list_selector; typedef OutEdgeListS out_edge_list_selector; typedef DirectedS directed_selector; typedef GraphProperty graph_property_type; typedef EdgeListS edge_list_selector; }; // Maybe initialize the indices of each vertex template<typename IteratorPair, typename VertexIndexMap> void maybe_initialize_vertex_indices(IteratorPair p, VertexIndexMap to_index, read_write_property_map_tag) { typedef typename property_traits<VertexIndexMap>::value_type index_t; index_t next_index = 0; while (p.first != p.second) put(to_index, *p.first++, next_index++); } template<typename IteratorPair, typename VertexIndexMap> inline void maybe_initialize_vertex_indices(IteratorPair p, VertexIndexMap to_index, readable_property_map_tag) { // Do nothing } template<typename IteratorPair, typename VertexIndexMap> inline void maybe_initialize_vertex_indices(IteratorPair p, VertexIndexMap to_index) { typedef typename property_traits<VertexIndexMap>::category category; maybe_initialize_vertex_indices(p, to_index, category()); } template<typename IteratorPair> inline void maybe_initialize_vertex_indices(IteratorPair p, ::boost::detail::error_property_not_found) { } /*********************************************************************** * Message Payloads * ***********************************************************************/ /** * Data stored with a msg_add_edge message, which requests the * remote addition of an edge. */ template<typename Vertex, typename LocalVertex> struct msg_add_edge_data { msg_add_edge_data() { } msg_add_edge_data(Vertex source, Vertex target) : source(source.local), target(target) { } /// The source of the edge; the processor will be the /// receiving processor. LocalVertex source; /// The target of the edge. Vertex target; template<typename Archiver> void serialize(Archiver& ar, const unsigned int /*version*/) { ar & unsafe_serialize(source) & target; } }; /** * Like @c msg_add_edge_data, but also includes a user-specified * property value to be attached to the edge. */ template<typename Vertex, typename LocalVertex, typename EdgeProperty> struct msg_add_edge_with_property_data : msg_add_edge_data<Vertex, LocalVertex>, maybe_store_property<EdgeProperty> { private: typedef msg_add_edge_data<Vertex, LocalVertex> inherited_data; typedef maybe_store_property<EdgeProperty> inherited_property; public: msg_add_edge_with_property_data() { } msg_add_edge_with_property_data(Vertex source, Vertex target, const EdgeProperty& property) : inherited_data(source, target), inherited_property(property) { } template<typename Archiver> void serialize(Archiver& ar, const unsigned int /*version*/) { ar & boost::serialization::base_object<inherited_data>(*this) & boost::serialization::base_object<inherited_property>(*this); } }; //------------------------------------------------------------------------ // Distributed adjacency list property map details /** * Metafunction that extracts the given property from the given * distributed adjacency list type. This could be implemented much * more cleanly, but even newer versions of GCC (e.g., 3.2.3) * cannot properly handle partial specializations involving * enumerator types. */ template<typename Property> struct get_adj_list_pmap { template<typename Graph> struct apply { typedef Graph graph_type; typedef typename graph_type::process_group_type process_group_type; typedef typename graph_type::inherited base_graph_type; typedef typename property_map<base_graph_type, Property>::type local_pmap; typedef typename property_map<base_graph_type, Property>::const_type local_const_pmap; typedef graph_traits<graph_type> traits; typedef typename graph_type::local_vertex_descriptor local_vertex; typedef typename property_traits<local_pmap>::key_type local_key_type; typedef typename property_traits<local_pmap>::value_type value_type; typedef typename property_map<Graph, vertex_global_t>::const_type vertex_global_map; typedef typename property_map<Graph, edge_global_t>::const_type edge_global_map; typedef typename mpl::if_c<(is_same<local_key_type, local_vertex>::value), vertex_global_map, edge_global_map>::type global_map; public: typedef ::boost::parallel::distributed_property_map< process_group_type, global_map, local_pmap> type; typedef ::boost::parallel::distributed_property_map< process_group_type, global_map, local_const_pmap> const_type; }; }; /** * The local vertex index property map is actually a mapping from * the local vertex descriptors to vertex indices. */ template<> struct get_adj_list_pmap<vertex_local_index_t> { template<typename Graph> struct apply : ::boost::property_map<typename Graph::inherited, vertex_index_t> { }; }; /** * The vertex index property map maps from global descriptors * (e.g., the vertex descriptor of a distributed adjacency list) * to the underlying local index. It is not valid to use this * property map with nonlocal descriptors. */ template<> struct get_adj_list_pmap<vertex_index_t> { template<typename Graph> struct apply { private: typedef typename property_map<Graph, vertex_global_t>::const_type global_map; typedef property_map<typename Graph::inherited, vertex_index_t> local; public: typedef local_property_map<typename Graph::process_group_type, global_map, typename local::type> type; typedef local_property_map<typename Graph::process_group_type, global_map, typename local::const_type> const_type; }; }; /** * The vertex owner property map maps from vertex descriptors to * the processor that owns the vertex. */ template<> struct get_adj_list_pmap<vertex_global_t> { template<typename Graph> struct apply { private: typedef typename Graph::local_vertex_descriptor local_vertex_descriptor; public: typedef global_descriptor_property_map<local_vertex_descriptor> type; typedef type const_type; }; }; /** * The vertex owner property map maps from vertex descriptors to * the processor that owns the vertex. */ template<> struct get_adj_list_pmap<vertex_owner_t> { template<typename Graph> struct apply { private: typedef typename Graph::local_vertex_descriptor local_vertex_descriptor; public: typedef owner_property_map<local_vertex_descriptor> type; typedef type const_type; }; }; /** * The vertex local property map maps from vertex descriptors to * the local descriptor for that vertex. */ template<> struct get_adj_list_pmap<vertex_local_t> { template<typename Graph> struct apply { private: typedef typename Graph::local_vertex_descriptor local_vertex_descriptor; public: typedef local_descriptor_property_map<local_vertex_descriptor> type; typedef type const_type; }; }; /** * The edge global property map maps from edge descriptors to * a pair of the owning processor and local descriptor. */ template<> struct get_adj_list_pmap<edge_global_t> { template<typename Graph> struct apply { private: typedef typename Graph::local_edge_descriptor local_edge_descriptor; public: typedef edge_global_property_map<local_edge_descriptor> type; typedef type const_type; }; }; /** * The edge owner property map maps from edge descriptors to * the processor that owns the edge. */ template<> struct get_adj_list_pmap<edge_owner_t> { template<typename Graph> struct apply { private: typedef typename Graph::local_edge_descriptor local_edge_descriptor; public: typedef edge_owner_property_map<local_edge_descriptor> type; typedef type const_type; }; }; /** * The edge local property map maps from edge descriptors to * the local descriptor for that edge. */ template<> struct get_adj_list_pmap<edge_local_t> { template<typename Graph> struct apply { private: typedef typename Graph::local_edge_descriptor local_edge_descriptor; public: typedef edge_local_property_map<local_edge_descriptor> type; typedef type const_type; }; }; //------------------------------------------------------------------------ // Directed graphs do not have in edges, so this is a no-op template<typename Graph> inline void remove_in_edge(typename Graph::edge_descriptor, Graph&, directedS) { } // Bidirectional graphs have in edges stored in the // vertex_in_edges property. template<typename Graph> inline void remove_in_edge(typename Graph::edge_descriptor e, Graph& g, bidirectionalS) { typedef typename Graph::in_edge_list_type in_edge_list_type; in_edge_list_type& in_edges = get(vertex_in_edges, g.base())[target(e, g).local]; typename in_edge_list_type::iterator i = in_edges.begin(); while (i != in_edges.end() && !(i->source_processor == source(e, g).owner) && i->e == e.local) ++i; BOOST_ASSERT(i != in_edges.end()); in_edges.erase(i); } // Undirected graphs have in edges stored as normal edges. template<typename Graph> inline void remove_in_edge(typename Graph::edge_descriptor e, Graph& g, undirectedS) { typedef typename Graph::inherited base_type; typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; // TBD: can we make this more efficient? // Removing edge (v, u). v is local base_type& bg = g.base(); vertex_descriptor u = source(e, g); vertex_descriptor v = target(e, g); if (v.owner != process_id(g.process_group())) { using std::swap; swap(u, v); } typename graph_traits<base_type>::out_edge_iterator ei, ei_end; for (boost::tie(ei, ei_end) = out_edges(v.local, bg); ei != ei_end; ++ei) { if (target(*ei, g.base()) == u.local // TBD: deal with parallel edges properly && *ei == e && get(edge_target_processor_id, bg, *ei) == u.owner) { remove_edge(ei, bg); return; } } if (v.owner == process_id(g.process_group())) { } } //------------------------------------------------------------------------ // Lazy addition of edges // Work around the fact that an adjacency_list with vecS vertex // storage automatically adds edges when the descriptor is // out-of-range. template <class Graph, class Config, class Base> inline std::pair<typename Config::edge_descriptor, bool> add_local_edge(typename Config::vertex_descriptor u, typename Config::vertex_descriptor v, const typename Config::edge_property_type& p, vec_adj_list_impl<Graph, Config, Base>& g_) { adj_list_helper<Config, Base>& g = g_; return add_edge(u, v, p, g); } template <class Graph, class Config, class Base> inline std::pair<typename Config::edge_descriptor, bool> add_local_edge(typename Config::vertex_descriptor u, typename Config::vertex_descriptor v, const typename Config::edge_property_type& p, boost::adj_list_impl<Graph, Config, Base>& g) { return add_edge(u, v, p, g); } template <class EdgeProperty,class EdgeDescriptor> struct msg_nonlocal_edge_data : public detail::parallel::maybe_store_property<EdgeProperty> { typedef EdgeProperty edge_property_type; typedef EdgeDescriptor local_edge_descriptor; typedef detail::parallel::maybe_store_property<edge_property_type> inherited; msg_nonlocal_edge_data() {} msg_nonlocal_edge_data(local_edge_descriptor e, const edge_property_type& p) : inherited(p), e(e) { } local_edge_descriptor e; template<typename Archiver> void serialize(Archiver& ar, const unsigned int /*version*/) { ar & boost::serialization::base_object<inherited>(*this) & e; } }; template <class EdgeDescriptor> struct msg_remove_edge_data { typedef EdgeDescriptor edge_descriptor; msg_remove_edge_data() {} explicit msg_remove_edge_data(edge_descriptor e) : e(e) {} edge_descriptor e; template<typename Archiver> void serialize(Archiver& ar, const unsigned int /*version*/) { ar & e; } }; } } // end namespace detail::parallel /** * Adjacency list traits for a distributed adjacency list. Contains * the vertex and edge descriptors, the directed-ness, and the * parallel edges typedefs. */ template<typename OutEdgeListS, typename ProcessGroup, typename InVertexListS, typename InDistribution, typename DirectedS> struct adjacency_list_traits<OutEdgeListS, distributedS<ProcessGroup, InVertexListS, InDistribution>, DirectedS> { private: typedef typename mpl::if_<is_same<InVertexListS, defaultS>, vecS, InVertexListS>::type VertexListS; typedef adjacency_list_traits<OutEdgeListS, VertexListS, directedS> base_type; public: typedef typename base_type::vertex_descriptor local_vertex_descriptor; typedef typename base_type::edge_descriptor local_edge_descriptor; typedef typename boost::mpl::if_<typename DirectedS::is_bidir_t, bidirectional_tag, typename boost::mpl::if_<typename DirectedS::is_directed_t, directed_tag, undirected_tag >::type >::type directed_category; typedef typename parallel_edge_traits<OutEdgeListS>::type edge_parallel_category; typedef detail::parallel::global_descriptor<local_vertex_descriptor> vertex_descriptor; typedef detail::parallel::edge_descriptor<local_edge_descriptor> edge_descriptor; }; #define PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS \ typename OutEdgeListS, typename ProcessGroup, typename InVertexListS, \ typename InDistribution, typename DirectedS, typename VertexProperty, \ typename EdgeProperty, typename GraphProperty, typename EdgeListS #define PBGL_DISTRIB_ADJLIST_TYPE \ adjacency_list<OutEdgeListS, \ distributedS<ProcessGroup, InVertexListS, InDistribution>, \ DirectedS, VertexProperty, EdgeProperty, GraphProperty, \ EdgeListS> #define PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG \ typename OutEdgeListS, typename ProcessGroup, typename InVertexListS, \ typename InDistribution, typename VertexProperty, \ typename EdgeProperty, typename GraphProperty, typename EdgeListS #define PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(directed) \ adjacency_list<OutEdgeListS, \ distributedS<ProcessGroup, InVertexListS, InDistribution>, \ directed, VertexProperty, EdgeProperty, GraphProperty, \ EdgeListS> /** A distributed adjacency list. * * This class template partial specialization defines a distributed * (or "partitioned") adjacency list graph. The distributed * adjacency list is similar to the standard Boost Graph Library * adjacency list, which stores a list of vertices and for each * verted the list of edges outgoing from the vertex (and, in some * cases, also the edges incoming to the vertex). The distributed * adjacency list differs in that it partitions the graph into * several subgraphs that are then divided among different * processors (or nodes within a cluster). The distributed adjacency * list attempts to maintain a high degree of compatibility with the * standard, non-distributed adjacency list. * * The graph is partitioned by vertex, with each processor storing * all of the required information for a particular subset of the * vertices, including vertex properties, outgoing edges, and (for * bidirectional graphs) incoming edges. This information is * accessible only on the processor that owns the vertex: for * instance, if processor 0 owns vertex @c v, no other processor can * directly access the properties of @c v or enumerate its outgoing * edges. * * Edges in a graph may be entirely local (connecting two local * vertices), but more often it is the case that edges are * non-local, meaning that the two vertices they connect reside in * different processes. Edge properties are stored with the * originating vertex for directed and bidirectional graphs, and are * therefore only accessible from the processor that owns the * originating vertex. Other processors may query the source and * target of the edge, but cannot access its properties. This is * particularly interesting when accessing the incoming edges of a * bidirectional graph, which are not guaranteed to be stored on the * processor that is able to perform the iteration. For undirected * graphs the situation is more complicated, since no vertex clearly * owns the edges: the list of edges incident to a vertex may * contain a mix of local and non-local edges. * * The distributed adjacency list is able to model several of the * existing Graph concepts. It models the Graph concept because it * exposes vertex and edge descriptors in the normal way; these * descriptors model the GlobalDescriptor concept (because they have * an owner and a local descriptor), and as such the distributed * adjacency list models the DistributedGraph concept. The adjacency * list also models the IncidenceGraph and AdjacencyGraph concepts, * although this is only true so long as the domain of the valid * expression arguments are restricted to vertices and edges stored * locally. Likewise, bidirectional and undirected distributed * adjacency lists model the BidirectionalGraph concept (vertex and * edge domains must be respectived) and the distributed adjacency * list models the MutableGraph concept (vertices and edges can only * be added or removed locally). T he distributed adjacency list * does not, however, model the VertexListGraph or EdgeListGraph * concepts, because we can not efficiently enumerate all vertices * or edges in the graph. Instead, the local subsets of vertices and * edges can be enumerated (with the same syntax): the distributed * adjacency list therefore models the DistributedVertexListGraph * and DistributedEdgeListGraph concepts, because concurrent * iteration over all of the vertices or edges stored on each * processor will visit each vertex or edge. * * The distributed adjacency list is distinguished from the * non-distributed version by the vertex list descriptor, which will * be @c distributedS<ProcessGroup,VertexListS>. Here, * the VertexListS type plays the same role as the VertexListS type * in the non-distributed adjacency list: it allows one to select * the data structure that will be used to store the local * vertices. The ProcessGroup type, on the other hand, is unique to * distributed data structures: it is the type that abstracts a * group of cooperating processes, and it used for process * identification, communication, and synchronization, among other * things. Different process group types represent different * communication mediums (e.g., MPI, PVM, TCP) or different models * of communication (LogP, CGM, BSP, synchronous, etc.). This * distributed adjacency list assumes a model based on non-blocking * sends. * * Distribution of vertices across different processors is * accomplished in two different ways. When initially constructing * the graph, the user may provide a distribution object (that * models the Distribution concept), which will determine the * distribution of vertices to each process. Additionally, the @c * add_vertex and @c add_edge operations add vertices or edges * stored on the local processor. For @c add_edge, this is * accomplished by requiring that the source vertex of the new edge * be local to the process executing @c add_edge. * * Internal properties of a distributed adjacency list are * accessible in the same manner as internal properties for a * non-distributed adjacency list for local vertices or * edges. Access to properties for remote vertices or edges occurs * with the same syntax, but involve communication with the owner of * the information: for more information, refer to class template * @ref distributed_property_map, which manages distributed * property maps. Note that the distributed property maps created * for internal properties determine their reduction operation via * the metafunction @ref property_reduce, which for the vast * majority of uses is correct behavior. * * Communication among the processes coordinating on a particular * distributed graph relies on non-blocking message passing along * with synchronization. Local portions of the distributed graph may * be modified concurrently, including the introduction of non-local * edges, but prior to accessing the graph it is recommended that * the @c synchronize free function be invoked on the graph to clear * up any pending interprocess communication and modifications. All * processes will then be released from the synchronization barrier * concurrently. * * \todo Determine precisely what we should do with nonlocal edges * in undirected graphs. Our parallelization of certain algorithms * relies on the ability to access edge property maps immediately * (e.g., edge_weight_t), so it may be necessary to duplicate the * edge properties in both processes (but then we need some form of * coherence protocol). * * \todo What does the user do if @c property_reduce doesn't do the * right thing? */ template<typename OutEdgeListS, typename ProcessGroup, typename InVertexListS, typename InDistribution, typename DirectedS, typename VertexProperty, typename EdgeProperty, typename GraphProperty, typename EdgeListS> class adjacency_list<OutEdgeListS, distributedS<ProcessGroup, InVertexListS, InDistribution>, DirectedS, VertexProperty, EdgeProperty, GraphProperty, EdgeListS> : // Support for named vertices public graph::distributed::maybe_named_graph< adjacency_list<OutEdgeListS, distributedS<ProcessGroup, InVertexListS, InDistribution>, DirectedS, VertexProperty, EdgeProperty, GraphProperty, EdgeListS>, typename adjacency_list_traits<OutEdgeListS, distributedS<ProcessGroup, InVertexListS, InDistribution>, DirectedS>::vertex_descriptor, typename adjacency_list_traits<OutEdgeListS, distributedS<ProcessGroup, InVertexListS, InDistribution>, DirectedS>::edge_descriptor, detail::parallel::adjacency_list_config<OutEdgeListS, ProcessGroup, InVertexListS, InDistribution, DirectedS, VertexProperty, EdgeProperty, GraphProperty, EdgeListS> > { typedef detail::parallel::adjacency_list_config<OutEdgeListS, ProcessGroup, InVertexListS, InDistribution, DirectedS, VertexProperty, EdgeProperty, GraphProperty, EdgeListS> config_type; typedef adjacency_list_traits<OutEdgeListS, distributedS<ProcessGroup, InVertexListS, InDistribution>, DirectedS> traits_type; typedef typename DirectedS::is_directed_t is_directed; typedef EdgeListS edge_list_selector; public: /// The container type that will store incoming edges for a /// bidirectional graph. typedef typename config_type::in_edge_list_type in_edge_list_type; // typedef typename inherited::edge_descriptor edge_descriptor; /// The type of the underlying adjacency list implementation typedef typename config_type::inherited inherited; /// The type of properties stored in the local subgraph /// Bidirectional graphs have an extra vertex property to store /// the incoming edges. typedef typename inherited::vertex_property_type base_vertex_property_type; /// The type of the distributed adjacency list (this type) typedef typename config_type::graph_type graph_type; /// Expose graph components and graph category typedef typename traits_type::local_vertex_descriptor local_vertex_descriptor; typedef typename traits_type::local_edge_descriptor local_edge_descriptor; typedef typename traits_type::vertex_descriptor vertex_descriptor; typedef typename traits_type::edge_descriptor edge_descriptor; typedef typename traits_type::directed_category directed_category; typedef typename inherited::edge_parallel_category edge_parallel_category; typedef typename inherited::graph_tag graph_tag; // Current implementation requires the ability to have parallel // edges in the underlying adjacency_list. Which processor each // edge refers to is attached as an internal property. TBD: // remove this restriction, which may require some rewriting. BOOST_STATIC_ASSERT((is_same<edge_parallel_category, allow_parallel_edge_tag>::value)); /** Determine the graph traversal category. * * A directed distributed adjacency list models the Distributed * Graph, Incidence Graph, and Adjacency Graph * concepts. Bidirectional and undirected graphs also model the * Bidirectional Graph concept. Note that when modeling these * concepts the domains of certain operations (e.g., in_edges) * are restricted; see the distributed adjacency_list * documentation. */ typedef typename boost::mpl::if_< is_same<DirectedS, directedS>, directed_distributed_adj_list_tag, typename boost::mpl::if_<is_same<DirectedS, bidirectionalS>, bidirectional_distributed_adj_list_tag, undirected_distributed_adj_list_tag>::type> ::type traversal_category; typedef typename inherited::degree_size_type degree_size_type; typedef typename inherited::vertices_size_type vertices_size_type; typedef typename inherited::edges_size_type edges_size_type; typedef VertexProperty vertex_property_type; typedef EdgeProperty edge_property_type; typedef typename inherited::graph_property_type graph_property_type; typedef typename inherited::vertex_bundled vertex_bundled; typedef typename inherited::edge_bundled edge_bundled; typedef typename inherited::graph_bundled graph_bundled; typedef typename container_gen<edge_list_selector, edge_descriptor>::type local_edge_list_type; private: typedef typename boost::mpl::if_<is_same<DirectedS, bidirectionalS>, typename in_edge_list_type::const_iterator, typename inherited::out_edge_iterator>::type base_in_edge_iterator; typedef typename inherited::out_edge_iterator base_out_edge_iterator; typedef typename graph_traits<inherited>::edge_iterator base_edge_iterator; typedef typename inherited::edge_property_type base_edge_property_type; typedef typename local_edge_list_type::const_iterator undirected_edge_iterator; typedef InDistribution in_distribution_type; typedef parallel::trigger_receive_context trigger_receive_context; public: /// Iterator over the (local) vertices of the graph typedef transform_iterator<typename vertex_descriptor::generator, typename inherited::vertex_iterator> vertex_iterator; /// Helper for out_edge_iterator typedef typename edge_descriptor::template out_generator<adjacency_list> out_edge_generator; /// Iterator over the outgoing edges of a vertex typedef transform_iterator<out_edge_generator, typename inherited::out_edge_iterator> out_edge_iterator; /// Helper for in_edge_iterator typedef typename edge_descriptor::template in_generator<adjacency_list> in_edge_generator; /// Iterator over the incoming edges of a vertex typedef transform_iterator<in_edge_generator, base_in_edge_iterator> in_edge_iterator; /// Iterator over the neighbors of a vertex typedef boost::adjacency_iterator< adjacency_list, vertex_descriptor, out_edge_iterator, typename std::iterator_traits<base_out_edge_iterator> ::difference_type> adjacency_iterator; /// Iterator over the (local) edges in a graph typedef typename boost::mpl::if_<is_same<DirectedS, undirectedS>, undirected_edge_iterator, transform_iterator<out_edge_generator, base_edge_iterator> >::type edge_iterator; public: /// The type of the mixin for named vertices typedef graph::distributed::maybe_named_graph<graph_type, vertex_descriptor, edge_descriptor, config_type> named_graph_mixin; /// Process group used for communication typedef ProcessGroup process_group_type; /// How to refer to a process typedef typename process_group_type::process_id_type process_id_type; /// Whether this graph is directed, undirected, or bidirectional typedef DirectedS directed_selector; // Structure used for the lazy addition of vertices struct lazy_add_vertex_with_property; friend struct lazy_add_vertex_with_property; // Structure used for the lazy addition of edges struct lazy_add_edge; friend struct lazy_add_edge; // Structure used for the lazy addition of edges with properties struct lazy_add_edge_with_property; friend struct lazy_add_edge_with_property; /// default_distribution_type is the type of the distribution used if the /// user didn't specify an explicit one typedef typename graph::distributed::select_distribution< InDistribution, VertexProperty, vertices_size_type, ProcessGroup>::default_type default_distribution_type; /// distribution_type is the type of the distribution instance stored in /// the maybe_named_graph base class typedef typename graph::distributed::select_distribution< InDistribution, VertexProperty, vertices_size_type, ProcessGroup>::type base_distribution_type; typedef graph::distributed::shuffled_distribution< base_distribution_type> distribution_type; private: // FIXME: the original adjacency_list contained this comment: // Default copy constructor and copy assignment operators OK??? TBD // but the adj_list_impl contained these declarations: adjacency_list(const adjacency_list& other); adjacency_list& operator=(const adjacency_list& other); public: adjacency_list(const ProcessGroup& pg = ProcessGroup()) : named_graph_mixin(pg, default_distribution_type(pg, 0)), m_local_graph(GraphProperty()), process_group_(pg, boost::parallel::attach_distributed_object()) { setup_triggers(); } adjacency_list(const ProcessGroup& pg, const base_distribution_type& distribution) : named_graph_mixin(pg, distribution), m_local_graph(GraphProperty()), process_group_(pg, boost::parallel::attach_distributed_object()) { setup_triggers(); } adjacency_list(const GraphProperty& g, const ProcessGroup& pg = ProcessGroup()) : named_graph_mixin(pg, default_distribution_type(pg, 0)), m_local_graph(g), process_group_(pg, boost::parallel::attach_distributed_object()) { setup_triggers(); } adjacency_list(vertices_size_type n, const GraphProperty& p, const ProcessGroup& pg, const base_distribution_type& distribution) : named_graph_mixin(pg, distribution), m_local_graph(distribution.block_size(process_id(pg), n), p), process_group_(pg, boost::parallel::attach_distributed_object()) { setup_triggers(); detail::parallel::maybe_initialize_vertex_indices(vertices(base()), get(vertex_index, base())); } adjacency_list(vertices_size_type n, const ProcessGroup& pg, const base_distribution_type& distribution) : named_graph_mixin(pg, distribution), m_local_graph(distribution.block_size(process_id(pg), n), GraphProperty()), process_group_(pg, boost::parallel::attach_distributed_object()) { setup_triggers(); detail::parallel::maybe_initialize_vertex_indices(vertices(base()), get(vertex_index, base())); } adjacency_list(vertices_size_type n, const GraphProperty& p, const ProcessGroup& pg = ProcessGroup()) : named_graph_mixin(pg, default_distribution_type(pg, n)), m_local_graph(this->distribution().block_size(process_id(pg), n), p), process_group_(pg, boost::parallel::attach_distributed_object()) { setup_triggers(); detail::parallel::maybe_initialize_vertex_indices(vertices(base()), get(vertex_index, base())); } adjacency_list(vertices_size_type n, const ProcessGroup& pg = ProcessGroup()) : named_graph_mixin(pg, default_distribution_type(pg, n)), m_local_graph(this->distribution().block_size(process_id(pg), n), GraphProperty()), process_group_(pg, boost::parallel::attach_distributed_object()) { setup_triggers(); detail::parallel::maybe_initialize_vertex_indices(vertices(base()), get(vertex_index, base())); } /* * We assume that every processor sees the same list of edges, so * they skip over any that don't originate from themselves. This * means that programs switching between a local and a distributed * graph will keep the same semantics. */ template <class EdgeIterator> adjacency_list(EdgeIterator first, EdgeIterator last, vertices_size_type n, const ProcessGroup& pg = ProcessGroup(), const GraphProperty& p = GraphProperty()) : named_graph_mixin(pg, default_distribution_type(pg, n)), m_local_graph(this->distribution().block_size(process_id(pg), n), p), process_group_(pg, boost::parallel::attach_distributed_object()) { setup_triggers(); typedef typename config_type::VertexListS vertex_list_selector; initialize(first, last, n, this->distribution(), vertex_list_selector()); detail::parallel::maybe_initialize_vertex_indices(vertices(base()), get(vertex_index, base())); } template <class EdgeIterator, class EdgePropertyIterator> adjacency_list(EdgeIterator first, EdgeIterator last, EdgePropertyIterator ep_iter, vertices_size_type n, const ProcessGroup& pg = ProcessGroup(), const GraphProperty& p = GraphProperty()) : named_graph_mixin(pg, default_distribution_type(pg, n)), m_local_graph(this->distribution().block_size(process_id(pg), n), p), process_group_(pg, boost::parallel::attach_distributed_object()) { setup_triggers(); typedef typename config_type::VertexListS vertex_list_selector; initialize(first, last, ep_iter, n, this->distribution(), vertex_list_selector()); detail::parallel::maybe_initialize_vertex_indices(vertices(base()), get(vertex_index, base())); } template <class EdgeIterator> adjacency_list(EdgeIterator first, EdgeIterator last, vertices_size_type n, const ProcessGroup& pg, const base_distribution_type& distribution, const GraphProperty& p = GraphProperty()) : named_graph_mixin(pg, distribution), m_local_graph(distribution.block_size(process_id(pg), n), p), process_group_(pg, boost::parallel::attach_distributed_object()) { setup_triggers(); typedef typename config_type::VertexListS vertex_list_selector; initialize(first, last, n, this->distribution(), vertex_list_selector()); detail::parallel::maybe_initialize_vertex_indices(vertices(base()), get(vertex_index, base())); } template <class EdgeIterator, class EdgePropertyIterator> adjacency_list(EdgeIterator first, EdgeIterator last, EdgePropertyIterator ep_iter, vertices_size_type n, const ProcessGroup& pg, const base_distribution_type& distribution, const GraphProperty& p = GraphProperty()) : named_graph_mixin(pg, distribution), m_local_graph(this->distribution().block_size(process_id(pg), n), p), process_group_(pg, boost::parallel::attach_distributed_object()) { setup_triggers(); typedef typename config_type::VertexListS vertex_list_selector; initialize(first, last, ep_iter, n, distribution, vertex_list_selector()); detail::parallel::maybe_initialize_vertex_indices(vertices(base()), get(vertex_index, base())); } ~adjacency_list() { synchronize(process_group_); } void clear() { base().clear(); local_edges_.clear(); named_graph_mixin::clearing_graph(); } void swap(adjacency_list& other) { using std::swap; base().swap(other); swap(process_group_, other.process_group_); } static vertex_descriptor null_vertex() { return vertex_descriptor(processor_id_type(0), inherited::null_vertex()); } inherited& base() { return m_local_graph; } const inherited& base() const { return m_local_graph; } processor_id_type processor() const { return process_id(process_group_); } process_group_type process_group() const { return process_group_.base(); } local_edge_list_type& local_edges() { return local_edges_; } const local_edge_list_type& local_edges() const { return local_edges_; } // Redistribute the vertices of the graph by placing each vertex // v on the processor get(vertex_to_processor, v). template<typename VertexProcessorMap> void redistribute(VertexProcessorMap vertex_to_processor); // Directly access a vertex or edge bundle vertex_bundled& operator[](vertex_descriptor v) { BOOST_ASSERT(v.owner == processor()); return base()[v.local]; } const vertex_bundled& operator[](vertex_descriptor v) const { BOOST_ASSERT(v.owner == processor()); return base()[v.local]; } edge_bundled& operator[](edge_descriptor e) { BOOST_ASSERT(e.owner() == processor()); return base()[e.local]; } const edge_bundled& operator[](edge_descriptor e) const { BOOST_ASSERT(e.owner() == processor()); return base()[e.local]; } graph_bundled& operator[](graph_bundle_t) { return get_property(*this); } graph_bundled const& operator[](graph_bundle_t) const { return get_property(*this); } template<typename OStreamConstructibleArchive> void save(std::string const& filename) const; template<typename IStreamConstructibleArchive> void load(std::string const& filename); // Callback that will be invoked whenever a new vertex is added locally boost::function<void(vertex_descriptor, adjacency_list&)> on_add_vertex; // Callback that will be invoked whenever a new edge is added locally boost::function<void(edge_descriptor, adjacency_list&)> on_add_edge; private: // Request vertex->processor mapping for neighbors <does nothing> template<typename VertexProcessorMap> void request_in_neighbors(vertex_descriptor, VertexProcessorMap, directedS) { } // Request vertex->processor mapping for neighbors <does nothing> template<typename VertexProcessorMap> void request_in_neighbors(vertex_descriptor, VertexProcessorMap, undirectedS) { } // Request vertex->processor mapping for neighbors template<typename VertexProcessorMap> void request_in_neighbors(vertex_descriptor v, VertexProcessorMap vertex_to_processor, bidirectionalS); // Clear the list of in-edges, but don't tell the remote processor void clear_in_edges_local(vertex_descriptor v, directedS) {} void clear_in_edges_local(vertex_descriptor v, undirectedS) {} void clear_in_edges_local(vertex_descriptor v, bidirectionalS) { get(vertex_in_edges, base())[v.local].clear(); } // Remove in-edges that have migrated <does nothing> template<typename VertexProcessorMap> void remove_migrated_in_edges(vertex_descriptor, VertexProcessorMap, directedS) { } // Remove in-edges that have migrated <does nothing> template<typename VertexProcessorMap> void remove_migrated_in_edges(vertex_descriptor, VertexProcessorMap, undirectedS) { } // Remove in-edges that have migrated template<typename VertexProcessorMap> void remove_migrated_in_edges(vertex_descriptor v, VertexProcessorMap vertex_to_processor, bidirectionalS); // Initialize the graph with the given edge list and vertex // distribution. This variation works only when // VertexListS=vecS, and we know how to create remote vertex // descriptors based solely on the distribution. template<typename EdgeIterator> void initialize(EdgeIterator first, EdgeIterator last, vertices_size_type, const base_distribution_type& distribution, vecS); // Initialize the graph with the given edge list, edge // properties, and vertex distribution. This variation works // only when VertexListS=vecS, and we know how to create remote // vertex descriptors based solely on the distribution. template<typename EdgeIterator, typename EdgePropertyIterator> void initialize(EdgeIterator first, EdgeIterator last, EdgePropertyIterator ep_iter, vertices_size_type, const base_distribution_type& distribution, vecS); // Initialize the graph with the given edge list, edge // properties, and vertex distribution. template<typename EdgeIterator, typename EdgePropertyIterator, typename VertexListS> void initialize(EdgeIterator first, EdgeIterator last, EdgePropertyIterator ep_iter, vertices_size_type n, const base_distribution_type& distribution, VertexListS); // Initialize the graph with the given edge list and vertex // distribution. This is nearly identical to the one below it, // for which I should be flogged. However, this version does use // slightly less memory than the version that accepts an edge // property iterator. template<typename EdgeIterator, typename VertexListS> void initialize(EdgeIterator first, EdgeIterator last, vertices_size_type n, const base_distribution_type& distribution, VertexListS); public: //--------------------------------------------------------------------- // Build a vertex property instance for the underlying adjacency // list from the given property instance of the type exposed to // the user. base_vertex_property_type build_vertex_property(const vertex_property_type& p) { return build_vertex_property(p, directed_selector()); } base_vertex_property_type build_vertex_property(const vertex_property_type& p, directedS) { return base_vertex_property_type(p); } base_vertex_property_type build_vertex_property(const vertex_property_type& p, bidirectionalS) { return base_vertex_property_type(in_edge_list_type(), p); } base_vertex_property_type build_vertex_property(const vertex_property_type& p, undirectedS) { return base_vertex_property_type(p); } //--------------------------------------------------------------------- //--------------------------------------------------------------------- // Build an edge property instance for the underlying adjacency // list from the given property instance of the type exposed to // the user. base_edge_property_type build_edge_property(const edge_property_type& p) { return build_edge_property(p, directed_selector()); } base_edge_property_type build_edge_property(const edge_property_type& p, directedS) { return base_edge_property_type(0, p); } base_edge_property_type build_edge_property(const edge_property_type& p, bidirectionalS) { return base_edge_property_type(0, p); } base_edge_property_type build_edge_property(const edge_property_type& p, undirectedS) { typedef typename base_edge_property_type::next_type edge_property_with_id; return base_edge_property_type(true, edge_property_with_id(0, p)); } //--------------------------------------------------------------------- //--------------------------------------------------------------------- // Opposite of above. edge_property_type split_edge_property(const base_edge_property_type& p) { return split_edge_property(p, directed_selector()); } edge_property_type split_edge_property(const base_edge_property_type& p, directedS) { return p.m_base; } edge_property_type split_edge_property(const base_edge_property_type& p, bidirectionalS) { return p.m_base; } edge_property_type split_edge_property(const base_edge_property_type& p, undirectedS) { return p.m_base.m_base; } //--------------------------------------------------------------------- /** The set of messages that can be transmitted and received by * a distributed adjacency list. This list will eventually be * exhaustive, but is currently quite limited. */ enum { /** * Request to add or find a vertex with the given vertex * property. The data will be a vertex_property_type * structure. */ msg_add_vertex_with_property = 0, /** * Request to add or find a vertex with the given vertex * property, and request that the remote processor return the * descriptor for the added/found edge. The data will be a * vertex_property_type structure. */ msg_add_vertex_with_property_and_reply, /** * Reply to a msg_add_vertex_* message, containing the local * vertex descriptor that was added or found. */ msg_add_vertex_reply, /** * Request to add an edge remotely. The data will be a * msg_add_edge_data structure. */ msg_add_edge, /** * Request to add an edge remotely. The data will be a * msg_add_edge_with_property_data structure. */ msg_add_edge_with_property, /** * Request to add an edge remotely and reply back with the * edge descriptor. The data will be a * msg_add_edge_data structure. */ msg_add_edge_with_reply, /** * Request to add an edge remotely and reply back with the * edge descriptor. The data will be a * msg_add_edge_with_property_data structure. */ msg_add_edge_with_property_and_reply, /** * Reply message responding to an @c msg_add_edge_with_reply * or @c msg_add_edge_with_property_and_reply messages. The * data will be a std::pair<edge_descriptor, bool>. */ msg_add_edge_reply, /** * Indicates that a nonlocal edge has been created that should * be added locally. Only valid for bidirectional and * undirected graphs. The message carries a * msg_nonlocal_edge_data structure. */ msg_nonlocal_edge, /** * Indicates that a remote edge should be removed. This * message does not exist for directedS graphs but may refer * to either in-edges or out-edges for undirectedS graphs. */ msg_remove_edge, /** * Indicates the number of vertices and edges that will be * relocated from the source processor to the target * processor. The data will be a pair<vertices_size_type, * edges_size_type>. */ msg_num_relocated }; typedef detail::parallel::msg_add_edge_data<vertex_descriptor, local_vertex_descriptor> msg_add_edge_data; typedef detail::parallel::msg_add_edge_with_property_data <vertex_descriptor, local_vertex_descriptor, edge_property_type> msg_add_edge_with_property_data; typedef boost::detail::parallel::msg_nonlocal_edge_data< edge_property_type,local_edge_descriptor> msg_nonlocal_edge_data; typedef boost::detail::parallel::msg_remove_edge_data<edge_descriptor> msg_remove_edge_data; void send_remove_edge_request(edge_descriptor e) { process_id_type dest = e.target_processor; if (e.target_processor == process_id(process_group_)) dest = e.source_processor; send(process_group_, dest, msg_remove_edge, msg_remove_edge_data(e)); } /// Process incoming messages. void setup_triggers(); void handle_add_vertex_with_property(int source, int tag, const vertex_property_type&, trigger_receive_context); local_vertex_descriptor handle_add_vertex_with_property_and_reply(int source, int tag, const vertex_property_type&, trigger_receive_context); void handle_add_edge(int source, int tag, const msg_add_edge_data& data, trigger_receive_context); boost::parallel::detail::untracked_pair<edge_descriptor, bool> handle_add_edge_with_reply(int source, int tag, const msg_add_edge_data& data, trigger_receive_context); void handle_add_edge_with_property(int source, int tag, const msg_add_edge_with_property_data&, trigger_receive_context); boost::parallel::detail::untracked_pair<edge_descriptor, bool> handle_add_edge_with_property_and_reply (int source, int tag, const msg_add_edge_with_property_data&, trigger_receive_context); void handle_nonlocal_edge(int source, int tag, const msg_nonlocal_edge_data& data, trigger_receive_context); void handle_remove_edge(int source, int tag, const msg_remove_edge_data& data, trigger_receive_context); protected: /** Add an edge (locally) that was received from another * processor. This operation is a no-op for directed graphs, * because all edges reside on the local processor. For * bidirectional graphs, this routine places the edge onto the * list of incoming edges for the target vertex. For undirected * graphs, the edge is placed along with all of the other edges * for the target vertex, but it is marked as a non-local edge * descriptor. * * \todo There is a potential problem here, where we could * unintentionally allow duplicate edges in undirected graphs * because the same edge is added on two different processors * simultaneously. It's not an issue now, because we require * that the graph allow parallel edges. Once we do support * containers such as setS or hash_setS that disallow parallel * edges we will need to deal with this. */ void add_remote_edge(const msg_nonlocal_edge_data&, processor_id_type, directedS) { } /** * \overload */ void add_remote_edge(const msg_nonlocal_edge_data& data, processor_id_type other_proc, bidirectionalS) { typedef detail::parallel::stored_in_edge<local_edge_descriptor> stored_edge; stored_edge edge(other_proc, data.e); local_vertex_descriptor v = target(data.e, base()); boost::graph_detail::push(get(vertex_in_edges, base())[v], edge); } /** * \overload */ void add_remote_edge(const msg_nonlocal_edge_data& data, processor_id_type other_proc, undirectedS) { std::pair<local_edge_descriptor, bool> edge = detail::parallel::add_local_edge(target(data.e, base()), source(data.e, base()), build_edge_property(data.get_property()), base()); BOOST_ASSERT(edge.second); put(edge_target_processor_id, base(), edge.first, other_proc); if (edge.second && on_add_edge) on_add_edge(edge_descriptor(processor(), other_proc, false, edge.first), *this); } void remove_local_edge(const msg_remove_edge_data&, processor_id_type, directedS) { } void remove_local_edge(const msg_remove_edge_data& data, processor_id_type other_proc, bidirectionalS) { /* When the source is local, we first check if the edge still * exists (it may have been deleted locally) and, if so, * remove it locally. */ vertex_descriptor src = source(data.e, *this); vertex_descriptor tgt = target(data.e, *this); if (src.owner == process_id(process_group_)) { base_out_edge_iterator ei, ei_end; for (boost::tie(ei, ei_end) = out_edges(src.local, base()); ei != ei_end; ++ei) { // TBD: can't check the descriptor here, because it could // have changed if we're allowing the removal of // edges. Egads! if (tgt.local == target(*ei, base()) && get(edge_target_processor_id, base(), *ei) == other_proc) break; } if (ei != ei_end) boost::remove_edge(ei, base()); remove_local_edge_from_list(src, tgt, undirectedS()); } else { BOOST_ASSERT(tgt.owner == process_id(process_group_)); in_edge_list_type& in_edges = get(vertex_in_edges, base())[tgt.local]; typename in_edge_list_type::iterator ei; for (ei = in_edges.begin(); ei != in_edges.end(); ++ei) { if (src.local == source(ei->e, base()) && src.owner == ei->source_processor) break; } if (ei != in_edges.end()) in_edges.erase(ei); } } void remove_local_edge(const msg_remove_edge_data& data, processor_id_type other_proc, undirectedS) { vertex_descriptor local_vertex = source(data.e, *this); vertex_descriptor remote_vertex = target(data.e, *this); if (remote_vertex.owner == process_id(process_group_)) { using std::swap; swap(local_vertex, remote_vertex); } // Remove the edge from the out-edge list, if it is there { base_out_edge_iterator ei, ei_end; for (boost::tie(ei, ei_end) = out_edges(local_vertex.local, base()); ei != ei_end; ++ei) { // TBD: can't check the descriptor here, because it could // have changed if we're allowing the removal of // edges. Egads! if (remote_vertex.local == target(*ei, base()) && get(edge_target_processor_id, base(), *ei) == other_proc) break; } if (ei != ei_end) boost::remove_edge(ei, base()); } remove_local_edge_from_list(local_vertex, remote_vertex, undirectedS()); } public: void remove_local_edge_from_list(vertex_descriptor, vertex_descriptor, directedS) { } void remove_local_edge_from_list(vertex_descriptor, vertex_descriptor, bidirectionalS) { } void remove_local_edge_from_list(vertex_descriptor src, vertex_descriptor tgt, undirectedS) { // TBD: At some point we'll be able to improve the speed here // because we'll know when the edge can't be in the local // list. { typename local_edge_list_type::iterator ei; for (ei = local_edges_.begin(); ei != local_edges_.end(); ++ei) { if ((source(*ei, *this) == src && target(*ei, *this) == tgt) || (source(*ei, *this) == tgt && target(*ei, *this) == src)) break; } if (ei != local_edges_.end()) local_edges_.erase(ei); } } private: /// The local subgraph inherited m_local_graph; /// The process group through which this distributed graph /// communicates. process_group_type process_group_; // TBD: should only be available for undirected graphs, but for // now it'll just be empty for directed and bidirectional // graphs. local_edge_list_type local_edges_; }; //------------------------------------------------------------------------ // Lazy addition of vertices template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> struct PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_vertex_with_property { /// Construct a lazy request to add a vertex lazy_add_vertex_with_property(adjacency_list& self, const vertex_property_type& property) : self(self), property(property), committed(false) { } /// Copying a lazy_add_vertex_with_property transfers the /// responsibility for adding the vertex to the newly-constructed /// object. lazy_add_vertex_with_property(const lazy_add_vertex_with_property& other) : self(other.self), property(other.property), committed(other.committed) { other.committed = true; } /// If the vertex has not yet been added, add the vertex but don't /// wait for a reply. ~lazy_add_vertex_with_property(); /// Returns commit(). operator vertex_descriptor() const { return commit(); } // Add the vertex. This operation will block if the vertex is // being added remotely. vertex_descriptor commit() const; protected: adjacency_list& self; vertex_property_type property; mutable bool committed; private: // No copy-assignment semantics void operator=(lazy_add_vertex_with_property&); }; template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_vertex_with_property:: ~lazy_add_vertex_with_property() { /// 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 = static_cast<graph_type&>(self).owner_by_property(property); if (owner == self.processor()) { /// Add the vertex locally. vertex_descriptor v(owner, add_vertex(self.build_vertex_property(property), self.base())); if (self.on_add_vertex) self.on_add_vertex(v, self); } else /// Ask the owner of this new vertex to add the vertex. We /// don't need a reply. send(self.process_group_, owner, msg_add_vertex_with_property, property); } template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_vertex_with_property:: commit() const { BOOST_ASSERT(!this->committed); this->committed = true; process_id_type owner = static_cast<graph_type&>(self).owner_by_property(property); local_vertex_descriptor local_v; if (owner == self.processor()) /// Add the vertex locally. local_v = add_vertex(self.build_vertex_property(property), self.base()); else { // Request that the remote process add the vertex immediately send_oob_with_reply(self.process_group_, owner, msg_add_vertex_with_property_and_reply, property, local_v); } vertex_descriptor v(owner, local_v); if (self.on_add_vertex) self.on_add_vertex(v, self); // Build the full vertex descriptor to return return v; } /** * 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<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> struct PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_edge { /// Construct a lazy request to add an edge lazy_add_edge(adjacency_list& self, vertex_descriptor source, vertex_descriptor target) : self(self), source(source), target(target), committed(false) { } /// Copying a lazy_add_edge transfers the responsibility for /// adding the edge to the newly-constructed object. lazy_add_edge(const lazy_add_edge& other) : self(other.self), source(other.source), target(other.target), 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: std::pair<edge_descriptor, bool> add_local_edge(const edge_property_type& property, directedS) const; std::pair<edge_descriptor, bool> add_local_edge(const edge_property_type& property, bidirectionalS) const; std::pair<edge_descriptor, bool> add_local_edge(const edge_property_type& property, undirectedS) const; adjacency_list& self; vertex_descriptor source; vertex_descriptor target; mutable bool committed; private: // No copy-assignment semantics void operator=(lazy_add_edge&); }; template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_edge::~lazy_add_edge() { /// 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 (source.owner == self.processor()) this->add_local_edge(edge_property_type(), DirectedS()); else // Request that the remote processor add an edge and, but // don't wait for a reply. send(self.process_group_, source.owner, msg_add_edge, msg_add_edge_data(source, target)); } template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> std::pair<typename PBGL_DISTRIB_ADJLIST_TYPE::edge_descriptor, bool> PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_edge::commit() const { BOOST_ASSERT(!committed); committed = true; if (source.owner == self.processor()) return this->add_local_edge(edge_property_type(), DirectedS()); else { // Request that the remote processor add an edge boost::parallel::detail::untracked_pair<edge_descriptor, bool> result; send_oob_with_reply(self.process_group_, source.owner, msg_add_edge_with_reply, msg_add_edge_data(source, target), result); return result; } } // Add a local edge into a directed graph template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> std::pair<typename PBGL_DISTRIB_ADJLIST_TYPE::edge_descriptor, bool> PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_edge:: add_local_edge(const edge_property_type& property, directedS) const { // Add the edge to the local part of the graph std::pair<local_edge_descriptor, bool> inserted = detail::parallel::add_local_edge(source.local, target.local, self.build_edge_property(property), self.base()); if (inserted.second) // Keep track of the owner of the target put(edge_target_processor_id, self.base(), inserted.first, target.owner); // Compose the edge descriptor and return the result edge_descriptor e(source.owner, target.owner, true, inserted.first); // Trigger the on_add_edge event if (inserted.second && self.on_add_edge) self.on_add_edge(e, self); return std::pair<edge_descriptor, bool>(e, inserted.second); } template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> std::pair<typename PBGL_DISTRIB_ADJLIST_TYPE::edge_descriptor, bool> PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_edge:: add_local_edge(const edge_property_type& property, bidirectionalS) const { // Add the directed edge. std::pair<edge_descriptor, bool> result = this->add_local_edge(property, directedS()); if (result.second) { if (target.owner == self.processor()) { // Edge is local, so add the stored edge to the in_edges list typedef detail::parallel::stored_in_edge<local_edge_descriptor> stored_edge; stored_edge e(self.processor(), result.first.local); boost::graph_detail::push(get(vertex_in_edges, self.base())[target.local], e); } else { // Edge is remote, so notify the target's owner that an edge // has been added. if (self.process_group_.trigger_context() == boost::parallel::trc_out_of_band) send_oob(self.process_group_, target.owner, msg_nonlocal_edge, msg_nonlocal_edge_data(result.first.local, property)); else send(self.process_group_, target.owner, msg_nonlocal_edge, msg_nonlocal_edge_data(result.first.local, property)); } } return result; } template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> std::pair<typename PBGL_DISTRIB_ADJLIST_TYPE::edge_descriptor, bool> PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_edge:: add_local_edge(const edge_property_type& property, undirectedS) const { // Add the directed edge std::pair<edge_descriptor, bool> result = this->add_local_edge(property, directedS()); if (result.second) { if (target.owner == self.processor()) { // Edge is local, so add the new edge to the list // TODO: This is not what we want to do for an undirected // edge, because we haven't linked the source and target's // representations of those edges. local_edge_descriptor return_edge = detail::parallel::add_local_edge(target.local, source.local, self.build_edge_property(property), self.base()).first; put(edge_target_processor_id, self.base(), return_edge, source.owner); } else { // Edge is remote, so notify the target's owner that an edge // has been added. if (self.process_group_.trigger_context() == boost::parallel::trc_out_of_band) send_oob(self.process_group_, target.owner, msg_nonlocal_edge, msg_nonlocal_edge_data(result.first.local, property)); else send(self.process_group_, target.owner, msg_nonlocal_edge, msg_nonlocal_edge_data(result.first.local, property)); } // Add this edge to the list of local edges graph_detail::push(self.local_edges(), result.first); } return result; } /** * Data structure returned from add_edge that will "lazily" add * the edge with its property, either when it is converted to a * pair<edge_descriptor, bool> or when the most recent copy has * been destroyed. */ template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> struct PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_edge_with_property : lazy_add_edge { /// Construct a lazy request to add an edge lazy_add_edge_with_property(adjacency_list& self, vertex_descriptor source, vertex_descriptor target, const edge_property_type& property) : lazy_add_edge(self, source, target), property(property) { } /// Copying a lazy_add_edge transfers the responsibility for /// adding the edge to the newly-constructed object. lazy_add_edge_with_property(const lazy_add_edge& other) : lazy_add_edge(other), property(other.property) { } /// 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; private: // No copy-assignment semantics void operator=(lazy_add_edge_with_property&); edge_property_type property; }; template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_edge_with_property:: ~lazy_add_edge_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 (this->committed || boost::core::uncaught_exceptions() > 0) return; this->committed = true; if (this->source.owner == this->self.processor()) // Add a local edge this->add_local_edge(property, DirectedS()); else // Request that the remote processor add an edge and, but // don't wait for a reply. send(this->self.process_group_, this->source.owner, msg_add_edge_with_property, msg_add_edge_with_property_data(this->source, this->target, property)); } template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> std::pair<typename PBGL_DISTRIB_ADJLIST_TYPE::edge_descriptor, bool> PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_edge_with_property:: commit() const { BOOST_ASSERT(!this->committed); this->committed = true; if (this->source.owner == this->self.processor()) // Add a local edge return this->add_local_edge(property, DirectedS()); else { // Request that the remote processor add an edge boost::parallel::detail::untracked_pair<edge_descriptor, bool> result; send_oob_with_reply(this->self.process_group_, this->source.owner, msg_add_edge_with_property_and_reply, msg_add_edge_with_property_data(this->source, this->target, property), result); return result; } } /** * Returns the set of vertices local to this processor. Note that * although this routine matches a valid expression of a * VertexListGraph, it does not meet the semantic requirements of * VertexListGraph because it returns only local vertices (not all * vertices). */ template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> std::pair<typename PBGL_DISTRIB_ADJLIST_TYPE ::vertex_iterator, typename PBGL_DISTRIB_ADJLIST_TYPE ::vertex_iterator> vertices(const PBGL_DISTRIB_ADJLIST_TYPE& g) { typedef typename PBGL_DISTRIB_ADJLIST_TYPE ::vertex_descriptor Vertex; typedef typename Vertex::generator generator; return std::make_pair(make_transform_iterator(vertices(g.base()).first, generator(g.processor())), make_transform_iterator(vertices(g.base()).second, generator(g.processor()))); } /** * Returns the number of vertices local to this processor. Note that * although this routine matches a valid expression of a * VertexListGraph, it does not meet the semantic requirements of * VertexListGraph because it returns only a count of local vertices * (not all vertices). */ template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> typename PBGL_DISTRIB_ADJLIST_TYPE ::vertices_size_type num_vertices(const PBGL_DISTRIB_ADJLIST_TYPE& g) { return num_vertices(g.base()); } /*************************************************************************** * Implementation of Incidence Graph concept ***************************************************************************/ /** * Returns the source of edge @param e in @param g. */ template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS, typename Edge> typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor source(const detail::parallel::edge_descriptor<Edge>& e, const PBGL_DISTRIB_ADJLIST_TYPE& g) { typedef typename PBGL_DISTRIB_ADJLIST_TYPE ::vertex_descriptor Vertex; return Vertex(e.source_processor, source(e.local, g.base())); } /** * Returns the target of edge @param e in @param g. */ template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS, typename Edge> typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor target(const detail::parallel::edge_descriptor<Edge>& e, const PBGL_DISTRIB_ADJLIST_TYPE& g) { typedef typename PBGL_DISTRIB_ADJLIST_TYPE ::vertex_descriptor Vertex; return Vertex(e.target_processor, target(e.local, g.base())); } /** * Return the set of edges outgoing from a particular vertex. The * vertex @param v must be local to the processor executing this * routine. */ template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> std::pair<typename PBGL_DISTRIB_ADJLIST_TYPE::out_edge_iterator, typename PBGL_DISTRIB_ADJLIST_TYPE::out_edge_iterator> out_edges(typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor v, const PBGL_DISTRIB_ADJLIST_TYPE& g) { BOOST_ASSERT(v.owner == g.processor()); typedef PBGL_DISTRIB_ADJLIST_TYPE impl; typedef typename impl::out_edge_generator generator; return std::make_pair( make_transform_iterator(out_edges(v.local, g.base()).first, generator(g)), make_transform_iterator(out_edges(v.local, g.base()).second, generator(g))); } /** * Return the number of edges outgoing from a particular vertex. The * vertex @param v must be local to the processor executing this * routine. */ template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> typename PBGL_DISTRIB_ADJLIST_TYPE::degree_size_type out_degree(typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor v, const PBGL_DISTRIB_ADJLIST_TYPE& g) { BOOST_ASSERT(v.owner == g.processor()); return out_degree(v.local, g.base()); } /*************************************************************************** * Implementation of Bidirectional Graph concept ***************************************************************************/ /** * Returns the set of edges incoming to a particular vertex. The * vertex @param v must be local to the processor executing this * routine. */ template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG> std::pair<typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS) ::in_edge_iterator, typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS) ::in_edge_iterator> in_edges(typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS) ::vertex_descriptor v, const PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS)& g) { BOOST_ASSERT(v.owner == g.processor()); typedef PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS) impl; typedef typename impl::inherited base_graph_type; typedef typename impl::in_edge_generator generator; typename property_map<base_graph_type, vertex_in_edges_t>::const_type in_edges = get(vertex_in_edges, g.base()); return std::make_pair(make_transform_iterator(in_edges[v.local].begin(), generator(g)), make_transform_iterator(in_edges[v.local].end(), generator(g))); } /** * \overload */ template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG> std::pair<typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS) ::in_edge_iterator, typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS) ::in_edge_iterator> in_edges(typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS) ::vertex_descriptor v, const PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS)& g) { BOOST_ASSERT(v.owner == g.processor()); typedef PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS) impl; typedef typename impl::in_edge_generator generator; return std::make_pair( make_transform_iterator(out_edges(v.local, g.base()).first, generator(g)), make_transform_iterator(out_edges(v.local, g.base()).second, generator(g))); } /** * Returns the number of edges incoming to a particular vertex. The * vertex @param v must be local to the processor executing this * routine. */ template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG> typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS)::degree_size_type in_degree(typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS) ::vertex_descriptor v, const PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS)& g) { BOOST_ASSERT(v.owner == g.processor()); return get(vertex_in_edges, g.base())[v.local].size(); } /** * \overload */ template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG> typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS)::degree_size_type in_degree(typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS) ::vertex_descriptor v, const PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS)& g) { BOOST_ASSERT(v.owner == g.processor()); return out_degree(v.local, g.base()); } /** * Returns the number of edges incident on the given vertex. The * vertex @param v must be local to the processor executing this * routine. */ template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG> typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS) ::degree_size_type degree(typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS) ::vertex_descriptor v, const PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS)& g) { BOOST_ASSERT(v.owner == g.processor()); return out_degree(v.local, g.base()); } /** * \overload */ template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG> typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS) ::degree_size_type degree(typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS) ::vertex_descriptor v, const PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS)& g) { BOOST_ASSERT(v.owner == g.processor()); return out_degree(v, g) + in_degree(v, g); } template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> typename PBGL_DISTRIB_ADJLIST_TYPE::edges_size_type num_edges(const PBGL_DISTRIB_ADJLIST_TYPE& g) { return num_edges(g.base()); } template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG> typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS)::edges_size_type num_edges(const PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS)& g) { return g.local_edges().size(); } template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> std::pair< typename PBGL_DISTRIB_ADJLIST_TYPE::edge_iterator, typename PBGL_DISTRIB_ADJLIST_TYPE::edge_iterator> edges(const PBGL_DISTRIB_ADJLIST_TYPE& g) { typedef PBGL_DISTRIB_ADJLIST_TYPE impl; typedef typename impl::out_edge_generator generator; return std::make_pair(make_transform_iterator(edges(g.base()).first, generator(g)), make_transform_iterator(edges(g.base()).second, generator(g))); } template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG> std::pair< typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS)::edge_iterator, typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS)::edge_iterator> edges(const PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS)& g) { return std::make_pair(g.local_edges().begin(), g.local_edges().end()); } template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> inline typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor vertex(typename PBGL_DISTRIB_ADJLIST_TYPE::vertices_size_type n, const PBGL_DISTRIB_ADJLIST_TYPE& g) { typedef typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor vertex_descriptor; return vertex_descriptor(g.distribution()(n), g.distribution().local(n)); } /*************************************************************************** * Access to particular edges ***************************************************************************/ template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG> std::pair< typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(directedS)::edge_descriptor, bool > edge(typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(directedS)::vertex_descriptor u, typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(directedS)::vertex_descriptor v, const PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(directedS)& g) { typedef typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(directedS) ::edge_descriptor edge_descriptor; // For directed graphs, u must be local BOOST_ASSERT(u.owner == process_id(g.process_group())); typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(directedS) ::out_edge_iterator ei, ei_end; for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) { if (target(*ei, g) == v) return std::make_pair(*ei, true); } return std::make_pair(edge_descriptor(), false); } template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> std::pair< typename PBGL_DISTRIB_ADJLIST_TYPE::edge_descriptor, bool > edge(typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor u, typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor v, const PBGL_DISTRIB_ADJLIST_TYPE& g) { typedef typename PBGL_DISTRIB_ADJLIST_TYPE ::edge_descriptor edge_descriptor; // For bidirectional and undirected graphs, u must be local or v // must be local if (u.owner == process_id(g.process_group())) { typename PBGL_DISTRIB_ADJLIST_TYPE::out_edge_iterator ei, ei_end; for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) { if (target(*ei, g) == v) return std::make_pair(*ei, true); } return std::make_pair(edge_descriptor(), false); } else if (v.owner == process_id(g.process_group())) { typename PBGL_DISTRIB_ADJLIST_TYPE::in_edge_iterator ei, ei_end; for (boost::tie(ei, ei_end) = in_edges(v, g); ei != ei_end; ++ei) { if (source(*ei, g) == u) return std::make_pair(*ei, true); } return std::make_pair(edge_descriptor(), false); } else { BOOST_ASSERT(false); abort(); } } #if 0 // TBD: not yet supported std::pair<out_edge_iterator, out_edge_iterator> edge_range(vertex_descriptor u, vertex_descriptor v, const adjacency_list& g); #endif /*************************************************************************** * Implementation of Adjacency Graph concept ***************************************************************************/ template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> std::pair<typename PBGL_DISTRIB_ADJLIST_TYPE::adjacency_iterator, typename PBGL_DISTRIB_ADJLIST_TYPE::adjacency_iterator> adjacent_vertices(typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor v, const PBGL_DISTRIB_ADJLIST_TYPE& g) { typedef typename PBGL_DISTRIB_ADJLIST_TYPE::adjacency_iterator iter; return std::make_pair(iter(out_edges(v, g).first, &g), iter(out_edges(v, g).second, &g)); } /*************************************************************************** * Implementation of Mutable Graph concept ***************************************************************************/ /************************************************************************ * add_edge ************************************************************************/ template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> typename PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_edge add_edge(typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor u, typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor v, PBGL_DISTRIB_ADJLIST_TYPE& g) { typedef typename PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_edge lazy_add_edge; return lazy_add_edge(g, u, v); } template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> typename PBGL_DISTRIB_ADJLIST_TYPE ::lazy_add_edge_with_property add_edge(typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor u, typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor v, typename PBGL_DISTRIB_ADJLIST_TYPE::edge_property_type const& p, PBGL_DISTRIB_ADJLIST_TYPE& g) { typedef typename PBGL_DISTRIB_ADJLIST_TYPE ::lazy_add_edge_with_property lazy_add_edge_with_property; return lazy_add_edge_with_property(g, u, v, p); } /************************************************************************ * * remove_edge * ************************************************************************/ template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> void remove_edge(typename PBGL_DISTRIB_ADJLIST_TYPE::edge_descriptor e, PBGL_DISTRIB_ADJLIST_TYPE& g) { BOOST_ASSERT(source(e, g).owner == g.processor() || target(e, g).owner == g.processor()); if (target(e, g).owner == g.processor()) detail::parallel::remove_in_edge(e, g, DirectedS()); if (source(e, g).owner == g.processor()) remove_edge(e.local, g.base()); g.remove_local_edge_from_list(source(e, g), target(e, g), DirectedS()); if (source(e, g).owner != g.processor() || (target(e, g).owner != g.processor() && !(is_same<DirectedS, directedS>::value))) { g.send_remove_edge_request(e); } } template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> void remove_edge(typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor u, typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor v, PBGL_DISTRIB_ADJLIST_TYPE& g) { typedef typename PBGL_DISTRIB_ADJLIST_TYPE ::edge_descriptor edge_descriptor; std::pair<edge_descriptor, bool> the_edge = edge(u, v, g); if (the_edge.second) remove_edge(the_edge.first, g); } template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> inline void remove_edge(typename PBGL_DISTRIB_ADJLIST_TYPE::out_edge_iterator ei, PBGL_DISTRIB_ADJLIST_TYPE& g) { remove_edge(*ei, g); } template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG> inline void remove_edge(typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(directedS) ::out_edge_iterator ei, PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(directedS)& g) { BOOST_ASSERT(source(*ei, g).owner == g.processor()); remove_edge(ei->local, g.base()); } /************************************************************************ * * remove_out_edge_if * ************************************************************************/ namespace parallel { namespace detail { /** * Function object that applies the underlying predicate to * determine if an out-edge should be removed. If so, either * removes the incoming edge (if it is stored locally) or sends a * message to the owner of the target requesting that it remove * the edge. */ template<typename Graph, typename Predicate> struct remove_out_edge_predicate { typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor; typedef typename Graph::local_edge_descriptor argument_type; typedef typename Graph::directed_selector directed_selector; typedef bool result_type; remove_out_edge_predicate(Graph& g, Predicate& predicate) : g(g), predicate(predicate) { } bool operator()(const argument_type& le) { typedef typename edge_descriptor::template out_generator<Graph> generator; edge_descriptor e = generator(g)(le); if (predicate(e)) { if (source(e, g).owner != target(e, g).owner && !(is_same<directed_selector, directedS>::value)) g.send_remove_edge_request(e); else ::boost::detail::parallel::remove_in_edge(e, g, directed_selector()); g.remove_local_edge_from_list(source(e, g), target(e, g), directed_selector()); return true; } else return false; } private: Graph& g; Predicate predicate; }; } } // end namespace parallel::detail template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS, typename Predicate> inline void remove_out_edge_if (typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor u, Predicate predicate, PBGL_DISTRIB_ADJLIST_TYPE& g) { typedef PBGL_DISTRIB_ADJLIST_TYPE Graph; typedef parallel::detail::remove_out_edge_predicate<Graph, Predicate> Pred; BOOST_ASSERT(u.owner == g.processor()); remove_out_edge_if(u.local, Pred(g, predicate), g.base()); } /************************************************************************ * * remove_in_edge_if * ************************************************************************/ namespace parallel { namespace detail { /** * Function object that applies the underlying predicate to * determine if an in-edge should be removed. If so, either * removes the outgoing edge (if it is stored locally) or sends a * message to the owner of the target requesting that it remove * the edge. Only required for bidirectional graphs. */ template<typename Graph, typename Predicate> struct remove_in_edge_predicate { typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor; typedef bool result_type; remove_in_edge_predicate(Graph& g, const Predicate& predicate) : g(g), predicate(predicate) { } template<typename StoredEdge> bool operator()(const StoredEdge& le) { typedef typename edge_descriptor::template in_generator<Graph> generator; edge_descriptor e = generator(g)(le); if (predicate(e)) { if (source(e, g).owner != target(e, g).owner) g.send_remove_edge_request(e); else remove_edge(source(e, g).local, target(e, g).local, g.base()); return true; } else return false; } private: Graph& g; Predicate predicate; }; } } // end namespace parallel::detail template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG, typename Predicate> inline void remove_in_edge_if (typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS) ::vertex_descriptor u, Predicate predicate, PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS)& g) { typedef PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS) Graph; typedef parallel::detail::remove_in_edge_predicate<Graph, Predicate> Pred; BOOST_ASSERT(u.owner == g.processor()); graph_detail::erase_if(get(vertex_in_edges, g.base())[u.local], Pred(g, predicate)); } template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG, typename Predicate> inline void remove_in_edge_if (typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS) ::vertex_descriptor u, Predicate predicate, PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS)& g) { remove_out_edge_if(u, predicate, g); } /************************************************************************ * * remove_edge_if * ************************************************************************/ namespace parallel { namespace detail { /** * Function object that applies the underlying predicate to * determine if a directed edge can be removed. This only applies * to directed graphs. */ template<typename Graph, typename Predicate> struct remove_directed_edge_predicate { typedef typename Graph::local_edge_descriptor argument_type; typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor; typedef bool result_type; remove_directed_edge_predicate(Graph& g, const Predicate& predicate) : g(g), predicate(predicate) { } bool operator()(const argument_type& le) { typedef typename edge_descriptor::template out_generator<Graph> generator; edge_descriptor e = generator(g)(le); return predicate(e); } private: Graph& g; Predicate predicate; }; } } // end namespace parallel::detail template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG, typename Predicate> inline void remove_edge_if(Predicate predicate, PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(directedS)& g) { typedef PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(directedS) Graph; typedef parallel::detail::remove_directed_edge_predicate<Graph, Predicate> Pred; remove_edge_if(Pred(g, predicate), g.base()); } template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG, typename Predicate> inline void remove_edge_if(Predicate predicate, PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS)& g) { typedef PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS) Graph; typedef parallel::detail::remove_out_edge_predicate<Graph, Predicate> Pred; remove_edge_if(Pred(g, predicate), g.base()); } namespace parallel { namespace detail { /** * Function object that applies the underlying predicate to * determine if an undirected edge should be removed. If so, * removes the local edges associated with the edge and * (potentially) sends a message to the remote processor that also * is removing this edge. */ template<typename Graph, typename Predicate> struct remove_undirected_edge_predicate { typedef typename graph_traits<Graph>::edge_descriptor argument_type; typedef bool result_type; remove_undirected_edge_predicate(Graph& g, Predicate& predicate) : g(g), predicate(predicate) { } bool operator()(const argument_type& e) { if (predicate(e)) { if (source(e, g).owner != target(e, g).owner) g.send_remove_edge_request(e); if (target(e, g).owner == g.processor()) ::boost::detail::parallel::remove_in_edge(e, g, undirectedS()); if (source(e, g).owner == g.processor()) remove_edge(e.local, g.base()); return true; } else return false; } private: Graph& g; Predicate predicate; }; } } // end namespace parallel::detail template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG, typename Predicate> inline void remove_edge_if(Predicate predicate, PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS)& g) { typedef PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS) Graph; typedef parallel::detail::remove_undirected_edge_predicate<Graph, Predicate> Pred; graph_detail::erase_if(g.local_edges(), Pred(g, predicate)); } /************************************************************************ * * clear_vertex * ************************************************************************/ namespace parallel { namespace detail { struct always_true { typedef bool result_type; template<typename T> bool operator()(const T&) const { return true; } }; } } // end namespace parallel::detail template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG> void clear_vertex (typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS) ::vertex_descriptor u, PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS)& g) { clear_out_edges(u, g); clear_in_edges(u, g); } template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG> void clear_vertex (typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS) ::vertex_descriptor u, PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS)& g) { remove_out_edge_if(u, parallel::detail::always_true(), g); } /************************************************************************ * * clear_out_edges * ************************************************************************/ template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG> void clear_out_edges (typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(directedS)::vertex_descriptor u, PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(directedS)& g) { BOOST_ASSERT(u.owner == g.processor()); clear_out_edges(u.local, g.base()); } template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG> void clear_out_edges (typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS) ::vertex_descriptor u, PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS)& g) { remove_out_edge_if(u, parallel::detail::always_true(), g); } /************************************************************************ * * clear_in_edges * ************************************************************************/ template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG> void clear_in_edges (typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS) ::vertex_descriptor u, PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS)& g) { remove_in_edge_if(u, parallel::detail::always_true(), g); } /************************************************************************ * * add_vertex * ************************************************************************/ template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor add_vertex(PBGL_DISTRIB_ADJLIST_TYPE& g) { typedef PBGL_DISTRIB_ADJLIST_TYPE graph_type; typename graph_type::vertex_property_type p; return add_vertex(p, g); } template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> typename PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_vertex_with_property add_vertex(typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_property_type const& p, PBGL_DISTRIB_ADJLIST_TYPE& g) { typedef typename PBGL_DISTRIB_ADJLIST_TYPE ::lazy_add_vertex_with_property lazy_add_vertex; return lazy_add_vertex(g, p); } /************************************************************************ * * remove_vertex * ************************************************************************/ template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> void remove_vertex(typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor u, PBGL_DISTRIB_ADJLIST_TYPE& g) { typedef typename PBGL_DISTRIB_ADJLIST_TYPE::graph_type graph_type; typedef typename graph_type::named_graph_mixin named_graph_mixin; BOOST_ASSERT(u.owner == g.processor()); static_cast<named_graph_mixin&>(static_cast<graph_type&>(g)) .removing_vertex(u, boost::graph_detail::iterator_stability(g.base().m_vertices)); g.distribution().clear(); remove_vertex(u.local, g.base()); } /*************************************************************************** * Implementation of Property Graph concept ***************************************************************************/ template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS, typename Property> struct property_map<PBGL_DISTRIB_ADJLIST_TYPE, Property> : detail::parallel::get_adj_list_pmap<Property> ::template apply<PBGL_DISTRIB_ADJLIST_TYPE> { }; template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS, typename Property> struct property_map<PBGL_DISTRIB_ADJLIST_TYPE const, Property> : boost::detail::parallel::get_adj_list_pmap<Property> // FIXME: in the original code the following was not const ::template apply<PBGL_DISTRIB_ADJLIST_TYPE const> { }; template<typename Property, PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, Property>::type get(Property p, PBGL_DISTRIB_ADJLIST_TYPE& g) { typedef PBGL_DISTRIB_ADJLIST_TYPE Graph; typedef typename property_map<Graph, Property>::type result_type; typedef typename property_traits<result_type>::value_type value_type; typedef typename property_reduce<Property>::template apply<value_type> reduce; typedef typename property_traits<result_type>::key_type descriptor; typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; typedef typename mpl::if_<is_same<descriptor, vertex_descriptor>, vertex_global_t, edge_global_t>::type global_map_t; return result_type(g.process_group(), get(global_map_t(), g), get(p, g.base()), reduce()); } template<typename Property, PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, Property>::const_type get(Property p, const PBGL_DISTRIB_ADJLIST_TYPE& g) { typedef PBGL_DISTRIB_ADJLIST_TYPE Graph; typedef typename property_map<Graph, Property>::const_type result_type; typedef typename property_traits<result_type>::value_type value_type; typedef typename property_reduce<Property>::template apply<value_type> reduce; typedef typename property_traits<result_type>::key_type descriptor; typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; typedef typename mpl::if_<is_same<descriptor, vertex_descriptor>, vertex_global_t, edge_global_t>::type global_map_t; return result_type(g.process_group(), get(global_map_t(), g), get(p, g.base()), reduce()); } template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, vertex_local_index_t>::type get(vertex_local_index_t, PBGL_DISTRIB_ADJLIST_TYPE& g) { return get(vertex_local_index, g.base()); } template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, vertex_local_index_t>::const_type get(vertex_local_index_t, const PBGL_DISTRIB_ADJLIST_TYPE& g) { return get(vertex_local_index, g.base()); } template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, vertex_global_t>::const_type get(vertex_global_t, const PBGL_DISTRIB_ADJLIST_TYPE& g) { typedef typename property_map< PBGL_DISTRIB_ADJLIST_TYPE, vertex_global_t>::const_type result_type; return result_type(); } template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, vertex_global_t>::const_type get(vertex_global_t, PBGL_DISTRIB_ADJLIST_TYPE& g) { typedef typename property_map< PBGL_DISTRIB_ADJLIST_TYPE, vertex_global_t>::const_type result_type; return result_type(); } /// Retrieve a property map mapping from a vertex descriptor to its /// owner. template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, vertex_owner_t>::type get(vertex_owner_t, PBGL_DISTRIB_ADJLIST_TYPE& g) { typedef typename property_map< PBGL_DISTRIB_ADJLIST_TYPE, vertex_owner_t>::type result_type; return result_type(); } /// Retrieve a property map mapping from a vertex descriptor to its /// owner. template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, vertex_owner_t>::const_type get(vertex_owner_t, const PBGL_DISTRIB_ADJLIST_TYPE& g) { typedef typename property_map< PBGL_DISTRIB_ADJLIST_TYPE, vertex_owner_t>::const_type result_type; return result_type(); } /// Retrieve the owner of a vertex template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> inline processor_id_type get(vertex_owner_t, PBGL_DISTRIB_ADJLIST_TYPE&, typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor v) { return v.owner; } /// Retrieve the owner of a vertex template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> inline processor_id_type get(vertex_owner_t, const PBGL_DISTRIB_ADJLIST_TYPE&, typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor v) { return v.owner; } /// Retrieve a property map that maps from a vertex descriptor to /// its local descriptor. template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, vertex_local_t>::type get(vertex_local_t, PBGL_DISTRIB_ADJLIST_TYPE& g) { typedef typename property_map< PBGL_DISTRIB_ADJLIST_TYPE, vertex_local_t>::type result_type; return result_type(); } /// Retrieve a property map that maps from a vertex descriptor to /// its local descriptor. template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, vertex_local_t>::const_type get(vertex_local_t, const PBGL_DISTRIB_ADJLIST_TYPE& g) { typedef typename property_map< PBGL_DISTRIB_ADJLIST_TYPE, vertex_local_t>::const_type result_type; return result_type(); } /// Retrieve the local descriptor of a vertex template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> inline typename PBGL_DISTRIB_ADJLIST_TYPE::local_vertex_descriptor get(vertex_local_t, PBGL_DISTRIB_ADJLIST_TYPE&, typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor v) { return v.local; } /// Retrieve the local descriptor of a vertex template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> inline typename PBGL_DISTRIB_ADJLIST_TYPE::local_vertex_descriptor get(vertex_local_t, const PBGL_DISTRIB_ADJLIST_TYPE&, typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor v) { return v.local; } template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, edge_global_t>::const_type get(edge_global_t, const PBGL_DISTRIB_ADJLIST_TYPE& g) { typedef typename property_map< PBGL_DISTRIB_ADJLIST_TYPE, edge_global_t>::const_type result_type; return result_type(); } template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, edge_global_t>::const_type get(edge_global_t, PBGL_DISTRIB_ADJLIST_TYPE& g) { typedef typename property_map< PBGL_DISTRIB_ADJLIST_TYPE, edge_global_t>::const_type result_type; return result_type(); } template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, edge_owner_t>::type get(edge_owner_t, PBGL_DISTRIB_ADJLIST_TYPE& g) { typedef typename property_map< PBGL_DISTRIB_ADJLIST_TYPE, edge_owner_t>::type result_type; return result_type(); } template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, edge_owner_t>::const_type get(edge_owner_t, const PBGL_DISTRIB_ADJLIST_TYPE& g) { typedef typename property_map< PBGL_DISTRIB_ADJLIST_TYPE, edge_owner_t>::const_type result_type; return result_type(); } template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, edge_local_t>::type get(edge_local_t, PBGL_DISTRIB_ADJLIST_TYPE& g) { typedef typename property_map< PBGL_DISTRIB_ADJLIST_TYPE, edge_local_t>::type result_type; return result_type(); } template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, edge_local_t>::const_type get(edge_local_t, const PBGL_DISTRIB_ADJLIST_TYPE& g) { typedef typename property_map< PBGL_DISTRIB_ADJLIST_TYPE, edge_local_t>::const_type result_type; return result_type(); } template<typename Property, PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS, typename Key> inline typename property_traits<typename property_map< PBGL_DISTRIB_ADJLIST_TYPE, Property>::const_type >::value_type get(Property p, const PBGL_DISTRIB_ADJLIST_TYPE& g, const Key& key) { if (owner(key) == process_id(g.process_group())) return get(p, g.base(), local(key)); else BOOST_ASSERT(false); } template<typename Property, PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS, typename Key, typename Value> void put(Property p, PBGL_DISTRIB_ADJLIST_TYPE& g, const Key& key, const Value& v) { if (owner(key) == process_id(g.process_group())) put(p, g.base(), local(key), v); else BOOST_ASSERT(false); } template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, vertex_index_t>::type get(vertex_index_t vi, PBGL_DISTRIB_ADJLIST_TYPE& g) { typedef PBGL_DISTRIB_ADJLIST_TYPE graph_type; typedef typename property_map<graph_type, vertex_index_t>::type result_type; return result_type(g.process_group(), get(vertex_global, g), get(vi, g.base())); } template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, vertex_index_t>::const_type get(vertex_index_t vi, const PBGL_DISTRIB_ADJLIST_TYPE& g) { typedef PBGL_DISTRIB_ADJLIST_TYPE graph_type; typedef typename property_map<graph_type, vertex_index_t>::const_type result_type; return result_type(g.process_group(), get(vertex_global, g), get(vi, g.base())); } /*************************************************************************** * Implementation of bundled properties ***************************************************************************/ template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS, typename T, typename Bundle> struct property_map<PBGL_DISTRIB_ADJLIST_TYPE, T Bundle::*> : detail::parallel::get_adj_list_pmap<T Bundle::*> ::template apply<PBGL_DISTRIB_ADJLIST_TYPE> { }; template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS, typename T, typename Bundle> struct property_map<PBGL_DISTRIB_ADJLIST_TYPE const, T Bundle::*> : detail::parallel::get_adj_list_pmap<T Bundle::*> ::template apply<PBGL_DISTRIB_ADJLIST_TYPE const> { }; template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS, typename T, typename Bundle> typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, T Bundle::*>::type get(T Bundle::* p, PBGL_DISTRIB_ADJLIST_TYPE& g) { typedef PBGL_DISTRIB_ADJLIST_TYPE Graph; typedef typename property_map<Graph, T Bundle::*>::type result_type; typedef typename property_traits<result_type>::value_type value_type; typedef typename property_reduce<T Bundle::*>::template apply<value_type> reduce; typedef typename property_traits<result_type>::key_type descriptor; typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; typedef typename mpl::if_<is_same<descriptor, vertex_descriptor>, vertex_global_t, edge_global_t>::type global_map_t; return result_type(g.process_group(), get(global_map_t(), g), get(p, g.base()), reduce()); } template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS, typename T, typename Bundle> typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, T Bundle::*>::const_type get(T Bundle::* p, const PBGL_DISTRIB_ADJLIST_TYPE& g) { typedef PBGL_DISTRIB_ADJLIST_TYPE Graph; typedef typename property_map<Graph, T Bundle::*>::const_type result_type; typedef typename property_traits<result_type>::value_type value_type; typedef typename property_reduce<T Bundle::*>::template apply<value_type> reduce; typedef typename property_traits<result_type>::key_type descriptor; typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; typedef typename mpl::if_<is_same<descriptor, vertex_descriptor>, vertex_global_t, edge_global_t>::type global_map_t; return result_type(g.process_group(), get(global_map_t(), g), get(p, g.base()), reduce()); } /*************************************************************************** * Implementation of DistributedGraph concept ***************************************************************************/ template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> void synchronize(const PBGL_DISTRIB_ADJLIST_TYPE& g) { synchronize(g.process_group()); } template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS> ProcessGroup process_group(const PBGL_DISTRIB_ADJLIST_TYPE& g) { return g.process_group(); } /*************************************************************************** * Specializations of is_mpi_datatype for Serializable entities ***************************************************************************/ namespace mpi { template<typename Directed, typename Vertex> struct is_mpi_datatype<boost::detail::edge_base<Directed, Vertex> > : is_mpi_datatype<Vertex> { }; template<typename Directed, typename Vertex> struct is_mpi_datatype<boost::detail::edge_desc_impl<Directed, Vertex> > : is_mpi_datatype<boost::detail::edge_base<Directed, Vertex> > { }; template<typename LocalDescriptor> struct is_mpi_datatype<boost::detail::parallel::global_descriptor<LocalDescriptor> > : is_mpi_datatype<LocalDescriptor> { }; template<typename Edge> struct is_mpi_datatype<boost::detail::parallel::edge_descriptor<Edge> > : is_mpi_datatype<Edge> { }; template<typename Vertex, typename LocalVertex> struct is_mpi_datatype<boost::detail::parallel:: msg_add_edge_data<Vertex, LocalVertex> > : is_mpi_datatype<Vertex> { }; template<typename Vertex, typename LocalVertex, typename EdgeProperty> struct is_mpi_datatype<boost::detail::parallel:: msg_add_edge_with_property_data<Vertex, LocalVertex, EdgeProperty> > : mpl::and_<is_mpi_datatype<Vertex>, is_mpi_datatype<EdgeProperty> > { }; template<typename EdgeProperty, typename EdgeDescriptor> struct is_mpi_datatype<boost::detail::parallel::msg_nonlocal_edge_data< EdgeProperty,EdgeDescriptor> > : mpl::and_< is_mpi_datatype<boost::detail::parallel::maybe_store_property< EdgeProperty> >, is_mpi_datatype<EdgeDescriptor> > {}; template<typename EdgeDescriptor> struct is_mpi_datatype< boost::detail::parallel::msg_remove_edge_data<EdgeDescriptor> > : is_mpi_datatype<EdgeDescriptor> {}; } /*************************************************************************** * Specializations of is_bitwise_serializable for Serializable entities ***************************************************************************/ namespace serialization { template<typename Directed, typename Vertex> struct is_bitwise_serializable<boost::detail::edge_base<Directed, Vertex> > : is_bitwise_serializable<Vertex> { }; template<typename Directed, typename Vertex> struct is_bitwise_serializable<boost::detail::edge_desc_impl<Directed, Vertex> > : is_bitwise_serializable<boost::detail::edge_base<Directed, Vertex> > { }; template<typename LocalDescriptor> struct is_bitwise_serializable<boost::detail::parallel::global_descriptor<LocalDescriptor> > : is_bitwise_serializable<LocalDescriptor> { }; template<typename Edge> struct is_bitwise_serializable<boost::detail::parallel::edge_descriptor<Edge> > : is_bitwise_serializable<Edge> { }; template<typename Vertex, typename LocalVertex> struct is_bitwise_serializable<boost::detail::parallel:: msg_add_edge_data<Vertex, LocalVertex> > : is_bitwise_serializable<Vertex> { }; template<typename Vertex, typename LocalVertex, typename EdgeProperty> struct is_bitwise_serializable<boost::detail::parallel:: msg_add_edge_with_property_data<Vertex, LocalVertex, EdgeProperty> > : mpl::and_<is_bitwise_serializable<Vertex>, is_bitwise_serializable<EdgeProperty> > { }; template<typename EdgeProperty, typename EdgeDescriptor> struct is_bitwise_serializable<boost::detail::parallel::msg_nonlocal_edge_data< EdgeProperty,EdgeDescriptor> > : mpl::and_< is_bitwise_serializable< boost::detail::parallel::maybe_store_property<EdgeProperty> >, is_bitwise_serializable<EdgeDescriptor> > {}; template<typename EdgeDescriptor> struct is_bitwise_serializable< boost::detail::parallel::msg_remove_edge_data<EdgeDescriptor> > : is_bitwise_serializable<EdgeDescriptor> {}; template<typename Directed, typename Vertex> struct implementation_level<boost::detail::edge_base<Directed, Vertex> > : mpl::int_<object_serializable> {}; template<typename Directed, typename Vertex> struct implementation_level<boost::detail::edge_desc_impl<Directed, Vertex> > : mpl::int_<object_serializable> {}; template<typename LocalDescriptor> struct implementation_level<boost::detail::parallel::global_descriptor<LocalDescriptor> > : mpl::int_<object_serializable> {}; template<typename Edge> struct implementation_level<boost::detail::parallel::edge_descriptor<Edge> > : mpl::int_<object_serializable> {}; template<typename Vertex, typename LocalVertex> struct implementation_level<boost::detail::parallel:: msg_add_edge_data<Vertex, LocalVertex> > : mpl::int_<object_serializable> {}; template<typename Vertex, typename LocalVertex, typename EdgeProperty> struct implementation_level<boost::detail::parallel:: msg_add_edge_with_property_data<Vertex, LocalVertex, EdgeProperty> > : mpl::int_<object_serializable> {}; template<typename EdgeProperty, typename EdgeDescriptor> struct implementation_level<boost::detail::parallel::msg_nonlocal_edge_data< EdgeProperty,EdgeDescriptor> > : mpl::int_<object_serializable> {}; template<typename EdgeDescriptor> struct implementation_level< boost::detail::parallel::msg_remove_edge_data<EdgeDescriptor> > : mpl::int_<object_serializable> {}; template<typename Directed, typename Vertex> struct tracking_level<boost::detail::edge_base<Directed, Vertex> > : mpl::int_<track_never> {}; template<typename Directed, typename Vertex> struct tracking_level<boost::detail::edge_desc_impl<Directed, Vertex> > : mpl::int_<track_never> {}; template<typename LocalDescriptor> struct tracking_level<boost::detail::parallel::global_descriptor<LocalDescriptor> > : mpl::int_<track_never> {}; template<typename Edge> struct tracking_level<boost::detail::parallel::edge_descriptor<Edge> > : mpl::int_<track_never> {}; template<typename Vertex, typename LocalVertex> struct tracking_level<boost::detail::parallel:: msg_add_edge_data<Vertex, LocalVertex> > : mpl::int_<track_never> {}; template<typename Vertex, typename LocalVertex, typename EdgeProperty> struct tracking_level<boost::detail::parallel:: msg_add_edge_with_property_data<Vertex, LocalVertex, EdgeProperty> > : mpl::int_<track_never> {}; template<typename EdgeProperty, typename EdgeDescriptor> struct tracking_level<boost::detail::parallel::msg_nonlocal_edge_data< EdgeProperty,EdgeDescriptor> > : mpl::int_<track_never> {}; template<typename EdgeDescriptor> struct tracking_level< boost::detail::parallel::msg_remove_edge_data<EdgeDescriptor> > : mpl::int_<track_never> {}; } // Hash function for global descriptors template<typename LocalDescriptor> struct hash<detail::parallel::global_descriptor<LocalDescriptor> > { typedef detail::parallel::global_descriptor<LocalDescriptor> argument_type; std::size_t operator()(argument_type const& x) const { std::size_t hash = hash_value(x.owner); hash_combine(hash, x.local); return hash; } }; // Hash function for parallel edge descriptors template<typename Edge> struct hash<detail::parallel::edge_descriptor<Edge> > { typedef detail::parallel::edge_descriptor<Edge> argument_type; std::size_t operator()(argument_type const& x) const { std::size_t hash = hash_value(x.owner()); hash_combine(hash, x.local); return hash; } }; } // end namespace boost #include <boost/graph/distributed/adjlist/handlers.hpp> #include <boost/graph/distributed/adjlist/initialize.hpp> #include <boost/graph/distributed/adjlist/redistribute.hpp> #include <boost/graph/distributed/adjlist/serialization.hpp> #endif // BOOST_GRAPH_DISTRIBUTED_ADJACENCY_LIST_HPP