graph/distributed/connected_components.hpp

0001 // Copyright (C) 2004-2006 The Trustees of Indiana University.
0002
0003 // Use, modification and distribution is subject to the Boost Software
0004 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0005 // http://www.boost.org/LICENSE_1_0.txt)
0006
0007 //  Authors: Nick Edmonds
0008 //           Douglas Gregor
0009 //           Andrew Lumsdaine
0010 #ifndef BOOST_GRAPH_PARALLEL_CC_HPP
0011 #define BOOST_GRAPH_PARALLEL_CC_HPP
0012
0013 #ifndef BOOST_GRAPH_USE_MPI
0014 #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
0015 #endif
0016
0017 #include <boost/detail/is_sorted.hpp>
0018 #include <boost/assert.hpp>
0019 #include <boost/property_map/property_map.hpp>
0020 #include <boost/property_map/parallel/parallel_property_maps.hpp>
0021 #include <boost/property_map/parallel/caching_property_map.hpp>
0022 #include <boost/graph/parallel/algorithm.hpp>
0023 #include <boost/pending/indirect_cmp.hpp>
0024 #include <boost/graph/graph_traits.hpp>
0025 #include <boost/graph/overloading.hpp>
0026 #include <boost/graph/distributed/concepts.hpp>
0027 #include <boost/graph/parallel/properties.hpp>
0028 #include <boost/graph/distributed/local_subgraph.hpp>
0029 #include <boost/graph/connected_components.hpp>
0030 #include <boost/graph/named_function_params.hpp>
0031 #include <boost/graph/parallel/process_group.hpp>
0032 #include <boost/optional.hpp>
0033 #include <functional>
0034 #include <algorithm>
0035 #include <vector>
0036 #include <list>
0037 #include <boost/graph/parallel/container_traits.hpp>
0038 #include <boost/graph/iteration_macros.hpp>
0039
0040 #define PBGL_IN_PLACE_MERGE /* In place merge instead of sorting */
0041 //#define PBGL_SORT_ASSERT    /* Assert sorted for in place merge */
0042
0043 /* Explicit sychronization in pointer doubling step? */
0044 #define PBGL_EXPLICIT_SYNCH
0045 //#define PBGL_CONSTRUCT_METAGRAPH
0046 #ifdef PBGL_CONSTRUCT_METAGRAPH
0047 #  define MAX_VERTICES_IN_METAGRAPH 10000
0048 #endif
0049
0050 namespace boost { namespace graph { namespace distributed {
0051   namespace cc_detail {
0052     enum connected_components_message {
0053       edges_msg, req_parents_msg, parents_msg, root_adj_msg
0054     };
0055
0056     template <typename Vertex>
0057     struct metaVertex {
0058       metaVertex() {}
0059       metaVertex(const Vertex& v) : name(v) {}
0060
0061       template<typename Archiver>
0062       void serialize(Archiver& ar, const unsigned int /*version*/)
0063       {
0064         ar & name;
0065       }
0066
0067       Vertex name;
0068     };
0069
0070 #ifdef PBGL_CONSTRUCT_METAGRAPH
0071     // Build meta-graph on result of local connected components
0072     template <typename Graph, typename ParentMap, typename RootIterator,
0073               typename AdjacencyMap>
0074     void
0075     build_local_metagraph(const Graph& g, ParentMap p, RootIterator r,
0076                           RootIterator r_end, AdjacencyMap& adj)
0077     {
0078       // TODO: Static assert that AdjacencyMap::value_type is std::vector<vertex_descriptor>
0079
0080       typedef typename boost::graph::parallel::process_group_type<Graph>::type
0081         process_group_type;
0082       typedef typename process_group_type::process_id_type process_id_type;
0083
0084       typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
0085
0086       BOOST_STATIC_ASSERT((is_same<typename AdjacencyMap::mapped_type,
0087                                      std::vector<vertex_descriptor> >::value));
0088
0089       using boost::graph::parallel::process_group;
0090
0091       process_group_type pg = process_group(g);
0092       process_id_type id = process_id(pg);
0093
0094       if (id != 0) {
0095
0096         // Send component roots and their associated edges to P0
0097         for ( ; r != r_end; ++r ) {
0098           std::vector<vertex_descriptor> adjs(1, *r); // Root
0099           adjs.reserve(adjs.size() + adj[*r].size());
0100           for (typename std::vector<vertex_descriptor>::iterator iter = adj[*r].begin();
0101                iter != adj[*r].end(); ++iter)
0102             adjs.push_back(get(p, *iter)); // Adjacencies
0103
0104           send(pg, 0, root_adj_msg, adjs);
0105         }
0106       }
0107
0108       synchronize(pg);
0109
0110       if (id == 0) {
0111         typedef metaVertex<vertex_descriptor> VertexProperties;
0112
0113         typedef boost::adjacency_list<vecS, vecS, undirectedS,
0114           VertexProperties> metaGraph;
0115         typedef typename graph_traits<metaGraph>::vertex_descriptor
0116           meta_vertex_descriptor;
0117
0118         std::map<vertex_descriptor, meta_vertex_descriptor> vertex_map;
0119         std::vector<std::pair<vertex_descriptor, vertex_descriptor> > edges;
0120
0121         // Receive remote roots and edges
0122         while (optional<std::pair<process_id_type, int> > m = probe(pg)) {
0123           BOOST_ASSERT(m->second == root_adj_msg);
0124
0125           std::vector<vertex_descriptor> adjs;
0126           receive(pg, m->first, m->second, adjs);
0127
0128           vertex_map[adjs[0]] = graph_traits<metaGraph>::null_vertex();
0129           for (typename std::vector<vertex_descriptor>::iterator iter
0130                  = ++adjs.begin(); iter != adjs.end(); ++iter)
0131             edges.push_back(std::make_pair(adjs[0], *iter));
0132         }
0133
0134         // Add local roots and edges
0135         for ( ; r != r_end; ++r ) {
0136           vertex_map[*r] = graph_traits<metaGraph>::null_vertex();
0137           edges.reserve(edges.size() + adj[*r].size());
0138           for (typename std::vector<vertex_descriptor>::iterator iter = adj[*r].begin();
0139                iter != adj[*r].end(); ++iter)
0140             edges.push_back(std::make_pair(*r, get(p, *iter)));
0141         }
0142
0143         // Build local meta-graph
0144         metaGraph mg;
0145
0146         // Add vertices with property to map back to distributed graph vertex
0147         for (typename std::map<vertex_descriptor, meta_vertex_descriptor>::iterator
0148                iter = vertex_map.begin(); iter != vertex_map.end(); ++iter)
0149           vertex_map[iter->first]
0150             = add_vertex(metaVertex<vertex_descriptor>(iter->first), mg);
0151
0152         // Build meta-vertex map
0153         typename property_map<metaGraph, vertex_descriptor VertexProperties::*>::type
0154           metaVertexMap = get(&VertexProperties::name, mg);
0155
0156         typename std::vector<std::pair<vertex_descriptor, vertex_descriptor> >
0157           ::iterator edge_iter = edges.begin();
0158         for ( ; edge_iter != edges.end(); ++edge_iter)
0159           add_edge(vertex_map[edge_iter->first], vertex_map[edge_iter->second], mg);
0160
0161         edges.clear();
0162
0163         // Call connected_components on it
0164         typedef typename property_map<metaGraph, vertex_index_t>::type
0165           meta_index_map_type;
0166         meta_index_map_type meta_index = get(vertex_index, mg);
0167
0168         std::vector<std::size_t> mg_component_vec(num_vertices(mg));
0169         typedef iterator_property_map<std::vector<std::size_t>::iterator,
0170                                       meta_index_map_type>
0171         meta_components_map_type;
0172         meta_components_map_type mg_component(mg_component_vec.begin(),
0173                                               meta_index);
0174         std::size_t num_comp = connected_components(mg, mg_component);
0175
0176         // Update Parent pointers
0177         std::vector<meta_vertex_descriptor> roots(num_comp, graph_traits<metaGraph>::null_vertex());
0178
0179         BGL_FORALL_VERTICES_T(v, mg, metaGraph) {
0180           size_t component = get(mg_component, v);
0181           if (roots[component] == graph_traits<metaGraph>::null_vertex() ||
0182               get(meta_index, v) < get(meta_index, roots[component]))
0183             roots[component] = v;
0184         }
0185
0186         // Set all the local parent pointers
0187         BGL_FORALL_VERTICES_T(v, mg, metaGraph) {
0188           // Problem in value being put (3rd parameter)
0189           put(p, get(metaVertexMap, v), get(metaVertexMap, roots[get(mg_component, v)]));
0190         }
0191       }
0192
0193       synchronize(p);
0194     }
0195 #endif
0196
0197     /* Function object used to remove internal vertices and vertices >
0198        the current vertex from the adjacent vertex lists at each
0199        root */
0200     template <typename Vertex, typename ParentMap>
0201     class cull_adjacency_list
0202     {
0203     public:
0204       cull_adjacency_list(const Vertex v, const ParentMap p) : v(v), p(p) {}
0205       bool operator() (const Vertex x) { return (get(p, x) == v || x == v); }
0206
0207     private:
0208       const Vertex    v;
0209       const ParentMap p;
0210     };
0211
0212     /* Comparison operator used to choose targets for hooking s.t. vertices
0213        that are hooked to are evenly distributed across processors */
0214     template <typename OwnerMap, typename LocalMap>
0215     class hashed_vertex_compare
0216     {
0217     public:
0218       hashed_vertex_compare (const OwnerMap& o, const LocalMap& l)
0219         : owner(o), local(l) { }
0220
0221       template <typename Vertex>
0222       bool operator() (const Vertex x, const Vertex y)
0223       {
0224         if (get(local, x) < get(local, y))
0225           return true;
0226         else if (get(local, x) == get(local, y))
0227           return (get(owner, x) < get(owner, y));
0228         return false;
0229       }
0230
0231     private:
0232       OwnerMap   owner;
0233       LocalMap   local;
0234     };
0235
0236 #ifdef PBGL_EXPLICIT_SYNCH
0237     template <typename Graph, typename ParentMap, typename VertexList>
0238     void
0239     request_parent_map_entries(const Graph& g, ParentMap p,
0240                                std::vector<VertexList>& parent_requests)
0241     {
0242       typedef typename boost::graph::parallel::process_group_type<Graph>
0243         ::type process_group_type;
0244       typedef typename process_group_type::process_id_type process_id_type;
0245
0246       typedef typename graph_traits<Graph>::vertex_descriptor
0247         vertex_descriptor;
0248
0249       process_group_type pg = process_group(g);
0250
0251       /*
0252         This should probably be send_oob_with_reply, especially when Dave
0253         finishes prefetch-batching
0254       */
0255
0256       // Send root requests
0257       for (process_id_type i = 0; i < num_processes(pg); ++i) {
0258         if (!parent_requests[i].empty()) {
0259           std::vector<vertex_descriptor> reqs(parent_requests[i].begin(),
0260                                               parent_requests[i].end());
0261           send(pg, i, req_parents_msg, reqs);
0262         }
0263       }
0264
0265       synchronize(pg);
0266
0267       // Receive root requests and reply to them
0268       while (optional<std::pair<process_id_type, int> > m = probe(pg)) {
0269         std::vector<vertex_descriptor> requests;
0270         receive(pg, m->first, m->second, requests);
0271         for (std::size_t i = 0; i < requests.size(); ++i)
0272           requests[i] = get(p, requests[i]);
0273         send(pg, m->first, parents_msg, requests);
0274       }
0275
0276       synchronize(pg);
0277
0278       // Receive requested parents
0279       std::vector<vertex_descriptor> responses;
0280       for (process_id_type i = 0; i < num_processes(pg); ++i) {
0281         if (!parent_requests[i].empty()) {
0282           receive(pg, i, parents_msg, responses);
0283           std::size_t parent_idx = 0;
0284           for (typename VertexList::iterator v = parent_requests[i].begin();
0285                v != parent_requests[i].end(); ++v, ++parent_idx)
0286             put(p, *v, responses[parent_idx]);
0287         }
0288       }
0289     }
0290 #endif
0291
0292     template<typename DistributedGraph, typename ParentMap>
0293     void
0294     parallel_connected_components(DistributedGraph& g, ParentMap p)
0295     {
0296       using boost::connected_components;
0297
0298       typedef typename graph_traits<DistributedGraph>::adjacency_iterator
0299         adjacency_iterator;
0300       typedef typename graph_traits<DistributedGraph>::vertex_descriptor
0301         vertex_descriptor;
0302
0303       typedef typename boost::graph::parallel::process_group_type<DistributedGraph>
0304         ::type process_group_type;
0305       typedef typename process_group_type::process_id_type process_id_type;
0306
0307       using boost::graph::parallel::process_group;
0308
0309       process_group_type pg = process_group(g);
0310       process_id_type id = process_id(pg);
0311
0312       // TODO (NGE): Should old_roots, roots, and completed_roots be std::list
0313       adjacency_iterator av1, av2;
0314       std::vector<vertex_descriptor> old_roots;
0315       typename std::vector<vertex_descriptor>::iterator liter;
0316       typename std::vector<vertex_descriptor>::iterator aliter;
0317       typename std::map<vertex_descriptor,
0318                         std::vector<vertex_descriptor> > adj;
0319
0320       typedef typename property_map<DistributedGraph, vertex_owner_t>::const_type
0321         OwnerMap;
0322       OwnerMap owner = get(vertex_owner, g);
0323       typedef typename property_map<DistributedGraph, vertex_local_t>::const_type
0324         LocalMap;
0325       LocalMap local = get(vertex_local, g);
0326
0327       // We need to hold on to all of the parent pointers
0328       p.set_max_ghost_cells(0);
0329
0330       //
0331       // STAGE 1 : Compute local components
0332       //
0333       local_subgraph<const DistributedGraph> ls(g);
0334       typedef typename property_map<local_subgraph<const DistributedGraph>,
0335                                     vertex_index_t>::type local_index_map_type;
0336       local_index_map_type local_index = get(vertex_index, ls);
0337
0338       // Compute local connected components
0339       std::vector<std::size_t> ls_components_vec(num_vertices(ls));
0340       typedef iterator_property_map<std::vector<std::size_t>::iterator,
0341                                     local_index_map_type>
0342         ls_components_map_type;
0343       ls_components_map_type ls_component(ls_components_vec.begin(),
0344                                           local_index);
0345       std::size_t num_comp = connected_components(ls, ls_component);
0346
0347       std::vector<vertex_descriptor>
0348         roots(num_comp, graph_traits<DistributedGraph>::null_vertex());
0349
0350       BGL_FORALL_VERTICES_T(v, g, DistributedGraph) {
0351         size_t component = get(ls_component, v);
0352         if (roots[component] == graph_traits<DistributedGraph>::null_vertex() ||
0353             get(local_index, v) < get(local_index, roots[component]))
0354           roots[component] = v;
0355       }
0356
0357       // Set all the local parent pointers
0358       BGL_FORALL_VERTICES_T(v, g, DistributedGraph) {
0359         put(p, v, roots[get(ls_component, v)]);
0360       }
0361
0362       if (num_processes(pg) == 1) return;
0363
0364       // Build adjacency list for all roots
0365       BGL_FORALL_VERTICES_T(v, g, DistributedGraph) {
0366         std::vector<vertex_descriptor>& my_adj = adj[get(p, v)];
0367         for (boost::tie(av1, av2) = adjacent_vertices(v, g);
0368              av1 != av2; ++av1) {
0369           if (get(owner, *av1) != id) my_adj.push_back(*av1);
0370         }
0371       }
0372
0373       // For all vertices adjacent to a local vertex get p(v)
0374       for ( liter = roots.begin(); liter != roots.end(); ++liter ) {
0375         std::vector<vertex_descriptor>& my_adj = adj[*liter];
0376         for ( aliter = my_adj.begin(); aliter != my_adj.end(); ++aliter )
0377           request(p, *aliter);
0378       }
0379       synchronize(p);
0380
0381       // Update adjacency list at root to make sure all adjacent
0382       // vertices are roots of remote components
0383       for ( liter = roots.begin(); liter != roots.end(); ++liter )
0384         {
0385           std::vector<vertex_descriptor>& my_adj = adj[*liter];
0386           for ( aliter = my_adj.begin(); aliter != my_adj.end(); ++aliter )
0387             *aliter = get(p, *aliter);
0388
0389           my_adj.erase
0390             (std::remove_if(my_adj.begin(), my_adj.end(),
0391                        cull_adjacency_list<vertex_descriptor,
0392                                            ParentMap>(*liter, p) ),
0393              my_adj.end());
0394           // This sort needs to be here to make sure the initial
0395           // adjacency list is sorted
0396           std::sort(my_adj.begin(), my_adj.end(), std::less<vertex_descriptor>());
0397           my_adj.erase(std::unique(my_adj.begin(), my_adj.end()), my_adj.end());
0398         }
0399
0400       // Get p(v) for the new adjacent roots
0401       p.clear();
0402       for ( liter = roots.begin(); liter != roots.end(); ++liter ) {
0403         std::vector<vertex_descriptor>& my_adj = adj[*liter];
0404         for ( aliter = my_adj.begin(); aliter != my_adj.end(); ++aliter )
0405           request(p, *aliter);
0406       }
0407 #ifdef PBGL_EXPLICIT_SYNCH
0408       synchronize(p);
0409 #endif
0410
0411       // Lastly, remove roots with no adjacent vertices, this is
0412       // unnecessary but will speed up sparse graphs
0413       for ( liter = roots.begin(); liter != roots.end(); /*in loop*/)
0414         {
0415           if ( adj[*liter].empty() )
0416             liter = roots.erase(liter);
0417           else
0418             ++liter;
0419         }
0420
0421 #ifdef PBGL_CONSTRUCT_METAGRAPH
0422       /* TODO: If the number of roots is sufficiently small, we can
0423                use a 'problem folding' approach like we do in MST
0424                to gather all the roots and their adjacencies on one proc
0425                and solve for the connected components of the meta-graph */
0426       using boost::parallel::all_reduce;
0427       std::size_t num_roots = all_reduce(pg, roots.size(), std::plus<std::size_t>());
0428       if (num_roots < MAX_VERTICES_IN_METAGRAPH) {
0429         build_local_metagraph(g, p, roots.begin(), roots.end(), adj);
0430
0431         // For each vertex in g, p(v) = p(p(v)), assign parent of leaf
0432         // vertices from first step to final parent
0433         BGL_FORALL_VERTICES_T(v, g, DistributedGraph) {
0434           put(p, v, get(p, get(p, v)));
0435         }
0436
0437         synchronize(p);
0438
0439         return;
0440       }
0441 #endif
0442
0443       //
0444       // Parallel Phase
0445       //
0446
0447       std::vector<vertex_descriptor> completed_roots;
0448       hashed_vertex_compare<OwnerMap, LocalMap> v_compare(owner, local);
0449       bool any_hooked;
0450       vertex_descriptor new_root;
0451
0452       std::size_t steps = 0;
0453
0454       do {
0455         ++steps;
0456
0457         // Pull in new parents for hooking phase
0458         synchronize(p);
0459
0460         //
0461         // Hooking
0462         //
0463         bool hooked = false;
0464         completed_roots.clear();
0465         for ( liter = roots.begin(); liter != roots.end(); )
0466           {
0467             new_root = graph_traits<DistributedGraph>::null_vertex();
0468             std::vector<vertex_descriptor>& my_adj = adj[*liter];
0469             for ( aliter = my_adj.begin(); aliter != my_adj.end(); ++aliter )
0470               // try to hook to better adjacent vertex
0471               if ( v_compare( get(p, *aliter), *liter ) )
0472                 new_root = get(p, *aliter);
0473
0474             if ( new_root != graph_traits<DistributedGraph>::null_vertex() )
0475               {
0476                 hooked = true;
0477                 put(p, *liter, new_root);
0478                 old_roots.push_back(*liter);
0479                 completed_roots.push_back(*liter);
0480                 liter = roots.erase(liter);
0481               }
0482             else
0483               ++liter;
0484           }
0485
0486         //
0487         // Pointer jumping, perform until new roots determined
0488         //
0489
0490         // TODO: Implement cycle reduction rules to reduce this from
0491         // O(n) to O(log n) [n = cycle length]
0492         bool all_done;
0493         std::size_t parent_root_count;
0494
0495         std::size_t double_steps = 0;
0496
0497         do {
0498           ++double_steps;
0499 #ifndef PBGL_EXPLICIT_SYNCH
0500           // Get p(p(v)) for all old roots, and p(v) for all current roots
0501           for ( liter = old_roots.begin(); liter != old_roots.end(); ++liter )
0502             request(p, get(p, *liter));
0503
0504           synchronize(p);
0505 #else
0506           // Build root requests
0507           typedef std::set<vertex_descriptor> VertexSet;
0508           std::vector<VertexSet> parent_requests(num_processes(pg));
0509           for ( liter = old_roots.begin(); liter != old_roots.end(); ++liter )
0510             {
0511               vertex_descriptor p1 = *liter;
0512               if (get(owner, p1) != id) parent_requests[get(owner, p1)].insert(p1);
0513               vertex_descriptor p2 = get(p, p1);
0514               if (get(owner, p2) != id) parent_requests[get(owner, p2)].insert(p2);
0515             }
0516
0517           request_parent_map_entries(g, p, parent_requests);
0518 #endif
0519           // Perform a pointer jumping step on all old roots
0520           for ( liter = old_roots.begin(); liter != old_roots.end(); ++liter )
0521               put(p, *liter, get(p, get(p, *liter)));
0522
0523           // make sure the parent of all old roots is itself a root
0524           parent_root_count = 0;
0525           for ( liter = old_roots.begin(); liter != old_roots.end(); ++liter )
0526             if ( get(p, *liter) == get(p, get(p, *liter)) )
0527               parent_root_count++;
0528
0529           bool done = parent_root_count == old_roots.size();
0530
0531           all_reduce(pg, &done, &done+1, &all_done,
0532                      std::logical_and<bool>());
0533         } while ( !all_done );
0534 #ifdef PARALLEL_BGL_DEBUG
0535         if (id == 0) std::cerr << double_steps << " doubling steps.\n";
0536 #endif
0537         //
0538         // Add adjacent vertices of just completed roots to adjacent
0539         // vertex list at new parent
0540         //
0541         typename std::vector<vertex_descriptor> outgoing_edges;
0542         for ( liter = completed_roots.begin(); liter != completed_roots.end();
0543               ++liter )
0544           {
0545             vertex_descriptor new_parent = get(p, *liter);
0546
0547             if ( get(owner, new_parent) == id )
0548               {
0549                 std::vector<vertex_descriptor>& my_adj = adj[new_parent];
0550                 my_adj.reserve(my_adj.size() + adj[*liter].size());
0551                 my_adj.insert( my_adj.end(),
0552                                adj[*liter].begin(), adj[*liter].end() );
0553 #ifdef PBGL_IN_PLACE_MERGE
0554 #ifdef PBGL_SORT_ASSERT
0555                 BOOST_ASSERT(::boost::detail::is_sorted(my_adj.begin(),
0556                                                   my_adj.end() - adj[*liter].size(),
0557                                                   std::less<vertex_descriptor>()));
0558                 BOOST_ASSERT(::boost::detail::is_sorted(my_adj.end() - adj[*liter].size(),
0559                                                   my_adj.end(),
0560                                                   std::less<vertex_descriptor>()));
0561 #endif
0562                 std::inplace_merge(my_adj.begin(),
0563                                    my_adj.end() - adj[*liter].size(),
0564                                    my_adj.end(),
0565                                    std::less<vertex_descriptor>());
0566 #endif
0567
0568
0569               }
0570             else if ( adj[*liter].begin() != adj[*liter].end() )
0571               {
0572                 outgoing_edges.clear();
0573                 outgoing_edges.reserve(adj[*liter].size() + 1);
0574                 // First element is the destination of the adjacency list
0575                 outgoing_edges.push_back(new_parent);
0576                 outgoing_edges.insert(outgoing_edges.end(),
0577                                       adj[*liter].begin(), adj[*liter].end() );
0578                 send(pg, get(owner, new_parent), edges_msg, outgoing_edges);
0579                 adj[*liter].clear();
0580               }
0581           }
0582         synchronize(pg);
0583
0584         // Receive edges sent by remote nodes and add them to the
0585         // indicated vertex's adjacency list
0586         while (optional<std::pair<process_id_type, int> > m
0587                = probe(pg))
0588           {
0589             std::vector<vertex_descriptor> incoming_edges;
0590             receive(pg, m->first, edges_msg, incoming_edges);
0591             typename std::vector<vertex_descriptor>::iterator aviter
0592               = incoming_edges.begin();
0593             ++aviter;
0594
0595             std::vector<vertex_descriptor>& my_adj = adj[incoming_edges[0]];
0596
0597             my_adj.reserve(my_adj.size() + incoming_edges.size() - 1);
0598             my_adj.insert( my_adj.end(), aviter, incoming_edges.end() );
0599
0600 #ifdef PBGL_IN_PLACE_MERGE
0601             std::size_t num_incoming_edges = incoming_edges.size();
0602 #ifdef PBGL_SORT_ASSERT
0603             BOOST_ASSERT(::boost::detail::is_sorted(my_adj.begin(),
0604                                               my_adj.end() - (num_incoming_edges-1),
0605                                               std::less<vertex_descriptor>()));
0606             BOOST_ASSERT(::boost::detail::is_sorted(my_adj.end() - (num_incoming_edges-1),
0607                                               my_adj.end(),
0608                                               std::less<vertex_descriptor>()));
0609 #endif
0610             std::inplace_merge(my_adj.begin(),
0611                                my_adj.end() - (num_incoming_edges - 1),
0612                                my_adj.end(),
0613                                std::less<vertex_descriptor>());
0614 #endif
0615
0616           }
0617
0618
0619         // Remove any adjacent vertices that are in the same component
0620         // as a root from that root's list
0621         for ( liter = roots.begin(); liter != roots.end(); ++liter )
0622           {
0623             // We can probably get away without sorting and removing
0624             // duplicates Though sorting *may* cause root
0625             // determination to occur faster by choosing the root with
0626             // the most potential to hook to at each step
0627             std::vector<vertex_descriptor>& my_adj = adj[*liter];
0628             my_adj.erase
0629               (std::remove_if(my_adj.begin(), my_adj.end(),
0630                          cull_adjacency_list<vertex_descriptor,
0631                                              ParentMap>(*liter, p) ),
0632                my_adj.end());
0633 #ifndef PBGL_IN_PLACE_MERGE
0634             std::sort(my_adj.begin(), my_adj.end(),
0635                  std::less<vertex_descriptor>() );
0636 #endif
0637             my_adj.erase(std::unique(my_adj.begin(), my_adj.end()), my_adj.end());
0638           }
0639
0640         // Reduce result of empty root list test
0641         all_reduce(pg, &hooked, &hooked+1, &any_hooked,
0642                    std::logical_or<bool>());
0643       } while ( any_hooked );
0644 #ifdef PARALLEL_BGL_DEBUG
0645       if (id == 0) std::cerr << steps << " iterations.\n";
0646 #endif
0647       //
0648       // Finalize
0649       //
0650
0651       // For each vertex in g, p(v) = p(p(v)), assign parent of leaf
0652       // vertices from first step to final parent
0653       BGL_FORALL_VERTICES_T(v, g, DistributedGraph) {
0654         put(p, v, get(p, get(p, v)));
0655       }
0656
0657       synchronize(p);
0658     }
0659
0660   } // end namespace cc_detail
0661
0662   template<typename Graph, typename ParentMap, typename ComponentMap>
0663   typename property_traits<ComponentMap>::value_type
0664   number_components_from_parents(const Graph& g, ParentMap p, ComponentMap c)
0665   {
0666     typedef typename graph_traits<Graph>::vertex_descriptor
0667       vertex_descriptor;
0668     typedef typename boost::graph::parallel::process_group_type<Graph>::type
0669       process_group_type;
0670     typedef typename property_traits<ComponentMap>::value_type
0671       ComponentMapType;
0672
0673     process_group_type pg = process_group(g);
0674
0675     /* Build list of roots */
0676     std::vector<vertex_descriptor> my_roots, all_roots;
0677
0678     BGL_FORALL_VERTICES_T(v, g, Graph) {
0679       if( std::find( my_roots.begin(), my_roots.end(), get(p, v) )
0680           == my_roots.end() )
0681         my_roots.push_back( get(p, v) );
0682     }
0683
0684     all_gather(pg, my_roots.begin(), my_roots.end(), all_roots);
0685
0686     /* Number components */
0687     std::map<vertex_descriptor, ComponentMapType> comp_numbers;
0688     ComponentMapType c_num = 0;
0689
0690     // Compute component numbers
0691     for (std::size_t i = 0; i < all_roots.size(); i++ )
0692       if ( comp_numbers.count(all_roots[i]) == 0 )
0693         comp_numbers[all_roots[i]] = c_num++;
0694
0695     // Broadcast component numbers
0696     BGL_FORALL_VERTICES_T(v, g, Graph) {
0697       put( c, v, comp_numbers[get(p, v)] );
0698     }
0699
0700     // Broadcast number of components
0701     if (process_id(pg) == 0) {
0702       typedef typename process_group_type::process_size_type
0703         process_size_type;
0704       for (process_size_type dest = 1, n = num_processes(pg);
0705            dest != n; ++dest)
0706         send(pg, dest, 0, c_num);
0707     }
0708     synchronize(pg);
0709
0710     if (process_id(pg) != 0) receive(pg, 0, 0, c_num);
0711
0712     synchronize(c);
0713
0714     return c_num;
0715   }
0716
0717   template<typename Graph, typename ParentMap>
0718   int
0719   number_components_from_parents(const Graph& g, ParentMap p,
0720                                  dummy_property_map)
0721   {
0722     using boost::parallel::all_reduce;
0723
0724     // Count local roots.
0725     int num_roots = 0;
0726     BGL_FORALL_VERTICES_T(v, g, Graph)
0727       if (get(p, v) == v) ++num_roots;
0728     return all_reduce(g.process_group(), num_roots, std::plus<int>());
0729   }
0730
0731   template<typename Graph, typename ComponentMap, typename ParentMap>
0732   typename property_traits<ComponentMap>::value_type
0733   connected_components
0734     (const Graph& g, ComponentMap c, ParentMap p
0735      BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph, distributed_graph_tag))
0736   {
0737     cc_detail::parallel_connected_components(g, p);
0738     return number_components_from_parents(g, p, c);
0739   }
0740
0741   /* Construct ParentMap by default */
0742   template<typename Graph, typename ComponentMap>
0743   typename property_traits<ComponentMap>::value_type
0744   connected_components
0745     ( const Graph& g, ComponentMap c
0746       BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph, distributed_graph_tag) )
0747   {
0748     typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
0749
0750     std::vector<vertex_descriptor> x(num_vertices(g));
0751
0752     return connected_components
0753              (g, c,
0754               make_iterator_property_map(x.begin(), get(vertex_index, g)));
0755   }
0756 } // end namespace distributed
0757
0758 using distributed::connected_components;
0759 } // end namespace graph
0760
0761 using graph::distributed::connected_components;
0762 } // end namespace boost
0763
0764 #endif // BOOST_GRAPH_PARALLEL_CC_HPP