boost_1_45_0/libs/graph/doc/strong_components.html - nest-learning-thermostat/5.0/boost - Git at Google

 <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>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 &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>
	<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/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>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>