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
191
192
193
194
195
196
197
198
199
200
201
|
<HTML>
<!--
-- Copyright (c) Jeremy Siek 2000
--
-- Distributed under 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)
-->
<Head>
<Title>Boost Graph Library: Strongly Connected Components</Title>
<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
ALINK="#ff0000">
<IMG SRC="../../../boost.png"
ALT="C++ Boost" width="277" height="86">
<BR Clear>
<H1>
<A NAME="sec:connected-components"></A><A NAME="sec:strongly-connected-components"></A>
<img src="figs/python.gif" alt="(Python)"/>
<TT>strong_components</TT>
</H1>
<PRE>
<i>// named parameter version</i>
template <class Graph, class ComponentMap, class P, class T, class R>
typename property_traits<ComponentMap>::value_type
strong_components(Graph& g, ComponentMap comp,
const bgl_named_params<P, T, R>& params = <i>all defaults</i>)
<i>// there is not a non-named parameter version of this function</i>
</PRE>
<P>
The <TT>strong_components()</TT> functions compute the strongly
connected components of a directed graph using Tarjan's algorithm
based on DFS [<A
HREF="bibliography.html#tarjan72:dfs_and_linear_algo">41</A>].
</p>
<P>
The output of the algorithm is recorded in the component property
map <TT>comp</TT>, which will contain numbers giving the component ID
assigned to each vertex. The number of components is the return value
of the function.
</p>
<H3>Where Defined</H3>
<P>
<a href="../../../boost/graph/strong_components.hpp"><TT>boost/graph/strong_components.hpp</TT></a>
<P>
<H3>Definitions</H3>
<P>
A <a name="def:strongly-connected-component"><b><I>strongly connected
component</I></b></a> of a directed graph <i>G=(V,E)</i> is a maximal
set of vertices <i>U</i> which is in <i>V</i> such that for every pair
of vertices <i>u</i> and <i>v</i> in <i>U</i>, we have both a path
from <i>u</i> to <i>v</i> and path from <i>v</i> to <i>u</i>. That is
to say that <i>u</i> and <i>v</i> are reachable from each other.
<P>
<h3>Parameters</h3>
IN: <tt>const Graph& g</tt>
<blockquote>
A directed graph. The graph type must be a model of <a
href="VertexListGraph.html">Vertex List Graph</a> and <a
href="IncidenceGraph.html">Incidence Graph</a>.<br>
<b>Python</b>: The parameter is named <tt>graph</tt>.
</blockquote>
OUT: <tt>ComponentMap c</tt>
<blockquote>
The algorithm computes how many connected components are in the graph,
and assigning each component an integer label. The algorithm then
records which component each vertex in the graph belongs to by
recording the component number in the component property map. The
<tt>ComponentMap</tt> type must be a model of <a
href="../../property_map/WritablePropertyMap.html">Writable Property
Map</a>. The value type shouch be an integer type, preferably the same
as the <tt>vertices_size_type</tt> of the graph. The key type must be
the graph's vertex descriptor type.<br>
<b>Python</b>: Must be an <tt>vertex_int_map</tt> for the graph.<br>
<b>Python default</b>: <tt>graph.get_vertex_int_map("component")</tt>
</blockquote>
<h3>Named Parameters</h3>
UTIL: <tt>root_map(RootMap r_map)</tt>
<blockquote>
This is used by the algorithm to record the candidate root vertex for
each vertex. By the end of the algorithm, there is a single root vertex
for each component and <tt>get(r_map, v)</tt> returns the root
vertex for whichever component vertex <tt>v</tt> is a member.
The <TT>RootMap</TT> must be a <a
href="../../property_map/ReadWritePropertyMap.html">
Read/Write Property Map</a>, where the key type and the value type are
the vertex descriptor type of the graph.<br>
<b>Default:</b> an <a
href="../../property_map/iterator_property_map.html">
<tt>iterator_property_map</tt></a> created from a
<tt>std::vector</tt> of vertex descriptors of size
<tt>num_vertices(g)</tt> and using the <tt>i_map</tt> for the index
map.<br>
<b>Python</b>: Unsupported parameter.
</blockquote>
UTIL: <tt>discover_time_map(TimeMap t_map)</tt>
<blockquote>
This is used by the algorithm to keep track of the DFS ordering
of the vertices. The <TT>TimeMap</TT> must be a model
of <a href="../../property_map/ReadWritePropertyMap.html"> Read/Write
Property Map</a> and its value type must be an integer type. The key
type must be the vertex descriptor type of the graph.<br>
<b>Default:</b>an <a
href="../../property_map/iterator_property_map.html">
<tt>iterator_property_map</tt></a> created from a
<tt>std::vector</tt> of integers with size
<tt>num_vertices(g)</tt> and using the <tt>i_map</tt> for the index
map.<br>
<b>Python</b>: Unsupported parameter.
</blockquote>
UTIL: <tt>color_map(ColorMap c_map)</tt>
<blockquote>
This is used by the algorithm to keep track of its progress through
the graph. The type <tt>ColorMap</tt> must be a model of <a
href="../../property_map/ReadWritePropertyMap.html">Read/Write
Property Map</a> and its key type must be the graph's vertex
descriptor type and the value type of the color map must model
<a href="./ColorValue.html">ColorValue</a>.<br>
<b>Default:</b> an <a
href="../../property_map/iterator_property_map.html">
<tt>iterator_property_map</tt></a> created from a
<tt>std::vector</tt> of <tt>default_color_type</tt> of size
<tt>num_vertices(g)</tt> and using the <tt>i_map</tt> for the index
map.<br>
<b>Python</b>: Unsupported parameter.
</blockquote>
IN: <tt>vertex_index_map(VertexIndexMap i_map)</tt>
<blockquote>
This maps each vertex to an integer in the range <tt>[0,
num_vertices(g))</tt>. This parameter is only necessary when a
default is used for one of the other named parameters. The type
<tt>VertexIndexMap</tt> must be a model of <a
href="../../property_map/ReadablePropertyMap.html">Readable Property
Map</a>. The value type of the map must be an integer type. The
vertex descriptor type of the graph needs to be usable as the key
type of the map.<br>
<b>Default:</b> <tt>get(vertex_index, g)</tt>
Note: if you use this default, make sure your graph has
an internal <tt>vertex_index</tt> property. For example,
<tt>adjacenty_list</tt> with <tt>VertexList=listS</tt> does
not have an internal <tt>vertex_index</tt> property.
<br>
<b>Python</b>: Unsupported parameter.
</blockquote>
<H3>Complexity</H3>
<P>
The time complexity for the strongly connected components algorithm is
<i>O(V + E)</i>.
<P>
<h3>See Also</h3>
<a href="./connected_components.html"><tt>connected_components()</tt></a>
and <a href="./incremental_components.html"><tt>incremental_components()</tt></a>
<H3>Example</H3>
<P>
See <a
href="../example/strong_components.cpp"><tt>examples/strong_components.cpp</tt></a>.
<br>
<HR>
<TABLE>
<TR valign=top>
<TD nowrap>Copyright © 2000-2001</TD><TD>
<A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>, Indiana University (<A HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)
</TD></TR></TABLE>
</BODY>
</HTML>
|
