Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_34_1/libs/graph/doc/biconnected_components.html @ 47

Last change on this file since 47 was 29, checked in by landauf, 17 years ago

updated boost from 1_33_1 to 1_34_1
File size: 9.8 KB
Line 
1<HTML>
2<!--
3  -- Copyright 2001-2004 The Trustees of Indiana University.
4  --
5  -- Use, modification and distribution is subject to the Boost Software
6  -- License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
7  -- http://www.boost.org/LICENSE_1_0.txt)
8  --
9  --  Authors: Douglas Gregor
10  --           Jeremy Siek
11  --           Andrew Lumsdaine
12  -->
13<Head>
14<Title>Boost Graph Library: Biconnected Components and Articulation Points</Title>
15<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 
16        ALINK="#ff0000"> 
17<IMG SRC="../../../boost.png" 
18     ALT="C++ Boost" width="277" height="86"> 
19
20<BR Clear>
21
22<h1>
23<TT>
24<img src="figs/python.gif" alt="(Python)"/>
25<A NAME="sec:biconnected-components">biconnected_components
26</A>
27</TT>
28and
29<tt>articulation_points</tt>
30</h1>
31
32<PRE>
33<i>// named parameter version</i>
34template &lt;typename Graph, typename ComponentMap, typename OutputIterator,
35          typename P, typename T, typename R&gt;
36std::pair&lt;std::size_t, OutputIterator&gt;
37biconnected_components(const Graph& g, ComponentMap comp, OutputIterator out,
38                       const bgl_named_params&lt;P, T, R&gt;&amp; params)
39
40template &lt;typename Graph, typename ComponentMap,
41          typename P, typename T, typename R&gt;
42std::size_t
43biconnected_components(const Graph& g, ComponentMap comp,
44                       const bgl_named_params&lt;P, T, R&gt;&amp; params)
45
46template &lt;typename Graph, typename OutputIterator,
47          typename P, typename T, typename R&gt;
48OutputIterator articulation_points(const Graph& g, OutputIterator out,
49                                   const bgl_named_params&lt;P, T, R&gt;&amp; params)
50
51<i>// non-named parameter version</i>
52template &lt;typename Graph, typename ComponentMap, typename OutputIterator,
53          typename DiscoverTimeMap, typename LowPointMap&gt;
54std::pair&lt;std::size_t, OutputIterator&gt;
55biconnected_components(const Graph& g, ComponentMap comp, OutputIterator out,
56                       DiscoverTimeMap discover_time, LowPointMap lowpt);
57
58template &lt;typename Graph, typename ComponentMap, typename OutputIterator&gt;
59std::pair&lt;std::size_t, OutputIterator&gt;
60biconnected_components(const Graph& g, ComponentMap comp, OutputIterator out);
61
62template &lt;typename Graph, typename ComponentMap&gt;
63std::size_t biconnected_components(const Graph& g, ComponentMap comp);
64<a name="sec:articulation_points">
65template &lt;typename Graph, typename OutputIterator&gt;
66OutputIterator articulation_points(const Graph& g, OutputIterator out);
67</PRE>
68
69<P>
70A connected graph is <i>biconnected</i> if the removal of any single
71vertex (and all edges incident on that vertex) can not disconnect the
72graph. More generally, the biconnected components of a graph are the
73maximal subsets of vertices such that the removal of a vertex from a
74particular component will not disconnect the component. Unlike
75connected components, vertices may belong to multiple biconnected
76components: those vertices that belong to more than one biconnected
77component are called <em>articulation points</em> or, equivalently,
78<em>cut vertices</em>. Articulation points are vertices whose removal
79would increase the number of connected components in the graph. Thus,
80a graph without articulation points is biconnected. The following
81figure illustrates the articulation points and biconnected components
82of a small graph:
83
84<p><center><img src="figs/biconnected.png"></center>
85
86<p>Vertices can be present in multiple biconnected components, but each
87edge can only be contained in a single biconnected component. The
88output of the <tt>biconnected_components</tt> algorithm records the
89biconnected component number of each edge in the property map
90<tt>comp</tt>. Articulation points will be emitted to the (optional)
91output iterator argument to <tt>biconnected_components</tt>, or can be
92computed without the use of a biconnected component number map via
93<tt>articulation_points</tt>. These functions return the number of
94biconnected components, the articulation point output iterator, or a
95pair of these quantities, depending on what information was
96recorded.
97
98<p>The algorithm implemented is due to Tarjan [<a href="bibliography.html#tarjan72:dfs_and_linear_algo">41</a>].
99
100<H3>Where Defined</H3>
101
102<P>
103<a href="../../../boost/graph/biconnected_components.hpp"><TT>boost/graph/biconnected_components.hpp</TT></a>
104
105
106<h3>Parameters</h3>
107
108IN: <tt>const Graph&amp; g</tt>
109<blockquote>
110An undirected graph. The graph type must be a model of <a
111href="VertexListGraph.html">Vertex List Graph</a> and <a
112href="IncidenceGraph.html">Incidence Graph</a>.<br>
113<b>Python</b>: The parameter is named <tt>graph</tt>.
114</blockquote>
115
116OUT: <tt>ComponentMap c</tt>
117<blockquote>
118The algorithm computes how many biconnected components are in the graph,
119and assigning each component an integer label. The algorithm then
120records which component each edge in the graph belongs to by
121recording the component number in the component property map. The
122<tt>ComponentMap</tt> type must be a model of <a
123href="../../property_map/WritablePropertyMap.html">Writable Property
124Map</a>. The value type shouch be an integer type, preferably the same
125as the <tt>edges_size_type</tt> of the graph. The key type must be
126the graph's edge descriptor type.<br>
127<b>Default</b>: <tt>dummy_property_map</tt>.<br>
128  <b>Python</b>: Must be an <tt>edge_int_map</tt> for the graph.<br>
129  <b>Python default</b>: <tt>graph.get_edge_int_map("bicomponent")</tt>
130</blockquote>
131
132OUT: <tt>OutputIterator out</tt>
133<blockquote>
134The algorithm writes articulation points via this output
135iterator and returns the resulting iterator.<br>
136<b>Default</b>: a dummy iterator that ignores values written to it.<br>
137
138<b>Python</b>: this parameter is not used in Python. Instead, both
139algorithms return a Python <tt>list</tt> containing the articulation
140points.
141</blockquote>
142
143<h3>Named Parameters</h3>
144
145IN: <tt>vertex_index_map(VertexIndexMap i_map)</tt> 
146<blockquote>
147  This maps each vertex to an integer in the range <tt>[0,
148    num_vertices(g))</tt>. The type
149  <tt>VertexIndexMap</tt> must be a model of
150  <a href="../../property_map/ReadablePropertyMap.html">Readable Property Map</a>. The value type of the map must be an
151  integer type. The vertex descriptor type of the graph needs to be
152  usable as the key type of the map.<br>
153  <b>Default:</b> <tt>get(vertex_index, g)</tt><br>
154
155  <b>Python</b>: Unsupported parameter.
156</blockquote>
157
158UTIL/OUT: <tt>discover_time_map(DiscoverTimeMap discover_time)</tt>
159<blockquote>
160  The discovery time of each vertex in the depth-first search. The
161  type <tt>DiscoverTimeMap</tt> must be a model of <a
162  href="../../property_map/ReadWritePropertyMap.html">Read/Write
163  Property Map</a>. The value type of the map must be an integer
164  type. The vertex descriptor type of the graph needs to be usable as
165  the key type of the map.<br>
166<b>Default</b>: an <a
167  href="../../property_map/iterator_property_map.html">
168  </tt>iterator_property_map</tt></a> created from a
169  <tt>std::vector</tt> of <tt>vertices_size_type</tt> of size
170  <tt>num_vertices(g)</tt> and using <tt>get(vertex_index, g)</tt> for
171  the index map.<br>
172
173  <b>Python</b>: Unsupported parameter.
174</blockquote>
175
176UTIL/OUT: <tt>lowpoint_map(LowPointMap lowpt)</tt>
177<blockquote>
178  The low point of each vertex in the depth-first search, which is the
179  smallest vertex reachable from a given vertex with at most one back
180  edge.  The type <tt>LowPointMap</tt> must be a model of <a
181  href="../../property_map/ReadWritePropertyMap.html">Read/Write
182  Property Map</a>. The value type of the map must be an integer
183  type. The vertex descriptor type of the graph needs to be usable as
184  the key type of the map.<br>
185<b>Default</b>: an <a
186  href="../../property_map/iterator_property_map.html">
187  </tt>iterator_property_map</tt></a> created from a
188  <tt>std::vector</tt> of <tt>vertices_size_type</tt> of size
189  <tt>num_vertices(g)</tt> and using <tt>get(vertex_index, g)</tt> for
190  the index map.<br>
191
192  <b>Python</b>: Unsupported parameter.
193</blockquote>
194
195UTIL/OUT: <tt>predecessor_map(PredecessorMap p_map)</tt> 
196<blockquote>
197  The predecessor map records the depth first search tree.
198  The <tt>PredecessorMap</tt> type
199  must be a <a
200  href="../../property_map/ReadWritePropertyMap.html">Read/Write
201  Property Map</a> whose key and value types are the same as the vertex
202  descriptor type of the graph.<br>
203  <b>Default:</b> an <a
204  href="../../property_map/iterator_property_map.html">
205  </tt>iterator_property_map</tt></a> created from a
206  <tt>std::vector</tt> of <tt>vertex_descriptor</tt> of size
207  <tt>num_vertices(g)</tt> and using <tt>get(vertex_index, g)</tt> for
208  the index map.<br>
209
210  <b>Python</b>: Must be a <tt>vertex_vertex_map</tt> for the graph.<br>
211</blockquote>
212
213IN: <tt>visitor(DFSVisitor vis)</tt>
214<blockquote>
215  A visitor object that is invoked inside the algorithm at the
216  event-points specified by the <a href="./DFSVisitor.html">DFS
217  Visitor</a> concept. The visitor object is passed by value <a
218  href="#1">[1]</a>. <br> <b>Default:</b>
219  <tt>dfs_visitor&lt;null_visitor&gt;</tt><br>
220
221  <b>Python</b>: The parameter should be an object that derives from
222  the <a href="DFSVisitor.html#python"><tt>DFSVisitor</tt></a> type of
223  the graph.
224</blockquote>
225
226<H3>Complexity</H3>
227
228<P>
229The time complexity for the biconnected components and articulation
230points algorithms
231<i>O(V + E)</i>.
232
233<P>
234
235<H3>Example</H3>
236
237<P> The file <a
238href="../example/biconnected_components.cpp"><tt>examples/biconnected_components.cpp</tt></a>
239contains an example of calculating the biconnected components and
240articulation points of an undirected graph.
241
242<br>
243<HR>
244<TABLE>
245<TR valign=top>
246<TD nowrap>Copyright &copy 2000-2004</TD><TD>
247<A HREF="../../../people/jeremy_siek.htm">Jeremy Siek</A>, Indiana
248University (<A
249HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br>
250<a href="../../../people/doug_gregor.html">Doug Gregor</a>, Indiana University
251</TD></TR></TABLE>
252
253</BODY>
254</HTML> 
Note: See TracBrowser for help on using the repository browser.