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> 27template <class Graph, class ComponentMap, class P, class T, class R> 28typename property_traits<ComponentMap>::value_type 29strong_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> 36The <TT>strong_components()</TT> functions compute the strongly 37connected components of a directed graph using Tarjan's algorithm 38based on DFS [<A 39HREF="bibliography.html#tarjan72:dfs_and_linear_algo">41</A>]. 40</p> 41 42<P> 43The output of the algorithm is recorded in the component property 44map <TT>comp</TT>, which will contain numbers giving the component ID 45assigned to each vertex. The number of components is the return value 46of 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> 59A <a name="def:strongly-connected-component"><b><I>strongly connected 60component</I></b></a> of a directed graph <i>G=(V,E)</i> is a maximal 61set of vertices <i>U</i> which is in <i>V</i> such that for every pair 62of vertices <i>u</i> and <i>v</i> in <i>U</i>, we have both a path 63from <i>u</i> to <i>v</i> and path from <i>v</i> to <i>u</i>. That is 64to say that <i>u</i> and <i>v</i> are reachable from each other. 65 66<P> 67 68<h3>Parameters</h3> 69 70IN: <tt>const Graph& g</tt> 71<blockquote> 72A directed graph. The graph type must be a model of <a 73href="VertexListGraph.html">Vertex List Graph</a> and <a 74href="IncidenceGraph.html">Incidence Graph</a>.<br> 75 76<b>Python</b>: The parameter is named <tt>graph</tt>. 77</blockquote> 78 79OUT: <tt>ComponentMap c</tt> 80<blockquote> 81The algorithm computes how many connected components are in the graph, 82and assigning each component an integer label. The algorithm then 83records which component each vertex in the graph belongs to by 84recording the component number in the component property map. The 85<tt>ComponentMap</tt> type must be a model of <a 86href="../../property_map/doc/WritablePropertyMap.html">Writable Property 87Map</a>. The value type should be an integer type, preferably the same 88as the <tt>vertices_size_type</tt> of the graph. The key type must be 89the 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 98UTIL: <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 118UTIL: <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 134UTIL: <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 151IN: <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> 176The 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> 184and <a href="./incremental_components.html"><tt>incremental_components()</tt></a> 185 186<H3>Example</H3> 187 188<P> 189See <a 190href="../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> 202
