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> 28and 29<tt>articulation_points</tt> 30</h1> 31 32<PRE> 33<i>// named parameter version</i> 34template <typename Graph, typename ComponentMap, typename OutputIterator, 35 typename P, typename T, typename R> 36std::pair<std::size_t, OutputIterator> 37biconnected_components(const Graph& g, ComponentMap comp, OutputIterator out, 38 const bgl_named_params<P, T, R>& params) 39 40template <typename Graph, typename ComponentMap, 41 typename P, typename T, typename R> 42std::size_t 43biconnected_components(const Graph& g, ComponentMap comp, 44 const bgl_named_params<P, T, R>& params) 45 46template <typename Graph, typename OutputIterator, 47 typename P, typename T, typename R> 48OutputIterator articulation_points(const Graph& g, OutputIterator out, 49 const bgl_named_params<P, T, R>& params) 50 51<i>// non-named parameter version</i> 52template <typename Graph, typename ComponentMap, typename OutputIterator, 53 typename DiscoverTimeMap, typename LowPointMap> 54std::pair<std::size_t, OutputIterator> 55biconnected_components(const Graph& g, ComponentMap comp, OutputIterator out, 56 DiscoverTimeMap discover_time, LowPointMap lowpt); 57 58template <typename Graph, typename ComponentMap, typename OutputIterator> 59std::pair<std::size_t, OutputIterator> 60biconnected_components(const Graph& g, ComponentMap comp, OutputIterator out); 61 62template <typename Graph, typename ComponentMap> 63std::size_t biconnected_components(const Graph& g, ComponentMap comp); 64<a name="sec:articulation_points"> 65template <typename Graph, typename OutputIterator> 66OutputIterator articulation_points(const Graph& g, OutputIterator out); 67</PRE> 68 69<P> 70A connected graph is <i>biconnected</i> if the removal of any single 71vertex (and all edges incident on that vertex) can not disconnect the 72graph. More generally, the biconnected components of a graph are the 73maximal subsets of vertices such that the removal of a vertex from a 74particular component will not disconnect the component. Unlike 75connected components, vertices may belong to multiple biconnected 76components: those vertices that belong to more than one biconnected 77component are called <em>articulation points</em> or, equivalently, 78<em>cut vertices</em>. Articulation points are vertices whose removal 79would increase the number of connected components in the graph. Thus, 80a graph without articulation points is biconnected. The following 81figure illustrates the articulation points and biconnected components 82of 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 87edge can only be contained in a single biconnected component. The 88output of the <tt>biconnected_components</tt> algorithm records the 89biconnected component number of each edge in the property map 90<tt>comp</tt>. Articulation points will be emitted to the (optional) 91output iterator argument to <tt>biconnected_components</tt>, or can be 92computed without the use of a biconnected component number map via 93<tt>articulation_points</tt>. These functions return the number of 94biconnected components, the articulation point output iterator, or a 95pair of these quantities, depending on what information was 96recorded. 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 108IN: <tt>const Graph& g</tt> 109<blockquote> 110An undirected graph. The graph type must be a model of <a 111href="VertexListGraph.html">Vertex List Graph</a> and <a 112href="IncidenceGraph.html">Incidence Graph</a>.<br> 113<b>Python</b>: The parameter is named <tt>graph</tt>. 114</blockquote> 115 116OUT: <tt>ComponentMap c</tt> 117<blockquote> 118The algorithm computes how many biconnected components are in the graph, 119and assigning each component an integer label. The algorithm then 120records which component each edge in the graph belongs to by 121recording the component number in the component property map. The 122<tt>ComponentMap</tt> type must be a model of <a 123href="../../property_map/doc/WritablePropertyMap.html">Writable Property 124Map</a>. The value type should be an integer type, preferably the same 125as the <tt>edges_size_type</tt> of the graph. The key type must be 126the 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 132OUT: <tt>OutputIterator out</tt> 133<blockquote> 134The algorithm writes articulation points via this output 135iterator 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 139algorithms return a Python <tt>list</tt> containing the articulation 140points. 141</blockquote> 142 143<h3>Named Parameters</h3> 144 145IN: <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 158UTIL/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 176UTIL/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 195UTIL/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 213IN: <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> 229The time complexity for the biconnected components and articulation 230points algorithms 231<i>O(V + E)</i>. 232 233<P> 234 235<H3>Example</H3> 236 237<P> The file <a 238href="../example/biconnected_components.cpp"><tt>examples/biconnected_components.cpp</tt></a> 239contains an example of calculating the biconnected components and 240articulation 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 257University (<A 258HREF="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> 264
