| 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/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/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/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/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/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/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/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/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>adjacenty_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="../../../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> |
|---|
