ceph/src/boost/libs/graph/doc/biconnected_components.html

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