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
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
|
<HTML>
<!--
-- Copyright 2001-2004 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)
--
-- Authors: Douglas Gregor
-- Jeremy Siek
-- Andrew Lumsdaine
-->
<Head>
<Title>Boost Graph Library: Biconnected Components and Articulation Points</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>
<TT>
<img src="figs/python.gif" alt="(Python)"/>
<A NAME="sec:biconnected-components">biconnected_components
</A>
</TT>
and
<tt>articulation_points</tt>
</h1>
<PRE>
<i>// named parameter version</i>
template <typename Graph, typename ComponentMap, typename OutputIterator,
typename P, typename T, typename R>
std::pair<std::size_t, OutputIterator>
biconnected_components(const Graph& g, ComponentMap comp, OutputIterator out,
const bgl_named_params<P, T, R>& params)
template <typename Graph, typename ComponentMap,
typename P, typename T, typename R>
std::size_t
biconnected_components(const Graph& g, ComponentMap comp,
const bgl_named_params<P, T, R>& params)
template <typename Graph, typename OutputIterator,
typename P, typename T, typename R>
OutputIterator articulation_points(const Graph& g, OutputIterator out,
const bgl_named_params<P, T, R>& params)
<i>// non-named parameter version</i>
template <typename Graph, typename ComponentMap, typename OutputIterator,
typename DiscoverTimeMap, typename LowPointMap>
std::pair<std::size_t, OutputIterator>
biconnected_components(const Graph& g, ComponentMap comp, OutputIterator out,
DiscoverTimeMap discover_time, LowPointMap lowpt);
template <typename Graph, typename ComponentMap, typename OutputIterator>
std::pair<std::size_t, OutputIterator>
biconnected_components(const Graph& g, ComponentMap comp, OutputIterator out);
template <typename Graph, typename ComponentMap>
std::size_t biconnected_components(const Graph& g, ComponentMap comp);
<a name="sec:articulation_points">
template <typename Graph, typename OutputIterator>
OutputIterator articulation_points(const Graph& g, OutputIterator out);
</PRE>
<P>
A connected graph is <i>biconnected</i> if the removal of any single
vertex (and all edges incident on that vertex) can not disconnect the
graph. More generally, the biconnected components of a graph are the
maximal subsets of vertices such that the removal of a vertex from a
particular component will not disconnect the component. Unlike
connected components, vertices may belong to multiple biconnected
components: those vertices that belong to more than one biconnected
component are called <em>articulation points</em> or, equivalently,
<em>cut vertices</em>. Articulation points are vertices whose removal
would increase the number of connected components in the graph. Thus,
a graph without articulation points is biconnected. The following
figure illustrates the articulation points and biconnected components
of a small graph:
<p><center><img src="figs/biconnected.png"></center>
<p>Vertices can be present in multiple biconnected components, but each
edge can only be contained in a single biconnected component. The
output of the <tt>biconnected_components</tt> algorithm records the
biconnected component number of each edge in the property map
<tt>comp</tt>. Articulation points will be emitted to the (optional)
output iterator argument to <tt>biconnected_components</tt>, or can be
computed without the use of a biconnected component number map via
<tt>articulation_points</tt>. These functions return the number of
biconnected components, the articulation point output iterator, or a
pair of these quantities, depending on what information was
recorded.
<p>The algorithm implemented is due to Tarjan [<a href="bibliography.html#tarjan72:dfs_and_linear_algo">41</a>].
<H3>Where Defined</H3>
<P>
<a href="../../../boost/graph/biconnected_components.hpp"><TT>boost/graph/biconnected_components.hpp</TT></a>
<h3>Parameters</h3>
IN: <tt>const Graph& g</tt>
<blockquote>
An undirected 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 biconnected components are in the graph,
and assigning each component an integer label. The algorithm then
records which component each edge 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>edges_size_type</tt> of the graph. The key type must be
the graph's edge descriptor type.<br>
<b>Default</b>: <tt>dummy_property_map</tt>.<br>
<b>Python</b>: Must be an <tt>edge_int_map</tt> for the graph.<br>
<b>Python default</b>: <tt>graph.get_edge_int_map("bicomponent")</tt>
</blockquote>
OUT: <tt>OutputIterator out</tt>
<blockquote>
The algorithm writes articulation points via this output
iterator and returns the resulting iterator.<br>
<b>Default</b>: a dummy iterator that ignores values written to it.<br>
<b>Python</b>: this parameter is not used in Python. Instead, both
algorithms return a Python <tt>list</tt> containing the articulation
points.
</blockquote>
<h3>Named Parameters</h3>
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>. 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><br>
<b>Python</b>: Unsupported parameter.
</blockquote>
UTIL/OUT: <tt>discover_time_map(DiscoverTimeMap discover_time)</tt>
<blockquote>
The discovery time of each vertex in the depth-first search. The
type <tt>DiscoverTimeMap</tt> must be a model of <a
href="../../property_map/ReadWritePropertyMap.html">Read/Write
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>: an <a
href="../../property_map/iterator_property_map.html">
</tt>iterator_property_map</tt></a> created from a
<tt>std::vector</tt> of <tt>vertices_size_type</tt> of size
<tt>num_vertices(g)</tt> and using <tt>get(vertex_index, g)</tt> for
the index map.<br>
<b>Python</b>: Unsupported parameter.
</blockquote>
UTIL/OUT: <tt>lowpoint_map(LowPointMap lowpt)</tt>
<blockquote>
The low point of each vertex in the depth-first search, which is the
smallest vertex reachable from a given vertex with at most one back
edge. The type <tt>LowPointMap</tt> must be a model of <a
href="../../property_map/ReadWritePropertyMap.html">Read/Write
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>: an <a
href="../../property_map/iterator_property_map.html">
</tt>iterator_property_map</tt></a> created from a
<tt>std::vector</tt> of <tt>vertices_size_type</tt> of size
<tt>num_vertices(g)</tt> and using <tt>get(vertex_index, g)</tt> for
the index map.<br>
<b>Python</b>: Unsupported parameter.
</blockquote>
UTIL/OUT: <tt>predecessor_map(PredecessorMap p_map)</tt>
<blockquote>
The predecessor map records the depth first search tree.
The <tt>PredecessorMap</tt> type
must be a <a
href="../../property_map/ReadWritePropertyMap.html">Read/Write
Property Map</a> whose key and value types are the same as 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 <tt>vertex_descriptor</tt> of size
<tt>num_vertices(g)</tt> and using <tt>get(vertex_index, g)</tt> for
the index map.<br>
<b>Python</b>: Must be a <tt>vertex_vertex_map</tt> for the graph.<br>
</blockquote>
IN: <tt>visitor(DFSVisitor vis)</tt>
<blockquote>
A visitor object that is invoked inside the algorithm at the
event-points specified by the <a href="./DFSVisitor.html">DFS
Visitor</a> concept. The visitor object is passed by value <a
href="#1">[1]</a>. <br> <b>Default:</b>
<tt>dfs_visitor<null_visitor></tt><br>
<b>Python</b>: The parameter should be an object that derives from
the <a href="DFSVisitor.html#python"><tt>DFSVisitor</tt></a> type of
the graph.
</blockquote>
<H3>Complexity</H3>
<P>
The time complexity for the biconnected components and articulation
points algorithms
<i>O(V + E)</i>.
<P>
<H3>Example</H3>
<P> The file <a
href="../example/biconnected_components.cpp"><tt>examples/biconnected_components.cpp</tt></a>
contains an example of calculating the biconnected components and
articulation points of an undirected graph.
<br>
<HR>
<TABLE>
<TR valign=top>
<TD nowrap>Copyright © 2000-2004</TD><TD>
<A HREF="../../../people/jeremy_siek.htm">Jeremy Siek</A>, Indiana
University (<A
HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br>
<a href="../../../people/doug_gregor.html">Doug Gregor</a>, Indiana University
</TD></TR></TABLE>
</BODY>
</HTML>
|
