]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | .. Copyright (C) 2004-2009 The Trustees of Indiana University. |
2 | Use, modification and distribution is subject to the Boost Software | |
3 | License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
4 | http://www.boost.org/LICENSE_1_0.txt) | |
5 | ||
6 | =========================================== | |
7 | |Logo| Connected Components Parallel Search | |
8 | =========================================== | |
9 | ||
10 | :: | |
11 | ||
12 | namespace graph { namespace distributed { | |
13 | template<typename Graph, typename ComponentMap> | |
14 | typename property_traits<ComponentMap>::value_type | |
15 | connected_components_ps(const Graph& g, ComponentMap c) | |
16 | } } | |
17 | ||
18 | The ``connected_components_ps()`` function computes the connected | |
19 | components of a graph by performing a breadth-first search from | |
20 | several sources in parallel while recording and eventually resolving | |
21 | the collisions. | |
22 | ||
23 | .. contents:: | |
24 | ||
25 | Where Defined | |
26 | ------------- | |
27 | <``boost/graph/distributed/connected_components_parallel_search.hpp``> | |
28 | ||
29 | Parameters | |
30 | ---------- | |
31 | ||
32 | IN: ``const Graph& g`` | |
33 | The graph type must be a model of `Distributed Graph`_. The graph | |
34 | type must also model the `Incidence Graph`_ and be directed. | |
35 | ||
36 | OUT: ``ComponentMap c`` | |
37 | The algorithm computes how many connected components are in the | |
38 | graph, and assigns each component an integer label. The algorithm | |
39 | then records to which component each vertex in the graph belongs by | |
40 | recording the component number in the component property map. The | |
41 | ``ComponentMap`` type must be a `Distributed Property Map`_. The | |
42 | value type must be the ``vertices_size_type`` of the graph. The key | |
43 | type must be the graph's vertex descriptor type. | |
44 | ||
45 | Complexity | |
46 | ---------- | |
47 | ||
48 | *O(PN^2 + VNP)* work, in *O(N + V)* time, where N is the | |
49 | number of mappings and V is the number of local vertices. | |
50 | ||
51 | Algorithm Description | |
52 | --------------------- | |
53 | ||
54 | Every *N* th nodes starts a parallel search from the first vertex in | |
55 | their local vertex list during the first superstep (the other nodes | |
56 | remain idle during the first superstep to reduce the number of | |
57 | conflicts in numbering the components). At each superstep, all new | |
58 | component mappings from remote nodes are handled. If there is no work | |
59 | from remote updates, a new vertex is removed from the local list and | |
60 | added to the work queue. | |
61 | ||
62 | Components are allocated from the ``component_value_allocator`` | |
63 | object, which ensures that a given component number is unique in the | |
64 | system, currently by using the rank and number of processes to stride | |
65 | allocations. | |
66 | ||
67 | When two components are discovered to actually be the same component, | |
68 | a collision is recorded. The lower component number is prefered in | |
69 | the resolution, so component numbering resolution is consistent. | |
70 | After the search has exhausted all vertices in the graph, the mapping | |
71 | is shared with all processes and they independently resolve the | |
72 | comonent mapping. This phase can likely be significantly sped up if a | |
73 | clever algorithm for the reduction can be found. | |
74 | ||
75 | ----------------------------------------------------------------------------- | |
76 | ||
77 | Copyright (C) 2009 The Trustees of Indiana University. | |
78 | ||
79 | Authors: Brian Barrett, Douglas Gregor, and Andrew Lumsdaine | |
80 | ||
81 | .. |Logo| image:: pbgl-logo.png | |
82 | :align: middle | |
83 | :alt: Parallel BGL | |
84 | :target: http://www.osl.iu.edu/research/pbgl | |
85 | ||
86 | .. _Distributed Graph: DistributedGraph.html | |
87 | .. _Distributed Property Map: distributed_property_map.html | |
88 | .. _Incidence Graph: http://www.boost.org/libs/graph/doc/IncidenceGraph.html |