1 // Copyright (C) 2004-2006 The Trustees of Indiana University.
2 // Copyright (C) 2007 Douglas Gregor
4 // Use, modification and distribution is subject to the Boost Software
5 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
6 // http://www.boost.org/LICENSE_1_0.txt)
8 // Authors: Douglas Gregor
11 #ifndef BOOST_GRAPH_DISTRIBUTED_ADJACENCY_LIST_HPP
12 #define BOOST_GRAPH_DISTRIBUTED_ADJACENCY_LIST_HPP
14 #ifndef BOOST_GRAPH_USE_MPI
15 #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
18 #include <boost/graph/adjacency_list.hpp>
19 #include <boost/graph/properties.hpp>
20 #include <boost/graph/graph_traits.hpp>
21 #include <boost/graph/iteration_macros.hpp>
22 #include <boost/graph/distributed/concepts.hpp>
23 #include <boost/iterator/transform_iterator.hpp>
24 #include <boost/property_map/property_map.hpp>
25 #include <boost/graph/adjacency_iterator.hpp>
26 #include <boost/property_map/parallel/distributed_property_map.hpp>
27 #include <boost/property_map/parallel/local_property_map.hpp>
28 #include <boost/graph/parallel/detail/property_holders.hpp>
29 #include <boost/mpl/if.hpp>
30 #include <boost/type_traits/is_same.hpp>
31 #include <boost/assert.hpp>
34 #include <boost/limits.hpp>
35 #include <boost/graph/parallel/properties.hpp>
36 #include <boost/graph/parallel/distribution.hpp>
37 #include <boost/graph/parallel/algorithm.hpp>
38 #include <boost/graph/distributed/selector.hpp>
39 #include <boost/graph/parallel/process_group.hpp>
40 #include <boost/pending/container_traits.hpp>
43 #include <boost/function/function2.hpp>
46 #include <boost/serialization/base_object.hpp>
47 #include <boost/mpi/datatype.hpp>
48 #include <boost/pending/property_serialize.hpp>
49 #include <boost/graph/distributed/unsafe_serialize.hpp>
52 #include <boost/graph/distributed/named_graph.hpp>
54 #include <boost/graph/distributed/shuffled_distribution.hpp>
58 /// The type used to store an identifier that uniquely names a processor.
59 // NGE: I doubt we'll be running on more than 32768 procs for the time being
60 typedef /*int*/ short processor_id_type;
62 // Tell which processor the target of an edge resides on (for
63 // directed graphs) or which processor the other end point of the
64 // edge resides on (for undirected graphs).
65 enum edge_target_processor_id_t { edge_target_processor_id };
66 BOOST_INSTALL_PROPERTY(edge, target_processor_id);
68 // For undirected graphs, tells whether the edge is locally owned.
69 enum edge_locally_owned_t { edge_locally_owned };
70 BOOST_INSTALL_PROPERTY(edge, locally_owned);
72 // For bidirectional graphs, stores the incoming edges.
73 enum vertex_in_edges_t { vertex_in_edges };
74 BOOST_INSTALL_PROPERTY(vertex, in_edges);
76 /// Tag class for directed, distributed adjacency list
77 struct directed_distributed_adj_list_tag
78 : public virtual distributed_graph_tag,
79 public virtual distributed_vertex_list_graph_tag,
80 public virtual distributed_edge_list_graph_tag,
81 public virtual incidence_graph_tag,
82 public virtual adjacency_graph_tag {};
84 /// Tag class for bidirectional, distributed adjacency list
85 struct bidirectional_distributed_adj_list_tag
86 : public virtual distributed_graph_tag,
87 public virtual distributed_vertex_list_graph_tag,
88 public virtual distributed_edge_list_graph_tag,
89 public virtual incidence_graph_tag,
90 public virtual adjacency_graph_tag,
91 public virtual bidirectional_graph_tag {};
93 /// Tag class for undirected, distributed adjacency list
94 struct undirected_distributed_adj_list_tag
95 : public virtual distributed_graph_tag,
96 public virtual distributed_vertex_list_graph_tag,
97 public virtual distributed_edge_list_graph_tag,
98 public virtual incidence_graph_tag,
99 public virtual adjacency_graph_tag,
100 public virtual bidirectional_graph_tag {};
103 template<typename Archiver, typename Directed, typename Vertex>
105 serialize(Archiver& ar, edge_base<Directed, Vertex>& e,
106 const unsigned int /*version*/)
108 ar & unsafe_serialize(e.m_source)
109 & unsafe_serialize(e.m_target);
112 template<typename Archiver, typename Directed, typename Vertex>
114 serialize(Archiver& ar, edge_desc_impl<Directed, Vertex>& e,
115 const unsigned int /*version*/)
117 ar & boost::serialization::base_object<edge_base<Directed, Vertex> >(e)
118 & unsafe_serialize(e.m_eproperty);
122 namespace detail { namespace parallel {
125 * A distributed vertex descriptor. These descriptors contain both
126 * the ID of the processor that owns the vertex and a local vertex
127 * descriptor that identifies the particular vertex for that
130 template<typename LocalDescriptor>
131 struct global_descriptor
133 typedef LocalDescriptor local_descriptor_type;
135 global_descriptor() : owner(), local() { }
137 global_descriptor(processor_id_type owner, LocalDescriptor local)
138 : owner(owner), local(local) { }
140 processor_id_type owner;
141 LocalDescriptor local;
144 * A function object that, given a processor ID, generates
145 * distributed vertex descriptors from local vertex
146 * descriptors. This function object is used by the
147 * vertex_iterator of the distributed adjacency list.
151 typedef global_descriptor<LocalDescriptor> result_type;
152 typedef LocalDescriptor argument_type;
155 generator(processor_id_type owner) : owner(owner) {}
157 result_type operator()(argument_type v) const
158 { return result_type(owner, v); }
161 processor_id_type owner;
164 template<typename Archiver>
165 void serialize(Archiver& ar, const unsigned int /*version*/)
167 ar & owner & unsafe_serialize(local);
171 /// Determine the process that owns the given descriptor
172 template<typename LocalDescriptor>
173 inline processor_id_type owner(const global_descriptor<LocalDescriptor>& v)
176 /// Determine the local portion of the given descriptor
177 template<typename LocalDescriptor>
178 inline LocalDescriptor local(const global_descriptor<LocalDescriptor>& v)
181 /// Compare distributed vertex descriptors for equality
182 template<typename LocalDescriptor>
184 operator==(const global_descriptor<LocalDescriptor>& u,
185 const global_descriptor<LocalDescriptor>& v)
187 return u.owner == v.owner && u.local == v.local;
190 /// Compare distributed vertex descriptors for inequality
191 template<typename LocalDescriptor>
193 operator!=(const global_descriptor<LocalDescriptor>& u,
194 const global_descriptor<LocalDescriptor>& v)
195 { return !(u == v); }
197 template<typename LocalDescriptor>
199 operator<(const global_descriptor<LocalDescriptor>& u,
200 const global_descriptor<LocalDescriptor>& v)
202 return (u.owner) < v.owner || (u.owner == v.owner && (u.local) < v.local);
205 template<typename LocalDescriptor>
207 operator<=(const global_descriptor<LocalDescriptor>& u,
208 const global_descriptor<LocalDescriptor>& v)
210 return u.owner <= v.owner || (u.owner == v.owner && u.local <= v.local);
213 template<typename LocalDescriptor>
215 operator>(const global_descriptor<LocalDescriptor>& u,
216 const global_descriptor<LocalDescriptor>& v)
221 template<typename LocalDescriptor>
223 operator>=(const global_descriptor<LocalDescriptor>& u,
224 const global_descriptor<LocalDescriptor>& v)
229 // DPG TBD: Add <, <=, >=, > for global descriptors
232 * A Readable Property Map that extracts a global descriptor pair
233 * from a global_descriptor.
235 template<typename LocalDescriptor>
236 struct global_descriptor_property_map
238 typedef std::pair<processor_id_type, LocalDescriptor> value_type;
239 typedef value_type reference;
240 typedef global_descriptor<LocalDescriptor> key_type;
241 typedef readable_property_map_tag category;
244 template<typename LocalDescriptor>
245 inline std::pair<processor_id_type, LocalDescriptor>
246 get(global_descriptor_property_map<LocalDescriptor>,
247 global_descriptor<LocalDescriptor> x)
249 return std::pair<processor_id_type, LocalDescriptor>(x.owner, x.local);
253 * A Readable Property Map that extracts the owner of a global
256 template<typename LocalDescriptor>
257 struct owner_property_map
259 typedef processor_id_type value_type;
260 typedef value_type reference;
261 typedef global_descriptor<LocalDescriptor> key_type;
262 typedef readable_property_map_tag category;
265 template<typename LocalDescriptor>
266 inline processor_id_type
267 get(owner_property_map<LocalDescriptor>,
268 global_descriptor<LocalDescriptor> x)
274 * A Readable Property Map that extracts the local descriptor from
275 * a global descriptor.
277 template<typename LocalDescriptor>
278 struct local_descriptor_property_map
280 typedef LocalDescriptor value_type;
281 typedef value_type reference;
282 typedef global_descriptor<LocalDescriptor> key_type;
283 typedef readable_property_map_tag category;
286 template<typename LocalDescriptor>
287 inline LocalDescriptor
288 get(local_descriptor_property_map<LocalDescriptor>,
289 global_descriptor<LocalDescriptor> x)
295 * Stores an incoming edge for a bidirectional distributed
296 * adjacency list. The user does not see this type directly,
297 * because it is just an implementation detail.
299 template<typename Edge>
300 struct stored_in_edge
302 stored_in_edge(processor_id_type sp, Edge e)
303 : source_processor(sp), e(e) {}
305 processor_id_type source_processor;
310 * A distributed edge descriptor. These descriptors contain the
311 * underlying edge descriptor, the processor IDs for both the
312 * source and the target of the edge, and a boolean flag that
313 * indicates which of the processors actually owns the edge.
315 template<typename Edge>
316 struct edge_descriptor
318 edge_descriptor(processor_id_type sp = processor_id_type(),
319 processor_id_type tp = processor_id_type(),
320 bool owns = false, Edge ld = Edge())
321 : source_processor(sp), target_processor(tp),
322 source_owns_edge(owns), local(ld) {}
324 processor_id_type owner() const
326 return source_owns_edge? source_processor : target_processor;
329 /// The processor that the source vertex resides on
330 processor_id_type source_processor;
332 /// The processor that the target vertex resides on
333 processor_id_type target_processor;
335 /// True when the source processor owns the edge, false when the
336 /// target processor owns the edge.
337 bool source_owns_edge;
339 /// The local edge descriptor.
343 * Function object that generates edge descriptors for the
344 * out_edge_iterator of the given distributed adjacency list
345 * from the edge descriptors of the underlying adjacency list.
347 template<typename Graph>
350 typedef typename Graph::directed_selector directed_selector;
353 typedef edge_descriptor<Edge> result_type;
354 typedef Edge argument_type;
356 out_generator() : g(0) {}
357 explicit out_generator(const Graph& g) : g(&g) {}
359 result_type operator()(argument_type e) const
360 { return map(e, directed_selector()); }
363 result_type map(argument_type e, directedS) const
365 return result_type(g->processor(),
366 get(edge_target_processor_id, g->base(), e),
370 result_type map(argument_type e, bidirectionalS) const
372 return result_type(g->processor(),
373 get(edge_target_processor_id, g->base(), e),
377 result_type map(argument_type e, undirectedS) const
379 return result_type(g->processor(),
380 get(edge_target_processor_id, g->base(), e),
381 get(edge_locally_owned, g->base(), e),
389 * Function object that generates edge descriptors for the
390 * in_edge_iterator of the given distributed adjacency list
391 * from the edge descriptors of the underlying adjacency list.
393 template<typename Graph>
396 typedef typename Graph::directed_selector DirectedS;
399 typedef typename boost::mpl::if_<is_same<DirectedS, bidirectionalS>,
400 stored_in_edge<Edge>,
401 Edge>::type argument_type;
402 typedef edge_descriptor<Edge> result_type;
404 in_generator() : g(0) {}
405 explicit in_generator(const Graph& g) : g(&g) {}
407 result_type operator()(argument_type e) const
408 { return map(e, DirectedS()); }
412 * For a bidirectional graph, we just generate the appropriate
415 result_type map(argument_type e, bidirectionalS) const
417 return result_type(e.source_processor,
424 * For an undirected graph, we generate descriptors for the
425 * incoming edges by swapping the source/target of the
426 * underlying edge descriptor (a hack). The target processor
427 * ID on the edge is actually the source processor for this
428 * edge, and our processor is the target processor. If the
429 * edge is locally owned, then it is owned by the target (us);
430 * otherwise it is owned by the source.
432 result_type map(argument_type e, undirectedS) const
434 typename Graph::local_edge_descriptor local_edge(e);
435 // TBD: This is a very, VERY lame hack that takes advantage
436 // of our knowledge of the internals of the BGL
437 // adjacency_list. There should be a cleaner way to handle
440 swap(local_edge.m_source, local_edge.m_target);
441 return result_type(get(edge_target_processor_id, g->base(), e),
443 !get(edge_locally_owned, g->base(), e),
451 friend class boost::serialization::access;
453 template<typename Archiver>
454 void serialize(Archiver& ar, const unsigned int /*version*/)
464 /// Determine the process that owns this edge
465 template<typename Edge>
466 inline processor_id_type
467 owner(const edge_descriptor<Edge>& e)
468 { return e.source_owns_edge? e.source_processor : e.target_processor; }
470 /// Determine the local descriptor for this edge.
471 template<typename Edge>
473 local(const edge_descriptor<Edge>& e)
477 * A Readable Property Map that extracts the owner and local
478 * descriptor of an edge descriptor.
480 template<typename Edge>
481 struct edge_global_property_map
483 typedef std::pair<processor_id_type, Edge> value_type;
484 typedef value_type reference;
485 typedef edge_descriptor<Edge> key_type;
486 typedef readable_property_map_tag category;
489 template<typename Edge>
490 inline std::pair<processor_id_type, Edge>
491 get(edge_global_property_map<Edge>, const edge_descriptor<Edge>& e)
493 typedef std::pair<processor_id_type, Edge> result_type;
494 return result_type(e.source_owns_edge? e.source_processor
495 /* target owns edge*/: e.target_processor,
500 * A Readable Property Map that extracts the owner of an edge
503 template<typename Edge>
504 struct edge_owner_property_map
506 typedef processor_id_type value_type;
507 typedef value_type reference;
508 typedef edge_descriptor<Edge> key_type;
509 typedef readable_property_map_tag category;
512 template<typename Edge>
513 inline processor_id_type
514 get(edge_owner_property_map<Edge>, const edge_descriptor<Edge>& e)
516 return e.source_owns_edge? e.source_processor : e.target_processor;
520 * A Readable Property Map that extracts the local descriptor from
521 * an edge descriptor.
523 template<typename Edge>
524 struct edge_local_property_map
526 typedef Edge value_type;
527 typedef value_type reference;
528 typedef edge_descriptor<Edge> key_type;
529 typedef readable_property_map_tag category;
532 template<typename Edge>
534 get(edge_local_property_map<Edge>,
535 const edge_descriptor<Edge>& e)
540 /** Compare distributed edge descriptors for equality.
542 * \todo need edge_descriptor to know if it is undirected so we
543 * can compare both ways.
545 template<typename Edge>
547 operator==(const edge_descriptor<Edge>& e1,
548 const edge_descriptor<Edge>& e2)
550 return (e1.source_processor == e2.source_processor
551 && e1.target_processor == e2.target_processor
552 && e1.local == e2.local);
555 /// Compare distributed edge descriptors for inequality.
556 template<typename Edge>
558 operator!=(const edge_descriptor<Edge>& e1,
559 const edge_descriptor<Edge>& e2)
560 { return !(e1 == e2); }
563 * Configuration for the distributed adjacency list. We use this
564 * parameter to store all of the configuration details for the
565 * implementation of the distributed adjacency list, which allows us to
566 * get at the distribution type in the maybe_named_graph.
568 template<typename OutEdgeListS, typename ProcessGroup,
569 typename InVertexListS, typename InDistribution,
570 typename DirectedS, typename VertexProperty,
571 typename EdgeProperty, typename GraphProperty,
573 struct adjacency_list_config
575 typedef typename mpl::if_<is_same<InVertexListS, defaultS>,
576 vecS, InVertexListS>::type
579 /// Introduce the target processor ID property for each edge
580 typedef property<edge_target_processor_id_t, processor_id_type,
581 EdgeProperty> edge_property_with_id;
583 /// For undirected graphs, introduce the locally-owned property for edges
584 typedef typename boost::mpl::if_<is_same<DirectedS, undirectedS>,
585 property<edge_locally_owned_t, bool,
586 edge_property_with_id>,
587 edge_property_with_id>::type
588 base_edge_property_type;
590 /// The edge descriptor type for the local subgraph
591 typedef typename adjacency_list_traits<OutEdgeListS,
593 directedS>::edge_descriptor
594 local_edge_descriptor;
596 /// For bidirectional graphs, the type of an incoming stored edge
597 typedef stored_in_edge<local_edge_descriptor> bidir_stored_edge;
599 /// The container type that will store incoming edges for a
600 /// bidirectional graph.
601 typedef typename container_gen<EdgeListS, bidir_stored_edge>::type
604 // Bidirectional graphs have an extra vertex property to store
605 // the incoming edges.
606 typedef typename boost::mpl::if_<is_same<DirectedS, bidirectionalS>,
607 property<vertex_in_edges_t, in_edge_list_type,
609 VertexProperty>::type
610 base_vertex_property_type;
612 // The type of the distributed adjacency list
613 typedef adjacency_list<OutEdgeListS,
614 distributedS<ProcessGroup,
617 DirectedS, VertexProperty, EdgeProperty,
618 GraphProperty, EdgeListS>
621 // The type of the underlying adjacency list implementation
622 typedef adjacency_list<OutEdgeListS, VertexListS, directedS,
623 base_vertex_property_type,
624 base_edge_property_type,
629 typedef InDistribution in_distribution_type;
630 typedef typename inherited::vertices_size_type vertices_size_type;
632 typedef typename ::boost::graph::distributed::select_distribution<
633 in_distribution_type, VertexProperty, vertices_size_type,
635 base_distribution_type;
637 typedef ::boost::graph::distributed::shuffled_distribution<
638 base_distribution_type> distribution_type;
640 typedef VertexProperty vertex_property_type;
641 typedef EdgeProperty edge_property_type;
642 typedef ProcessGroup process_group_type;
644 typedef VertexListS vertex_list_selector;
645 typedef OutEdgeListS out_edge_list_selector;
646 typedef DirectedS directed_selector;
647 typedef GraphProperty graph_property_type;
648 typedef EdgeListS edge_list_selector;
651 // Maybe initialize the indices of each vertex
652 template<typename IteratorPair, typename VertexIndexMap>
654 maybe_initialize_vertex_indices(IteratorPair p, VertexIndexMap to_index,
655 read_write_property_map_tag)
657 typedef typename property_traits<VertexIndexMap>::value_type index_t;
658 index_t next_index = 0;
659 while (p.first != p.second)
660 put(to_index, *p.first++, next_index++);
663 template<typename IteratorPair, typename VertexIndexMap>
665 maybe_initialize_vertex_indices(IteratorPair p, VertexIndexMap to_index,
666 readable_property_map_tag)
671 template<typename IteratorPair, typename VertexIndexMap>
673 maybe_initialize_vertex_indices(IteratorPair p, VertexIndexMap to_index)
675 typedef typename property_traits<VertexIndexMap>::category category;
676 maybe_initialize_vertex_indices(p, to_index, category());
679 template<typename IteratorPair>
681 maybe_initialize_vertex_indices(IteratorPair p,
682 ::boost::detail::error_property_not_found)
685 /***********************************************************************
687 ***********************************************************************/
690 * Data stored with a msg_add_edge message, which requests the
691 * remote addition of an edge.
693 template<typename Vertex, typename LocalVertex>
694 struct msg_add_edge_data
696 msg_add_edge_data() { }
698 msg_add_edge_data(Vertex source, Vertex target)
699 : source(source.local), target(target) { }
701 /// The source of the edge; the processor will be the
702 /// receiving processor.
705 /// The target of the edge.
708 template<typename Archiver>
709 void serialize(Archiver& ar, const unsigned int /*version*/)
711 ar & unsafe_serialize(source) & target;
716 * Like @c msg_add_edge_data, but also includes a user-specified
717 * property value to be attached to the edge.
719 template<typename Vertex, typename LocalVertex, typename EdgeProperty>
720 struct msg_add_edge_with_property_data
721 : msg_add_edge_data<Vertex, LocalVertex>,
722 maybe_store_property<EdgeProperty>
725 typedef msg_add_edge_data<Vertex, LocalVertex> inherited_data;
726 typedef maybe_store_property<EdgeProperty> inherited_property;
729 msg_add_edge_with_property_data() { }
731 msg_add_edge_with_property_data(Vertex source,
733 const EdgeProperty& property)
734 : inherited_data(source, target),
735 inherited_property(property) { }
737 template<typename Archiver>
738 void serialize(Archiver& ar, const unsigned int /*version*/)
740 ar & boost::serialization::base_object<inherited_data>(*this)
741 & boost::serialization::base_object<inherited_property>(*this);
745 //------------------------------------------------------------------------
746 // Distributed adjacency list property map details
748 * Metafunction that extracts the given property from the given
749 * distributed adjacency list type. This could be implemented much
750 * more cleanly, but even newer versions of GCC (e.g., 3.2.3)
751 * cannot properly handle partial specializations involving
754 template<typename Property>
755 struct get_adj_list_pmap
757 template<typename Graph>
760 typedef Graph graph_type;
761 typedef typename graph_type::process_group_type process_group_type;
762 typedef typename graph_type::inherited base_graph_type;
763 typedef typename property_map<base_graph_type, Property>::type
765 typedef typename property_map<base_graph_type, Property>::const_type
768 typedef graph_traits<graph_type> traits;
769 typedef typename graph_type::local_vertex_descriptor local_vertex;
770 typedef typename property_traits<local_pmap>::key_type local_key_type;
772 typedef typename property_traits<local_pmap>::value_type value_type;
774 typedef typename property_map<Graph, vertex_global_t>::const_type
776 typedef typename property_map<Graph, edge_global_t>::const_type
779 typedef typename mpl::if_c<(is_same<local_key_type,
780 local_vertex>::value),
781 vertex_global_map, edge_global_map>::type
785 typedef ::boost::parallel::distributed_property_map<
786 process_group_type, global_map, local_pmap> type;
788 typedef ::boost::parallel::distributed_property_map<
789 process_group_type, global_map, local_const_pmap> const_type;
794 * The local vertex index property map is actually a mapping from
795 * the local vertex descriptors to vertex indices.
798 struct get_adj_list_pmap<vertex_local_index_t>
800 template<typename Graph>
802 : ::boost::property_map<typename Graph::inherited, vertex_index_t>
807 * The vertex index property map maps from global descriptors
808 * (e.g., the vertex descriptor of a distributed adjacency list)
809 * to the underlying local index. It is not valid to use this
810 * property map with nonlocal descriptors.
813 struct get_adj_list_pmap<vertex_index_t>
815 template<typename Graph>
819 typedef typename property_map<Graph, vertex_global_t>::const_type
822 typedef property_map<typename Graph::inherited, vertex_index_t> local;
825 typedef local_property_map<typename Graph::process_group_type,
827 typename local::type> type;
828 typedef local_property_map<typename Graph::process_group_type,
830 typename local::const_type> const_type;
835 * The vertex owner property map maps from vertex descriptors to
836 * the processor that owns the vertex.
839 struct get_adj_list_pmap<vertex_global_t>
841 template<typename Graph>
845 typedef typename Graph::local_vertex_descriptor
846 local_vertex_descriptor;
848 typedef global_descriptor_property_map<local_vertex_descriptor> type;
849 typedef type const_type;
854 * The vertex owner property map maps from vertex descriptors to
855 * the processor that owns the vertex.
858 struct get_adj_list_pmap<vertex_owner_t>
860 template<typename Graph>
864 typedef typename Graph::local_vertex_descriptor
865 local_vertex_descriptor;
867 typedef owner_property_map<local_vertex_descriptor> type;
868 typedef type const_type;
873 * The vertex local property map maps from vertex descriptors to
874 * the local descriptor for that vertex.
877 struct get_adj_list_pmap<vertex_local_t>
879 template<typename Graph>
883 typedef typename Graph::local_vertex_descriptor
884 local_vertex_descriptor;
886 typedef local_descriptor_property_map<local_vertex_descriptor> type;
887 typedef type const_type;
892 * The edge global property map maps from edge descriptors to
893 * a pair of the owning processor and local descriptor.
896 struct get_adj_list_pmap<edge_global_t>
898 template<typename Graph>
902 typedef typename Graph::local_edge_descriptor
903 local_edge_descriptor;
905 typedef edge_global_property_map<local_edge_descriptor> type;
906 typedef type const_type;
911 * The edge owner property map maps from edge descriptors to
912 * the processor that owns the edge.
915 struct get_adj_list_pmap<edge_owner_t>
917 template<typename Graph>
921 typedef typename Graph::local_edge_descriptor
922 local_edge_descriptor;
924 typedef edge_owner_property_map<local_edge_descriptor> type;
925 typedef type const_type;
930 * The edge local property map maps from edge descriptors to
931 * the local descriptor for that edge.
934 struct get_adj_list_pmap<edge_local_t>
936 template<typename Graph>
940 typedef typename Graph::local_edge_descriptor
941 local_edge_descriptor;
943 typedef edge_local_property_map<local_edge_descriptor> type;
944 typedef type const_type;
947 //------------------------------------------------------------------------
949 // Directed graphs do not have in edges, so this is a no-op
950 template<typename Graph>
952 remove_in_edge(typename Graph::edge_descriptor, Graph&, directedS)
955 // Bidirectional graphs have in edges stored in the
956 // vertex_in_edges property.
957 template<typename Graph>
959 remove_in_edge(typename Graph::edge_descriptor e, Graph& g, bidirectionalS)
961 typedef typename Graph::in_edge_list_type in_edge_list_type;
962 in_edge_list_type& in_edges =
963 get(vertex_in_edges, g.base())[target(e, g).local];
964 typename in_edge_list_type::iterator i = in_edges.begin();
965 while (i != in_edges.end()
966 && !(i->source_processor == source(e, g).owner)
970 BOOST_ASSERT(i != in_edges.end());
974 // Undirected graphs have in edges stored as normal edges.
975 template<typename Graph>
977 remove_in_edge(typename Graph::edge_descriptor e, Graph& g, undirectedS)
979 typedef typename Graph::inherited base_type;
980 typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
982 // TBD: can we make this more efficient?
983 // Removing edge (v, u). v is local
984 base_type& bg = g.base();
985 vertex_descriptor u = source(e, g);
986 vertex_descriptor v = target(e, g);
987 if (v.owner != process_id(g.process_group())) {
992 typename graph_traits<base_type>::out_edge_iterator ei, ei_end;
993 for (boost::tie(ei, ei_end) = out_edges(v.local, bg); ei != ei_end; ++ei)
995 if (target(*ei, g.base()) == u.local
996 // TBD: deal with parallel edges properly && *ei == e
997 && get(edge_target_processor_id, bg, *ei) == u.owner) {
1003 if (v.owner == process_id(g.process_group())) {
1008 //------------------------------------------------------------------------
1009 // Lazy addition of edges
1011 // Work around the fact that an adjacency_list with vecS vertex
1012 // storage automatically adds edges when the descriptor is
1014 template <class Graph, class Config, class Base>
1015 inline std::pair<typename Config::edge_descriptor, bool>
1016 add_local_edge(typename Config::vertex_descriptor u,
1017 typename Config::vertex_descriptor v,
1018 const typename Config::edge_property_type& p,
1019 vec_adj_list_impl<Graph, Config, Base>& g_)
1021 adj_list_helper<Config, Base>& g = g_;
1022 return add_edge(u, v, p, g);
1025 template <class Graph, class Config, class Base>
1026 inline std::pair<typename Config::edge_descriptor, bool>
1027 add_local_edge(typename Config::vertex_descriptor u,
1028 typename Config::vertex_descriptor v,
1029 const typename Config::edge_property_type& p,
1030 boost::adj_list_impl<Graph, Config, Base>& g)
1032 return add_edge(u, v, p, g);
1035 template <class EdgeProperty,class EdgeDescriptor>
1036 struct msg_nonlocal_edge_data
1037 : public detail::parallel::maybe_store_property<EdgeProperty>
1039 typedef EdgeProperty edge_property_type;
1040 typedef EdgeDescriptor local_edge_descriptor;
1041 typedef detail::parallel::maybe_store_property<edge_property_type>
1044 msg_nonlocal_edge_data() {}
1045 msg_nonlocal_edge_data(local_edge_descriptor e,
1046 const edge_property_type& p)
1047 : inherited(p), e(e) { }
1049 local_edge_descriptor e;
1051 template<typename Archiver>
1052 void serialize(Archiver& ar, const unsigned int /*version*/)
1054 ar & boost::serialization::base_object<inherited>(*this) & e;
1058 template <class EdgeDescriptor>
1059 struct msg_remove_edge_data
1061 typedef EdgeDescriptor edge_descriptor;
1062 msg_remove_edge_data() {}
1063 explicit msg_remove_edge_data(edge_descriptor e) : e(e) {}
1067 template<typename Archiver>
1068 void serialize(Archiver& ar, const unsigned int /*version*/)
1074 } } // end namespace detail::parallel
1077 * Adjacency list traits for a distributed adjacency list. Contains
1078 * the vertex and edge descriptors, the directed-ness, and the
1079 * parallel edges typedefs.
1081 template<typename OutEdgeListS, typename ProcessGroup,
1082 typename InVertexListS, typename InDistribution, typename DirectedS>
1083 struct adjacency_list_traits<OutEdgeListS,
1084 distributedS<ProcessGroup,
1090 typedef typename mpl::if_<is_same<InVertexListS, defaultS>,
1092 InVertexListS>::type VertexListS;
1094 typedef adjacency_list_traits<OutEdgeListS, VertexListS, directedS>
1098 typedef typename base_type::vertex_descriptor local_vertex_descriptor;
1099 typedef typename base_type::edge_descriptor local_edge_descriptor;
1101 typedef typename boost::mpl::if_<typename DirectedS::is_bidir_t,
1103 typename boost::mpl::if_<typename DirectedS::is_directed_t,
1104 directed_tag, undirected_tag
1106 >::type directed_category;
1108 typedef typename parallel_edge_traits<OutEdgeListS>::type
1109 edge_parallel_category;
1111 typedef detail::parallel::global_descriptor<local_vertex_descriptor>
1114 typedef detail::parallel::edge_descriptor<local_edge_descriptor>
1118 #define PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS \
1119 typename OutEdgeListS, typename ProcessGroup, typename InVertexListS, \
1120 typename InDistribution, typename DirectedS, typename VertexProperty, \
1121 typename EdgeProperty, typename GraphProperty, typename EdgeListS
1123 #define PBGL_DISTRIB_ADJLIST_TYPE \
1124 adjacency_list<OutEdgeListS, \
1125 distributedS<ProcessGroup, InVertexListS, InDistribution>, \
1126 DirectedS, VertexProperty, EdgeProperty, GraphProperty, \
1129 #define PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG \
1130 typename OutEdgeListS, typename ProcessGroup, typename InVertexListS, \
1131 typename InDistribution, typename VertexProperty, \
1132 typename EdgeProperty, typename GraphProperty, typename EdgeListS
1134 #define PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(directed) \
1135 adjacency_list<OutEdgeListS, \
1136 distributedS<ProcessGroup, InVertexListS, InDistribution>, \
1137 directed, VertexProperty, EdgeProperty, GraphProperty, \
1140 /** A distributed adjacency list.
1142 * This class template partial specialization defines a distributed
1143 * (or "partitioned") adjacency list graph. The distributed
1144 * adjacency list is similar to the standard Boost Graph Library
1145 * adjacency list, which stores a list of vertices and for each
1146 * verted the list of edges outgoing from the vertex (and, in some
1147 * cases, also the edges incoming to the vertex). The distributed
1148 * adjacency list differs in that it partitions the graph into
1149 * several subgraphs that are then divided among different
1150 * processors (or nodes within a cluster). The distributed adjacency
1151 * list attempts to maintain a high degree of compatibility with the
1152 * standard, non-distributed adjacency list.
1154 * The graph is partitioned by vertex, with each processor storing
1155 * all of the required information for a particular subset of the
1156 * vertices, including vertex properties, outgoing edges, and (for
1157 * bidirectional graphs) incoming edges. This information is
1158 * accessible only on the processor that owns the vertex: for
1159 * instance, if processor 0 owns vertex @c v, no other processor can
1160 * directly access the properties of @c v or enumerate its outgoing
1163 * Edges in a graph may be entirely local (connecting two local
1164 * vertices), but more often it is the case that edges are
1165 * non-local, meaning that the two vertices they connect reside in
1166 * different processes. Edge properties are stored with the
1167 * originating vertex for directed and bidirectional graphs, and are
1168 * therefore only accessible from the processor that owns the
1169 * originating vertex. Other processors may query the source and
1170 * target of the edge, but cannot access its properties. This is
1171 * particularly interesting when accessing the incoming edges of a
1172 * bidirectional graph, which are not guaranteed to be stored on the
1173 * processor that is able to perform the iteration. For undirected
1174 * graphs the situation is more complicated, since no vertex clearly
1175 * owns the edges: the list of edges incident to a vertex may
1176 * contain a mix of local and non-local edges.
1178 * The distributed adjacency list is able to model several of the
1179 * existing Graph concepts. It models the Graph concept because it
1180 * exposes vertex and edge descriptors in the normal way; these
1181 * descriptors model the GlobalDescriptor concept (because they have
1182 * an owner and a local descriptor), and as such the distributed
1183 * adjacency list models the DistributedGraph concept. The adjacency
1184 * list also models the IncidenceGraph and AdjacencyGraph concepts,
1185 * although this is only true so long as the domain of the valid
1186 * expression arguments are restricted to vertices and edges stored
1187 * locally. Likewise, bidirectional and undirected distributed
1188 * adjacency lists model the BidirectionalGraph concept (vertex and
1189 * edge domains must be respectived) and the distributed adjacency
1190 * list models the MutableGraph concept (vertices and edges can only
1191 * be added or removed locally). T he distributed adjacency list
1192 * does not, however, model the VertexListGraph or EdgeListGraph
1193 * concepts, because we can not efficiently enumerate all vertices
1194 * or edges in the graph. Instead, the local subsets of vertices and
1195 * edges can be enumerated (with the same syntax): the distributed
1196 * adjacency list therefore models the DistributedVertexListGraph
1197 * and DistributedEdgeListGraph concepts, because concurrent
1198 * iteration over all of the vertices or edges stored on each
1199 * processor will visit each vertex or edge.
1201 * The distributed adjacency list is distinguished from the
1202 * non-distributed version by the vertex list descriptor, which will
1203 * be @c distributedS<ProcessGroup,VertexListS>. Here,
1204 * the VertexListS type plays the same role as the VertexListS type
1205 * in the non-distributed adjacency list: it allows one to select
1206 * the data structure that will be used to store the local
1207 * vertices. The ProcessGroup type, on the other hand, is unique to
1208 * distributed data structures: it is the type that abstracts a
1209 * group of cooperating processes, and it used for process
1210 * identification, communication, and synchronization, among other
1211 * things. Different process group types represent different
1212 * communication mediums (e.g., MPI, PVM, TCP) or different models
1213 * of communication (LogP, CGM, BSP, synchronous, etc.). This
1214 * distributed adjacency list assumes a model based on non-blocking
1217 * Distribution of vertices across different processors is
1218 * accomplished in two different ways. When initially constructing
1219 * the graph, the user may provide a distribution object (that
1220 * models the Distribution concept), which will determine the
1221 * distribution of vertices to each process. Additionally, the @c
1222 * add_vertex and @c add_edge operations add vertices or edges
1223 * stored on the local processor. For @c add_edge, this is
1224 * accomplished by requiring that the source vertex of the new edge
1225 * be local to the process executing @c add_edge.
1227 * Internal properties of a distributed adjacency list are
1228 * accessible in the same manner as internal properties for a
1229 * non-distributed adjacency list for local vertices or
1230 * edges. Access to properties for remote vertices or edges occurs
1231 * with the same syntax, but involve communication with the owner of
1232 * the information: for more information, refer to class template
1233 * @ref distributed_property_map, which manages distributed
1234 * property maps. Note that the distributed property maps created
1235 * for internal properties determine their reduction operation via
1236 * the metafunction @ref property_reduce, which for the vast
1237 * majority of uses is correct behavior.
1239 * Communication among the processes coordinating on a particular
1240 * distributed graph relies on non-blocking message passing along
1241 * with synchronization. Local portions of the distributed graph may
1242 * be modified concurrently, including the introduction of non-local
1243 * edges, but prior to accessing the graph it is recommended that
1244 * the @c synchronize free function be invoked on the graph to clear
1245 * up any pending interprocess communication and modifications. All
1246 * processes will then be released from the synchronization barrier
1249 * \todo Determine precisely what we should do with nonlocal edges
1250 * in undirected graphs. Our parallelization of certain algorithms
1251 * relies on the ability to access edge property maps immediately
1252 * (e.g., edge_weight_t), so it may be necessary to duplicate the
1253 * edge properties in both processes (but then we need some form of
1254 * coherence protocol).
1256 * \todo What does the user do if @c property_reduce doesn't do the
1259 template<typename OutEdgeListS, typename ProcessGroup,
1260 typename InVertexListS, typename InDistribution, typename DirectedS,
1261 typename VertexProperty, typename EdgeProperty,
1262 typename GraphProperty, typename EdgeListS>
1263 class adjacency_list<OutEdgeListS,
1264 distributedS<ProcessGroup,
1267 DirectedS, VertexProperty,
1268 EdgeProperty, GraphProperty, EdgeListS>
1269 : // Support for named vertices
1270 public graph::distributed::maybe_named_graph<
1271 adjacency_list<OutEdgeListS,
1272 distributedS<ProcessGroup,
1275 DirectedS, VertexProperty,
1276 EdgeProperty, GraphProperty, EdgeListS>,
1277 typename adjacency_list_traits<OutEdgeListS,
1278 distributedS<ProcessGroup,
1281 DirectedS>::vertex_descriptor,
1282 typename adjacency_list_traits<OutEdgeListS,
1283 distributedS<ProcessGroup,
1286 DirectedS>::edge_descriptor,
1287 detail::parallel::adjacency_list_config<OutEdgeListS, ProcessGroup,
1288 InVertexListS, InDistribution,
1289 DirectedS, VertexProperty,
1290 EdgeProperty, GraphProperty,
1293 typedef detail::parallel::adjacency_list_config<OutEdgeListS, ProcessGroup,
1294 InVertexListS, InDistribution,
1295 DirectedS, VertexProperty,
1296 EdgeProperty, GraphProperty,
1300 typedef adjacency_list_traits<OutEdgeListS,
1301 distributedS<ProcessGroup,
1307 typedef typename DirectedS::is_directed_t is_directed;
1309 typedef EdgeListS edge_list_selector;
1312 /// The container type that will store incoming edges for a
1313 /// bidirectional graph.
1314 typedef typename config_type::in_edge_list_type in_edge_list_type;
1315 // typedef typename inherited::edge_descriptor edge_descriptor;
1317 /// The type of the underlying adjacency list implementation
1318 typedef typename config_type::inherited inherited;
1320 /// The type of properties stored in the local subgraph
1321 /// Bidirectional graphs have an extra vertex property to store
1322 /// the incoming edges.
1323 typedef typename inherited::vertex_property_type
1324 base_vertex_property_type;
1326 /// The type of the distributed adjacency list (this type)
1327 typedef typename config_type::graph_type graph_type;
1329 /// Expose graph components and graph category
1330 typedef typename traits_type::local_vertex_descriptor
1331 local_vertex_descriptor;
1332 typedef typename traits_type::local_edge_descriptor
1333 local_edge_descriptor;
1334 typedef typename traits_type::vertex_descriptor vertex_descriptor;
1335 typedef typename traits_type::edge_descriptor edge_descriptor;
1337 typedef typename traits_type::directed_category directed_category;
1338 typedef typename inherited::edge_parallel_category
1339 edge_parallel_category;
1340 typedef typename inherited::graph_tag graph_tag;
1342 // Current implementation requires the ability to have parallel
1343 // edges in the underlying adjacency_list. Which processor each
1344 // edge refers to is attached as an internal property. TBD:
1345 // remove this restriction, which may require some rewriting.
1346 BOOST_STATIC_ASSERT((is_same<edge_parallel_category,
1347 allow_parallel_edge_tag>::value));
1349 /** Determine the graph traversal category.
1351 * A directed distributed adjacency list models the Distributed
1352 * Graph, Incidence Graph, and Adjacency Graph
1353 * concepts. Bidirectional and undirected graphs also model the
1354 * Bidirectional Graph concept. Note that when modeling these
1355 * concepts the domains of certain operations (e.g., in_edges)
1356 * are restricted; see the distributed adjacency_list
1359 typedef typename boost::mpl::if_<
1360 is_same<DirectedS, directedS>,
1361 directed_distributed_adj_list_tag,
1362 typename boost::mpl::if_<is_same<DirectedS, bidirectionalS>,
1363 bidirectional_distributed_adj_list_tag,
1364 undirected_distributed_adj_list_tag>::type>
1365 ::type traversal_category;
1367 typedef typename inherited::degree_size_type degree_size_type;
1368 typedef typename inherited::vertices_size_type vertices_size_type;
1369 typedef typename inherited::edges_size_type edges_size_type;
1370 typedef VertexProperty vertex_property_type;
1371 typedef EdgeProperty edge_property_type;
1372 typedef typename inherited::graph_property_type graph_property_type;
1373 typedef typename inherited::vertex_bundled vertex_bundled;
1374 typedef typename inherited::edge_bundled edge_bundled;
1375 typedef typename inherited::graph_bundled graph_bundled;
1377 typedef typename container_gen<edge_list_selector, edge_descriptor>::type
1378 local_edge_list_type;
1381 typedef typename boost::mpl::if_<is_same<DirectedS, bidirectionalS>,
1382 typename in_edge_list_type::const_iterator,
1383 typename inherited::out_edge_iterator>::type
1384 base_in_edge_iterator;
1386 typedef typename inherited::out_edge_iterator base_out_edge_iterator;
1387 typedef typename graph_traits<inherited>::edge_iterator
1389 typedef typename inherited::edge_property_type base_edge_property_type;
1391 typedef typename local_edge_list_type::const_iterator
1392 undirected_edge_iterator;
1394 typedef InDistribution in_distribution_type;
1396 typedef parallel::trigger_receive_context trigger_receive_context;
1399 /// Iterator over the (local) vertices of the graph
1400 typedef transform_iterator<typename vertex_descriptor::generator,
1401 typename inherited::vertex_iterator>
1404 /// Helper for out_edge_iterator
1405 typedef typename edge_descriptor::template out_generator<adjacency_list>
1408 /// Iterator over the outgoing edges of a vertex
1409 typedef transform_iterator<out_edge_generator,
1410 typename inherited::out_edge_iterator>
1413 /// Helper for in_edge_iterator
1414 typedef typename edge_descriptor::template in_generator<adjacency_list>
1417 /// Iterator over the incoming edges of a vertex
1418 typedef transform_iterator<in_edge_generator, base_in_edge_iterator>
1421 /// Iterator over the neighbors of a vertex
1422 typedef boost::adjacency_iterator<
1423 adjacency_list, vertex_descriptor, out_edge_iterator,
1424 typename detail::iterator_traits<base_out_edge_iterator>
1428 /// Iterator over the (local) edges in a graph
1429 typedef typename boost::mpl::if_<is_same<DirectedS, undirectedS>,
1430 undirected_edge_iterator,
1431 transform_iterator<out_edge_generator,
1437 /// The type of the mixin for named vertices
1438 typedef graph::distributed::maybe_named_graph<graph_type,
1444 /// Process group used for communication
1445 typedef ProcessGroup process_group_type;
1447 /// How to refer to a process
1448 typedef typename process_group_type::process_id_type process_id_type;
1450 /// Whether this graph is directed, undirected, or bidirectional
1451 typedef DirectedS directed_selector;
1453 // Structure used for the lazy addition of vertices
1454 struct lazy_add_vertex_with_property;
1455 friend struct lazy_add_vertex_with_property;
1457 // Structure used for the lazy addition of edges
1458 struct lazy_add_edge;
1459 friend struct lazy_add_edge;
1461 // Structure used for the lazy addition of edges with properties
1462 struct lazy_add_edge_with_property;
1463 friend struct lazy_add_edge_with_property;
1465 /// default_distribution_type is the type of the distribution used if the
1466 /// user didn't specify an explicit one
1467 typedef typename graph::distributed::select_distribution<
1468 InDistribution, VertexProperty, vertices_size_type,
1469 ProcessGroup>::default_type
1470 default_distribution_type;
1472 /// distribution_type is the type of the distribution instance stored in
1473 /// the maybe_named_graph base class
1474 typedef typename graph::distributed::select_distribution<
1475 InDistribution, VertexProperty, vertices_size_type,
1477 base_distribution_type;
1479 typedef graph::distributed::shuffled_distribution<
1480 base_distribution_type> distribution_type;
1483 // FIXME: the original adjacency_list contained this comment:
1484 // Default copy constructor and copy assignment operators OK??? TBD
1485 // but the adj_list_impl contained these declarations:
1486 adjacency_list(const adjacency_list& other);
1487 adjacency_list& operator=(const adjacency_list& other);
1490 adjacency_list(const ProcessGroup& pg = ProcessGroup())
1491 : named_graph_mixin(pg, default_distribution_type(pg, 0)),
1492 m_local_graph(GraphProperty()),
1493 process_group_(pg, boost::parallel::attach_distributed_object())
1498 adjacency_list(const ProcessGroup& pg,
1499 const base_distribution_type& distribution)
1500 : named_graph_mixin(pg, distribution),
1501 m_local_graph(GraphProperty()),
1502 process_group_(pg, boost::parallel::attach_distributed_object())
1507 adjacency_list(const GraphProperty& g,
1508 const ProcessGroup& pg = ProcessGroup())
1509 : named_graph_mixin(pg, default_distribution_type(pg, 0)),
1511 process_group_(pg, boost::parallel::attach_distributed_object())
1516 adjacency_list(vertices_size_type n,
1517 const GraphProperty& p,
1518 const ProcessGroup& pg,
1519 const base_distribution_type& distribution)
1520 : named_graph_mixin(pg, distribution),
1521 m_local_graph(distribution.block_size(process_id(pg), n), p),
1522 process_group_(pg, boost::parallel::attach_distributed_object())
1526 detail::parallel::maybe_initialize_vertex_indices(vertices(base()),
1527 get(vertex_index, base()));
1530 adjacency_list(vertices_size_type n,
1531 const ProcessGroup& pg,
1532 const base_distribution_type& distribution)
1533 : named_graph_mixin(pg, distribution),
1534 m_local_graph(distribution.block_size(process_id(pg), n), GraphProperty()),
1535 process_group_(pg, boost::parallel::attach_distributed_object())
1539 detail::parallel::maybe_initialize_vertex_indices(vertices(base()),
1540 get(vertex_index, base()));
1543 adjacency_list(vertices_size_type n,
1544 const GraphProperty& p,
1545 const ProcessGroup& pg = ProcessGroup())
1546 : named_graph_mixin(pg, default_distribution_type(pg, n)),
1547 m_local_graph(this->distribution().block_size(process_id(pg), n), p),
1548 process_group_(pg, boost::parallel::attach_distributed_object())
1552 detail::parallel::maybe_initialize_vertex_indices(vertices(base()),
1553 get(vertex_index, base()));
1556 adjacency_list(vertices_size_type n,
1557 const ProcessGroup& pg = ProcessGroup())
1558 : named_graph_mixin(pg, default_distribution_type(pg, n)),
1559 m_local_graph(this->distribution().block_size(process_id(pg), n),
1561 process_group_(pg, boost::parallel::attach_distributed_object())
1565 detail::parallel::maybe_initialize_vertex_indices(vertices(base()),
1566 get(vertex_index, base()));
1570 * We assume that every processor sees the same list of edges, so
1571 * they skip over any that don't originate from themselves. This
1572 * means that programs switching between a local and a distributed
1573 * graph will keep the same semantics.
1575 template <class EdgeIterator>
1576 adjacency_list(EdgeIterator first, EdgeIterator last,
1577 vertices_size_type n,
1578 const ProcessGroup& pg = ProcessGroup(),
1579 const GraphProperty& p = GraphProperty())
1580 : named_graph_mixin(pg, default_distribution_type(pg, n)),
1581 m_local_graph(this->distribution().block_size(process_id(pg), n), p),
1582 process_group_(pg, boost::parallel::attach_distributed_object())
1586 typedef typename config_type::VertexListS vertex_list_selector;
1587 initialize(first, last, n, this->distribution(), vertex_list_selector());
1588 detail::parallel::maybe_initialize_vertex_indices(vertices(base()),
1589 get(vertex_index, base()));
1593 template <class EdgeIterator, class EdgePropertyIterator>
1594 adjacency_list(EdgeIterator first, EdgeIterator last,
1595 EdgePropertyIterator ep_iter,
1596 vertices_size_type n,
1597 const ProcessGroup& pg = ProcessGroup(),
1598 const GraphProperty& p = GraphProperty())
1599 : named_graph_mixin(pg, default_distribution_type(pg, n)),
1600 m_local_graph(this->distribution().block_size(process_id(pg), n), p),
1601 process_group_(pg, boost::parallel::attach_distributed_object())
1605 typedef typename config_type::VertexListS vertex_list_selector;
1606 initialize(first, last, ep_iter, n, this->distribution(),
1607 vertex_list_selector());
1608 detail::parallel::maybe_initialize_vertex_indices(vertices(base()),
1609 get(vertex_index, base()));
1613 template <class EdgeIterator>
1614 adjacency_list(EdgeIterator first, EdgeIterator last,
1615 vertices_size_type n,
1616 const ProcessGroup& pg,
1617 const base_distribution_type& distribution,
1618 const GraphProperty& p = GraphProperty())
1619 : named_graph_mixin(pg, distribution),
1620 m_local_graph(distribution.block_size(process_id(pg), n), p),
1621 process_group_(pg, boost::parallel::attach_distributed_object())
1625 typedef typename config_type::VertexListS vertex_list_selector;
1626 initialize(first, last, n, this->distribution(), vertex_list_selector());
1627 detail::parallel::maybe_initialize_vertex_indices(vertices(base()),
1628 get(vertex_index, base()));
1632 template <class EdgeIterator, class EdgePropertyIterator>
1633 adjacency_list(EdgeIterator first, EdgeIterator last,
1634 EdgePropertyIterator ep_iter,
1635 vertices_size_type n,
1636 const ProcessGroup& pg,
1637 const base_distribution_type& distribution,
1638 const GraphProperty& p = GraphProperty())
1639 : named_graph_mixin(pg, distribution),
1640 m_local_graph(this->distribution().block_size(process_id(pg), n), p),
1641 process_group_(pg, boost::parallel::attach_distributed_object())
1645 typedef typename config_type::VertexListS vertex_list_selector;
1646 initialize(first, last, ep_iter, n, distribution,
1647 vertex_list_selector());
1648 detail::parallel::maybe_initialize_vertex_indices(vertices(base()),
1649 get(vertex_index, base()));
1655 synchronize(process_group_);
1661 local_edges_.clear();
1662 named_graph_mixin::clearing_graph();
1665 void swap(adjacency_list& other)
1670 swap(process_group_, other.process_group_);
1673 static vertex_descriptor null_vertex()
1675 return vertex_descriptor(processor_id_type(0),
1676 inherited::null_vertex());
1679 inherited& base() { return m_local_graph; }
1680 const inherited& base() const { return m_local_graph; }
1682 processor_id_type processor() const { return process_id(process_group_); }
1683 process_group_type process_group() const { return process_group_.base(); }
1685 local_edge_list_type& local_edges() { return local_edges_; }
1686 const local_edge_list_type& local_edges() const { return local_edges_; }
1688 // Redistribute the vertices of the graph by placing each vertex
1689 // v on the processor get(vertex_to_processor, v).
1690 template<typename VertexProcessorMap>
1691 void redistribute(VertexProcessorMap vertex_to_processor);
1693 // Directly access a vertex or edge bundle
1694 vertex_bundled& operator[](vertex_descriptor v)
1696 BOOST_ASSERT(v.owner == processor());
1697 return base()[v.local];
1700 const vertex_bundled& operator[](vertex_descriptor v) const
1702 BOOST_ASSERT(v.owner == processor());
1703 return base()[v.local];
1706 edge_bundled& operator[](edge_descriptor e)
1708 BOOST_ASSERT(e.owner() == processor());
1709 return base()[e.local];
1712 const edge_bundled& operator[](edge_descriptor e) const
1714 BOOST_ASSERT(e.owner() == processor());
1715 return base()[e.local];
1718 graph_bundled& operator[](graph_bundle_t)
1719 { return get_property(*this); }
1721 graph_bundled const& operator[](graph_bundle_t) const
1722 { return get_property(*this); }
1724 template<typename OStreamConstructibleArchive>
1725 void save(std::string const& filename) const;
1727 template<typename IStreamConstructibleArchive>
1728 void load(std::string const& filename);
1730 // Callback that will be invoked whenever a new vertex is added locally
1731 boost::function<void(vertex_descriptor, adjacency_list&)> on_add_vertex;
1733 // Callback that will be invoked whenever a new edge is added locally
1734 boost::function<void(edge_descriptor, adjacency_list&)> on_add_edge;
1737 // Request vertex->processor mapping for neighbors <does nothing>
1738 template<typename VertexProcessorMap>
1740 request_in_neighbors(vertex_descriptor,
1744 // Request vertex->processor mapping for neighbors <does nothing>
1745 template<typename VertexProcessorMap>
1747 request_in_neighbors(vertex_descriptor,
1751 // Request vertex->processor mapping for neighbors
1752 template<typename VertexProcessorMap>
1754 request_in_neighbors(vertex_descriptor v,
1755 VertexProcessorMap vertex_to_processor,
1758 // Clear the list of in-edges, but don't tell the remote processor
1759 void clear_in_edges_local(vertex_descriptor v, directedS) {}
1760 void clear_in_edges_local(vertex_descriptor v, undirectedS) {}
1762 void clear_in_edges_local(vertex_descriptor v, bidirectionalS)
1763 { get(vertex_in_edges, base())[v.local].clear(); }
1765 // Remove in-edges that have migrated <does nothing>
1766 template<typename VertexProcessorMap>
1768 remove_migrated_in_edges(vertex_descriptor,
1772 // Remove in-edges that have migrated <does nothing>
1773 template<typename VertexProcessorMap>
1775 remove_migrated_in_edges(vertex_descriptor,
1779 // Remove in-edges that have migrated
1780 template<typename VertexProcessorMap>
1782 remove_migrated_in_edges(vertex_descriptor v,
1783 VertexProcessorMap vertex_to_processor,
1786 // Initialize the graph with the given edge list and vertex
1787 // distribution. This variation works only when
1788 // VertexListS=vecS, and we know how to create remote vertex
1789 // descriptors based solely on the distribution.
1790 template<typename EdgeIterator>
1792 initialize(EdgeIterator first, EdgeIterator last,
1793 vertices_size_type, const base_distribution_type& distribution,
1796 // Initialize the graph with the given edge list, edge
1797 // properties, and vertex distribution. This variation works
1798 // only when VertexListS=vecS, and we know how to create remote
1799 // vertex descriptors based solely on the distribution.
1800 template<typename EdgeIterator, typename EdgePropertyIterator>
1802 initialize(EdgeIterator first, EdgeIterator last,
1803 EdgePropertyIterator ep_iter,
1804 vertices_size_type, const base_distribution_type& distribution,
1807 // Initialize the graph with the given edge list, edge
1808 // properties, and vertex distribution.
1809 template<typename EdgeIterator, typename EdgePropertyIterator,
1810 typename VertexListS>
1812 initialize(EdgeIterator first, EdgeIterator last,
1813 EdgePropertyIterator ep_iter,
1814 vertices_size_type n,
1815 const base_distribution_type& distribution,
1818 // Initialize the graph with the given edge list and vertex
1819 // distribution. This is nearly identical to the one below it,
1820 // for which I should be flogged. However, this version does use
1821 // slightly less memory than the version that accepts an edge
1822 // property iterator.
1823 template<typename EdgeIterator, typename VertexListS>
1825 initialize(EdgeIterator first, EdgeIterator last,
1826 vertices_size_type n,
1827 const base_distribution_type& distribution,
1831 //---------------------------------------------------------------------
1832 // Build a vertex property instance for the underlying adjacency
1833 // list from the given property instance of the type exposed to
1835 base_vertex_property_type
1836 build_vertex_property(const vertex_property_type& p)
1837 { return build_vertex_property(p, directed_selector()); }
1839 base_vertex_property_type
1840 build_vertex_property(const vertex_property_type& p, directedS)
1842 return base_vertex_property_type(p);
1845 base_vertex_property_type
1846 build_vertex_property(const vertex_property_type& p, bidirectionalS)
1848 return base_vertex_property_type(in_edge_list_type(), p);
1851 base_vertex_property_type
1852 build_vertex_property(const vertex_property_type& p, undirectedS)
1854 return base_vertex_property_type(p);
1856 //---------------------------------------------------------------------
1858 //---------------------------------------------------------------------
1859 // Build an edge property instance for the underlying adjacency
1860 // list from the given property instance of the type exposed to
1862 base_edge_property_type build_edge_property(const edge_property_type& p)
1863 { return build_edge_property(p, directed_selector()); }
1865 base_edge_property_type
1866 build_edge_property(const edge_property_type& p, directedS)
1868 return base_edge_property_type(0, p);
1871 base_edge_property_type
1872 build_edge_property(const edge_property_type& p, bidirectionalS)
1874 return base_edge_property_type(0, p);
1877 base_edge_property_type
1878 build_edge_property(const edge_property_type& p, undirectedS)
1880 typedef typename base_edge_property_type::next_type
1881 edge_property_with_id;
1882 return base_edge_property_type(true, edge_property_with_id(0, p));
1884 //---------------------------------------------------------------------
1886 //---------------------------------------------------------------------
1887 // Opposite of above.
1888 edge_property_type split_edge_property(const base_edge_property_type& p)
1889 { return split_edge_property(p, directed_selector()); }
1892 split_edge_property(const base_edge_property_type& p, directedS)
1898 split_edge_property(const base_edge_property_type& p, bidirectionalS)
1904 split_edge_property(const base_edge_property_type& p, undirectedS)
1906 return p.m_base.m_base;
1908 //---------------------------------------------------------------------
1910 /** The set of messages that can be transmitted and received by
1911 * a distributed adjacency list. This list will eventually be
1912 * exhaustive, but is currently quite limited.
1916 * Request to add or find a vertex with the given vertex
1917 * property. The data will be a vertex_property_type
1920 msg_add_vertex_with_property = 0,
1923 * Request to add or find a vertex with the given vertex
1924 * property, and request that the remote processor return the
1925 * descriptor for the added/found edge. The data will be a
1926 * vertex_property_type structure.
1928 msg_add_vertex_with_property_and_reply,
1931 * Reply to a msg_add_vertex_* message, containing the local
1932 * vertex descriptor that was added or found.
1934 msg_add_vertex_reply,
1937 * Request to add an edge remotely. The data will be a
1938 * msg_add_edge_data structure.
1943 * Request to add an edge remotely. The data will be a
1944 * msg_add_edge_with_property_data structure.
1946 msg_add_edge_with_property,
1949 * Request to add an edge remotely and reply back with the
1950 * edge descriptor. The data will be a
1951 * msg_add_edge_data structure.
1953 msg_add_edge_with_reply,
1956 * Request to add an edge remotely and reply back with the
1957 * edge descriptor. The data will be a
1958 * msg_add_edge_with_property_data structure.
1960 msg_add_edge_with_property_and_reply,
1963 * Reply message responding to an @c msg_add_edge_with_reply
1964 * or @c msg_add_edge_with_property_and_reply messages. The
1965 * data will be a std::pair<edge_descriptor, bool>.
1970 * Indicates that a nonlocal edge has been created that should
1971 * be added locally. Only valid for bidirectional and
1972 * undirected graphs. The message carries a
1973 * msg_nonlocal_edge_data structure.
1978 * Indicates that a remote edge should be removed. This
1979 * message does not exist for directedS graphs but may refer
1980 * to either in-edges or out-edges for undirectedS graphs.
1985 * Indicates the number of vertices and edges that will be
1986 * relocated from the source processor to the target
1987 * processor. The data will be a pair<vertices_size_type,
1993 typedef detail::parallel::msg_add_edge_data<vertex_descriptor,
1994 local_vertex_descriptor>
1997 typedef detail::parallel::msg_add_edge_with_property_data
1998 <vertex_descriptor, local_vertex_descriptor,
1999 edge_property_type> msg_add_edge_with_property_data;
2001 typedef boost::detail::parallel::msg_nonlocal_edge_data<
2002 edge_property_type,local_edge_descriptor> msg_nonlocal_edge_data;
2004 typedef boost::detail::parallel::msg_remove_edge_data<edge_descriptor>
2005 msg_remove_edge_data;
2007 void send_remove_edge_request(edge_descriptor e)
2009 process_id_type dest = e.target_processor;
2010 if (e.target_processor == process_id(process_group_))
2011 dest = e.source_processor;
2012 send(process_group_, dest, msg_remove_edge, msg_remove_edge_data(e));
2015 /// Process incoming messages.
2016 void setup_triggers();
2019 handle_add_vertex_with_property(int source, int tag,
2020 const vertex_property_type&,
2021 trigger_receive_context);
2023 local_vertex_descriptor
2024 handle_add_vertex_with_property_and_reply(int source, int tag,
2025 const vertex_property_type&,
2026 trigger_receive_context);
2029 handle_add_edge(int source, int tag, const msg_add_edge_data& data,
2030 trigger_receive_context);
2032 boost::parallel::detail::untracked_pair<edge_descriptor, bool>
2033 handle_add_edge_with_reply(int source, int tag,
2034 const msg_add_edge_data& data,
2035 trigger_receive_context);
2038 handle_add_edge_with_property(int source, int tag,
2039 const msg_add_edge_with_property_data&,
2040 trigger_receive_context);
2042 boost::parallel::detail::untracked_pair<edge_descriptor, bool>
2043 handle_add_edge_with_property_and_reply
2044 (int source, int tag, const msg_add_edge_with_property_data&,
2045 trigger_receive_context);
2048 handle_nonlocal_edge(int source, int tag,
2049 const msg_nonlocal_edge_data& data,
2050 trigger_receive_context);
2053 handle_remove_edge(int source, int tag,
2054 const msg_remove_edge_data& data,
2055 trigger_receive_context);
2058 /** Add an edge (locally) that was received from another
2059 * processor. This operation is a no-op for directed graphs,
2060 * because all edges reside on the local processor. For
2061 * bidirectional graphs, this routine places the edge onto the
2062 * list of incoming edges for the target vertex. For undirected
2063 * graphs, the edge is placed along with all of the other edges
2064 * for the target vertex, but it is marked as a non-local edge
2067 * \todo There is a potential problem here, where we could
2068 * unintentionally allow duplicate edges in undirected graphs
2069 * because the same edge is added on two different processors
2070 * simultaneously. It's not an issue now, because we require
2071 * that the graph allow parallel edges. Once we do support
2072 * containers such as setS or hash_setS that disallow parallel
2073 * edges we will need to deal with this.
2076 add_remote_edge(const msg_nonlocal_edge_data&,
2077 processor_id_type, directedS)
2085 add_remote_edge(const msg_nonlocal_edge_data& data,
2086 processor_id_type other_proc, bidirectionalS)
2088 typedef detail::parallel::stored_in_edge<local_edge_descriptor> stored_edge;
2090 stored_edge edge(other_proc, data.e);
2091 local_vertex_descriptor v = target(data.e, base());
2092 boost::graph_detail::push(get(vertex_in_edges, base())[v], edge);
2099 add_remote_edge(const msg_nonlocal_edge_data& data,
2100 processor_id_type other_proc, undirectedS)
2102 std::pair<local_edge_descriptor, bool> edge =
2103 detail::parallel::add_local_edge(target(data.e, base()),
2104 source(data.e, base()),
2105 build_edge_property(data.get_property()), base());
2106 BOOST_ASSERT(edge.second);
2107 put(edge_target_processor_id, base(), edge.first, other_proc);
2109 if (edge.second && on_add_edge)
2110 on_add_edge(edge_descriptor(processor(), other_proc, false,
2116 remove_local_edge(const msg_remove_edge_data&, processor_id_type,
2121 remove_local_edge(const msg_remove_edge_data& data,
2122 processor_id_type other_proc, bidirectionalS)
2124 /* When the source is local, we first check if the edge still
2125 * exists (it may have been deleted locally) and, if so,
2126 * remove it locally.
2128 vertex_descriptor src = source(data.e, *this);
2129 vertex_descriptor tgt = target(data.e, *this);
2131 if (src.owner == process_id(process_group_)) {
2132 base_out_edge_iterator ei, ei_end;
2133 for (boost::tie(ei, ei_end) = out_edges(src.local, base());
2134 ei != ei_end; ++ei) {
2135 // TBD: can't check the descriptor here, because it could
2136 // have changed if we're allowing the removal of
2138 if (tgt.local == target(*ei, base())
2139 && get(edge_target_processor_id, base(), *ei) == other_proc)
2143 if (ei != ei_end) boost::remove_edge(ei, base());
2145 remove_local_edge_from_list(src, tgt, undirectedS());
2147 BOOST_ASSERT(tgt.owner == process_id(process_group_));
2148 in_edge_list_type& in_edges =
2149 get(vertex_in_edges, base())[tgt.local];
2150 typename in_edge_list_type::iterator ei;
2151 for (ei = in_edges.begin(); ei != in_edges.end(); ++ei) {
2152 if (src.local == source(ei->e, base())
2153 && src.owner == ei->source_processor)
2157 if (ei != in_edges.end()) in_edges.erase(ei);
2162 remove_local_edge(const msg_remove_edge_data& data,
2163 processor_id_type other_proc, undirectedS)
2165 vertex_descriptor local_vertex = source(data.e, *this);
2166 vertex_descriptor remote_vertex = target(data.e, *this);
2167 if (remote_vertex.owner == process_id(process_group_)) {
2169 swap(local_vertex, remote_vertex);
2172 // Remove the edge from the out-edge list, if it is there
2174 base_out_edge_iterator ei, ei_end;
2175 for (boost::tie(ei, ei_end) = out_edges(local_vertex.local, base());
2176 ei != ei_end; ++ei) {
2177 // TBD: can't check the descriptor here, because it could
2178 // have changed if we're allowing the removal of
2180 if (remote_vertex.local == target(*ei, base())
2181 && get(edge_target_processor_id, base(), *ei) == other_proc)
2185 if (ei != ei_end) boost::remove_edge(ei, base());
2188 remove_local_edge_from_list(local_vertex, remote_vertex, undirectedS());
2193 remove_local_edge_from_list(vertex_descriptor, vertex_descriptor,
2199 remove_local_edge_from_list(vertex_descriptor, vertex_descriptor,
2205 remove_local_edge_from_list(vertex_descriptor src, vertex_descriptor tgt,
2208 // TBD: At some point we'll be able to improve the speed here
2209 // because we'll know when the edge can't be in the local
2212 typename local_edge_list_type::iterator ei;
2213 for (ei = local_edges_.begin(); ei != local_edges_.end(); ++ei) {
2214 if ((source(*ei, *this) == src
2215 && target(*ei, *this) == tgt)
2216 || (source(*ei, *this) == tgt
2217 && target(*ei, *this) == src))
2221 if (ei != local_edges_.end()) local_edges_.erase(ei);
2227 /// The local subgraph
2228 inherited m_local_graph;
2230 /// The process group through which this distributed graph
2232 process_group_type process_group_;
2234 // TBD: should only be available for undirected graphs, but for
2235 // now it'll just be empty for directed and bidirectional
2237 local_edge_list_type local_edges_;
2240 //------------------------------------------------------------------------
2241 // Lazy addition of vertices
2242 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
2243 struct PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_vertex_with_property
2245 /// Construct a lazy request to add a vertex
2246 lazy_add_vertex_with_property(adjacency_list& self,
2247 const vertex_property_type& property)
2248 : self(self), property(property), committed(false) { }
2250 /// Copying a lazy_add_vertex_with_property transfers the
2251 /// responsibility for adding the vertex to the newly-constructed
2253 lazy_add_vertex_with_property(const lazy_add_vertex_with_property& other)
2254 : self(other.self), property(other.property),
2255 committed(other.committed)
2257 other.committed = true;
2260 /// If the vertex has not yet been added, add the vertex but don't
2261 /// wait for a reply.
2262 ~lazy_add_vertex_with_property();
2264 /// Returns commit().
2265 operator vertex_descriptor() const { return commit(); }
2267 // Add the vertex. This operation will block if the vertex is
2268 // being added remotely.
2269 vertex_descriptor commit() const;
2272 adjacency_list& self;
2273 vertex_property_type property;
2274 mutable bool committed;
2277 // No copy-assignment semantics
2278 void operator=(lazy_add_vertex_with_property&);
2281 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
2282 PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_vertex_with_property::
2283 ~lazy_add_vertex_with_property()
2285 /// If this vertex has already been created or will be created by
2286 /// someone else, or if someone threw an exception, we will not
2287 /// create the vertex now.
2288 if (committed || std::uncaught_exception())
2293 process_id_type owner
2294 = static_cast<graph_type&>(self).owner_by_property(property);
2295 if (owner == self.processor()) {
2296 /// Add the vertex locally.
2297 vertex_descriptor v(owner,
2298 add_vertex(self.build_vertex_property(property),
2300 if (self.on_add_vertex)
2301 self.on_add_vertex(v, self);
2304 /// Ask the owner of this new vertex to add the vertex. We
2305 /// don't need a reply.
2306 send(self.process_group_, owner, msg_add_vertex_with_property,
2310 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
2311 typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor
2312 PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_vertex_with_property::
2315 BOOST_ASSERT(!this->committed);
2316 this->committed = true;
2318 process_id_type owner
2319 = static_cast<graph_type&>(self).owner_by_property(property);
2320 local_vertex_descriptor local_v;
2321 if (owner == self.processor())
2322 /// Add the vertex locally.
2323 local_v = add_vertex(self.build_vertex_property(property),
2326 // Request that the remote process add the vertex immediately
2327 send_oob_with_reply(self.process_group_, owner,
2328 msg_add_vertex_with_property_and_reply, property,
2332 vertex_descriptor v(owner, local_v);
2333 if (self.on_add_vertex)
2334 self.on_add_vertex(v, self);
2336 // Build the full vertex descriptor to return
2342 * Data structure returned from add_edge that will "lazily" add
2343 * the edge, either when it is converted to a
2344 * @c pair<edge_descriptor, bool> or when the most recent copy has
2347 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
2348 struct PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_edge
2350 /// Construct a lazy request to add an edge
2351 lazy_add_edge(adjacency_list& self,
2352 vertex_descriptor source, vertex_descriptor target)
2353 : self(self), source(source), target(target), committed(false) { }
2355 /// Copying a lazy_add_edge transfers the responsibility for
2356 /// adding the edge to the newly-constructed object.
2357 lazy_add_edge(const lazy_add_edge& other)
2358 : self(other.self), source(other.source), target(other.target),
2359 committed(other.committed)
2361 other.committed = true;
2364 /// If the edge has not yet been added, add the edge but don't
2365 /// wait for a reply.
2368 /// Returns commit().
2369 operator std::pair<edge_descriptor, bool>() const { return commit(); }
2371 // Add the edge. This operation will block if a remote edge is
2373 std::pair<edge_descriptor, bool> commit() const;
2376 std::pair<edge_descriptor, bool>
2377 add_local_edge(const edge_property_type& property, directedS) const;
2379 std::pair<edge_descriptor, bool>
2380 add_local_edge(const edge_property_type& property, bidirectionalS) const;
2382 std::pair<edge_descriptor, bool>
2383 add_local_edge(const edge_property_type& property, undirectedS) const;
2385 adjacency_list& self;
2386 vertex_descriptor source;
2387 vertex_descriptor target;
2388 mutable bool committed;
2391 // No copy-assignment semantics
2392 void operator=(lazy_add_edge&);
2395 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
2396 PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_edge::~lazy_add_edge()
2398 /// If this edge has already been created or will be created by
2399 /// someone else, or if someone threw an exception, we will not
2400 /// create the edge now.
2401 if (committed || std::uncaught_exception())
2406 if (source.owner == self.processor())
2407 this->add_local_edge(edge_property_type(), DirectedS());
2409 // Request that the remote processor add an edge and, but
2410 // don't wait for a reply.
2411 send(self.process_group_, source.owner, msg_add_edge,
2412 msg_add_edge_data(source, target));
2415 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
2416 std::pair<typename PBGL_DISTRIB_ADJLIST_TYPE::edge_descriptor, bool>
2417 PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_edge::commit() const
2419 BOOST_ASSERT(!committed);
2422 if (source.owner == self.processor())
2423 return this->add_local_edge(edge_property_type(), DirectedS());
2425 // Request that the remote processor add an edge
2426 boost::parallel::detail::untracked_pair<edge_descriptor, bool> result;
2427 send_oob_with_reply(self.process_group_, source.owner,
2428 msg_add_edge_with_reply,
2429 msg_add_edge_data(source, target), result);
2434 // Add a local edge into a directed graph
2435 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
2436 std::pair<typename PBGL_DISTRIB_ADJLIST_TYPE::edge_descriptor, bool>
2437 PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_edge::
2438 add_local_edge(const edge_property_type& property, directedS) const
2440 // Add the edge to the local part of the graph
2441 std::pair<local_edge_descriptor, bool> inserted =
2442 detail::parallel::add_local_edge(source.local, target.local,
2443 self.build_edge_property(property),
2446 if (inserted.second)
2447 // Keep track of the owner of the target
2448 put(edge_target_processor_id, self.base(), inserted.first,
2451 // Compose the edge descriptor and return the result
2452 edge_descriptor e(source.owner, target.owner, true, inserted.first);
2454 // Trigger the on_add_edge event
2455 if (inserted.second && self.on_add_edge)
2456 self.on_add_edge(e, self);
2458 return std::pair<edge_descriptor, bool>(e, inserted.second);
2461 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
2462 std::pair<typename PBGL_DISTRIB_ADJLIST_TYPE::edge_descriptor, bool>
2463 PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_edge::
2464 add_local_edge(const edge_property_type& property, bidirectionalS) const
2466 // Add the directed edge.
2467 std::pair<edge_descriptor, bool> result
2468 = this->add_local_edge(property, directedS());
2470 if (result.second) {
2471 if (target.owner == self.processor()) {
2472 // Edge is local, so add the stored edge to the in_edges list
2473 typedef detail::parallel::stored_in_edge<local_edge_descriptor>
2476 stored_edge e(self.processor(), result.first.local);
2477 boost::graph_detail::push(get(vertex_in_edges,
2478 self.base())[target.local], e);
2481 // Edge is remote, so notify the target's owner that an edge
2483 if (self.process_group_.trigger_context() == boost::parallel::trc_out_of_band)
2484 send_oob(self.process_group_, target.owner, msg_nonlocal_edge,
2485 msg_nonlocal_edge_data(result.first.local, property));
2487 send(self.process_group_, target.owner, msg_nonlocal_edge,
2488 msg_nonlocal_edge_data(result.first.local, property));
2495 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
2496 std::pair<typename PBGL_DISTRIB_ADJLIST_TYPE::edge_descriptor, bool>
2497 PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_edge::
2498 add_local_edge(const edge_property_type& property, undirectedS) const
2500 // Add the directed edge
2501 std::pair<edge_descriptor, bool> result
2502 = this->add_local_edge(property, directedS());
2504 if (result.second) {
2505 if (target.owner == self.processor()) {
2506 // Edge is local, so add the new edge to the list
2508 // TODO: This is not what we want to do for an undirected
2509 // edge, because we haven't linked the source and target's
2510 // representations of those edges.
2511 local_edge_descriptor return_edge =
2512 detail::parallel::add_local_edge(target.local, source.local,
2513 self.build_edge_property(property),
2516 put(edge_target_processor_id, self.base(), return_edge,
2520 // Edge is remote, so notify the target's owner that an edge
2522 if (self.process_group_.trigger_context() == boost::parallel::trc_out_of_band)
2523 send_oob(self.process_group_, target.owner, msg_nonlocal_edge,
2524 msg_nonlocal_edge_data(result.first.local, property));
2526 send(self.process_group_, target.owner, msg_nonlocal_edge,
2527 msg_nonlocal_edge_data(result.first.local, property));
2531 // Add this edge to the list of local edges
2532 graph_detail::push(self.local_edges(), result.first);
2540 * Data structure returned from add_edge that will "lazily" add
2541 * the edge with its property, either when it is converted to a
2542 * pair<edge_descriptor, bool> or when the most recent copy has
2545 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
2546 struct PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_edge_with_property
2549 /// Construct a lazy request to add an edge
2550 lazy_add_edge_with_property(adjacency_list& self,
2551 vertex_descriptor source,
2552 vertex_descriptor target,
2553 const edge_property_type& property)
2554 : lazy_add_edge(self, source, target), property(property) { }
2556 /// Copying a lazy_add_edge transfers the responsibility for
2557 /// adding the edge to the newly-constructed object.
2558 lazy_add_edge_with_property(const lazy_add_edge& other)
2559 : lazy_add_edge(other), property(other.property) { }
2561 /// If the edge has not yet been added, add the edge but don't
2562 /// wait for a reply.
2563 ~lazy_add_edge_with_property();
2565 /// Returns commit().
2566 operator std::pair<edge_descriptor, bool>() const { return commit(); }
2568 // Add the edge. This operation will block if a remote edge is
2570 std::pair<edge_descriptor, bool> commit() const;
2573 // No copy-assignment semantics
2574 void operator=(lazy_add_edge_with_property&);
2576 edge_property_type property;
2579 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
2580 PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_edge_with_property::
2581 ~lazy_add_edge_with_property()
2583 /// If this edge has already been created or will be created by
2584 /// someone else, or if someone threw an exception, we will not
2585 /// create the edge now.
2586 if (this->committed || std::uncaught_exception())
2589 this->committed = true;
2591 if (this->source.owner == this->self.processor())
2593 this->add_local_edge(property, DirectedS());
2595 // Request that the remote processor add an edge and, but
2596 // don't wait for a reply.
2597 send(this->self.process_group_, this->source.owner,
2598 msg_add_edge_with_property,
2599 msg_add_edge_with_property_data(this->source, this->target,
2603 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
2604 std::pair<typename PBGL_DISTRIB_ADJLIST_TYPE::edge_descriptor, bool>
2605 PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_edge_with_property::
2608 BOOST_ASSERT(!this->committed);
2609 this->committed = true;
2611 if (this->source.owner == this->self.processor())
2613 return this->add_local_edge(property, DirectedS());
2615 // Request that the remote processor add an edge
2616 boost::parallel::detail::untracked_pair<edge_descriptor, bool> result;
2617 send_oob_with_reply(this->self.process_group_, this->source.owner,
2618 msg_add_edge_with_property_and_reply,
2619 msg_add_edge_with_property_data(this->source,
2629 * Returns the set of vertices local to this processor. Note that
2630 * although this routine matches a valid expression of a
2631 * VertexListGraph, it does not meet the semantic requirements of
2632 * VertexListGraph because it returns only local vertices (not all
2635 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
2636 std::pair<typename PBGL_DISTRIB_ADJLIST_TYPE
2638 typename PBGL_DISTRIB_ADJLIST_TYPE
2640 vertices(const PBGL_DISTRIB_ADJLIST_TYPE& g)
2642 typedef typename PBGL_DISTRIB_ADJLIST_TYPE
2643 ::vertex_descriptor Vertex;
2645 typedef typename Vertex::generator generator;
2647 return std::make_pair(make_transform_iterator(vertices(g.base()).first,
2648 generator(g.processor())),
2649 make_transform_iterator(vertices(g.base()).second,
2650 generator(g.processor())));
2654 * Returns the number of vertices local to this processor. Note that
2655 * although this routine matches a valid expression of a
2656 * VertexListGraph, it does not meet the semantic requirements of
2657 * VertexListGraph because it returns only a count of local vertices
2658 * (not all vertices).
2660 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
2661 typename PBGL_DISTRIB_ADJLIST_TYPE
2662 ::vertices_size_type
2663 num_vertices(const PBGL_DISTRIB_ADJLIST_TYPE& g)
2665 return num_vertices(g.base());
2668 /***************************************************************************
2669 * Implementation of Incidence Graph concept
2670 ***************************************************************************/
2672 * Returns the source of edge @param e in @param g.
2674 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS, typename Edge>
2675 typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor
2676 source(const detail::parallel::edge_descriptor<Edge>& e,
2677 const PBGL_DISTRIB_ADJLIST_TYPE& g)
2679 typedef typename PBGL_DISTRIB_ADJLIST_TYPE
2680 ::vertex_descriptor Vertex;
2681 return Vertex(e.source_processor, source(e.local, g.base()));
2685 * Returns the target of edge @param e in @param g.
2687 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS, typename Edge>
2688 typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor
2689 target(const detail::parallel::edge_descriptor<Edge>& e,
2690 const PBGL_DISTRIB_ADJLIST_TYPE& g)
2692 typedef typename PBGL_DISTRIB_ADJLIST_TYPE
2693 ::vertex_descriptor Vertex;
2694 return Vertex(e.target_processor, target(e.local, g.base()));
2698 * Return the set of edges outgoing from a particular vertex. The
2699 * vertex @param v must be local to the processor executing this
2702 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
2703 std::pair<typename PBGL_DISTRIB_ADJLIST_TYPE::out_edge_iterator,
2704 typename PBGL_DISTRIB_ADJLIST_TYPE::out_edge_iterator>
2705 out_edges(typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor v,
2706 const PBGL_DISTRIB_ADJLIST_TYPE& g)
2708 BOOST_ASSERT(v.owner == g.processor());
2710 typedef PBGL_DISTRIB_ADJLIST_TYPE impl;
2711 typedef typename impl::out_edge_generator generator;
2713 return std::make_pair(
2714 make_transform_iterator(out_edges(v.local, g.base()).first,
2716 make_transform_iterator(out_edges(v.local, g.base()).second,
2721 * Return the number of edges outgoing from a particular vertex. The
2722 * vertex @param v must be local to the processor executing this
2725 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
2726 typename PBGL_DISTRIB_ADJLIST_TYPE::degree_size_type
2727 out_degree(typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor v,
2728 const PBGL_DISTRIB_ADJLIST_TYPE& g)
2730 BOOST_ASSERT(v.owner == g.processor());
2732 return out_degree(v.local, g.base());
2735 /***************************************************************************
2736 * Implementation of Bidirectional Graph concept
2737 ***************************************************************************/
2739 * Returns the set of edges incoming to a particular vertex. The
2740 * vertex @param v must be local to the processor executing this
2743 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG>
2744 std::pair<typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS)
2746 typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS)
2748 in_edges(typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS)
2749 ::vertex_descriptor v,
2750 const PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS)& g)
2752 BOOST_ASSERT(v.owner == g.processor());
2754 typedef PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS) impl;
2755 typedef typename impl::inherited base_graph_type;
2756 typedef typename impl::in_edge_generator generator;
2759 typename property_map<base_graph_type, vertex_in_edges_t>::const_type
2760 in_edges = get(vertex_in_edges, g.base());
2762 return std::make_pair(make_transform_iterator(in_edges[v.local].begin(),
2764 make_transform_iterator(in_edges[v.local].end(),
2771 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG>
2772 std::pair<typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS)
2774 typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS)
2776 in_edges(typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS)
2777 ::vertex_descriptor v,
2778 const PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS)& g)
2780 BOOST_ASSERT(v.owner == g.processor());
2782 typedef PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS) impl;
2783 typedef typename impl::in_edge_generator generator;
2785 return std::make_pair(
2786 make_transform_iterator(out_edges(v.local, g.base()).first,
2788 make_transform_iterator(out_edges(v.local, g.base()).second,
2793 * Returns the number of edges incoming to a particular vertex. The
2794 * vertex @param v must be local to the processor executing this
2797 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG>
2798 typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS)::degree_size_type
2799 in_degree(typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS)
2800 ::vertex_descriptor v,
2801 const PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS)& g)
2803 BOOST_ASSERT(v.owner == g.processor());
2805 return get(vertex_in_edges, g.base())[v.local].size();
2811 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG>
2812 typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS)::degree_size_type
2813 in_degree(typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS)
2814 ::vertex_descriptor v,
2815 const PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS)& g)
2817 BOOST_ASSERT(v.owner == g.processor());
2819 return out_degree(v.local, g.base());
2823 * Returns the number of edges incident on the given vertex. The
2824 * vertex @param v must be local to the processor executing this
2827 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG>
2828 typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS)
2830 degree(typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS)
2831 ::vertex_descriptor v,
2832 const PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS)& g)
2834 BOOST_ASSERT(v.owner == g.processor());
2835 return out_degree(v.local, g.base());
2841 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG>
2842 typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS)
2844 degree(typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS)
2845 ::vertex_descriptor v,
2846 const PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS)& g)
2848 BOOST_ASSERT(v.owner == g.processor());
2849 return out_degree(v, g) + in_degree(v, g);
2852 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
2853 typename PBGL_DISTRIB_ADJLIST_TYPE::edges_size_type
2854 num_edges(const PBGL_DISTRIB_ADJLIST_TYPE& g)
2856 return num_edges(g.base());
2859 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG>
2860 typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS)::edges_size_type
2861 num_edges(const PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS)& g)
2863 return g.local_edges().size();
2866 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
2868 typename PBGL_DISTRIB_ADJLIST_TYPE::edge_iterator,
2869 typename PBGL_DISTRIB_ADJLIST_TYPE::edge_iterator>
2870 edges(const PBGL_DISTRIB_ADJLIST_TYPE& g)
2872 typedef PBGL_DISTRIB_ADJLIST_TYPE impl;
2873 typedef typename impl::out_edge_generator generator;
2875 return std::make_pair(make_transform_iterator(edges(g.base()).first,
2877 make_transform_iterator(edges(g.base()).second,
2881 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG>
2883 typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS)::edge_iterator,
2884 typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS)::edge_iterator>
2885 edges(const PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS)& g)
2887 return std::make_pair(g.local_edges().begin(), g.local_edges().end());
2890 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
2892 typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor
2893 vertex(typename PBGL_DISTRIB_ADJLIST_TYPE::vertices_size_type n,
2894 const PBGL_DISTRIB_ADJLIST_TYPE& g)
2896 typedef typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor
2899 return vertex_descriptor(g.distribution()(n), g.distribution().local(n));
2902 /***************************************************************************
2903 * Access to particular edges
2904 ***************************************************************************/
2905 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG>
2907 typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(directedS)::edge_descriptor,
2910 edge(typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(directedS)::vertex_descriptor u,
2911 typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(directedS)::vertex_descriptor v,
2912 const PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(directedS)& g)
2914 typedef typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(directedS)
2915 ::edge_descriptor edge_descriptor;
2917 // For directed graphs, u must be local
2918 BOOST_ASSERT(u.owner == process_id(g.process_group()));
2920 typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(directedS)
2921 ::out_edge_iterator ei, ei_end;
2922 for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) {
2923 if (target(*ei, g) == v) return std::make_pair(*ei, true);
2925 return std::make_pair(edge_descriptor(), false);
2928 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
2930 typename PBGL_DISTRIB_ADJLIST_TYPE::edge_descriptor,
2933 edge(typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor u,
2934 typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor v,
2935 const PBGL_DISTRIB_ADJLIST_TYPE& g)
2937 typedef typename PBGL_DISTRIB_ADJLIST_TYPE
2938 ::edge_descriptor edge_descriptor;
2940 // For bidirectional and undirected graphs, u must be local or v
2942 if (u.owner == process_id(g.process_group())) {
2943 typename PBGL_DISTRIB_ADJLIST_TYPE::out_edge_iterator ei, ei_end;
2944 for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) {
2945 if (target(*ei, g) == v) return std::make_pair(*ei, true);
2947 return std::make_pair(edge_descriptor(), false);
2948 } else if (v.owner == process_id(g.process_group())) {
2949 typename PBGL_DISTRIB_ADJLIST_TYPE::in_edge_iterator ei, ei_end;
2950 for (boost::tie(ei, ei_end) = in_edges(v, g); ei != ei_end; ++ei) {
2951 if (source(*ei, g) == u) return std::make_pair(*ei, true);
2953 return std::make_pair(edge_descriptor(), false);
2955 BOOST_ASSERT(false);
2961 // TBD: not yet supported
2962 std::pair<out_edge_iterator, out_edge_iterator>
2963 edge_range(vertex_descriptor u, vertex_descriptor v,
2964 const adjacency_list& g);
2967 /***************************************************************************
2968 * Implementation of Adjacency Graph concept
2969 ***************************************************************************/
2970 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
2971 std::pair<typename PBGL_DISTRIB_ADJLIST_TYPE::adjacency_iterator,
2972 typename PBGL_DISTRIB_ADJLIST_TYPE::adjacency_iterator>
2973 adjacent_vertices(typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor v,
2974 const PBGL_DISTRIB_ADJLIST_TYPE& g)
2976 typedef typename PBGL_DISTRIB_ADJLIST_TYPE::adjacency_iterator iter;
2977 return std::make_pair(iter(out_edges(v, g).first, &g),
2978 iter(out_edges(v, g).second, &g));
2981 /***************************************************************************
2982 * Implementation of Mutable Graph concept
2983 ***************************************************************************/
2985 /************************************************************************
2987 ************************************************************************/
2988 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
2989 typename PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_edge
2990 add_edge(typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor u,
2991 typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor v,
2992 PBGL_DISTRIB_ADJLIST_TYPE& g)
2994 typedef typename PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_edge lazy_add_edge;
2996 return lazy_add_edge(g, u, v);
2999 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
3000 typename PBGL_DISTRIB_ADJLIST_TYPE
3001 ::lazy_add_edge_with_property
3002 add_edge(typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor u,
3003 typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor v,
3004 typename PBGL_DISTRIB_ADJLIST_TYPE::edge_property_type const& p,
3005 PBGL_DISTRIB_ADJLIST_TYPE& g)
3007 typedef typename PBGL_DISTRIB_ADJLIST_TYPE
3008 ::lazy_add_edge_with_property lazy_add_edge_with_property;
3009 return lazy_add_edge_with_property(g, u, v, p);
3012 /************************************************************************
3016 ************************************************************************/
3017 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
3019 remove_edge(typename PBGL_DISTRIB_ADJLIST_TYPE::edge_descriptor e,
3020 PBGL_DISTRIB_ADJLIST_TYPE& g)
3022 BOOST_ASSERT(source(e, g).owner == g.processor()
3023 || target(e, g).owner == g.processor());
3025 if (target(e, g).owner == g.processor())
3026 detail::parallel::remove_in_edge(e, g, DirectedS());
3027 if (source(e, g).owner == g.processor())
3028 remove_edge(e.local, g.base());
3030 g.remove_local_edge_from_list(source(e, g), target(e, g), DirectedS());
3032 if (source(e, g).owner != g.processor()
3033 || (target(e, g).owner != g.processor()
3034 && !(is_same<DirectedS, directedS>::value))) {
3035 g.send_remove_edge_request(e);
3039 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
3041 remove_edge(typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor u,
3042 typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor v,
3043 PBGL_DISTRIB_ADJLIST_TYPE& g)
3045 typedef typename PBGL_DISTRIB_ADJLIST_TYPE
3046 ::edge_descriptor edge_descriptor;
3047 std::pair<edge_descriptor, bool> the_edge = edge(u, v, g);
3048 if (the_edge.second) remove_edge(the_edge.first, g);
3051 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
3053 remove_edge(typename PBGL_DISTRIB_ADJLIST_TYPE::out_edge_iterator ei,
3054 PBGL_DISTRIB_ADJLIST_TYPE& g)
3056 remove_edge(*ei, g);
3059 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG>
3061 remove_edge(typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(directedS)
3062 ::out_edge_iterator ei,
3063 PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(directedS)& g)
3065 BOOST_ASSERT(source(*ei, g).owner == g.processor());
3066 remove_edge(ei->local, g.base());
3069 /************************************************************************
3071 * remove_out_edge_if
3073 ************************************************************************/
3074 namespace parallel { namespace detail {
3076 * Function object that applies the underlying predicate to
3077 * determine if an out-edge should be removed. If so, either
3078 * removes the incoming edge (if it is stored locally) or sends a
3079 * message to the owner of the target requesting that it remove
3082 template<typename Graph, typename Predicate>
3083 struct remove_out_edge_predicate
3085 typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
3086 typedef typename Graph::local_edge_descriptor argument_type;
3087 typedef typename Graph::directed_selector directed_selector;
3088 typedef bool result_type;
3090 remove_out_edge_predicate(Graph& g, Predicate& predicate)
3091 : g(g), predicate(predicate) { }
3093 bool operator()(const argument_type& le)
3095 typedef typename edge_descriptor::template out_generator<Graph>
3098 edge_descriptor e = generator(g)(le);
3101 if (source(e, g).owner != target(e, g).owner
3102 && !(is_same<directed_selector, directedS>::value))
3103 g.send_remove_edge_request(e);
3105 ::boost::detail::parallel::remove_in_edge(e, g,
3106 directed_selector());
3108 g.remove_local_edge_from_list(source(e, g), target(e, g),
3109 directed_selector());
3111 } else return false;
3116 Predicate predicate;
3118 } } // end namespace parallel::detail
3120 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS, typename Predicate>
3123 (typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor u,
3124 Predicate predicate,
3125 PBGL_DISTRIB_ADJLIST_TYPE& g)
3127 typedef PBGL_DISTRIB_ADJLIST_TYPE Graph;
3128 typedef parallel::detail::remove_out_edge_predicate<Graph, Predicate>
3131 BOOST_ASSERT(u.owner == g.processor());
3132 remove_out_edge_if(u.local, Pred(g, predicate), g.base());
3135 /************************************************************************
3139 ************************************************************************/
3140 namespace parallel { namespace detail {
3142 * Function object that applies the underlying predicate to
3143 * determine if an in-edge should be removed. If so, either
3144 * removes the outgoing edge (if it is stored locally) or sends a
3145 * message to the owner of the target requesting that it remove
3146 * the edge. Only required for bidirectional graphs.
3148 template<typename Graph, typename Predicate>
3149 struct remove_in_edge_predicate
3151 typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
3152 typedef bool result_type;
3154 remove_in_edge_predicate(Graph& g, const Predicate& predicate)
3155 : g(g), predicate(predicate) { }
3157 template<typename StoredEdge>
3158 bool operator()(const StoredEdge& le)
3160 typedef typename edge_descriptor::template in_generator<Graph>
3163 edge_descriptor e = generator(g)(le);
3166 if (source(e, g).owner != target(e, g).owner)
3167 g.send_remove_edge_request(e);
3169 remove_edge(source(e, g).local, target(e, g).local, g.base());
3171 } else return false;
3176 Predicate predicate;
3178 } } // end namespace parallel::detail
3180 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG, typename Predicate>
3183 (typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS)
3184 ::vertex_descriptor u,
3185 Predicate predicate,
3186 PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS)& g)
3188 typedef PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS) Graph;
3189 typedef parallel::detail::remove_in_edge_predicate<Graph, Predicate>
3192 BOOST_ASSERT(u.owner == g.processor());
3193 graph_detail::erase_if(get(vertex_in_edges, g.base())[u.local],
3194 Pred(g, predicate));
3197 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG, typename Predicate>
3200 (typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS)
3201 ::vertex_descriptor u,
3202 Predicate predicate,
3203 PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS)& g)
3205 remove_out_edge_if(u, predicate, g);
3208 /************************************************************************
3212 ************************************************************************/
3213 namespace parallel { namespace detail {
3215 * Function object that applies the underlying predicate to
3216 * determine if a directed edge can be removed. This only applies
3217 * to directed graphs.
3219 template<typename Graph, typename Predicate>
3220 struct remove_directed_edge_predicate
3222 typedef typename Graph::local_edge_descriptor argument_type;
3223 typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
3224 typedef bool result_type;
3226 remove_directed_edge_predicate(Graph& g, const Predicate& predicate)
3227 : g(g), predicate(predicate) { }
3229 bool operator()(const argument_type& le)
3231 typedef typename edge_descriptor::template out_generator<Graph>
3234 edge_descriptor e = generator(g)(le);
3235 return predicate(e);
3240 Predicate predicate;
3242 } } // end namespace parallel::detail
3244 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG, typename Predicate>
3246 remove_edge_if(Predicate predicate,
3247 PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(directedS)& g)
3249 typedef PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(directedS) Graph;
3250 typedef parallel::detail::remove_directed_edge_predicate<Graph,
3252 remove_edge_if(Pred(g, predicate), g.base());
3255 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG, typename Predicate>
3257 remove_edge_if(Predicate predicate,
3258 PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS)& g)
3260 typedef PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS) Graph;
3261 typedef parallel::detail::remove_out_edge_predicate<Graph,
3263 remove_edge_if(Pred(g, predicate), g.base());
3266 namespace parallel { namespace detail {
3268 * Function object that applies the underlying predicate to
3269 * determine if an undirected edge should be removed. If so,
3270 * removes the local edges associated with the edge and
3271 * (potentially) sends a message to the remote processor that also
3272 * is removing this edge.
3274 template<typename Graph, typename Predicate>
3275 struct remove_undirected_edge_predicate
3277 typedef typename graph_traits<Graph>::edge_descriptor argument_type;
3278 typedef bool result_type;
3280 remove_undirected_edge_predicate(Graph& g, Predicate& predicate)
3281 : g(g), predicate(predicate) { }
3283 bool operator()(const argument_type& e)
3286 if (source(e, g).owner != target(e, g).owner)
3287 g.send_remove_edge_request(e);
3288 if (target(e, g).owner == g.processor())
3289 ::boost::detail::parallel::remove_in_edge(e, g, undirectedS());
3290 if (source(e, g).owner == g.processor())
3291 remove_edge(e.local, g.base());
3293 } else return false;
3298 Predicate predicate;
3300 } } // end namespace parallel::detail
3302 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG, typename Predicate>
3304 remove_edge_if(Predicate predicate,
3305 PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS)& g)
3307 typedef PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS) Graph;
3308 typedef parallel::detail::remove_undirected_edge_predicate<Graph,
3310 graph_detail::erase_if(g.local_edges(), Pred(g, predicate));
3313 /************************************************************************
3317 ************************************************************************/
3318 namespace parallel { namespace detail {
3321 typedef bool result_type;
3323 template<typename T> bool operator()(const T&) const { return true; }
3325 } } // end namespace parallel::detail
3327 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG>
3330 (typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS)
3331 ::vertex_descriptor u,
3332 PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS)& g)
3334 clear_out_edges(u, g);
3335 clear_in_edges(u, g);
3338 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG>
3341 (typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS)
3342 ::vertex_descriptor u,
3343 PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(undirectedS)& g)
3345 remove_out_edge_if(u, parallel::detail::always_true(), g);
3348 /************************************************************************
3352 ************************************************************************/
3353 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG>
3356 (typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(directedS)::vertex_descriptor u,
3357 PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(directedS)& g)
3359 BOOST_ASSERT(u.owner == g.processor());
3360 clear_out_edges(u.local, g.base());
3363 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG>
3366 (typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS)
3367 ::vertex_descriptor u,
3368 PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS)& g)
3370 remove_out_edge_if(u, parallel::detail::always_true(), g);
3373 /************************************************************************
3377 ************************************************************************/
3378 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS_CONFIG>
3381 (typename PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS)
3382 ::vertex_descriptor u,
3383 PBGL_DISTRIB_ADJLIST_TYPE_CONFIG(bidirectionalS)& g)
3385 remove_in_edge_if(u, parallel::detail::always_true(), g);
3388 /************************************************************************
3392 ************************************************************************/
3393 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
3394 typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor
3395 add_vertex(PBGL_DISTRIB_ADJLIST_TYPE& g)
3397 typedef PBGL_DISTRIB_ADJLIST_TYPE graph_type;
3398 typename graph_type::vertex_property_type p;
3399 return add_vertex(p, g);
3402 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
3403 typename PBGL_DISTRIB_ADJLIST_TYPE::lazy_add_vertex_with_property
3404 add_vertex(typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_property_type const& p,
3405 PBGL_DISTRIB_ADJLIST_TYPE& g)
3407 typedef typename PBGL_DISTRIB_ADJLIST_TYPE
3408 ::lazy_add_vertex_with_property lazy_add_vertex;
3409 return lazy_add_vertex(g, p);
3412 /************************************************************************
3416 ************************************************************************/
3417 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
3419 remove_vertex(typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor u,
3420 PBGL_DISTRIB_ADJLIST_TYPE& g)
3422 typedef typename PBGL_DISTRIB_ADJLIST_TYPE::graph_type graph_type;
3423 typedef typename graph_type::named_graph_mixin named_graph_mixin;
3424 BOOST_ASSERT(u.owner == g.processor());
3425 static_cast<named_graph_mixin&>(static_cast<graph_type&>(g))
3426 .removing_vertex(u, boost::graph_detail::iterator_stability(g.base().m_vertices));
3427 g.distribution().clear();
3428 remove_vertex(u.local, g.base());
3431 /***************************************************************************
3432 * Implementation of Property Graph concept
3433 ***************************************************************************/
3434 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS, typename Property>
3435 struct property_map<PBGL_DISTRIB_ADJLIST_TYPE, Property>
3436 : detail::parallel::get_adj_list_pmap<Property>
3437 ::template apply<PBGL_DISTRIB_ADJLIST_TYPE>
3440 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS, typename Property>
3441 struct property_map<PBGL_DISTRIB_ADJLIST_TYPE const, Property>
3442 : boost::detail::parallel::get_adj_list_pmap<Property>
3443 // FIXME: in the original code the following was not const
3444 ::template apply<PBGL_DISTRIB_ADJLIST_TYPE const>
3447 template<typename Property, PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
3448 typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, Property>::type
3449 get(Property p, PBGL_DISTRIB_ADJLIST_TYPE& g)
3451 typedef PBGL_DISTRIB_ADJLIST_TYPE Graph;
3452 typedef typename property_map<Graph, Property>::type result_type;
3453 typedef typename property_traits<result_type>::value_type value_type;
3454 typedef typename property_reduce<Property>::template apply<value_type>
3457 typedef typename property_traits<result_type>::key_type descriptor;
3458 typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
3459 typedef typename mpl::if_<is_same<descriptor, vertex_descriptor>,
3460 vertex_global_t, edge_global_t>::type
3463 return result_type(g.process_group(), get(global_map_t(), g),
3464 get(p, g.base()), reduce());
3467 template<typename Property, PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
3468 typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, Property>::const_type
3469 get(Property p, const PBGL_DISTRIB_ADJLIST_TYPE& g)
3471 typedef PBGL_DISTRIB_ADJLIST_TYPE Graph;
3472 typedef typename property_map<Graph, Property>::const_type result_type;
3473 typedef typename property_traits<result_type>::value_type value_type;
3474 typedef typename property_reduce<Property>::template apply<value_type>
3477 typedef typename property_traits<result_type>::key_type descriptor;
3478 typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
3479 typedef typename mpl::if_<is_same<descriptor, vertex_descriptor>,
3480 vertex_global_t, edge_global_t>::type
3483 return result_type(g.process_group(), get(global_map_t(), g),
3484 get(p, g.base()), reduce());
3487 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
3488 typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, vertex_local_index_t>::type
3489 get(vertex_local_index_t, PBGL_DISTRIB_ADJLIST_TYPE& g)
3491 return get(vertex_local_index, g.base());
3494 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
3495 typename property_map<PBGL_DISTRIB_ADJLIST_TYPE,
3496 vertex_local_index_t>::const_type
3497 get(vertex_local_index_t, const PBGL_DISTRIB_ADJLIST_TYPE& g)
3499 return get(vertex_local_index, g.base());
3502 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
3503 typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, vertex_global_t>::const_type
3504 get(vertex_global_t, const PBGL_DISTRIB_ADJLIST_TYPE& g)
3506 typedef typename property_map<
3507 PBGL_DISTRIB_ADJLIST_TYPE,
3508 vertex_global_t>::const_type result_type;
3509 return result_type();
3512 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
3513 typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, vertex_global_t>::const_type
3514 get(vertex_global_t, PBGL_DISTRIB_ADJLIST_TYPE& g)
3516 typedef typename property_map<
3517 PBGL_DISTRIB_ADJLIST_TYPE,
3518 vertex_global_t>::const_type result_type;
3519 return result_type();
3522 /// Retrieve a property map mapping from a vertex descriptor to its
3524 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
3525 typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, vertex_owner_t>::type
3526 get(vertex_owner_t, PBGL_DISTRIB_ADJLIST_TYPE& g)
3528 typedef typename property_map<
3529 PBGL_DISTRIB_ADJLIST_TYPE,
3530 vertex_owner_t>::type result_type;
3531 return result_type();
3534 /// Retrieve a property map mapping from a vertex descriptor to its
3536 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
3537 typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, vertex_owner_t>::const_type
3538 get(vertex_owner_t, const PBGL_DISTRIB_ADJLIST_TYPE& g)
3540 typedef typename property_map<
3541 PBGL_DISTRIB_ADJLIST_TYPE,
3542 vertex_owner_t>::const_type result_type;
3543 return result_type();
3546 /// Retrieve the owner of a vertex
3547 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
3548 inline processor_id_type
3549 get(vertex_owner_t, PBGL_DISTRIB_ADJLIST_TYPE&,
3550 typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor v)
3555 /// Retrieve the owner of a vertex
3556 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
3557 inline processor_id_type
3558 get(vertex_owner_t, const PBGL_DISTRIB_ADJLIST_TYPE&,
3559 typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor v)
3564 /// Retrieve a property map that maps from a vertex descriptor to
3565 /// its local descriptor.
3566 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
3567 typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, vertex_local_t>::type
3568 get(vertex_local_t, PBGL_DISTRIB_ADJLIST_TYPE& g)
3570 typedef typename property_map<
3571 PBGL_DISTRIB_ADJLIST_TYPE,
3572 vertex_local_t>::type result_type;
3573 return result_type();
3576 /// Retrieve a property map that maps from a vertex descriptor to
3577 /// its local descriptor.
3578 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
3579 typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, vertex_local_t>::const_type
3580 get(vertex_local_t, const PBGL_DISTRIB_ADJLIST_TYPE& g)
3582 typedef typename property_map<
3583 PBGL_DISTRIB_ADJLIST_TYPE,
3584 vertex_local_t>::const_type result_type;
3585 return result_type();
3588 /// Retrieve the local descriptor of a vertex
3589 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
3590 inline typename PBGL_DISTRIB_ADJLIST_TYPE::local_vertex_descriptor
3591 get(vertex_local_t, PBGL_DISTRIB_ADJLIST_TYPE&,
3592 typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor v)
3597 /// Retrieve the local descriptor of a vertex
3598 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
3599 inline typename PBGL_DISTRIB_ADJLIST_TYPE::local_vertex_descriptor
3600 get(vertex_local_t, const PBGL_DISTRIB_ADJLIST_TYPE&,
3601 typename PBGL_DISTRIB_ADJLIST_TYPE::vertex_descriptor v)
3607 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
3608 typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, edge_global_t>::const_type
3609 get(edge_global_t, const PBGL_DISTRIB_ADJLIST_TYPE& g)
3611 typedef typename property_map<
3612 PBGL_DISTRIB_ADJLIST_TYPE,
3613 edge_global_t>::const_type result_type;
3614 return result_type();
3617 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
3618 typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, edge_global_t>::const_type
3619 get(edge_global_t, PBGL_DISTRIB_ADJLIST_TYPE& g)
3621 typedef typename property_map<
3622 PBGL_DISTRIB_ADJLIST_TYPE,
3623 edge_global_t>::const_type result_type;
3624 return result_type();
3627 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
3628 typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, edge_owner_t>::type
3629 get(edge_owner_t, PBGL_DISTRIB_ADJLIST_TYPE& g)
3631 typedef typename property_map<
3632 PBGL_DISTRIB_ADJLIST_TYPE,
3633 edge_owner_t>::type result_type;
3634 return result_type();
3637 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
3638 typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, edge_owner_t>::const_type
3639 get(edge_owner_t, const PBGL_DISTRIB_ADJLIST_TYPE& g)
3641 typedef typename property_map<
3642 PBGL_DISTRIB_ADJLIST_TYPE,
3643 edge_owner_t>::const_type result_type;
3644 return result_type();
3647 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
3648 typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, edge_local_t>::type
3649 get(edge_local_t, PBGL_DISTRIB_ADJLIST_TYPE& g)
3651 typedef typename property_map<
3652 PBGL_DISTRIB_ADJLIST_TYPE,
3653 edge_local_t>::type result_type;
3654 return result_type();
3657 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
3658 typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, edge_local_t>::const_type
3659 get(edge_local_t, const PBGL_DISTRIB_ADJLIST_TYPE& g)
3661 typedef typename property_map<
3662 PBGL_DISTRIB_ADJLIST_TYPE,
3663 edge_local_t>::const_type result_type;
3664 return result_type();
3667 template<typename Property, PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS,
3670 typename property_traits<typename property_map<
3671 PBGL_DISTRIB_ADJLIST_TYPE, Property>::const_type
3673 get(Property p, const PBGL_DISTRIB_ADJLIST_TYPE& g, const Key& key)
3675 if (owner(key) == process_id(g.process_group()))
3676 return get(p, g.base(), local(key));
3678 BOOST_ASSERT(false);
3681 template<typename Property, PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS,
3682 typename Key, typename Value>
3684 put(Property p, PBGL_DISTRIB_ADJLIST_TYPE& g, const Key& key, const Value& v)
3686 if (owner(key) == process_id(g.process_group()))
3687 put(p, g.base(), local(key), v);
3689 BOOST_ASSERT(false);
3692 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
3693 typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, vertex_index_t>::type
3694 get(vertex_index_t vi, PBGL_DISTRIB_ADJLIST_TYPE& g)
3696 typedef PBGL_DISTRIB_ADJLIST_TYPE graph_type;
3697 typedef typename property_map<graph_type, vertex_index_t>::type
3699 return result_type(g.process_group(), get(vertex_global, g),
3703 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
3704 typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, vertex_index_t>::const_type
3705 get(vertex_index_t vi, const PBGL_DISTRIB_ADJLIST_TYPE& g)
3707 typedef PBGL_DISTRIB_ADJLIST_TYPE graph_type;
3708 typedef typename property_map<graph_type, vertex_index_t>::const_type
3710 return result_type(g.process_group(), get(vertex_global, g),
3714 /***************************************************************************
3715 * Implementation of bundled properties
3716 ***************************************************************************/
3717 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS, typename T, typename Bundle>
3718 struct property_map<PBGL_DISTRIB_ADJLIST_TYPE, T Bundle::*>
3719 : detail::parallel::get_adj_list_pmap<T Bundle::*>
3720 ::template apply<PBGL_DISTRIB_ADJLIST_TYPE>
3723 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS, typename T, typename Bundle>
3724 struct property_map<PBGL_DISTRIB_ADJLIST_TYPE const, T Bundle::*>
3725 : detail::parallel::get_adj_list_pmap<T Bundle::*>
3726 ::template apply<PBGL_DISTRIB_ADJLIST_TYPE const>
3729 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS, typename T, typename Bundle>
3730 typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, T Bundle::*>::type
3731 get(T Bundle::* p, PBGL_DISTRIB_ADJLIST_TYPE& g)
3733 typedef PBGL_DISTRIB_ADJLIST_TYPE Graph;
3734 typedef typename property_map<Graph, T Bundle::*>::type result_type;
3735 typedef typename property_traits<result_type>::value_type value_type;
3736 typedef typename property_reduce<T Bundle::*>::template apply<value_type>
3739 typedef typename property_traits<result_type>::key_type descriptor;
3740 typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
3741 typedef typename mpl::if_<is_same<descriptor, vertex_descriptor>,
3742 vertex_global_t, edge_global_t>::type
3745 return result_type(g.process_group(), get(global_map_t(), g),
3746 get(p, g.base()), reduce());
3749 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS, typename T, typename Bundle>
3750 typename property_map<PBGL_DISTRIB_ADJLIST_TYPE, T Bundle::*>::const_type
3751 get(T Bundle::* p, const PBGL_DISTRIB_ADJLIST_TYPE& g)
3753 typedef PBGL_DISTRIB_ADJLIST_TYPE Graph;
3754 typedef typename property_map<Graph, T Bundle::*>::const_type result_type;
3755 typedef typename property_traits<result_type>::value_type value_type;
3756 typedef typename property_reduce<T Bundle::*>::template apply<value_type>
3759 typedef typename property_traits<result_type>::key_type descriptor;
3760 typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
3761 typedef typename mpl::if_<is_same<descriptor, vertex_descriptor>,
3762 vertex_global_t, edge_global_t>::type
3765 return result_type(g.process_group(), get(global_map_t(), g),
3766 get(p, g.base()), reduce());
3769 /***************************************************************************
3770 * Implementation of DistributedGraph concept
3771 ***************************************************************************/
3772 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
3773 void synchronize(const PBGL_DISTRIB_ADJLIST_TYPE& g)
3775 synchronize(g.process_group());
3778 template<PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
3780 process_group(const PBGL_DISTRIB_ADJLIST_TYPE& g)
3781 { return g.process_group(); }
3783 /***************************************************************************
3784 * Specializations of is_mpi_datatype for Serializable entities
3785 ***************************************************************************/
3787 template<typename Directed, typename Vertex>
3788 struct is_mpi_datatype<boost::detail::edge_base<Directed, Vertex> >
3789 : is_mpi_datatype<Vertex> { };
3791 template<typename Directed, typename Vertex>
3792 struct is_mpi_datatype<boost::detail::edge_desc_impl<Directed, Vertex> >
3793 : is_mpi_datatype<boost::detail::edge_base<Directed, Vertex> > { };
3795 template<typename LocalDescriptor>
3796 struct is_mpi_datatype<boost::detail::parallel::global_descriptor<LocalDescriptor> >
3797 : is_mpi_datatype<LocalDescriptor> { };
3799 template<typename Edge>
3800 struct is_mpi_datatype<boost::detail::parallel::edge_descriptor<Edge> >
3801 : is_mpi_datatype<Edge> { };
3803 template<typename Vertex, typename LocalVertex>
3804 struct is_mpi_datatype<boost::detail::parallel::
3805 msg_add_edge_data<Vertex, LocalVertex> >
3806 : is_mpi_datatype<Vertex> { };
3808 template<typename Vertex, typename LocalVertex, typename EdgeProperty>
3809 struct is_mpi_datatype<boost::detail::parallel::
3810 msg_add_edge_with_property_data<Vertex,
3813 : mpl::and_<is_mpi_datatype<Vertex>, is_mpi_datatype<EdgeProperty> > { };
3816 template<typename EdgeProperty, typename EdgeDescriptor>
3817 struct is_mpi_datatype<boost::detail::parallel::msg_nonlocal_edge_data<
3818 EdgeProperty,EdgeDescriptor> >
3820 is_mpi_datatype<boost::detail::parallel::maybe_store_property<
3822 is_mpi_datatype<EdgeDescriptor> >
3825 template<typename EdgeDescriptor>
3826 struct is_mpi_datatype<
3827 boost::detail::parallel::msg_remove_edge_data<EdgeDescriptor> >
3828 : is_mpi_datatype<EdgeDescriptor> {};
3831 /***************************************************************************
3832 * Specializations of is_bitwise_serializable for Serializable entities
3833 ***************************************************************************/
3834 namespace serialization {
3835 template<typename Directed, typename Vertex>
3836 struct is_bitwise_serializable<boost::detail::edge_base<Directed, Vertex> >
3837 : is_bitwise_serializable<Vertex> { };
3839 template<typename Directed, typename Vertex>
3840 struct is_bitwise_serializable<boost::detail::edge_desc_impl<Directed, Vertex> >
3841 : is_bitwise_serializable<boost::detail::edge_base<Directed, Vertex> > { };
3843 template<typename LocalDescriptor>
3844 struct is_bitwise_serializable<boost::detail::parallel::global_descriptor<LocalDescriptor> >
3845 : is_bitwise_serializable<LocalDescriptor> { };
3847 template<typename Edge>
3848 struct is_bitwise_serializable<boost::detail::parallel::edge_descriptor<Edge> >
3849 : is_bitwise_serializable<Edge> { };
3851 template<typename Vertex, typename LocalVertex>
3852 struct is_bitwise_serializable<boost::detail::parallel::
3853 msg_add_edge_data<Vertex, LocalVertex> >
3854 : is_bitwise_serializable<Vertex> { };
3856 template<typename Vertex, typename LocalVertex, typename EdgeProperty>
3857 struct is_bitwise_serializable<boost::detail::parallel::
3858 msg_add_edge_with_property_data<Vertex,
3861 : mpl::and_<is_bitwise_serializable<Vertex>,
3862 is_bitwise_serializable<EdgeProperty> > { };
3864 template<typename EdgeProperty, typename EdgeDescriptor>
3865 struct is_bitwise_serializable<boost::detail::parallel::msg_nonlocal_edge_data<
3866 EdgeProperty,EdgeDescriptor> >
3868 is_bitwise_serializable<
3869 boost::detail::parallel::maybe_store_property<EdgeProperty> >,
3870 is_bitwise_serializable<EdgeDescriptor> >
3873 template<typename EdgeDescriptor>
3874 struct is_bitwise_serializable<
3875 boost::detail::parallel::msg_remove_edge_data<EdgeDescriptor> >
3876 : is_bitwise_serializable<EdgeDescriptor> {};
3878 template<typename Directed, typename Vertex>
3879 struct implementation_level<boost::detail::edge_base<Directed, Vertex> >
3880 : mpl::int_<object_serializable> {};
3882 template<typename Directed, typename Vertex>
3883 struct implementation_level<boost::detail::edge_desc_impl<Directed, Vertex> >
3884 : mpl::int_<object_serializable> {};
3886 template<typename LocalDescriptor>
3887 struct implementation_level<boost::detail::parallel::global_descriptor<LocalDescriptor> >
3888 : mpl::int_<object_serializable> {};
3890 template<typename Edge>
3891 struct implementation_level<boost::detail::parallel::edge_descriptor<Edge> >
3892 : mpl::int_<object_serializable> {};
3894 template<typename Vertex, typename LocalVertex>
3895 struct implementation_level<boost::detail::parallel::
3896 msg_add_edge_data<Vertex, LocalVertex> >
3897 : mpl::int_<object_serializable> {};
3899 template<typename Vertex, typename LocalVertex, typename EdgeProperty>
3900 struct implementation_level<boost::detail::parallel::
3901 msg_add_edge_with_property_data<Vertex,
3904 : mpl::int_<object_serializable> {};
3906 template<typename EdgeProperty, typename EdgeDescriptor>
3907 struct implementation_level<boost::detail::parallel::msg_nonlocal_edge_data<
3908 EdgeProperty,EdgeDescriptor> >
3909 : mpl::int_<object_serializable> {};
3911 template<typename EdgeDescriptor>
3912 struct implementation_level<
3913 boost::detail::parallel::msg_remove_edge_data<EdgeDescriptor> >
3914 : mpl::int_<object_serializable> {};
3916 template<typename Directed, typename Vertex>
3917 struct tracking_level<boost::detail::edge_base<Directed, Vertex> >
3918 : mpl::int_<track_never> {};
3920 template<typename Directed, typename Vertex>
3921 struct tracking_level<boost::detail::edge_desc_impl<Directed, Vertex> >
3922 : mpl::int_<track_never> {};
3924 template<typename LocalDescriptor>
3925 struct tracking_level<boost::detail::parallel::global_descriptor<LocalDescriptor> >
3926 : mpl::int_<track_never> {};
3928 template<typename Edge>
3929 struct tracking_level<boost::detail::parallel::edge_descriptor<Edge> >
3930 : mpl::int_<track_never> {};
3932 template<typename Vertex, typename LocalVertex>
3933 struct tracking_level<boost::detail::parallel::
3934 msg_add_edge_data<Vertex, LocalVertex> >
3935 : mpl::int_<track_never> {};
3937 template<typename Vertex, typename LocalVertex, typename EdgeProperty>
3938 struct tracking_level<boost::detail::parallel::
3939 msg_add_edge_with_property_data<Vertex,
3942 : mpl::int_<track_never> {};
3944 template<typename EdgeProperty, typename EdgeDescriptor>
3945 struct tracking_level<boost::detail::parallel::msg_nonlocal_edge_data<
3946 EdgeProperty,EdgeDescriptor> >
3947 : mpl::int_<track_never> {};
3949 template<typename EdgeDescriptor>
3950 struct tracking_level<
3951 boost::detail::parallel::msg_remove_edge_data<EdgeDescriptor> >
3952 : mpl::int_<track_never> {};
3955 // Hash function for global descriptors
3956 template<typename LocalDescriptor>
3957 struct hash<detail::parallel::global_descriptor<LocalDescriptor> >
3959 typedef detail::parallel::global_descriptor<LocalDescriptor> argument_type;
3960 std::size_t operator()(argument_type const& x) const
3962 std::size_t hash = hash_value(x.owner);
3963 hash_combine(hash, x.local);
3968 // Hash function for parallel edge descriptors
3969 template<typename Edge>
3970 struct hash<detail::parallel::edge_descriptor<Edge> >
3972 typedef detail::parallel::edge_descriptor<Edge> argument_type;
3974 std::size_t operator()(argument_type const& x) const
3976 std::size_t hash = hash_value(x.owner());
3977 hash_combine(hash, x.local);
3982 } // end namespace boost
3984 #include <boost/graph/distributed/adjlist/handlers.hpp>
3985 #include <boost/graph/distributed/adjlist/initialize.hpp>
3986 #include <boost/graph/distributed/adjlist/redistribute.hpp>
3987 #include <boost/graph/distributed/adjlist/serialization.hpp>
3989 #endif // BOOST_GRAPH_DISTRIBUTED_ADJACENCY_LIST_HPP