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