]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | .. Copyright (C) 2004-2008 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 | |
8 | =========================== | |
9 | ||
10 | :: | |
11 | ||
12 | template<typename Graph, typename ComponentMap> | |
13 | inline typename property_traits<ComponentMap>::value_type | |
14 | strong_components( const Graph& g, ComponentMap c); | |
15 | ||
16 | namespace graph { | |
17 | template<typename Graph, typename VertexComponentMap> | |
18 | void | |
19 | fleischer_hendrickson_pinar_strong_components(const Graph& g, VertexComponentMap r); | |
20 | ||
21 | template<typename Graph, typename ReverseGraph, | |
22 | typename ComponentMap, typename IsoMapFR, typename IsoMapRF> | |
23 | inline typename property_traits<ComponentMap>::value_type | |
24 | fleischer_hendrickson_pinar_strong_components(const Graph& g, | |
25 | ComponentMap c, | |
26 | const ReverseGraph& gr, | |
27 | IsoMapFR fr, IsoMapRF rf); | |
28 | } | |
29 | ||
30 | The ``strong_components()`` function computes the strongly connected | |
31 | components of a directed graph. The distributed strong components | |
32 | algorithm uses the `sequential strong components`_ algorithm to | |
33 | identify components local to a processor. The distributed portion of | |
34 | the algorithm is built on the `distributed breadth first search`_ | |
35 | algorithm and is based on the work of Fleischer, Hendrickson, and | |
36 | Pinar [FHP00]_. The interface is a superset of the interface to the | |
37 | BGL `sequential strong components`_ algorithm. The number of | |
38 | strongly-connected components in the graph is returned to all | |
39 | processes. | |
40 | ||
41 | The distributed strong components algorithm works on both ``directed`` | |
42 | and ``bidirectional`` graphs. In the bidirectional case, a reverse | |
43 | graph adapter is used to produce the required reverse graph. In | |
44 | the directed case, a separate graph is constructed in which all the | |
45 | edges are reversed. | |
46 | ||
47 | .. contents:: | |
48 | ||
49 | Where Defined | |
50 | ------------- | |
51 | <``boost/graph/distributed/strong_components.hpp``> | |
52 | ||
53 | also accessible from | |
54 | ||
55 | <``boost/graph/strong_components.hpp``> | |
56 | ||
57 | Parameters | |
58 | ---------- | |
59 | ||
60 | IN: ``const Graph& g`` | |
61 | The graph type must be a model of `Distributed Graph`_. The graph | |
62 | type must also model the `Incidence Graph`_ and be directed. | |
63 | ||
64 | OUT: ``ComponentMap c`` | |
65 | The algorithm computes how many strongly connected components are in the | |
66 | graph, and assigns each component an integer label. The algorithm | |
67 | then records to which component each vertex in the graph belongs by | |
68 | recording the component number in the component property map. The | |
69 | ``ComponentMap`` type must be a `Distributed Property Map`_. The | |
70 | value type must be the ``vertices_size_type`` of the graph. The key | |
71 | type must be the graph's vertex descriptor type. | |
72 | ||
73 | UTIL: ``VertexComponentMap r`` | |
74 | The algorithm computes a mapping from each vertex to the | |
75 | representative of the strong component, stored in this property map. | |
76 | The ``VertexComponentMap`` type must be a `Distributed Property Map`_. | |
77 | The value and key types must be the vertex descriptor of the graph. | |
78 | ||
79 | IN: ``const ReverseGraph& gr`` | |
80 | The reverse (or transpose) graph of ``g``, such that for each | |
81 | directed edge *(u, v)* in ``g`` there exists a directed edge | |
82 | *(fr(v), fr(u))* in ``gr`` and for each edge *(v', u')* in *gr* | |
83 | there exists an edge *(rf(u'), rf(v'))* in ``g``. The functions | |
84 | *fr* and *rf* map from vertices in the graph to the reverse graph | |
85 | and vice-verse, and are represented as property map arguments. The | |
86 | concept requirements on this graph type are equivalent to those on | |
87 | the ``Graph`` type, but the types need not be the same. | |
88 | ||
89 | **Default**: Either a ``reverse_graph`` adaptor over the original | |
90 | graph (if the graph type is bidirectional, i.e., models the | |
91 | `Bidirectional Graph`_ concept) or a `distributed adjacency list`_ | |
92 | constructed from the input graph. | |
93 | ||
94 | IN: ``IsoMapFR fr`` | |
95 | A property map that maps from vertices in the input graph ``g`` to | |
96 | vertices in the reversed graph ``gr``. The type ``IsoMapFR`` must | |
97 | model the `Readable Property Map`_ concept and have the graph's | |
98 | vertex descriptor as its key type and the reverse graph's vertex | |
99 | descriptor as its value type. | |
100 | ||
101 | **Default**: An identity property map (if the graph type is | |
102 | bidirectional) or a distributed ``iterator_property_map`` (if the | |
103 | graph type is directed). | |
104 | ||
105 | IN: ``IsoMapRF rf`` | |
106 | A property map that maps from vertices in the reversed graph ``gr`` | |
107 | to vertices in the input graph ``g``. The type ``IsoMapRF`` must | |
108 | model the `Readable Property Map`_ concept and have the reverse | |
109 | graph's vertex descriptor as its key type and the graph's vertex | |
110 | descriptor as its value type. | |
111 | ||
112 | **Default**: An identity property map (if the graph type is | |
113 | bidirectional) or a distributed ``iterator_property_map`` (if the | |
114 | graph type is directed). | |
115 | ||
116 | Complexity | |
117 | ---------- | |
118 | ||
119 | The local phase of the algorithm is *O(V + E)*. The parallel phase of | |
120 | the algorithm requires at most *O(V)* supersteps each containing two | |
121 | breadth first searches which are *O(V + E)* each. | |
122 | ||
123 | ||
124 | Algorithm Description | |
125 | --------------------- | |
126 | ||
127 | Prior to executing the sequential phase of the algorithm, each process | |
128 | identifies any completely local strong components which it labels and | |
129 | removes from the vertex set considered in the parallel phase of the | |
130 | algorithm. | |
131 | ||
132 | The parallel phase of the distributed strong components algorithm | |
133 | consists of series of supersteps. Each superstep starts with one | |
134 | or more vertex sets which are guaranteed to completely contain | |
135 | any remaining strong components. A `distributed breadth first search`_ | |
136 | is performed starting from the first vertex in each vertex set. | |
137 | All of these breadth first searches are performed in parallel by having | |
138 | each processor call ``breadth_first_search()`` with a different starting | |
139 | vertex, and if necessary inserting additional vertices into the | |
140 | ``distributed queue`` used for breadth first search before invoking | |
141 | the algorithm. A second `distributed breadth first search`_ is | |
142 | performed on the reverse graph in the same fashion. For each initial | |
143 | vertex set, the successor set (the vertices reached in the forward | |
144 | breadth first search), and the predecessor set (the vertices reached | |
145 | in the backward breadth first search) is computed. The intersection | |
146 | of the predecessor and successor sets form a strongly connected | |
147 | component which is labeled as such. The remaining vertices in the | |
148 | initial vertex set are partitioned into three subsets each guaranteed | |
149 | to completely contain any remaining strong components. These three sets | |
150 | are the vertices in the predecessor set not contained in the identified | |
151 | strongly connected component, the vertices in the successor set not | |
152 | in the strongly connected component, and the remaing vertices in the | |
153 | initial vertex set not in the predecessor or successor sets. Once | |
154 | new vertex sets are identified, the algorithm begins a new superstep. | |
155 | The algorithm halts when no vertices remain. | |
156 | ||
157 | To boost performance in sparse graphs when identifying small components, | |
158 | when less than a given portion of the initial number of vertices | |
159 | remain in active vertex sets, a filtered graph adapter is used | |
160 | to limit the graph seen by the breadth first search algorithm to the | |
161 | active vertices. | |
162 | ||
163 | Bibliography | |
164 | ------------ | |
165 | ||
166 | .. [FHP00] Lisa Fleischer, Bruce Hendrickson, and Ali Pinar. On | |
167 | Identifying Strongly Connected Components in Parallel. In Parallel and | |
168 | Distributed Processing (IPDPS), volume 1800 of Lecture Notes in | |
169 | Computer Science, pages 505--511, 2000. Springer. | |
170 | ||
171 | ----------------------------------------------------------------------------- | |
172 | ||
173 | Copyright (C) 2004, 2005 The Trustees of Indiana University. | |
174 | ||
175 | Authors: Nick Edmonds, Douglas Gregor, and Andrew Lumsdaine | |
176 | ||
177 | .. |Logo| image:: pbgl-logo.png | |
178 | :align: middle | |
179 | :alt: Parallel BGL | |
180 | :target: http://www.osl.iu.edu/research/pbgl | |
181 | ||
182 | .. _Sequential strong components: http://www.boost.org/libs/graph/doc/strong_components.html | |
183 | .. _Distributed breadth first search: breadth_first_search.html | |
184 | .. _Distributed Graph: DistributedGraph.html | |
185 | .. _Distributed Property Map: distributed_property_map.html | |
186 | .. _Incidence Graph: http://www.boost.org/libs/graph/doc/IncidenceGraph.html | |
187 | .. _Bidirectional Graph: http://www.boost.org/libs/graph/doc/BidirectionalGraph.html | |
188 | .. _distributed adjacency list: distributed_adjacency_list.html | |
189 | .. _Readable Property Map: http://www.boost.org/libs/property_map/ReadablePropertyMap.html | |
190 | .. |