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

<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 &lt;class Graph, class ComponentMap, class P, class T, class R&gt;
typename property_traits&lt;ComponentMap&gt;::value_type
strong_components(Graph& g, ComponentMap comp,
    const bgl_named_params&lt;P, T, R&gt;&amp; 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&nbsp;[<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&amp; 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/doc/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/doc/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/doc/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/doc/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/doc/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/doc/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/doc/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/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>
    Note: if you use this default, make sure your graph has
    an internal <tt>vertex_index</tt> property. For example,
    <tt>adjacency_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 &copy; 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>
Commit	Line	Data
7c673cae FG	1	<HTML>
	2	<!--
	3	Copyright (c) Jeremy Siek 2000
	4
	5	Distributed under the Boost Software License, Version 1.0.
	6	(See accompanying file LICENSE_1_0.txt or copy at
	7	http://www.boost.org/LICENSE_1_0.txt)
	8	-->
	9	<Head>
	10	<Title>Boost Graph Library: Strongly Connected Components</Title>
	11	<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
	12	ALINK="#ff0000">
	13	<IMG SRC="../../../boost.png"
	14	ALT="C++ Boost" width="277" height="86">
	15
	16	<BR Clear>
	17
	18
	19	<H1>
	20	<A NAME="sec:connected-components"></A><A NAME="sec:strongly-connected-components"></A>
	21	<img src="figs/python.gif" alt="(Python)"/>
	22	<TT>strong_components</TT>
	23	</H1>
	24
	25	<PRE>
	26	<i>// named parameter version</i>
	27	template <class Graph, class ComponentMap, class P, class T, class R>
	28	typename property_traits<ComponentMap>::value_type
	29	strong_components(Graph& g, ComponentMap comp,
	30	const bgl_named_params<P, T, R>& params = <i>all defaults</i>)
	31
	32	<i>// there is not a non-named parameter version of this function</i>
	33	</PRE>
	34
	35	<P>
	36	The <TT>strong_components()</TT> functions compute the strongly
	37	connected components of a directed graph using Tarjan's algorithm
	38	based on DFS [<A
	39	HREF="bibliography.html#tarjan72:dfs_and_linear_algo">41</A>].
	40	</p>
	41
	42	<P>
	43	The output of the algorithm is recorded in the component property
	44	map <TT>comp</TT>, which will contain numbers giving the component ID
	45	assigned to each vertex. The number of components is the return value
	46	of the function.
	47	</p>
	48
	49	<H3>Where Defined</H3>
	50
	51	<P>
	52	<a href="../../../boost/graph/strong_components.hpp"><TT>boost/graph/strong_components.hpp</TT></a>
	53
	54	<P>
	55
	56	<H3>Definitions</H3>
	57
	58	<P>
	59	A <a name="def:strongly-connected-component"><b><I>strongly connected
	60	component</I></b></a> of a directed graph <i>G=(V,E)</i> is a maximal
	61	set of vertices <i>U</i> which is in <i>V</i> such that for every pair
	62	of vertices <i>u</i> and <i>v</i> in <i>U</i>, we have both a path
	63	from <i>u</i> to <i>v</i> and path from <i>v</i> to <i>u</i>. That is
	64	to say that <i>u</i> and <i>v</i> are reachable from each other.
65
66	<P>
67
68	<h3>Parameters</h3>
69
70	IN: <tt>const Graph& g</tt>
71	<blockquote>
72	A directed graph. The graph type must be a model of <a
73	href="VertexListGraph.html">Vertex List Graph</a> and <a
74	href="IncidenceGraph.html">Incidence Graph</a>.<br>
75
76	<b>Python</b>: The parameter is named <tt>graph</tt>.
77	</blockquote>
78
79	OUT: <tt>ComponentMap c</tt>
80	<blockquote>
81	The algorithm computes how many connected components are in the graph,
82	and assigning each component an integer label. The algorithm then
83	records which component each vertex in the graph belongs to by
84	recording the component number in the component property map. The
85	<tt>ComponentMap</tt> type must be a model of <a
86	href="../../property_map/doc/WritablePropertyMap.html">Writable Property
87	Map</a>. The value type shouch be an integer type, preferably the same
88	as the <tt>vertices_size_type</tt> of the graph. The key type must be
89	the graph's vertex descriptor type.<br>
90
91	<b>Python</b>: Must be an <tt>vertex_int_map</tt> for the graph.<br>
92	<b>Python default</b>: <tt>graph.get_vertex_int_map("component")</tt>
93	</blockquote>
94
95
96	<h3>Named Parameters</h3>
97
98	UTIL: <tt>root_map(RootMap r_map)</tt>
99	<blockquote>
100	This is used by the algorithm to record the candidate root vertex for
101	each vertex. By the end of the algorithm, there is a single root vertex
102	for each component and <tt>get(r_map, v)</tt> returns the root
103	vertex for whichever component vertex <tt>v</tt> is a member.
104	The <TT>RootMap</TT> must be a <a
105	href="../../property_map/doc/ReadWritePropertyMap.html">
106	Read/Write Property Map</a>, where the key type and the value type are
107	the vertex descriptor type of the graph.<br>
108
109	<b>Default:</b> an <a
110	href="../../property_map/doc/iterator_property_map.html">
111	<tt>iterator_property_map</tt></a> created from a
112	<tt>std::vector</tt> of vertex descriptors of size
113	<tt>num_vertices(g)</tt> and using the <tt>i_map</tt> for the index
114	map.<br>
115	<b>Python</b>: Unsupported parameter.
116	</blockquote>
117
118	UTIL: <tt>discover_time_map(TimeMap t_map)</tt>
119	<blockquote>
120	This is used by the algorithm to keep track of the DFS ordering
121	of the vertices. The <TT>TimeMap</TT> must be a model
122	of <a href="../../property_map/doc/ReadWritePropertyMap.html"> Read/Write
123	Property Map</a> and its value type must be an integer type. The key
124	type must be the vertex descriptor type of the graph.<br>
125	<b>Default:</b>an <a
126	href="../../property_map/doc/iterator_property_map.html">
127	<tt>iterator_property_map</tt></a> created from a
128	<tt>std::vector</tt> of integers with size
129	<tt>num_vertices(g)</tt> and using the <tt>i_map</tt> for the index
130	map.<br>
131	<b>Python</b>: Unsupported parameter.
132	</blockquote>
133
134	UTIL: <tt>color_map(ColorMap c_map)</tt>
135	<blockquote>
136	This is used by the algorithm to keep track of its progress through
137	the graph. The type <tt>ColorMap</tt> must be a model of <a
138	href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write
139	Property Map</a> and its key type must be the graph's vertex
140	descriptor type and the value type of the color map must model
141	<a href="./ColorValue.html">ColorValue</a>.<br>
142	<b>Default:</b> an <a
143	href="../../property_map/doc/iterator_property_map.html">
144	<tt>iterator_property_map</tt></a> created from a
145	<tt>std::vector</tt> of <tt>default_color_type</tt> of size
146	<tt>num_vertices(g)</tt> and using the <tt>i_map</tt> for the index
147	map.<br>
148	<b>Python</b>: Unsupported parameter.
149	</blockquote>
150
151	IN: <tt>vertex_index_map(VertexIndexMap i_map)</tt>
152	<blockquote>
153	This maps each vertex to an integer in the range <tt>[0,
154	num_vertices(g))</tt>. This parameter is only necessary when a
155	default is used for one of the other named parameters. The type
156	<tt>VertexIndexMap</tt> must be a model of <a
157	href="../../property_map/doc/ReadablePropertyMap.html">Readable Property
158	Map</a>. The value type of the map must be an integer type. The
159	vertex descriptor type of the graph needs to be usable as the key
160	type of the map.<br>
161
162	<b>Default:</b> <tt>get(vertex_index, g)</tt>
163	Note: if you use this default, make sure your graph has
164	an internal <tt>vertex_index</tt> property. For example,
165	<tt>adjacency_list</tt> with <tt>VertexList=listS</tt> does
166	not have an internal <tt>vertex_index</tt> property.
167	<br>
168
169	<b>Python</b>: Unsupported parameter.
170	</blockquote>
171
172
173	<H3>Complexity</H3>
174
175	<P>
176	The time complexity for the strongly connected components algorithm is
177	<i>O(V + E)</i>.
178
179	<P>
180
181	<h3>See Also</h3>
182
183	<a href="./connected_components.html"><tt>connected_components()</tt></a>
184	and <a href="./incremental_components.html"><tt>incremental_components()</tt></a>
185
186	<H3>Example</H3>
187
188	<P>
189	See <a
190	href="../example/strong_components.cpp"><tt>examples/strong_components.cpp</tt></a>.
191
192	<br>
193	<HR>
194	<TABLE>
195	<TR valign=top>
196	<TD nowrap>Copyright © 2000-2001</TD><TD>
197	<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>)
198	</TD></TR></TABLE>
199
200	</BODY>
201	</HTML>