[ceph.git] / ceph / src / boost / libs / graph / doc / biconnected_components.html

<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 &lt;typename Graph, typename ComponentMap, typename OutputIterator,
          typename P, typename T, typename R&gt;
std::pair&lt;std::size_t, OutputIterator&gt;
biconnected_components(const Graph& g, ComponentMap comp, OutputIterator out, 
                       const bgl_named_params&lt;P, T, R&gt;&amp; params)

template &lt;typename Graph, typename ComponentMap,
          typename P, typename T, typename R&gt;
std::size_t
biconnected_components(const Graph& g, ComponentMap comp, 
                       const bgl_named_params&lt;P, T, R&gt;&amp; params)

template &lt;typename Graph, typename OutputIterator, 
          typename P, typename T, typename R&gt;
OutputIterator articulation_points(const Graph& g, OutputIterator out, 
                                   const bgl_named_params&lt;P, T, R&gt;&amp; params)

<i>// non-named parameter version</i>
template &lt;typename Graph, typename ComponentMap, typename OutputIterator,
          typename DiscoverTimeMap, typename LowPointMap&gt;
std::pair&lt;std::size_t, OutputIterator&gt;
biconnected_components(const Graph& g, ComponentMap comp, OutputIterator out, 
                       DiscoverTimeMap discover_time, LowPointMap lowpt);

template &lt;typename Graph, typename ComponentMap, typename OutputIterator&gt;
std::pair&lt;std::size_t, OutputIterator&gt;
biconnected_components(const Graph& g, ComponentMap comp, OutputIterator out);

template &lt;typename Graph, typename ComponentMap&gt;
std::size_t biconnected_components(const Graph& g, ComponentMap comp);
<a name="sec:articulation_points">
template &lt;typename Graph, typename OutputIterator&gt;
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&amp; 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/doc/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/doc/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/doc/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/doc/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/doc/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/doc/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/doc/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/doc/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&lt;null_visitor&gt;</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.

<h3>Notes</h3>

<p><a name="1">[1]</a> 
  Since the visitor parameter is passed by value, if your visitor
  contains state then any changes to the state during the algorithm
  will be made to a copy of the visitor object, not the visitor object
  passed in. Therefore you may want the visitor to hold this state by
  pointer or reference.

<br>
<HR>
<TABLE>
<TR valign=top>
<TD nowrap>Copyright &copy; 2000-2004</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>)<br>
<a href="http://www.boost.org/people/doug_gregor.html">Doug Gregor</a>, Indiana University
</TD></TR></TABLE>

</BODY>
</HTML>
Commit	Line	Data
7c673cae FG	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>
	28	and
	29	<tt>articulation_points</tt>
	30	</h1>
	31
	32	<PRE>
	33	<i>// named parameter version</i>
	34	template <typename Graph, typename ComponentMap, typename OutputIterator,
	35	typename P, typename T, typename R>
	36	std::pair<std::size_t, OutputIterator>
	37	biconnected_components(const Graph& g, ComponentMap comp, OutputIterator out,
	38	const bgl_named_params<P, T, R>& params)
	39
	40	template <typename Graph, typename ComponentMap,
	41	typename P, typename T, typename R>
	42	std::size_t
	43	biconnected_components(const Graph& g, ComponentMap comp,
	44	const bgl_named_params<P, T, R>& params)
	45
	46	template <typename Graph, typename OutputIterator,
	47	typename P, typename T, typename R>
	48	OutputIterator articulation_points(const Graph& g, OutputIterator out,
	49	const bgl_named_params<P, T, R>& params)
	50
	51	<i>// non-named parameter version</i>
	52	template <typename Graph, typename ComponentMap, typename OutputIterator,
	53	typename DiscoverTimeMap, typename LowPointMap>
	54	std::pair<std::size_t, OutputIterator>
	55	biconnected_components(const Graph& g, ComponentMap comp, OutputIterator out,
	56	DiscoverTimeMap discover_time, LowPointMap lowpt);
	57
	58	template <typename Graph, typename ComponentMap, typename OutputIterator>
	59	std::pair<std::size_t, OutputIterator>
	60	biconnected_components(const Graph& g, ComponentMap comp, OutputIterator out);
	61
	62	template <typename Graph, typename ComponentMap>
	63	std::size_t biconnected_components(const Graph& g, ComponentMap comp);
	64	<a name="sec:articulation_points">
65	template <typename Graph, typename OutputIterator>
66	OutputIterator articulation_points(const Graph& g, OutputIterator out);
67	</PRE>
68
69	<P>
70	A connected graph is <i>biconnected</i> if the removal of any single
71	vertex (and all edges incident on that vertex) can not disconnect the
72	graph. More generally, the biconnected components of a graph are the
73	maximal subsets of vertices such that the removal of a vertex from a
74	particular component will not disconnect the component. Unlike
75	connected components, vertices may belong to multiple biconnected
76	components: those vertices that belong to more than one biconnected
77	component are called <em>articulation points</em> or, equivalently,
78	<em>cut vertices</em>. Articulation points are vertices whose removal
79	would increase the number of connected components in the graph. Thus,
80	a graph without articulation points is biconnected. The following
81	figure illustrates the articulation points and biconnected components
82	of 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
87	edge can only be contained in a single biconnected component. The
88	output of the <tt>biconnected_components</tt> algorithm records the
89	biconnected component number of each edge in the property map
90	<tt>comp</tt>. Articulation points will be emitted to the (optional)
91	output iterator argument to <tt>biconnected_components</tt>, or can be
92	computed without the use of a biconnected component number map via
93	<tt>articulation_points</tt>. These functions return the number of
94	biconnected components, the articulation point output iterator, or a
95	pair of these quantities, depending on what information was
96	recorded.
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
108	IN: <tt>const Graph& g</tt>
109	<blockquote>
110	An undirected graph. The graph type must be a model of <a
111	href="VertexListGraph.html">Vertex List Graph</a> and <a
112	href="IncidenceGraph.html">Incidence Graph</a>.<br>
113	<b>Python</b>: The parameter is named <tt>graph</tt>.
114	</blockquote>
115
116	OUT: <tt>ComponentMap c</tt>
117	<blockquote>
118	The algorithm computes how many biconnected components are in the graph,
119	and assigning each component an integer label. The algorithm then
120	records which component each edge in the graph belongs to by
121	recording the component number in the component property map. The
122	<tt>ComponentMap</tt> type must be a model of <a
123	href="../../property_map/doc/WritablePropertyMap.html">Writable Property
124	Map</a>. The value type shouch be an integer type, preferably the same
125	as the <tt>edges_size_type</tt> of the graph. The key type must be
126	the 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
132	OUT: <tt>OutputIterator out</tt>
133	<blockquote>
134	The algorithm writes articulation points via this output
135	iterator 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
139	algorithms return a Python <tt>list</tt> containing the articulation
140	points.
141	</blockquote>
142
143	<h3>Named Parameters</h3>
144
145	IN: <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/doc/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
158	UTIL/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/doc/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/doc/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
176	UTIL/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/doc/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/doc/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
195	UTIL/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/doc/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/doc/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
213	IN: <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<null_visitor></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>
229	The time complexity for the biconnected components and articulation
230	points algorithms
231	<i>O(V + E)</i>.
232
233	<P>
234
235	<H3>Example</H3>
236
237	<P> The file <a
238	href="../example/biconnected_components.cpp"><tt>examples/biconnected_components.cpp</tt></a>
239	contains an example of calculating the biconnected components and
240	articulation points of an undirected graph.
241
242	<h3>Notes</h3>
243
244	<p><a name="1">[1]</a>
245	Since the visitor parameter is passed by value, if your visitor
246	contains state then any changes to the state during the algorithm
247	will be made to a copy of the visitor object, not the visitor object
248	passed in. Therefore you may want the visitor to hold this state by
249	pointer or reference.
250
251	<br>
252	<HR>
253	<TABLE>
254	<TR valign=top>
255	<TD nowrap>Copyright © 2000-2004</TD><TD>
256	<A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>, Indiana
257	University (<A
258	HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br>
259	<a href="http://www.boost.org/people/doug_gregor.html">Doug Gregor</a>, Indiana University
260	</TD></TR></TABLE>
261
262	</BODY>
263	</HTML>