1 // Copyright (C) 2004-2006 The Trustees of Indiana University.
3 // Use, modification and distribution is subject to the Boost Software
4 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
5 // http://www.boost.org/LICENSE_1_0.txt)
7 // Authors: Nick Edmonds
10 #ifndef BOOST_GRAPH_PARALLEL_CC_HPP
11 #define BOOST_GRAPH_PARALLEL_CC_HPP
13 #ifndef BOOST_GRAPH_USE_MPI
14 #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
17 #include <boost/detail/is_sorted.hpp>
18 #include <boost/assert.hpp>
19 #include <boost/property_map/property_map.hpp>
20 #include <boost/property_map/parallel/caching_property_map.hpp>
21 #include <boost/graph/parallel/algorithm.hpp>
22 #include <boost/pending/indirect_cmp.hpp>
23 #include <boost/graph/graph_traits.hpp>
24 #include <boost/graph/overloading.hpp>
25 #include <boost/graph/distributed/concepts.hpp>
26 #include <boost/graph/parallel/properties.hpp>
27 #include <boost/graph/distributed/local_subgraph.hpp>
28 #include <boost/graph/connected_components.hpp>
29 #include <boost/graph/named_function_params.hpp>
30 #include <boost/graph/parallel/process_group.hpp>
31 #include <boost/optional.hpp>
36 #include <boost/graph/parallel/container_traits.hpp>
37 #include <boost/graph/iteration_macros.hpp>
39 #define PBGL_IN_PLACE_MERGE /* In place merge instead of sorting */
40 //#define PBGL_SORT_ASSERT /* Assert sorted for in place merge */
42 /* Explicit sychronization in pointer doubling step? */
43 #define PBGL_EXPLICIT_SYNCH
44 //#define PBGL_CONSTRUCT_METAGRAPH
45 #ifdef PBGL_CONSTRUCT_METAGRAPH
46 # define MAX_VERTICES_IN_METAGRAPH 10000
49 namespace boost { namespace graph { namespace distributed {
51 enum connected_components_message {
52 edges_msg, req_parents_msg, parents_msg, root_adj_msg
55 template <typename Vertex>
58 metaVertex(const Vertex& v) : name(v) {}
60 template<typename Archiver>
61 void serialize(Archiver& ar, const unsigned int /*version*/)
69 #ifdef PBGL_CONSTRUCT_METAGRAPH
70 // Build meta-graph on result of local connected components
71 template <typename Graph, typename ParentMap, typename RootIterator,
72 typename AdjacencyMap>
74 build_local_metagraph(const Graph& g, ParentMap p, RootIterator r,
75 RootIterator r_end, AdjacencyMap& adj)
77 // TODO: Static assert that AdjacencyMap::value_type is std::vector<vertex_descriptor>
79 typedef typename boost::graph::parallel::process_group_type<Graph>::type
81 typedef typename process_group_type::process_id_type process_id_type;
83 typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
85 BOOST_STATIC_ASSERT((is_same<typename AdjacencyMap::mapped_type,
86 std::vector<vertex_descriptor> >::value));
88 using boost::graph::parallel::process_group;
90 process_group_type pg = process_group(g);
91 process_id_type id = process_id(pg);
95 // Send component roots and their associated edges to P0
96 for ( ; r != r_end; ++r ) {
97 std::vector<vertex_descriptor> adjs(1, *r); // Root
98 adjs.reserve(adjs.size() + adj[*r].size());
99 for (typename std::vector<vertex_descriptor>::iterator iter = adj[*r].begin();
100 iter != adj[*r].end(); ++iter)
101 adjs.push_back(get(p, *iter)); // Adjacencies
103 send(pg, 0, root_adj_msg, adjs);
110 typedef metaVertex<vertex_descriptor> VertexProperties;
112 typedef boost::adjacency_list<vecS, vecS, undirectedS,
113 VertexProperties> metaGraph;
114 typedef typename graph_traits<metaGraph>::vertex_descriptor
115 meta_vertex_descriptor;
117 std::map<vertex_descriptor, meta_vertex_descriptor> vertex_map;
118 std::vector<std::pair<vertex_descriptor, vertex_descriptor> > edges;
120 // Receive remote roots and edges
121 while (optional<std::pair<process_id_type, int> > m = probe(pg)) {
122 BOOST_ASSERT(m->second == root_adj_msg);
124 std::vector<vertex_descriptor> adjs;
125 receive(pg, m->first, m->second, adjs);
127 vertex_map[adjs[0]] = graph_traits<metaGraph>::null_vertex();
128 for (typename std::vector<vertex_descriptor>::iterator iter
129 = ++adjs.begin(); iter != adjs.end(); ++iter)
130 edges.push_back(std::make_pair(adjs[0], *iter));
133 // Add local roots and edges
134 for ( ; r != r_end; ++r ) {
135 vertex_map[*r] = graph_traits<metaGraph>::null_vertex();
136 edges.reserve(edges.size() + adj[*r].size());
137 for (typename std::vector<vertex_descriptor>::iterator iter = adj[*r].begin();
138 iter != adj[*r].end(); ++iter)
139 edges.push_back(std::make_pair(*r, get(p, *iter)));
142 // Build local meta-graph
145 // Add vertices with property to map back to distributed graph vertex
146 for (typename std::map<vertex_descriptor, meta_vertex_descriptor>::iterator
147 iter = vertex_map.begin(); iter != vertex_map.end(); ++iter)
148 vertex_map[iter->first]
149 = add_vertex(metaVertex<vertex_descriptor>(iter->first), mg);
151 // Build meta-vertex map
152 typename property_map<metaGraph, vertex_descriptor VertexProperties::*>::type
153 metaVertexMap = get(&VertexProperties::name, mg);
155 typename std::vector<std::pair<vertex_descriptor, vertex_descriptor> >
156 ::iterator edge_iter = edges.begin();
157 for ( ; edge_iter != edges.end(); ++edge_iter)
158 add_edge(vertex_map[edge_iter->first], vertex_map[edge_iter->second], mg);
162 // Call connected_components on it
163 typedef typename property_map<metaGraph, vertex_index_t>::type
165 meta_index_map_type meta_index = get(vertex_index, mg);
167 std::vector<std::size_t> mg_component_vec(num_vertices(mg));
168 typedef iterator_property_map<std::vector<std::size_t>::iterator,
170 meta_components_map_type;
171 meta_components_map_type mg_component(mg_component_vec.begin(),
173 std::size_t num_comp = connected_components(mg, mg_component);
175 // Update Parent pointers
176 std::vector<meta_vertex_descriptor> roots(num_comp, graph_traits<metaGraph>::null_vertex());
178 BGL_FORALL_VERTICES_T(v, mg, metaGraph) {
179 size_t component = get(mg_component, v);
180 if (roots[component] == graph_traits<metaGraph>::null_vertex() ||
181 get(meta_index, v) < get(meta_index, roots[component]))
182 roots[component] = v;
185 // Set all the local parent pointers
186 BGL_FORALL_VERTICES_T(v, mg, metaGraph) {
187 // Problem in value being put (3rd parameter)
188 put(p, get(metaVertexMap, v), get(metaVertexMap, roots[get(mg_component, v)]));
196 /* Function object used to remove internal vertices and vertices >
197 the current vertex from the adjacent vertex lists at each
199 template <typename Vertex, typename ParentMap>
200 class cull_adjacency_list
203 cull_adjacency_list(const Vertex v, const ParentMap p) : v(v), p(p) {}
204 bool operator() (const Vertex x) { return (get(p, x) == v || x == v); }
211 /* Comparison operator used to choose targets for hooking s.t. vertices
212 that are hooked to are evenly distributed across processors */
213 template <typename OwnerMap, typename LocalMap>
214 class hashed_vertex_compare
217 hashed_vertex_compare (const OwnerMap& o, const LocalMap& l)
218 : owner(o), local(l) { }
220 template <typename Vertex>
221 bool operator() (const Vertex x, const Vertex y)
223 if (get(local, x) < get(local, y))
225 else if (get(local, x) == get(local, y))
226 return (get(owner, x) < get(owner, y));
235 #ifdef PBGL_EXPLICIT_SYNCH
236 template <typename Graph, typename ParentMap, typename VertexList>
238 request_parent_map_entries(const Graph& g, ParentMap p,
239 std::vector<VertexList>& parent_requests)
241 typedef typename boost::graph::parallel::process_group_type<Graph>
242 ::type process_group_type;
243 typedef typename process_group_type::process_id_type process_id_type;
245 typedef typename graph_traits<Graph>::vertex_descriptor
248 process_group_type pg = process_group(g);
251 This should probably be send_oob_with_reply, especially when Dave
252 finishes prefetch-batching
255 // Send root requests
256 for (process_id_type i = 0; i < num_processes(pg); ++i) {
257 if (!parent_requests[i].empty()) {
258 std::vector<vertex_descriptor> reqs(parent_requests[i].begin(),
259 parent_requests[i].end());
260 send(pg, i, req_parents_msg, reqs);
266 // Receive root requests and reply to them
267 while (optional<std::pair<process_id_type, int> > m = probe(pg)) {
268 std::vector<vertex_descriptor> requests;
269 receive(pg, m->first, m->second, requests);
270 for (std::size_t i = 0; i < requests.size(); ++i)
271 requests[i] = get(p, requests[i]);
272 send(pg, m->first, parents_msg, requests);
277 // Receive requested parents
278 std::vector<vertex_descriptor> responses;
279 for (process_id_type i = 0; i < num_processes(pg); ++i) {
280 if (!parent_requests[i].empty()) {
281 receive(pg, i, parents_msg, responses);
282 std::size_t parent_idx = 0;
283 for (typename VertexList::iterator v = parent_requests[i].begin();
284 v != parent_requests[i].end(); ++v, ++parent_idx)
285 put(p, *v, responses[parent_idx]);
291 template<typename DistributedGraph, typename ParentMap>
293 parallel_connected_components(DistributedGraph& g, ParentMap p)
295 using boost::connected_components;
297 typedef typename graph_traits<DistributedGraph>::adjacency_iterator
299 typedef typename graph_traits<DistributedGraph>::vertex_descriptor
302 typedef typename boost::graph::parallel::process_group_type<DistributedGraph>
303 ::type process_group_type;
304 typedef typename process_group_type::process_id_type process_id_type;
306 using boost::graph::parallel::process_group;
308 process_group_type pg = process_group(g);
309 process_id_type id = process_id(pg);
311 // TODO (NGE): Should old_roots, roots, and completed_roots be std::list
312 adjacency_iterator av1, av2;
313 std::vector<vertex_descriptor> old_roots;
314 typename std::vector<vertex_descriptor>::iterator liter;
315 typename std::vector<vertex_descriptor>::iterator aliter;
316 typename std::map<vertex_descriptor,
317 std::vector<vertex_descriptor> > adj;
319 typedef typename property_map<DistributedGraph, vertex_owner_t>::const_type
321 OwnerMap owner = get(vertex_owner, g);
322 typedef typename property_map<DistributedGraph, vertex_local_t>::const_type
324 LocalMap local = get(vertex_local, g);
326 // We need to hold on to all of the parent pointers
327 p.set_max_ghost_cells(0);
330 // STAGE 1 : Compute local components
332 local_subgraph<const DistributedGraph> ls(g);
333 typedef typename property_map<local_subgraph<const DistributedGraph>,
334 vertex_index_t>::type local_index_map_type;
335 local_index_map_type local_index = get(vertex_index, ls);
337 // Compute local connected components
338 std::vector<std::size_t> ls_components_vec(num_vertices(ls));
339 typedef iterator_property_map<std::vector<std::size_t>::iterator,
340 local_index_map_type>
341 ls_components_map_type;
342 ls_components_map_type ls_component(ls_components_vec.begin(),
344 std::size_t num_comp = connected_components(ls, ls_component);
346 std::vector<vertex_descriptor>
347 roots(num_comp, graph_traits<DistributedGraph>::null_vertex());
349 BGL_FORALL_VERTICES_T(v, g, DistributedGraph) {
350 size_t component = get(ls_component, v);
351 if (roots[component] == graph_traits<DistributedGraph>::null_vertex() ||
352 get(local_index, v) < get(local_index, roots[component]))
353 roots[component] = v;
356 // Set all the local parent pointers
357 BGL_FORALL_VERTICES_T(v, g, DistributedGraph) {
358 put(p, v, roots[get(ls_component, v)]);
361 if (num_processes(pg) == 1) return;
363 // Build adjacency list for all roots
364 BGL_FORALL_VERTICES_T(v, g, DistributedGraph) {
365 std::vector<vertex_descriptor>& my_adj = adj[get(p, v)];
366 for (boost::tie(av1, av2) = adjacent_vertices(v, g);
368 if (get(owner, *av1) != id) my_adj.push_back(*av1);
372 // For all vertices adjacent to a local vertex get p(v)
373 for ( liter = roots.begin(); liter != roots.end(); ++liter ) {
374 std::vector<vertex_descriptor>& my_adj = adj[*liter];
375 for ( aliter = my_adj.begin(); aliter != my_adj.end(); ++aliter )
380 // Update adjacency list at root to make sure all adjacent
381 // vertices are roots of remote components
382 for ( liter = roots.begin(); liter != roots.end(); ++liter )
384 std::vector<vertex_descriptor>& my_adj = adj[*liter];
385 for ( aliter = my_adj.begin(); aliter != my_adj.end(); ++aliter )
386 *aliter = get(p, *aliter);
389 (std::remove_if(my_adj.begin(), my_adj.end(),
390 cull_adjacency_list<vertex_descriptor,
391 ParentMap>(*liter, p) ),
393 // This sort needs to be here to make sure the initial
394 // adjacency list is sorted
395 std::sort(my_adj.begin(), my_adj.end(), std::less<vertex_descriptor>());
396 my_adj.erase(std::unique(my_adj.begin(), my_adj.end()), my_adj.end());
399 // Get p(v) for the new adjacent roots
401 for ( liter = roots.begin(); liter != roots.end(); ++liter ) {
402 std::vector<vertex_descriptor>& my_adj = adj[*liter];
403 for ( aliter = my_adj.begin(); aliter != my_adj.end(); ++aliter )
406 #ifdef PBGL_EXPLICIT_SYNCH
410 // Lastly, remove roots with no adjacent vertices, this is
411 // unnecessary but will speed up sparse graphs
412 for ( liter = roots.begin(); liter != roots.end(); /*in loop*/)
414 if ( adj[*liter].empty() )
415 liter = roots.erase(liter);
420 #ifdef PBGL_CONSTRUCT_METAGRAPH
421 /* TODO: If the number of roots is sufficiently small, we can
422 use a 'problem folding' approach like we do in MST
423 to gather all the roots and their adjacencies on one proc
424 and solve for the connected components of the meta-graph */
425 using boost::parallel::all_reduce;
426 std::size_t num_roots = all_reduce(pg, roots.size(), std::plus<std::size_t>());
427 if (num_roots < MAX_VERTICES_IN_METAGRAPH) {
428 build_local_metagraph(g, p, roots.begin(), roots.end(), adj);
430 // For each vertex in g, p(v) = p(p(v)), assign parent of leaf
431 // vertices from first step to final parent
432 BGL_FORALL_VERTICES_T(v, g, DistributedGraph) {
433 put(p, v, get(p, get(p, v)));
446 std::vector<vertex_descriptor> completed_roots;
447 hashed_vertex_compare<OwnerMap, LocalMap> v_compare(owner, local);
449 vertex_descriptor new_root;
451 std::size_t steps = 0;
456 // Pull in new parents for hooking phase
463 completed_roots.clear();
464 for ( liter = roots.begin(); liter != roots.end(); )
466 new_root = graph_traits<DistributedGraph>::null_vertex();
467 std::vector<vertex_descriptor>& my_adj = adj[*liter];
468 for ( aliter = my_adj.begin(); aliter != my_adj.end(); ++aliter )
469 // try to hook to better adjacent vertex
470 if ( v_compare( get(p, *aliter), *liter ) )
471 new_root = get(p, *aliter);
473 if ( new_root != graph_traits<DistributedGraph>::null_vertex() )
476 put(p, *liter, new_root);
477 old_roots.push_back(*liter);
478 completed_roots.push_back(*liter);
479 liter = roots.erase(liter);
486 // Pointer jumping, perform until new roots determined
489 // TODO: Implement cycle reduction rules to reduce this from
490 // O(n) to O(log n) [n = cycle length]
492 std::size_t parent_root_count;
494 std::size_t double_steps = 0;
498 #ifndef PBGL_EXPLICIT_SYNCH
499 // Get p(p(v)) for all old roots, and p(v) for all current roots
500 for ( liter = old_roots.begin(); liter != old_roots.end(); ++liter )
501 request(p, get(p, *liter));
505 // Build root requests
506 typedef std::set<vertex_descriptor> VertexSet;
507 std::vector<VertexSet> parent_requests(num_processes(pg));
508 for ( liter = old_roots.begin(); liter != old_roots.end(); ++liter )
510 vertex_descriptor p1 = *liter;
511 if (get(owner, p1) != id) parent_requests[get(owner, p1)].insert(p1);
512 vertex_descriptor p2 = get(p, p1);
513 if (get(owner, p2) != id) parent_requests[get(owner, p2)].insert(p2);
516 request_parent_map_entries(g, p, parent_requests);
518 // Perform a pointer jumping step on all old roots
519 for ( liter = old_roots.begin(); liter != old_roots.end(); ++liter )
520 put(p, *liter, get(p, get(p, *liter)));
522 // make sure the parent of all old roots is itself a root
523 parent_root_count = 0;
524 for ( liter = old_roots.begin(); liter != old_roots.end(); ++liter )
525 if ( get(p, *liter) == get(p, get(p, *liter)) )
528 bool done = parent_root_count == old_roots.size();
530 all_reduce(pg, &done, &done+1, &all_done,
531 std::logical_and<bool>());
532 } while ( !all_done );
533 #ifdef PARALLEL_BGL_DEBUG
534 if (id == 0) std::cerr << double_steps << " doubling steps.\n";
537 // Add adjacent vertices of just completed roots to adjacent
538 // vertex list at new parent
540 typename std::vector<vertex_descriptor> outgoing_edges;
541 for ( liter = completed_roots.begin(); liter != completed_roots.end();
544 vertex_descriptor new_parent = get(p, *liter);
546 if ( get(owner, new_parent) == id )
548 std::vector<vertex_descriptor>& my_adj = adj[new_parent];
549 my_adj.reserve(my_adj.size() + adj[*liter].size());
550 my_adj.insert( my_adj.end(),
551 adj[*liter].begin(), adj[*liter].end() );
552 #ifdef PBGL_IN_PLACE_MERGE
553 #ifdef PBGL_SORT_ASSERT
554 BOOST_ASSERT(::boost::detail::is_sorted(my_adj.begin(),
555 my_adj.end() - adj[*liter].size(),
556 std::less<vertex_descriptor>()));
557 BOOST_ASSERT(::boost::detail::is_sorted(my_adj.end() - adj[*liter].size(),
559 std::less<vertex_descriptor>()));
561 std::inplace_merge(my_adj.begin(),
562 my_adj.end() - adj[*liter].size(),
564 std::less<vertex_descriptor>());
569 else if ( adj[*liter].begin() != adj[*liter].end() )
571 outgoing_edges.clear();
572 outgoing_edges.reserve(adj[*liter].size() + 1);
573 // First element is the destination of the adjacency list
574 outgoing_edges.push_back(new_parent);
575 outgoing_edges.insert(outgoing_edges.end(),
576 adj[*liter].begin(), adj[*liter].end() );
577 send(pg, get(owner, new_parent), edges_msg, outgoing_edges);
583 // Receive edges sent by remote nodes and add them to the
584 // indicated vertex's adjacency list
585 while (optional<std::pair<process_id_type, int> > m
588 std::vector<vertex_descriptor> incoming_edges;
589 receive(pg, m->first, edges_msg, incoming_edges);
590 typename std::vector<vertex_descriptor>::iterator aviter
591 = incoming_edges.begin();
594 std::vector<vertex_descriptor>& my_adj = adj[incoming_edges[0]];
596 my_adj.reserve(my_adj.size() + incoming_edges.size() - 1);
597 my_adj.insert( my_adj.end(), aviter, incoming_edges.end() );
599 #ifdef PBGL_IN_PLACE_MERGE
600 std::size_t num_incoming_edges = incoming_edges.size();
601 #ifdef PBGL_SORT_ASSERT
602 BOOST_ASSERT(::boost::detail::is_sorted(my_adj.begin(),
603 my_adj.end() - (num_incoming_edges-1),
604 std::less<vertex_descriptor>()));
605 BOOST_ASSERT(::boost::detail::is_sorted(my_adj.end() - (num_incoming_edges-1),
607 std::less<vertex_descriptor>()));
609 std::inplace_merge(my_adj.begin(),
610 my_adj.end() - (num_incoming_edges - 1),
612 std::less<vertex_descriptor>());
618 // Remove any adjacent vertices that are in the same component
619 // as a root from that root's list
620 for ( liter = roots.begin(); liter != roots.end(); ++liter )
622 // We can probably get away without sorting and removing
623 // duplicates Though sorting *may* cause root
624 // determination to occur faster by choosing the root with
625 // the most potential to hook to at each step
626 std::vector<vertex_descriptor>& my_adj = adj[*liter];
628 (std::remove_if(my_adj.begin(), my_adj.end(),
629 cull_adjacency_list<vertex_descriptor,
630 ParentMap>(*liter, p) ),
632 #ifndef PBGL_IN_PLACE_MERGE
633 std::sort(my_adj.begin(), my_adj.end(),
634 std::less<vertex_descriptor>() );
636 my_adj.erase(std::unique(my_adj.begin(), my_adj.end()), my_adj.end());
639 // Reduce result of empty root list test
640 all_reduce(pg, &hooked, &hooked+1, &any_hooked,
641 std::logical_or<bool>());
642 } while ( any_hooked );
643 #ifdef PARALLEL_BGL_DEBUG
644 if (id == 0) std::cerr << steps << " iterations.\n";
650 // For each vertex in g, p(v) = p(p(v)), assign parent of leaf
651 // vertices from first step to final parent
652 BGL_FORALL_VERTICES_T(v, g, DistributedGraph) {
653 put(p, v, get(p, get(p, v)));
659 } // end namespace cc_detail
661 template<typename Graph, typename ParentMap, typename ComponentMap>
662 typename property_traits<ComponentMap>::value_type
663 number_components_from_parents(const Graph& g, ParentMap p, ComponentMap c)
665 typedef typename graph_traits<Graph>::vertex_descriptor
667 typedef typename boost::graph::parallel::process_group_type<Graph>::type
669 typedef typename property_traits<ComponentMap>::value_type
672 process_group_type pg = process_group(g);
674 /* Build list of roots */
675 std::vector<vertex_descriptor> my_roots, all_roots;
677 BGL_FORALL_VERTICES_T(v, g, Graph) {
678 if( std::find( my_roots.begin(), my_roots.end(), get(p, v) )
680 my_roots.push_back( get(p, v) );
683 all_gather(pg, my_roots.begin(), my_roots.end(), all_roots);
685 /* Number components */
686 std::map<vertex_descriptor, ComponentMapType> comp_numbers;
687 ComponentMapType c_num = 0;
689 // Compute component numbers
690 for (std::size_t i = 0; i < all_roots.size(); i++ )
691 if ( comp_numbers.count(all_roots[i]) == 0 )
692 comp_numbers[all_roots[i]] = c_num++;
694 // Broadcast component numbers
695 BGL_FORALL_VERTICES_T(v, g, Graph) {
696 put( c, v, comp_numbers[get(p, v)] );
699 // Broadcast number of components
700 if (process_id(pg) == 0) {
701 typedef typename process_group_type::process_size_type
703 for (process_size_type dest = 1, n = num_processes(pg);
705 send(pg, dest, 0, c_num);
709 if (process_id(pg) != 0) receive(pg, 0, 0, c_num);
716 template<typename Graph, typename ParentMap>
718 number_components_from_parents(const Graph& g, ParentMap p,
721 using boost::parallel::all_reduce;
723 // Count local roots.
725 BGL_FORALL_VERTICES_T(v, g, Graph)
726 if (get(p, v) == v) ++num_roots;
727 return all_reduce(g.process_group(), num_roots, std::plus<int>());
730 template<typename Graph, typename ComponentMap, typename ParentMap>
731 typename property_traits<ComponentMap>::value_type
733 (const Graph& g, ComponentMap c, ParentMap p
734 BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph, distributed_graph_tag))
736 cc_detail::parallel_connected_components(g, p);
737 return number_components_from_parents(g, p, c);
740 /* Construct ParentMap by default */
741 template<typename Graph, typename ComponentMap>
742 typename property_traits<ComponentMap>::value_type
744 ( const Graph& g, ComponentMap c
745 BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph, distributed_graph_tag) )
747 typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
749 std::vector<vertex_descriptor> x(num_vertices(g));
751 return connected_components
753 make_iterator_property_map(x.begin(), get(vertex_index, g)));
755 } // end namespace distributed
757 using distributed::connected_components;
758 } // end namespace graph
760 using graph::distributed::connected_components;
761 } // end namespace boost
763 #endif // BOOST_GRAPH_PARALLEL_CC_HPP