1 // Copyright (C) 2004-2006 The Trustees of Indiana University. 2 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) 6 7 // Authors: Nick Edmonds 8 // Douglas Gregor 9 // Andrew Lumsdaine 10 #ifndef BOOST_GRAPH_PARALLEL_CC_HPP 11 #define BOOST_GRAPH_PARALLEL_CC_HPP 12 13 #ifndef BOOST_GRAPH_USE_MPI 14 #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included" 15 #endif 16 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> 32 #include <functional> 33 #include <algorithm> 34 #include <vector> 35 #include <list> 36 #include <boost/graph/parallel/container_traits.hpp> 37 #include <boost/graph/iteration_macros.hpp> 38 39 #define PBGL_IN_PLACE_MERGE /* In place merge instead of sorting */ 40 //#define PBGL_SORT_ASSERT /* Assert sorted for in place merge */ 41 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 47 #endif 48 49 namespace boost { namespace graph { namespace distributed { 50 namespace cc_detail { 51 enum connected_components_message { 52 edges_msg, req_parents_msg, parents_msg, root_adj_msg 53 }; 54 55 template <typename Vertex> 56 struct metaVertex { metaVertexboost::graph::distributed::cc_detail::metaVertex57 metaVertex() {} metaVertexboost::graph::distributed::cc_detail::metaVertex58 metaVertex(const Vertex& v) : name(v) {} 59 60 template<typename Archiver> serializeboost::graph::distributed::cc_detail::metaVertex61 void serialize(Archiver& ar, const unsigned int /*version*/) 62 { 63 ar & name; 64 } 65 66 Vertex name; 67 }; 68 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> 73 void build_local_metagraph(const Graph & g,ParentMap p,RootIterator r,RootIterator r_end,AdjacencyMap & adj)74 build_local_metagraph(const Graph& g, ParentMap p, RootIterator r, 75 RootIterator r_end, AdjacencyMap& adj) 76 { 77 // TODO: Static assert that AdjacencyMap::value_type is std::vector<vertex_descriptor> 78 79 typedef typename boost::graph::parallel::process_group_type<Graph>::type 80 process_group_type; 81 typedef typename process_group_type::process_id_type process_id_type; 82 83 typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; 84 85 BOOST_STATIC_ASSERT((is_same<typename AdjacencyMap::mapped_type, 86 std::vector<vertex_descriptor> >::value)); 87 88 using boost::graph::parallel::process_group; 89 90 process_group_type pg = process_group(g); 91 process_id_type id = process_id(pg); 92 93 if (id != 0) { 94 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 102 103 send(pg, 0, root_adj_msg, adjs); 104 } 105 } 106 107 synchronize(pg); 108 109 if (id == 0) { 110 typedef metaVertex<vertex_descriptor> VertexProperties; 111 112 typedef boost::adjacency_list<vecS, vecS, undirectedS, 113 VertexProperties> metaGraph; 114 typedef typename graph_traits<metaGraph>::vertex_descriptor 115 meta_vertex_descriptor; 116 117 std::map<vertex_descriptor, meta_vertex_descriptor> vertex_map; 118 std::vector<std::pair<vertex_descriptor, vertex_descriptor> > edges; 119 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); 123 124 std::vector<vertex_descriptor> adjs; 125 receive(pg, m->first, m->second, adjs); 126 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)); 131 } 132 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))); 140 } 141 142 // Build local meta-graph 143 metaGraph mg; 144 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); 150 151 // Build meta-vertex map 152 typename property_map<metaGraph, vertex_descriptor VertexProperties::*>::type 153 metaVertexMap = get(&VertexProperties::name, mg); 154 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); 159 160 edges.clear(); 161 162 // Call connected_components on it 163 typedef typename property_map<metaGraph, vertex_index_t>::type 164 meta_index_map_type; 165 meta_index_map_type meta_index = get(vertex_index, mg); 166 167 std::vector<std::size_t> mg_component_vec(num_vertices(mg)); 168 typedef iterator_property_map<std::vector<std::size_t>::iterator, 169 meta_index_map_type> 170 meta_components_map_type; 171 meta_components_map_type mg_component(mg_component_vec.begin(), 172 meta_index); 173 std::size_t num_comp = connected_components(mg, mg_component); 174 175 // Update Parent pointers 176 std::vector<meta_vertex_descriptor> roots(num_comp, graph_traits<metaGraph>::null_vertex()); 177 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; 183 } 184 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)])); 189 } 190 } 191 192 synchronize(p); 193 } 194 #endif 195 196 /* Function object used to remove internal vertices and vertices > 197 the current vertex from the adjacent vertex lists at each 198 root */ 199 template <typename Vertex, typename ParentMap> 200 class cull_adjacency_list 201 { 202 public: cull_adjacency_list(const Vertex v,const ParentMap p)203 cull_adjacency_list(const Vertex v, const ParentMap p) : v(v), p(p) {} operator ()(const Vertex x)204 bool operator() (const Vertex x) { return (get(p, x) == v || x == v); } 205 206 private: 207 const Vertex v; 208 const ParentMap p; 209 }; 210 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 215 { 216 public: hashed_vertex_compare(const OwnerMap & o,const LocalMap & l)217 hashed_vertex_compare (const OwnerMap& o, const LocalMap& l) 218 : owner(o), local(l) { } 219 220 template <typename Vertex> operator ()(const Vertex x,const Vertex y)221 bool operator() (const Vertex x, const Vertex y) 222 { 223 if (get(local, x) < get(local, y)) 224 return true; 225 else if (get(local, x) == get(local, y)) 226 return (get(owner, x) < get(owner, y)); 227 return false; 228 } 229 230 private: 231 OwnerMap owner; 232 LocalMap local; 233 }; 234 235 #ifdef PBGL_EXPLICIT_SYNCH 236 template <typename Graph, typename ParentMap, typename VertexList> 237 void request_parent_map_entries(const Graph & g,ParentMap p,std::vector<VertexList> & parent_requests)238 request_parent_map_entries(const Graph& g, ParentMap p, 239 std::vector<VertexList>& parent_requests) 240 { 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; 244 245 typedef typename graph_traits<Graph>::vertex_descriptor 246 vertex_descriptor; 247 248 process_group_type pg = process_group(g); 249 250 /* 251 This should probably be send_oob_with_reply, especially when Dave 252 finishes prefetch-batching 253 */ 254 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); 261 } 262 } 263 264 synchronize(pg); 265 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); 273 } 274 275 synchronize(pg); 276 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]); 286 } 287 } 288 } 289 #endif 290 291 template<typename DistributedGraph, typename ParentMap> 292 void parallel_connected_components(DistributedGraph & g,ParentMap p)293 parallel_connected_components(DistributedGraph& g, ParentMap p) 294 { 295 using boost::connected_components; 296 297 typedef typename graph_traits<DistributedGraph>::adjacency_iterator 298 adjacency_iterator; 299 typedef typename graph_traits<DistributedGraph>::vertex_descriptor 300 vertex_descriptor; 301 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; 305 306 using boost::graph::parallel::process_group; 307 308 process_group_type pg = process_group(g); 309 process_id_type id = process_id(pg); 310 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; 318 319 typedef typename property_map<DistributedGraph, vertex_owner_t>::const_type 320 OwnerMap; 321 OwnerMap owner = get(vertex_owner, g); 322 typedef typename property_map<DistributedGraph, vertex_local_t>::const_type 323 LocalMap; 324 LocalMap local = get(vertex_local, g); 325 326 // We need to hold on to all of the parent pointers 327 p.set_max_ghost_cells(0); 328 329 // 330 // STAGE 1 : Compute local components 331 // 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); 336 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(), 343 local_index); 344 std::size_t num_comp = connected_components(ls, ls_component); 345 346 std::vector<vertex_descriptor> 347 roots(num_comp, graph_traits<DistributedGraph>::null_vertex()); 348 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; 354 } 355 356 // Set all the local parent pointers 357 BGL_FORALL_VERTICES_T(v, g, DistributedGraph) { 358 put(p, v, roots[get(ls_component, v)]); 359 } 360 361 if (num_processes(pg) == 1) return; 362 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); 367 av1 != av2; ++av1) { 368 if (get(owner, *av1) != id) my_adj.push_back(*av1); 369 } 370 } 371 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 ) 376 request(p, *aliter); 377 } 378 synchronize(p); 379 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 ) 383 { 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); 387 388 my_adj.erase 389 (std::remove_if(my_adj.begin(), my_adj.end(), 390 cull_adjacency_list<vertex_descriptor, 391 ParentMap>(*liter, p) ), 392 my_adj.end()); 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()); 397 } 398 399 // Get p(v) for the new adjacent roots 400 p.clear(); 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 ) 404 request(p, *aliter); 405 } 406 #ifdef PBGL_EXPLICIT_SYNCH 407 synchronize(p); 408 #endif 409 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*/) 413 { 414 if ( adj[*liter].empty() ) 415 liter = roots.erase(liter); 416 else 417 ++liter; 418 } 419 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); 429 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))); 434 } 435 436 synchronize(p); 437 438 return; 439 } 440 #endif 441 442 // 443 // Parallel Phase 444 // 445 446 std::vector<vertex_descriptor> completed_roots; 447 hashed_vertex_compare<OwnerMap, LocalMap> v_compare(owner, local); 448 bool any_hooked; 449 vertex_descriptor new_root; 450 451 std::size_t steps = 0; 452 453 do { 454 ++steps; 455 456 // Pull in new parents for hooking phase 457 synchronize(p); 458 459 // 460 // Hooking 461 // 462 bool hooked = false; 463 completed_roots.clear(); 464 for ( liter = roots.begin(); liter != roots.end(); ) 465 { 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); 472 473 if ( new_root != graph_traits<DistributedGraph>::null_vertex() ) 474 { 475 hooked = true; 476 put(p, *liter, new_root); 477 old_roots.push_back(*liter); 478 completed_roots.push_back(*liter); 479 liter = roots.erase(liter); 480 } 481 else 482 ++liter; 483 } 484 485 // 486 // Pointer jumping, perform until new roots determined 487 // 488 489 // TODO: Implement cycle reduction rules to reduce this from 490 // O(n) to O(log n) [n = cycle length] 491 bool all_done; 492 std::size_t parent_root_count; 493 494 std::size_t double_steps = 0; 495 496 do { 497 ++double_steps; 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)); 502 503 synchronize(p); 504 #else 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 ) 509 { 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); 514 } 515 516 request_parent_map_entries(g, p, parent_requests); 517 #endif 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))); 521 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)) ) 526 parent_root_count++; 527 528 bool done = parent_root_count == old_roots.size(); 529 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"; 535 #endif 536 // 537 // Add adjacent vertices of just completed roots to adjacent 538 // vertex list at new parent 539 // 540 typename std::vector<vertex_descriptor> outgoing_edges; 541 for ( liter = completed_roots.begin(); liter != completed_roots.end(); 542 ++liter ) 543 { 544 vertex_descriptor new_parent = get(p, *liter); 545 546 if ( get(owner, new_parent) == id ) 547 { 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(), 558 my_adj.end(), 559 std::less<vertex_descriptor>())); 560 #endif 561 std::inplace_merge(my_adj.begin(), 562 my_adj.end() - adj[*liter].size(), 563 my_adj.end(), 564 std::less<vertex_descriptor>()); 565 #endif 566 567 568 } 569 else if ( adj[*liter].begin() != adj[*liter].end() ) 570 { 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); 578 adj[*liter].clear(); 579 } 580 } 581 synchronize(pg); 582 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 586 = probe(pg)) 587 { 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(); 592 ++aviter; 593 594 std::vector<vertex_descriptor>& my_adj = adj[incoming_edges[0]]; 595 596 my_adj.reserve(my_adj.size() + incoming_edges.size() - 1); 597 my_adj.insert( my_adj.end(), aviter, incoming_edges.end() ); 598 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), 606 my_adj.end(), 607 std::less<vertex_descriptor>())); 608 #endif 609 std::inplace_merge(my_adj.begin(), 610 my_adj.end() - (num_incoming_edges - 1), 611 my_adj.end(), 612 std::less<vertex_descriptor>()); 613 #endif 614 615 } 616 617 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 ) 621 { 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]; 627 my_adj.erase 628 (std::remove_if(my_adj.begin(), my_adj.end(), 629 cull_adjacency_list<vertex_descriptor, 630 ParentMap>(*liter, p) ), 631 my_adj.end()); 632 #ifndef PBGL_IN_PLACE_MERGE 633 std::sort(my_adj.begin(), my_adj.end(), 634 std::less<vertex_descriptor>() ); 635 #endif 636 my_adj.erase(std::unique(my_adj.begin(), my_adj.end()), my_adj.end()); 637 } 638 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"; 645 #endif 646 // 647 // Finalize 648 // 649 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))); 654 } 655 656 synchronize(p); 657 } 658 659 } // end namespace cc_detail 660 661 template<typename Graph, typename ParentMap, typename ComponentMap> 662 typename property_traits<ComponentMap>::value_type number_components_from_parents(const Graph & g,ParentMap p,ComponentMap c)663 number_components_from_parents(const Graph& g, ParentMap p, ComponentMap c) 664 { 665 typedef typename graph_traits<Graph>::vertex_descriptor 666 vertex_descriptor; 667 typedef typename boost::graph::parallel::process_group_type<Graph>::type 668 process_group_type; 669 typedef typename property_traits<ComponentMap>::value_type 670 ComponentMapType; 671 672 process_group_type pg = process_group(g); 673 674 /* Build list of roots */ 675 std::vector<vertex_descriptor> my_roots, all_roots; 676 677 BGL_FORALL_VERTICES_T(v, g, Graph) { 678 if( std::find( my_roots.begin(), my_roots.end(), get(p, v) ) 679 == my_roots.end() ) 680 my_roots.push_back( get(p, v) ); 681 } 682 683 all_gather(pg, my_roots.begin(), my_roots.end(), all_roots); 684 685 /* Number components */ 686 std::map<vertex_descriptor, ComponentMapType> comp_numbers; 687 ComponentMapType c_num = 0; 688 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++; 693 694 // Broadcast component numbers 695 BGL_FORALL_VERTICES_T(v, g, Graph) { 696 put( c, v, comp_numbers[get(p, v)] ); 697 } 698 699 // Broadcast number of components 700 if (process_id(pg) == 0) { 701 typedef typename process_group_type::process_size_type 702 process_size_type; 703 for (process_size_type dest = 1, n = num_processes(pg); 704 dest != n; ++dest) 705 send(pg, dest, 0, c_num); 706 } 707 synchronize(pg); 708 709 if (process_id(pg) != 0) receive(pg, 0, 0, c_num); 710 711 synchronize(c); 712 713 return c_num; 714 } 715 716 template<typename Graph, typename ParentMap> 717 int number_components_from_parents(const Graph & g,ParentMap p,dummy_property_map)718 number_components_from_parents(const Graph& g, ParentMap p, 719 dummy_property_map) 720 { 721 using boost::parallel::all_reduce; 722 723 // Count local roots. 724 int num_roots = 0; 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>()); 728 } 729 730 template<typename Graph, typename ComponentMap, typename ParentMap> 731 typename property_traits<ComponentMap>::value_type connected_components(const Graph & g,ComponentMap c,ParentMap p BOOST_GRAPH_ENABLE_IF_MODELS_PARM (Graph,distributed_graph_tag))732 connected_components 733 (const Graph& g, ComponentMap c, ParentMap p 734 BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph, distributed_graph_tag)) 735 { 736 cc_detail::parallel_connected_components(g, p); 737 return number_components_from_parents(g, p, c); 738 } 739 740 /* Construct ParentMap by default */ 741 template<typename Graph, typename ComponentMap> 742 typename property_traits<ComponentMap>::value_type connected_components(const Graph & g,ComponentMap c BOOST_GRAPH_ENABLE_IF_MODELS_PARM (Graph,distributed_graph_tag))743 connected_components 744 ( const Graph& g, ComponentMap c 745 BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph, distributed_graph_tag) ) 746 { 747 typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; 748 749 std::vector<vertex_descriptor> x(num_vertices(g)); 750 751 return connected_components 752 (g, c, 753 make_iterator_property_map(x.begin(), get(vertex_index, g))); 754 } 755 } // end namespace distributed 756 757 using distributed::connected_components; 758 } // end namespace graph 759 760 using graph::distributed::connected_components; 761 } // end namespace boost 762 763 #endif // BOOST_GRAPH_PARALLEL_CC_HPP 764