]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 { | |
57 | metaVertex() {} | |
58 | metaVertex(const Vertex& v) : name(v) {} | |
59 | ||
60 | template<typename Archiver> | |
61 | 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 | |
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: | |
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); } | |
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: | |
217 | hashed_vertex_compare (const OwnerMap& o, const LocalMap& l) | |
218 | : owner(o), local(l) { } | |
219 | ||
220 | template <typename Vertex> | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 |