]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Copyright 2005 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: Douglas Gregor | |
8 | // Andrew Lumsdaine | |
9 | ||
10 | // An implementation of Walter Hohberg's distributed biconnected | |
11 | // components algorithm, from: | |
12 | // | |
13 | // Walter Hohberg. How to Find Biconnected Components in Distributed | |
14 | // Networks. J. Parallel Distrib. Comput., 9(4):374-386, 1990. | |
15 | // | |
16 | #ifndef BOOST_GRAPH_DISTRIBUTED_HOHBERG_BICONNECTED_COMPONENTS_HPP | |
17 | #define BOOST_GRAPH_DISTRIBUTED_HOHBERG_BICONNECTED_COMPONENTS_HPP | |
18 | ||
19 | #ifndef BOOST_GRAPH_USE_MPI | |
20 | #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included" | |
21 | #endif | |
22 | ||
23 | /* You can define PBGL_HOHBERG_DEBUG to an integer value (1, 2, or 3) | |
24 | * to enable debugging information. 1 includes only the phases of the | |
25 | * algorithm and messages as their are received. 2 and 3 add | |
26 | * additional levels of detail about internal data structures related | |
27 | * to the algorithm itself. | |
28 | * | |
29 | * #define PBGL_HOHBERG_DEBUG 1 | |
30 | */ | |
31 | ||
32 | #include <boost/graph/graph_traits.hpp> | |
33 | #include <boost/graph/parallel/container_traits.hpp> | |
34 | #include <boost/graph/parallel/process_group.hpp> | |
35 | #include <boost/static_assert.hpp> | |
36 | #include <boost/mpi/operations.hpp> | |
37 | #include <boost/type_traits/is_convertible.hpp> | |
38 | #include <boost/graph/graph_concepts.hpp> | |
39 | #include <boost/graph/iteration_macros.hpp> | |
40 | #include <boost/optional.hpp> | |
41 | #include <utility> // for std::pair | |
42 | #include <boost/assert.hpp> | |
43 | #include <algorithm> // for std::find, std::mismatch | |
44 | #include <vector> | |
45 | #include <boost/graph/parallel/algorithm.hpp> | |
46 | #include <boost/graph/distributed/connected_components.hpp> | |
47 | #include <boost/concept/assert.hpp> | |
48 | ||
49 | namespace boost { namespace graph { namespace distributed { | |
50 | ||
51 | namespace hohberg_detail { | |
52 | enum message_kind { | |
53 | /* A header for the PATH message, stating which edge the message | |
54 | is coming on and how many vertices will be following. The data | |
55 | structure communicated will be a path_header. */ | |
56 | msg_path_header, | |
57 | /* A message containing the vertices that make up a path. It will | |
58 | always follow a msg_path_header and will contain vertex | |
59 | descriptors, only. */ | |
60 | msg_path_vertices, | |
61 | /* A header for the TREE message, stating the value of gamma and | |
62 | the number of vertices to come in the following | |
63 | msg_tree_vertices. */ | |
64 | msg_tree_header, | |
65 | /* A message containing the vertices that make up the set of | |
66 | vertices in the same bicomponent as the sender. It will always | |
67 | follow a msg_tree_header and will contain vertex descriptors, | |
68 | only. */ | |
69 | msg_tree_vertices, | |
70 | /* Provides a name for the biconnected component of the edge. */ | |
71 | msg_name | |
72 | }; | |
73 | ||
74 | // Payload for a msg_path_header message. | |
75 | template<typename EdgeDescriptor> | |
76 | struct path_header | |
77 | { | |
78 | // The edge over which the path is being communicated | |
79 | EdgeDescriptor edge; | |
80 | ||
81 | // The length of the path, i.e., the number of vertex descriptors | |
82 | // that will be coming in the next msg_path_vertices message. | |
83 | std::size_t path_length; | |
84 | ||
85 | template<typename Archiver> | |
86 | void serialize(Archiver& ar, const unsigned int /*version*/) | |
87 | { | |
88 | ar & edge & path_length; | |
89 | } | |
90 | }; | |
91 | ||
92 | // Payload for a msg_tree_header message. | |
93 | template<typename Vertex, typename Edge> | |
94 | struct tree_header | |
95 | { | |
96 | // The edge over which the tree is being communicated | |
97 | Edge edge; | |
98 | ||
99 | // Gamma, which is the eta of the sender. | |
100 | Vertex gamma; | |
101 | ||
102 | // The length of the list of vertices in the bicomponent, i.e., | |
103 | // the number of vertex descriptors that will be coming in the | |
104 | // next msg_tree_vertices message. | |
105 | std::size_t bicomp_length; | |
106 | ||
107 | template<typename Archiver> | |
108 | void serialize(Archiver& ar, const unsigned int /*version*/) | |
109 | { | |
110 | ar & edge & gamma & bicomp_length; | |
111 | } | |
112 | }; | |
113 | ||
114 | // Payload for the msg_name message. | |
115 | template<typename EdgeDescriptor> | |
116 | struct name_header | |
117 | { | |
118 | // The edge being communicated and named. | |
119 | EdgeDescriptor edge; | |
120 | ||
121 | // The 0-based name of the component | |
122 | std::size_t name; | |
123 | ||
124 | template<typename Archiver> | |
125 | void serialize(Archiver& ar, const unsigned int /*version*/) | |
126 | { | |
127 | ar & edge & name; | |
128 | } | |
129 | }; | |
130 | ||
131 | /* Computes the branch point between two paths. The branch point is | |
132 | the last position at which both paths are equivalent, beyond | |
133 | which the paths diverge. Both paths must have length > 0 and the | |
134 | initial elements of the paths must be equal. This is guaranteed | |
135 | in Hohberg's algorithm because all paths start at the | |
136 | leader. Returns the value at the branch point. */ | |
137 | template<typename T> | |
138 | T branch_point(const std::vector<T>& p1, const std::vector<T>& p2) | |
139 | { | |
140 | BOOST_ASSERT(!p1.empty()); | |
141 | BOOST_ASSERT(!p2.empty()); | |
142 | BOOST_ASSERT(p1.front() == p2.front()); | |
143 | ||
144 | typedef typename std::vector<T>::const_iterator iterator; | |
145 | ||
146 | iterator mismatch_pos; | |
147 | if (p1.size() <= p2.size()) | |
148 | mismatch_pos = std::mismatch(p1.begin(), p1.end(), p2.begin()).first; | |
149 | else | |
150 | mismatch_pos = std::mismatch(p2.begin(), p2.end(), p1.begin()).first; | |
151 | --mismatch_pos; | |
152 | return *mismatch_pos; | |
153 | } | |
154 | ||
155 | /* Computes the infimum of vertices a and b in the given path. The | |
156 | infimum is the largest element that is on the paths from a to the | |
157 | root and from b to the root. */ | |
158 | template<typename T> | |
159 | T infimum(const std::vector<T>& parent_path, T a, T b) | |
160 | { | |
161 | using std::swap; | |
162 | ||
163 | typedef typename std::vector<T>::const_iterator iterator; | |
164 | iterator first = parent_path.begin(), last = parent_path.end(); | |
165 | ||
166 | #if defined(PBGL_HOHBERG_DEBUG) && PBGL_HOHBERG_DEBUG > 2 | |
167 | std::cerr << "infimum("; | |
168 | for (iterator i = first; i != last; ++i) { | |
169 | if (i != first) std::cerr << ' '; | |
170 | std::cerr << local(*i) << '@' << owner(*i); | |
171 | } | |
172 | std::cerr << ", " << local(a) << '@' << owner(a) << ", " | |
173 | << local(b) << '@' << owner(b) << ") = "; | |
174 | #endif | |
175 | ||
176 | if (a == b) { | |
177 | #if defined(PBGL_HOHBERG_DEBUG) && PBGL_HOHBERG_DEBUG > 2 | |
178 | std::cerr << local(a) << '@' << owner(a) << std::endl; | |
179 | #endif | |
180 | return a; | |
181 | } | |
182 | ||
183 | // Try to find a or b, whichever is closest to the end | |
184 | --last; | |
185 | while (*last != a) { | |
186 | // If we match b, swap the two so we'll be looking for b later. | |
187 | if (*last == b) { swap(a,b); break; } | |
188 | ||
189 | if (last == first) { | |
190 | #if defined(PBGL_HOHBERG_DEBUG) && PBGL_HOHBERG_DEBUG > 2 | |
191 | std::cerr << local(*first) << '@' << owner(*first) << std::endl; | |
192 | #endif | |
193 | return *first; | |
194 | } | |
195 | else --last; | |
196 | } | |
197 | ||
198 | // Try to find b (which may originally have been a) | |
199 | while (*last != b) { | |
200 | if (last == first) { | |
201 | #if defined(PBGL_HOHBERG_DEBUG) && PBGL_HOHBERG_DEBUG > 2 | |
202 | std::cerr << local(*first) << '@' << owner(*first) << std::endl; | |
203 | #endif | |
204 | return *first; | |
205 | } | |
206 | else --last; | |
207 | } | |
208 | ||
209 | #if defined(PBGL_HOHBERG_DEBUG) && PBGL_HOHBERG_DEBUG > 2 | |
210 | std::cerr << local(*last) << '@' << owner(*last) << std::endl; | |
211 | #endif | |
212 | // We've found b; it's the infimum. | |
213 | return *last; | |
214 | } | |
215 | } // end namespace hohberg_detail | |
216 | ||
217 | /* A message that will be stored for each edge by Hohberg's algorithm. */ | |
218 | template<typename Graph> | |
219 | struct hohberg_message | |
220 | { | |
221 | typedef typename graph_traits<Graph>::vertex_descriptor Vertex; | |
222 | typedef typename graph_traits<Graph>::edge_descriptor Edge; | |
223 | ||
224 | // Assign from a path message | |
225 | void assign(const std::vector<Vertex>& path) | |
226 | { | |
227 | gamma = graph_traits<Graph>::null_vertex(); | |
228 | path_or_bicomp = path; | |
229 | } | |
230 | ||
231 | // Assign from a tree message | |
232 | void assign(Vertex gamma, const std::vector<Vertex>& in_same_bicomponent) | |
233 | { | |
234 | this->gamma = gamma; | |
235 | path_or_bicomp = in_same_bicomponent; | |
236 | } | |
237 | ||
238 | bool is_path() const { return gamma == graph_traits<Graph>::null_vertex(); } | |
239 | bool is_tree() const { return gamma != graph_traits<Graph>::null_vertex(); } | |
240 | ||
241 | /// The "gamma" of a tree message, or null_vertex() for a path message | |
242 | Vertex gamma; | |
243 | ||
244 | // Either the path for a path message or the in_same_bicomponent | |
245 | std::vector<Vertex> path_or_bicomp; | |
246 | }; | |
247 | ||
248 | ||
249 | /* An abstraction of a vertex processor in Hohberg's algorithm. The | |
250 | hohberg_vertex_processor class is responsible for processing | |
251 | messages transmitted to it via its edges. */ | |
252 | template<typename Graph> | |
253 | class hohberg_vertex_processor | |
254 | { | |
255 | typedef typename graph_traits<Graph>::vertex_descriptor Vertex; | |
256 | typedef typename graph_traits<Graph>::edge_descriptor Edge; | |
257 | typedef typename graph_traits<Graph>::degree_size_type degree_size_type; | |
258 | typedef typename graph_traits<Graph>::edges_size_type edges_size_type; | |
259 | typedef typename boost::graph::parallel::process_group_type<Graph>::type | |
260 | ProcessGroup; | |
261 | typedef std::vector<Vertex> path_t; | |
262 | typedef typename path_t::iterator path_iterator; | |
263 | ||
264 | public: | |
265 | hohberg_vertex_processor() | |
266 | : phase(1), | |
267 | parent(graph_traits<Graph>::null_vertex()), | |
268 | eta(graph_traits<Graph>::null_vertex()) | |
269 | { | |
270 | } | |
271 | ||
272 | // Called to initialize a leader in the algorithm, which involves | |
273 | // sending out the initial path messages and being ready to receive | |
274 | // them. | |
275 | void initialize_leader(Vertex alpha, const Graph& g); | |
276 | ||
277 | /// Handle a path message on edge e. The path will be destroyed by | |
278 | /// this operation. | |
279 | void | |
280 | operator()(Edge e, path_t& path, const Graph& g); | |
281 | ||
282 | /// Handle a tree message on edge e. in_same_bicomponent will be | |
283 | /// destroyed by this operation. | |
284 | void | |
285 | operator()(Edge e, Vertex gamma, path_t& in_same_bicomponent, | |
286 | const Graph& g); | |
287 | ||
288 | // Handle a name message. | |
289 | void operator()(Edge e, edges_size_type name, const Graph& g); | |
290 | ||
291 | // Retrieve the phase | |
292 | unsigned char get_phase() const { return phase; } | |
293 | ||
294 | // Start the naming phase. The current phase must be 3 (echo), and | |
295 | // the offset contains the offset at which this processor should | |
296 | // begin when labelling its bicomponents. The offset is just a | |
297 | // parallel prefix sum of the number of bicomponents in each | |
298 | // processor that precedes it (globally). | |
299 | void | |
300 | start_naming_phase(Vertex alpha, const Graph& g, edges_size_type offset); | |
301 | ||
302 | /* Determine the number of bicomponents that we will be naming | |
303 | * ourselves. | |
304 | */ | |
305 | edges_size_type num_starting_bicomponents(Vertex alpha, const Graph& g); | |
306 | ||
307 | // Fill in the edge component map with biconnected component | |
308 | // numbers. | |
309 | template<typename ComponentMap> | |
310 | void fill_edge_map(Vertex alpha, const Graph& g, ComponentMap& component); | |
311 | ||
312 | protected: | |
313 | /* Start the echo phase (phase 3) where we propagate information up | |
314 | the tree. */ | |
315 | void echo_phase(Vertex alpha, const Graph& g); | |
316 | ||
317 | /* Retrieve the index of edge in the out-edges list of target(e, g). */ | |
318 | std::size_t get_edge_index(Edge e, const Graph& g); | |
319 | ||
320 | /* Retrieve the index of the edge incidence on v in the out-edges | |
321 | list of vertex u. */ | |
322 | std::size_t get_incident_edge_index(Vertex u, Vertex v, const Graph& g); | |
323 | ||
324 | /* Keeps track of which phase of the algorithm we are in. There are | |
325 | * four phases plus the "finished" phase: | |
326 | * | |
327 | * 1) Building the spanning tree | |
328 | * 2) Discovering cycles | |
329 | * 3) Echoing back up the spanning tree | |
330 | * 4) Labelling biconnected components | |
331 | * 5) Finished | |
332 | */ | |
333 | unsigned char phase; | |
334 | ||
335 | /* The parent of this vertex in the spanning tree. This value will | |
336 | be graph_traits<Graph>::null_vertex() for the leader. */ | |
337 | Vertex parent; | |
338 | ||
339 | /* The farthest ancestor up the tree that resides in the same | |
340 | biconnected component as we do. This information is approximate: | |
341 | we might not know about the actual farthest ancestor, but this is | |
342 | the farthest one we've seen so far. */ | |
343 | Vertex eta; | |
344 | ||
345 | /* The number of edges that have not yet transmitted any messages to | |
346 | us. This starts at the degree of the vertex and decreases as we | |
347 | receive messages. When this counter hits zero, we're done with | |
348 | the second phase of the algorithm. In Hohberg's paper, the actual | |
349 | remaining edge set E is stored with termination when all edges | |
350 | have been removed from E, but we only need to detect termination | |
351 | so the set E need not be explicitly represented. */ | |
352 | degree_size_type num_edges_not_transmitted; | |
353 | ||
354 | /* The path from the root of the spanning tree to this vertex. This | |
355 | vector will always store only the parts of the path leading up to | |
356 | this vertex, and not the vertex itself. Thus, it will be empty | |
357 | for the leader. */ | |
358 | std::vector<Vertex> path_from_root; | |
359 | ||
360 | /* Structure containing all of the extra data we need to keep around | |
361 | PER EDGE. This information can not be contained within a property | |
362 | map, because it can't be shared among vertices without breaking | |
363 | the algorithm. Decreasing the size of this structure will drastically */ | |
364 | struct per_edge_data | |
365 | { | |
366 | hohberg_message<Graph> msg; | |
367 | std::vector<Vertex> M; | |
368 | bool is_tree_edge; | |
369 | degree_size_type partition; | |
370 | }; | |
371 | ||
372 | /* Data for each edge in the graph. This structure will be indexed | |
373 | by the position of the edge in the out_edges() list. */ | |
374 | std::vector<per_edge_data> edge_data; | |
375 | ||
376 | /* The mapping from local partition numbers (0..n-1) to global | |
377 | partition numbers. */ | |
378 | std::vector<edges_size_type> local_to_global_partitions; | |
379 | ||
380 | friend class boost::serialization::access; | |
381 | ||
382 | // We cannot actually serialize a vertex processor, nor would we | |
383 | // want to. However, the fact that we're putting instances into a | |
384 | // distributed_property_map means that we need to have a serialize() | |
385 | // function available. | |
386 | template<typename Archiver> | |
387 | void serialize(Archiver&, const unsigned int /*version*/) | |
388 | { | |
389 | BOOST_ASSERT(false); | |
390 | } | |
391 | }; | |
392 | ||
393 | template<typename Graph> | |
394 | void | |
395 | hohberg_vertex_processor<Graph>::initialize_leader(Vertex alpha, | |
396 | const Graph& g) | |
397 | { | |
398 | using namespace hohberg_detail; | |
399 | ||
400 | ProcessGroup pg = process_group(g); | |
401 | ||
402 | typename property_map<Graph, vertex_owner_t>::const_type | |
403 | owner = get(vertex_owner, g); | |
404 | ||
405 | path_header<Edge> header; | |
406 | header.path_length = 1; | |
407 | BGL_FORALL_OUTEDGES_T(alpha, e, g, Graph) { | |
408 | header.edge = e; | |
409 | send(pg, get(owner, target(e, g)), msg_path_header, header); | |
410 | send(pg, get(owner, target(e, g)), msg_path_vertices, alpha); | |
411 | } | |
412 | ||
413 | num_edges_not_transmitted = degree(alpha, g); | |
414 | edge_data.resize(num_edges_not_transmitted); | |
415 | phase = 2; | |
416 | } | |
417 | ||
418 | template<typename Graph> | |
419 | void | |
420 | hohberg_vertex_processor<Graph>::operator()(Edge e, path_t& path, | |
421 | const Graph& g) | |
422 | { | |
423 | using namespace hohberg_detail; | |
424 | ||
425 | typename property_map<Graph, vertex_owner_t>::const_type | |
426 | owner = get(vertex_owner, g); | |
427 | ||
428 | #ifdef PBGL_HOHBERG_DEBUG | |
429 | // std::cerr << local(source(e, g)) << '@' << owner(source(e, g)) << " -> " | |
430 | // << local(target(e, g)) << '@' << owner(target(e, g)) << ": path("; | |
431 | // for (std::size_t i = 0; i < path.size(); ++i) { | |
432 | // if (i > 0) std::cerr << ' '; | |
433 | // std::cerr << local(path[i]) << '@' << owner(path[i]); | |
434 | // } | |
435 | std::cerr << "), phase = " << (int)phase << std::endl; | |
436 | #endif | |
437 | ||
438 | // Get access to edge-specific data | |
439 | if (edge_data.empty()) | |
440 | edge_data.resize(degree(target(e, g), g)); | |
441 | per_edge_data& edata = edge_data[get_edge_index(e, g)]; | |
442 | ||
443 | // Record the message. We'll need it in phase 3. | |
444 | edata.msg.assign(path); | |
445 | ||
446 | // Note: "alpha" refers to the vertex "processor" receiving the | |
447 | // message. | |
448 | Vertex alpha = target(e, g); | |
449 | ||
450 | switch (phase) { | |
451 | case 1: | |
452 | { | |
453 | num_edges_not_transmitted = degree(alpha, g) - 1; | |
454 | edata.is_tree_edge = true; | |
455 | parent = path.back(); | |
456 | eta = parent; | |
457 | edata.M.clear(); edata.M.push_back(parent); | |
458 | ||
459 | // Broadcast the path from the root to our potential children in | |
460 | // the spanning tree. | |
461 | path.push_back(alpha); | |
462 | path_header<Edge> header; | |
463 | header.path_length = path.size(); | |
464 | ProcessGroup pg = process_group(g); | |
465 | BGL_FORALL_OUTEDGES_T(alpha, oe, g, Graph) { | |
466 | // Skip the tree edge we just received | |
467 | if (target(oe, g) != source(e, g)) { | |
468 | header.edge = oe; | |
469 | send(pg, get(owner, target(oe, g)), msg_path_header, header); | |
470 | send(pg, get(owner, target(oe, g)), msg_path_vertices, &path[0], | |
471 | header.path_length); | |
472 | } | |
473 | } | |
474 | path.pop_back(); | |
475 | ||
476 | // Swap the old path in, to save some extra copying. Nobody | |
477 | path_from_root.swap(path); | |
478 | ||
479 | // Once we have received our place in the spanning tree, move on | |
480 | // to phase 2. | |
481 | phase = 2; | |
482 | ||
483 | // If we only had only edge, skip to phase 3. | |
484 | if (num_edges_not_transmitted == 0) | |
485 | echo_phase(alpha, g); | |
486 | return; | |
487 | } | |
488 | ||
489 | case 2: | |
490 | { | |
491 | --num_edges_not_transmitted; | |
492 | edata.is_tree_edge = false; | |
493 | ||
494 | // Determine if alpha (our vertex) is in the path | |
495 | path_iterator pos = std::find(path.begin(), path.end(), alpha); | |
496 | if (pos != path.end()) { | |
497 | // Case A: There is a cycle alpha beta ... gamma alpha | |
498 | // M(e) <- {beta, gammar} | |
499 | edata.M.clear(); | |
500 | ++pos; | |
501 | // If pos == path.end(), we have a self-loop | |
502 | if (pos != path.end()) { | |
503 | // Add beta | |
504 | edata.M.push_back(*pos); | |
505 | ++pos; | |
506 | } | |
507 | // If pos == path.end(), we have a self-loop or beta == gamma | |
508 | // (parallel edge). Otherwise, add gamma. | |
509 | if (pos != path.end()) edata.M.push_back(path.back()); | |
510 | } else { | |
511 | // Case B: There is a cycle but we haven't seen alpha yet. | |
512 | // M(e) = {parent, path.back()} | |
513 | edata.M.clear(); | |
514 | edata.M.push_back(path.back()); | |
515 | if (parent != path.back()) edata.M.push_back(parent); | |
516 | ||
517 | // eta = inf(eta, bra(pi_t, pi)) | |
518 | eta = infimum(path_from_root, eta, branch_point(path_from_root, path)); | |
519 | } | |
520 | if (num_edges_not_transmitted == 0) | |
521 | echo_phase(alpha, g); | |
522 | break; | |
523 | } | |
524 | ||
525 | default: | |
526 | // std::cerr << "Phase is " << int(phase) << "\n"; | |
527 | BOOST_ASSERT(false); | |
528 | } | |
529 | } | |
530 | ||
531 | template<typename Graph> | |
532 | void | |
533 | hohberg_vertex_processor<Graph>::operator()(Edge e, Vertex gamma, | |
534 | path_t& in_same_bicomponent, | |
535 | const Graph& g) | |
536 | { | |
537 | using namespace hohberg_detail; | |
538 | ||
539 | #ifdef PBGL_HOHBERG_DEBUG | |
540 | std::cerr << local(source(e, g)) << '@' << owner(source(e, g)) << " -> " | |
541 | << local(target(e, g)) << '@' << owner(target(e, g)) << ": tree(" | |
542 | << local(gamma) << '@' << owner(gamma) << ", "; | |
543 | for (std::size_t i = 0; i < in_same_bicomponent.size(); ++i) { | |
544 | if (i > 0) std::cerr << ' '; | |
545 | std::cerr << local(in_same_bicomponent[i]) << '@' | |
546 | << owner(in_same_bicomponent[i]); | |
547 | } | |
548 | std::cerr << ", " << local(source(e, g)) << '@' << owner(source(e, g)) | |
549 | << "), phase = " << (int)phase << std::endl; | |
550 | #endif | |
551 | ||
552 | // Get access to edge-specific data | |
553 | per_edge_data& edata = edge_data[get_edge_index(e, g)]; | |
554 | ||
555 | // Record the message. We'll need it in phase 3. | |
556 | edata.msg.assign(gamma, in_same_bicomponent); | |
557 | ||
558 | // Note: "alpha" refers to the vertex "processor" receiving the | |
559 | // message. | |
560 | Vertex alpha = target(e, g); | |
561 | Vertex beta = source(e, g); | |
562 | ||
563 | switch (phase) { | |
564 | case 2: | |
565 | --num_edges_not_transmitted; | |
566 | edata.is_tree_edge = true; | |
567 | ||
568 | if (gamma == alpha) { | |
569 | // Case C | |
570 | edata.M.swap(in_same_bicomponent); | |
571 | } else { | |
572 | // Case D | |
573 | edata.M.clear(); | |
574 | edata.M.push_back(parent); | |
575 | if (beta != parent) edata.M.push_back(beta); | |
576 | eta = infimum(path_from_root, eta, gamma); | |
577 | } | |
578 | if (num_edges_not_transmitted == 0) | |
579 | echo_phase(alpha, g); | |
580 | break; | |
581 | ||
582 | default: | |
583 | BOOST_ASSERT(false); | |
584 | } | |
585 | } | |
586 | ||
587 | template<typename Graph> | |
588 | void | |
589 | hohberg_vertex_processor<Graph>::operator()(Edge e, edges_size_type name, | |
590 | const Graph& g) | |
591 | { | |
592 | using namespace hohberg_detail; | |
593 | ||
594 | #ifdef PBGL_HOHBERG_DEBUG | |
595 | std::cerr << local(source(e, g)) << '@' << owner(source(e, g)) << " -> " | |
596 | << local(target(e, g)) << '@' << owner(target(e, g)) << ": name(" | |
597 | << name << "), phase = " << (int)phase << std::endl; | |
598 | #endif | |
599 | ||
600 | BOOST_ASSERT(phase == 4); | |
601 | ||
602 | typename property_map<Graph, vertex_owner_t>::const_type | |
603 | owner = get(vertex_owner, g); | |
604 | ||
605 | // Send name messages along the spanning tree edges that are in the | |
606 | // same bicomponent as the edge to our parent. | |
607 | ProcessGroup pg = process_group(g); | |
608 | ||
609 | Vertex alpha = target(e, g); | |
610 | ||
611 | std::size_t idx = 0; | |
612 | BGL_FORALL_OUTEDGES_T(alpha, e, g, Graph) { | |
613 | per_edge_data& edata = edge_data[idx++]; | |
614 | if (edata.is_tree_edge | |
615 | && find(edata.M.begin(), edata.M.end(), parent) != edata.M.end() | |
616 | && target(e, g) != parent) { | |
617 | // Notify our children in the spanning tree of this name | |
618 | name_header<Edge> header; | |
619 | header.edge = e; | |
620 | header.name = name; | |
621 | send(pg, get(owner, target(e, g)), msg_name, header); | |
622 | } else if (target(e, g) == parent) { | |
623 | // Map from local partition numbers to global bicomponent numbers | |
624 | local_to_global_partitions[edata.partition] = name; | |
625 | } | |
626 | } | |
627 | ||
628 | // Final stage | |
629 | phase = 5; | |
630 | } | |
631 | ||
632 | template<typename Graph> | |
633 | typename hohberg_vertex_processor<Graph>::edges_size_type | |
634 | hohberg_vertex_processor<Graph>:: | |
635 | num_starting_bicomponents(Vertex alpha, const Graph& g) | |
636 | { | |
637 | edges_size_type not_mapped = (std::numeric_limits<edges_size_type>::max)(); | |
638 | ||
639 | edges_size_type result = 0; | |
640 | std::size_t idx = 0; | |
641 | BGL_FORALL_OUTEDGES_T(alpha, e, g, Graph) { | |
642 | per_edge_data& edata = edge_data[idx++]; | |
643 | if (edata.is_tree_edge | |
644 | && find(edata.M.begin(), edata.M.end(), parent) == edata.M.end()) { | |
645 | // Map from local partition numbers to global bicomponent numbers | |
646 | if (local_to_global_partitions[edata.partition] == not_mapped) | |
647 | local_to_global_partitions[edata.partition] = result++; | |
648 | } | |
649 | } | |
650 | ||
651 | #ifdef PBGL_HOHBERG_DEBUG | |
652 | std::cerr << local(alpha) << '@' << owner(alpha) << " has " << result | |
653 | << " bicomponents originating at it." << std::endl; | |
654 | #endif | |
655 | ||
656 | return result; | |
657 | } | |
658 | ||
659 | template<typename Graph> | |
660 | template<typename ComponentMap> | |
661 | void | |
662 | hohberg_vertex_processor<Graph>:: | |
663 | fill_edge_map(Vertex alpha, const Graph& g, ComponentMap& component) | |
664 | { | |
665 | std::size_t idx = 0; | |
666 | BGL_FORALL_OUTEDGES_T(alpha, e, g, Graph) { | |
667 | per_edge_data& edata = edge_data[idx++]; | |
668 | local_put(component, e, local_to_global_partitions[edata.partition]); | |
669 | ||
670 | #if defined(PBGL_HOHBERG_DEBUG) && PBGL_HOHBERG_DEBUG > 2 | |
671 | std::cerr << "component(" | |
672 | << local(source(e, g)) << '@' << owner(source(e, g)) << " -> " | |
673 | << local(target(e, g)) << '@' << owner(target(e, g)) << ") = " | |
674 | << local_to_global_partitions[edata.partition] | |
675 | << " (partition = " << edata.partition << " of " | |
676 | << local_to_global_partitions.size() << ")" << std::endl; | |
677 | #endif | |
678 | } | |
679 | } | |
680 | ||
681 | template<typename Graph> | |
682 | void | |
683 | hohberg_vertex_processor<Graph>:: | |
684 | start_naming_phase(Vertex alpha, const Graph& g, edges_size_type offset) | |
685 | { | |
686 | using namespace hohberg_detail; | |
687 | ||
688 | BOOST_ASSERT(phase == 4); | |
689 | ||
690 | typename property_map<Graph, vertex_owner_t>::const_type | |
691 | owner = get(vertex_owner, g); | |
692 | ||
693 | // Send name messages along the spanning tree edges of the | |
694 | // components that we get to number. | |
695 | ProcessGroup pg = process_group(g); | |
696 | ||
697 | bool has_more_children_to_name = false; | |
698 | ||
699 | // Map from local partition numbers to global bicomponent numbers | |
700 | edges_size_type not_mapped = (std::numeric_limits<edges_size_type>::max)(); | |
701 | for (std::size_t i = 0; i < local_to_global_partitions.size(); ++i) { | |
702 | if (local_to_global_partitions[i] != not_mapped) | |
703 | local_to_global_partitions[i] += offset; | |
704 | } | |
705 | ||
706 | std::size_t idx = 0; | |
707 | BGL_FORALL_OUTEDGES_T(alpha, e, g, Graph) { | |
708 | per_edge_data& edata = edge_data[idx++]; | |
709 | if (edata.is_tree_edge | |
710 | && find(edata.M.begin(), edata.M.end(), parent) == edata.M.end()) { | |
711 | // Notify our children in the spanning tree of this new name | |
712 | name_header<Edge> header; | |
713 | header.edge = e; | |
714 | header.name = local_to_global_partitions[edata.partition]; | |
715 | send(pg, get(owner, target(e, g)), msg_name, header); | |
716 | } else if (edata.is_tree_edge) { | |
717 | has_more_children_to_name = true; | |
718 | } | |
719 | #if defined(PBGL_HOHBERG_DEBUG) && PBGL_HOHBERG_DEBUG > 2 | |
720 | std::cerr << "M[" << local(source(e, g)) << '@' << owner(source(e, g)) | |
721 | << " -> " << local(target(e, g)) << '@' << owner(target(e, g)) | |
722 | << "] = "; | |
723 | for (std::size_t i = 0; i < edata.M.size(); ++i) { | |
724 | std::cerr << local(edata.M[i]) << '@' << owner(edata.M[i]) << ' '; | |
725 | } | |
726 | std::cerr << std::endl; | |
727 | #endif | |
728 | } | |
729 | ||
730 | // See if we're done. | |
731 | if (!has_more_children_to_name) | |
732 | // Final stage | |
733 | phase = 5; | |
734 | } | |
735 | ||
736 | template<typename Graph> | |
737 | void | |
738 | hohberg_vertex_processor<Graph>::echo_phase(Vertex alpha, const Graph& g) | |
739 | { | |
740 | using namespace hohberg_detail; | |
741 | ||
742 | typename property_map<Graph, vertex_owner_t>::const_type | |
743 | owner = get(vertex_owner, g); | |
744 | ||
745 | /* We're entering the echo phase. */ | |
746 | phase = 3; | |
747 | ||
748 | if (parent != graph_traits<Graph>::null_vertex()) { | |
749 | Edge edge_to_parent; | |
750 | ||
751 | #if defined(PBGL_HOHBERG_DEBUG) && PBGL_HOHBERG_DEBUG > 1 | |
752 | std::cerr << local(alpha) << '@' << owner(alpha) << " echo: parent = " | |
753 | << local(parent) << '@' << owner(parent) << ", eta = " | |
754 | << local(eta) << '@' << owner(eta) << ", Gamma = "; | |
755 | #endif | |
756 | ||
757 | std::vector<Vertex> bicomp; | |
758 | std::size_t e_index = 0; | |
759 | BGL_FORALL_OUTEDGES_T(alpha, e, g, Graph) { | |
760 | if (target(e, g) == parent && parent == eta) { | |
761 | edge_to_parent = e; | |
762 | if (find(bicomp.begin(), bicomp.end(), alpha) == bicomp.end()) { | |
763 | #if defined(PBGL_HOHBERG_DEBUG) && PBGL_HOHBERG_DEBUG > 1 | |
764 | std::cerr << local(alpha) << '@' << owner(alpha) << ' '; | |
765 | #endif | |
766 | bicomp.push_back(alpha); | |
767 | } | |
768 | } else { | |
769 | if (target(e, g) == parent) edge_to_parent = e; | |
770 | ||
771 | per_edge_data& edata = edge_data[e_index]; | |
772 | ||
773 | if (edata.msg.is_path()) { | |
774 | path_iterator pos = std::find(edata.msg.path_or_bicomp.begin(), | |
775 | edata.msg.path_or_bicomp.end(), | |
776 | eta); | |
777 | if (pos != edata.msg.path_or_bicomp.end()) { | |
778 | ++pos; | |
779 | if (pos != edata.msg.path_or_bicomp.end() | |
780 | && find(bicomp.begin(), bicomp.end(), *pos) == bicomp.end()) { | |
781 | #if defined(PBGL_HOHBERG_DEBUG) && PBGL_HOHBERG_DEBUG > 1 | |
782 | std::cerr << local(*pos) << '@' << owner(*pos) << ' '; | |
783 | #endif | |
784 | bicomp.push_back(*pos); | |
785 | } | |
786 | } | |
787 | } else if (edata.msg.is_tree() && edata.msg.gamma == eta) { | |
788 | for (path_iterator i = edata.msg.path_or_bicomp.begin(); | |
789 | i != edata.msg.path_or_bicomp.end(); ++i) { | |
790 | if (find(bicomp.begin(), bicomp.end(), *i) == bicomp.end()) { | |
791 | #if defined(PBGL_HOHBERG_DEBUG) && PBGL_HOHBERG_DEBUG > 1 | |
792 | std::cerr << local(*i) << '@' << owner(*i) << ' '; | |
793 | #endif | |
794 | bicomp.push_back(*i); | |
795 | } | |
796 | } | |
797 | } | |
798 | } | |
799 | ++e_index; | |
800 | } | |
801 | #ifdef PBGL_HOHBERG_DEBUG | |
802 | std::cerr << std::endl; | |
803 | #endif | |
804 | ||
805 | // Send tree(eta, bicomp) to parent | |
806 | tree_header<Vertex, Edge> header; | |
807 | header.edge = edge_to_parent; | |
808 | header.gamma = eta; | |
809 | header.bicomp_length = bicomp.size(); | |
810 | ProcessGroup pg = process_group(g); | |
811 | send(pg, get(owner, parent), msg_tree_header, header); | |
812 | send(pg, get(owner, parent), msg_tree_vertices, &bicomp[0], | |
813 | header.bicomp_length); | |
814 | } | |
815 | ||
816 | // Compute the partition of edges such that iff two edges e1 and e2 | |
817 | // are in different subsets then M(e1) is disjoint from M(e2). | |
818 | ||
819 | // Start by putting each edge in a different partition | |
820 | std::vector<degree_size_type> parent_vec(edge_data.size()); | |
821 | degree_size_type idx = 0; | |
822 | for (idx = 0; idx < edge_data.size(); ++idx) | |
823 | parent_vec[idx] = idx; | |
824 | ||
825 | // Go through each edge e, performing a union() on the edges | |
826 | // incident on all vertices in M[e]. | |
827 | idx = 0; | |
828 | BGL_FORALL_OUTEDGES_T(alpha, e, g, Graph) { | |
829 | per_edge_data& edata = edge_data[idx++]; | |
830 | ||
831 | // Compute union of vertices in M | |
832 | if (!edata.M.empty()) { | |
833 | degree_size_type e1 = get_incident_edge_index(alpha, edata.M.front(), g); | |
834 | while (parent_vec[e1] != e1) e1 = parent_vec[e1]; | |
835 | ||
836 | for (std::size_t i = 1; i < edata.M.size(); ++i) { | |
837 | degree_size_type e2 = get_incident_edge_index(alpha, edata.M[i], g); | |
838 | while (parent_vec[e2] != e2) e2 = parent_vec[e2]; | |
839 | parent_vec[e2] = e1; | |
840 | } | |
841 | } | |
842 | } | |
843 | ||
844 | edges_size_type not_mapped = (std::numeric_limits<edges_size_type>::max)(); | |
845 | ||
846 | // Determine the number of partitions | |
847 | for (idx = 0; idx < parent_vec.size(); ++idx) { | |
848 | if (parent_vec[idx] == idx) { | |
849 | edge_data[idx].partition = local_to_global_partitions.size(); | |
850 | local_to_global_partitions.push_back(not_mapped); | |
851 | } | |
852 | } | |
853 | ||
854 | // Assign partition numbers to each edge | |
855 | for (idx = 0; idx < parent_vec.size(); ++idx) { | |
856 | degree_size_type rep = parent_vec[idx]; | |
857 | while (rep != parent_vec[rep]) rep = parent_vec[rep]; | |
858 | edge_data[idx].partition = edge_data[rep].partition; | |
859 | } | |
860 | ||
861 | // Enter the naming phase (but don't send anything yet). | |
862 | phase = 4; | |
863 | } | |
864 | ||
865 | template<typename Graph> | |
866 | std::size_t | |
867 | hohberg_vertex_processor<Graph>::get_edge_index(Edge e, const Graph& g) | |
868 | { | |
869 | std::size_t result = 0; | |
870 | BGL_FORALL_OUTEDGES_T(target(e, g), oe, g, Graph) { | |
871 | if (source(e, g) == target(oe, g)) return result; | |
872 | ++result; | |
873 | } | |
874 | BOOST_ASSERT(false); | |
875 | } | |
876 | ||
877 | template<typename Graph> | |
878 | std::size_t | |
879 | hohberg_vertex_processor<Graph>::get_incident_edge_index(Vertex u, Vertex v, | |
880 | const Graph& g) | |
881 | { | |
882 | std::size_t result = 0; | |
883 | BGL_FORALL_OUTEDGES_T(u, e, g, Graph) { | |
884 | if (target(e, g) == v) return result; | |
885 | ++result; | |
886 | } | |
887 | BOOST_ASSERT(false); | |
888 | } | |
889 | ||
890 | template<typename Graph, typename InputIterator, typename ComponentMap, | |
891 | typename VertexProcessorMap> | |
892 | typename graph_traits<Graph>::edges_size_type | |
893 | hohberg_biconnected_components | |
894 | (const Graph& g, | |
895 | ComponentMap component, | |
896 | InputIterator first, InputIterator last, | |
897 | VertexProcessorMap vertex_processor) | |
898 | { | |
899 | using namespace boost::graph::parallel; | |
900 | using namespace hohberg_detail; | |
901 | using boost::parallel::all_reduce; | |
902 | ||
903 | typename property_map<Graph, vertex_owner_t>::const_type | |
904 | owner = get(vertex_owner, g); | |
905 | ||
906 | // The graph must be undirected | |
907 | BOOST_STATIC_ASSERT( | |
908 | (is_convertible<typename graph_traits<Graph>::directed_category, | |
909 | undirected_tag>::value)); | |
910 | ||
911 | // The graph must model Incidence Graph | |
912 | BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<Graph> )); | |
913 | ||
914 | typedef typename graph_traits<Graph>::edges_size_type edges_size_type; | |
915 | typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; | |
916 | typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor; | |
917 | ||
918 | // Retrieve the process group we will use for communication | |
919 | typedef typename process_group_type<Graph>::type process_group_type; | |
920 | process_group_type pg = process_group(g); | |
921 | ||
922 | // Keeps track of the edges that we know to be tree edges. | |
923 | std::vector<edge_descriptor> tree_edges; | |
924 | ||
925 | // The leaders send out a path message to initiate the algorithm | |
926 | while (first != last) { | |
927 | vertex_descriptor leader = *first; | |
928 | if (process_id(pg) == get(owner, leader)) | |
929 | vertex_processor[leader].initialize_leader(leader, g); | |
930 | ++first; | |
931 | } | |
932 | synchronize(pg); | |
933 | ||
934 | // Will hold the number of bicomponents in the graph. | |
935 | edges_size_type num_bicomponents = 0; | |
936 | ||
937 | // Keep track of the path length that we should expect, based on the | |
938 | // level in the breadth-first search tree. At present, this is only | |
939 | // used as a sanity check. TBD: This could be used to decrease the | |
940 | // amount of communication required per-edge (by about 4 bytes). | |
941 | std::size_t path_length = 1; | |
942 | ||
943 | typedef std::vector<vertex_descriptor> path_t; | |
944 | ||
945 | unsigned char minimum_phase = 5; | |
946 | do { | |
947 | while (optional<std::pair<int, int> > msg = probe(pg)) { | |
948 | switch (msg->second) { | |
949 | case msg_path_header: | |
950 | { | |
951 | // Receive the path header | |
952 | path_header<edge_descriptor> header; | |
953 | receive(pg, msg->first, msg->second, header); | |
954 | BOOST_ASSERT(path_length == header.path_length); | |
955 | ||
956 | // Receive the path itself | |
957 | path_t path(path_length); | |
958 | receive(pg, msg->first, msg_path_vertices, &path[0], path_length); | |
959 | ||
960 | edge_descriptor e = header.edge; | |
961 | vertex_processor[target(e, g)](e, path, g); | |
962 | } | |
963 | break; | |
964 | ||
965 | case msg_path_vertices: | |
966 | // Should be handled in msg_path_header case, unless we're going | |
967 | // stateless. | |
968 | BOOST_ASSERT(false); | |
969 | break; | |
970 | ||
971 | case msg_tree_header: | |
972 | { | |
973 | // Receive the tree header | |
974 | tree_header<vertex_descriptor, edge_descriptor> header; | |
975 | receive(pg, msg->first, msg->second, header); | |
976 | ||
977 | // Receive the tree itself | |
978 | path_t in_same_bicomponent(header.bicomp_length); | |
979 | receive(pg, msg->first, msg_tree_vertices, &in_same_bicomponent[0], | |
980 | header.bicomp_length); | |
981 | ||
982 | edge_descriptor e = header.edge; | |
983 | vertex_processor[target(e, g)](e, header.gamma, in_same_bicomponent, | |
984 | g); | |
985 | } | |
986 | break; | |
987 | ||
988 | case msg_tree_vertices: | |
989 | // Should be handled in msg_tree_header case, unless we're | |
990 | // going stateless. | |
991 | BOOST_ASSERT(false); | |
992 | break; | |
993 | ||
994 | case msg_name: | |
995 | { | |
996 | name_header<edge_descriptor> header; | |
997 | receive(pg, msg->first, msg->second, header); | |
998 | edge_descriptor e = header.edge; | |
999 | vertex_processor[target(e, g)](e, header.name, g); | |
1000 | } | |
1001 | break; | |
1002 | ||
1003 | default: | |
1004 | BOOST_ASSERT(false); | |
1005 | } | |
1006 | } | |
1007 | ++path_length; | |
1008 | ||
1009 | // Compute minimum phase locally | |
1010 | minimum_phase = 5; | |
1011 | unsigned char maximum_phase = 1; | |
1012 | BGL_FORALL_VERTICES_T(v, g, Graph) { | |
1013 | minimum_phase = (std::min)(minimum_phase, vertex_processor[v].get_phase()); | |
1014 | maximum_phase = (std::max)(maximum_phase, vertex_processor[v].get_phase()); | |
1015 | } | |
1016 | ||
1017 | #ifdef PBGL_HOHBERG_DEBUG | |
1018 | if (process_id(pg) == 0) | |
1019 | std::cerr << "<---------End of stage------------->" << std::endl; | |
1020 | #endif | |
1021 | // Compute minimum phase globally | |
1022 | minimum_phase = all_reduce(pg, minimum_phase, boost::mpi::minimum<char>()); | |
1023 | ||
1024 | #ifdef PBGL_HOHBERG_DEBUG | |
1025 | if (process_id(pg) == 0) | |
1026 | std::cerr << "Minimum phase = " << (int)minimum_phase << std::endl; | |
1027 | #endif | |
1028 | ||
1029 | if (minimum_phase == 4 | |
1030 | && all_reduce(pg, maximum_phase, boost::mpi::maximum<char>()) == 4) { | |
1031 | ||
1032 | #ifdef PBGL_HOHBERG_DEBUG | |
1033 | if (process_id(pg) == 0) | |
1034 | std::cerr << "<---------Naming phase------------->" << std::endl; | |
1035 | #endif | |
1036 | // Compute the biconnected component number offsets for each | |
1037 | // vertex. | |
1038 | std::vector<edges_size_type> local_offsets; | |
1039 | local_offsets.reserve(num_vertices(g)); | |
1040 | edges_size_type num_local_bicomponents = 0; | |
1041 | BGL_FORALL_VERTICES_T(v, g, Graph) { | |
1042 | local_offsets.push_back(num_local_bicomponents); | |
1043 | num_local_bicomponents += | |
1044 | vertex_processor[v].num_starting_bicomponents(v, g); | |
1045 | } | |
1046 | ||
1047 | synchronize(pg); | |
1048 | ||
1049 | // Find our the number of bicomponent names that will originate | |
1050 | // from each process. This tells us how many bicomponents are in | |
1051 | // the entire graph and what our global offset is for computing | |
1052 | // our own biconnected component names. | |
1053 | std::vector<edges_size_type> all_bicomponents(num_processes(pg)); | |
1054 | all_gather(pg, &num_local_bicomponents, &num_local_bicomponents + 1, | |
1055 | all_bicomponents); | |
1056 | num_bicomponents = 0; | |
1057 | edges_size_type my_global_offset = 0; | |
1058 | for (std::size_t i = 0; i < all_bicomponents.size(); ++i) { | |
1059 | if (i == (std::size_t)process_id(pg)) | |
1060 | my_global_offset = num_bicomponents; | |
1061 | num_bicomponents += all_bicomponents[i]; | |
1062 | } | |
1063 | ||
1064 | std::size_t index = 0; | |
1065 | BGL_FORALL_VERTICES_T(v, g, Graph) { | |
1066 | edges_size_type offset = my_global_offset + local_offsets[index++]; | |
1067 | vertex_processor[v].start_naming_phase(v, g, offset); | |
1068 | } | |
1069 | } | |
1070 | ||
1071 | synchronize(pg); | |
1072 | } while (minimum_phase < 5); | |
1073 | ||
1074 | // Number the edges appropriately. | |
1075 | BGL_FORALL_VERTICES_T(v, g, Graph) | |
1076 | vertex_processor[v].fill_edge_map(v, g, component); | |
1077 | ||
1078 | return num_bicomponents; | |
1079 | } | |
1080 | ||
1081 | template<typename Graph, typename ComponentMap, typename InputIterator> | |
1082 | typename graph_traits<Graph>::edges_size_type | |
1083 | hohberg_biconnected_components | |
1084 | (const Graph& g, ComponentMap component, | |
1085 | InputIterator first, InputIterator last) | |
1086 | ||
1087 | { | |
1088 | std::vector<hohberg_vertex_processor<Graph> > | |
1089 | vertex_processors(num_vertices(g)); | |
1090 | return hohberg_biconnected_components | |
1091 | (g, component, first, last, | |
1092 | make_iterator_property_map(vertex_processors.begin(), | |
1093 | get(vertex_index, g))); | |
1094 | } | |
1095 | ||
1096 | template<typename Graph, typename ComponentMap, typename ParentMap> | |
1097 | typename graph_traits<Graph>::edges_size_type | |
1098 | hohberg_biconnected_components(const Graph& g, ComponentMap component, | |
1099 | ParentMap parent) | |
1100 | { | |
1101 | // We need the connected components of the graph, but we don't care | |
1102 | // about component numbers. | |
1103 | connected_components(g, dummy_property_map(), parent); | |
1104 | ||
1105 | // Each root in the parent map is a leader | |
1106 | typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; | |
1107 | std::vector<vertex_descriptor> leaders; | |
1108 | BGL_FORALL_VERTICES_T(v, g, Graph) | |
1109 | if (get(parent, v) == v) leaders.push_back(v); | |
1110 | ||
1111 | return hohberg_biconnected_components(g, component, | |
1112 | leaders.begin(), leaders.end()); | |
1113 | } | |
1114 | ||
1115 | template<typename Graph, typename ComponentMap> | |
1116 | typename graph_traits<Graph>::edges_size_type | |
1117 | hohberg_biconnected_components(const Graph& g, ComponentMap component) | |
1118 | { | |
1119 | typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; | |
1120 | std::vector<vertex_descriptor> parents(num_vertices(g)); | |
1121 | return hohberg_biconnected_components | |
1122 | (g, component, make_iterator_property_map(parents.begin(), | |
1123 | get(vertex_index, g))); | |
1124 | } | |
1125 | ||
1126 | } } } // end namespace boost::graph::distributed | |
1127 | ||
1128 | #endif // BOOST_GRAPH_DISTRIBUTED_HOHBERG_BICONNECTED_COMPONENTS_HPP |