libs/graph/doc/undirected_dfs.html

   1 <HTML>
   2 <!--
   3      Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 2002
   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: Undirected Depth-First Search</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 <H1><A NAME="sec:depth-first-search"></A>
  19 <img src="figs/python.gif" alt="(Python)"/>
  20 <TT>undirected_dfs</TT>
  21 </H1>
  22
  23 <P>
  24 <PRE>
  25 <i>// named parameter version</i>
  26 template &lt;typename Graph, typename P, typename T, typename R&gt;
  27 void undirected_dfs(Graph&amp; G, const bgl_named_params&lt;P, T, R&gt;&amp; params);
  28
  29 <i>// non-named parameter version</i>
  30 template &lt;typename Graph, typename <a href="DFSVisitor.html">DFSVisitor</a>, typename VertexColorMap, typename EdgeColorMap&gt;
  31 void undirected_dfs(const Graph&amp; g, DFSVisitor vis, VertexColorMap vertex_color, EdgeColorMap edge_color)
  32
  33 template &lt;typename Graph, typename <a href="DFSVisitor.html">DFSVisitor</a>, typename VertexColorMap, typename EdgeColorMap&gt;
  34 void undirected_dfs(const Graph&amp; g, DFSVisitor vis,
  35                     VertexColorMap vertex_color, EdgeColorMap edge_color,
  36                     typename graph_traits&lt;Graph&gt;::vertex_descriptor start)
  37
  38 </PRE>
  39
  40 <p>
  41 The <tt>undirected_dfs()</tt> function performs a depth-first
  42 traversal of the vertices in an undirected graph.  When possible, a
  43 depth-first traversal chooses a vertex adjacent to the current vertex
  44 to visit next. If all adjacent vertices have already been discovered,
  45 or there are no adjacent vertices, then the algorithm backtracks to
  46 the last vertex that had undiscovered neighbors. Once all reachable
  47 vertices have been visited, the algorithm selects from any remaining
  48 undiscovered vertices and continues the traversal. The algorithm
  49 finishes when all vertices have been visited. Depth-first search is
  50 useful for categorizing edges in a graph, and for imposing an ordering
  51 on the vertices. Section <a
  52 href="./graph_theory_review.html#sec:dfs-algorithm">Depth-First
  53 Search</a> describes the various properties of DFS and walks through
  54 an example.
  55 </p>
  56
  57 <p>
  58 Similar to BFS, color markers are used to keep track of which vertices
  59 have been discovered. White marks vertices that have yet to be
  60 discovered, gray marks a vertex that is discovered but still has
  61 vertices adjacent to it that are undiscovered. A black vertex is
  62 discovered vertex that is not adjacent to any white vertices.
  63 </p>
  64
  65 <p>
  66 Edges are also colored during the search to disambiguate tree and back
  67 edges.
  68 </p>
  69
  70 <p>
  71 The <tt>undirected_dfs()</tt> function invokes user-defined actions at
  72 certain event-points within the algorithm. This provides a mechanism
  73 for adapting the generic DFS algorithm to the many situations in which
  74 it can be used.  In the pseudo-code below, the event points for DFS
  75 are indicated in by the triangles and labels on the right. The
  76 user-defined actions must be provided in the form of a visitor object,
  77 that is, an object whose type meets the requirements for a <a
  78 href="./DFSVisitor.html">DFS Visitor</a>. In the pseudo-code we show
  79 the algorithm computing predecessors <i>p</i>, discover time <i>d</i>
  80 and finish time <i>t</i>.  By default, the <tt>undirected_dfs()</tt>
  81 function does not compute these properties, however there are
  82 pre-defined visitors such as <a
  83 href="./predecessor_recorder.html"><tt>predecessor_recorder</tt></a>
  84 and <a href="./time_stamper.html"><tt>time_stamper</tt></a> that can
  85 be used to do this.
  86 </p>
  87
  88 <table>
  89 <tr>
  90 <td valign="top">
  91 <pre>
  92 DFS(<i>G</i>)
  93   <b>for</b> each vertex <i>u in V</i>
  94     <i>vcolor[u] :=</i> WHITE
  95     <i>p[u] := u</i>
  96   <b>end for</b>
  97   <b>for</b> each edge <i>e in E</i>
  98     <i>ecolor[u] :=</i> WHITE
  99   <b>end for</b>
 100   <i>time := 0</i>
 101   <b>if</b> there is a starting vertex <i>s</i>
 102     <b>call</b> DFS-VISIT(<i>G</i>, <i>s</i>)
 103   <b>for</b> each vertex <i>u in V</i>
 104     <b>if</b> <i>vcolor[u] =</i> WHITE
 105       <b>call</b> DFS-VISIT(<i>G</i>, <i>u</i>)
 106   <b>end for</b>
 107   <b>return</b> (<i>p</i>,<i>d_time</i>,<i>f_time</i>) <br>
 108 DFS-VISIT(<i>G</i>, <i>u</i>)
 109   <i>vcolor[u] :=</i> GRAY
 110   <i>d_time[u] := time := time + 1</i>
 111   <b>for</b> each <i>e in Out[u]</i>
 112     <b>var</b> <i>ec := ecolor[e]</i>
 113     <i>ecolor[e] :=</i> BLACK
 114     <b>if</b> (<i>vcolor[v] =</i> WHITE)
 115       <i>p[v] := u</i>
 116       <b>call</b> DFS-VISIT(<i>G</i>, <i>v</i>)
 117     <b>else if</b> (<i>vcolor[v] =</i> GRAY and <i>ec =</i> WHITE)
 118       <i>...</i>
 119     <i>...</i>
 120   <b>end for</b>
 121   <i>vcolor[u] :=</i> BLACK
 122   <i>f_time[u] := time := time + 1</i>
 123 <pre>
 124 </td>
 125 <td valign="top">
 126 <pre>
 127 -
 128 -
 129 initialize vertex <i>u</i>
 130 -
 131 -
 132 -
 133 -
 134 -
 135 -
 136 -
 137 start vertex <i>s</i>
 138 -
 139 -
 140 start vertex <i>u</i>
 141 -
 142 -
 143 -
 144 -
 145 discover vertex <i>u</i>
 146 -
 147 examine edge <i>(u,v)</i>
 148 -
 149 -
 150 <i>(u,v)</i> is a tree edge
 151 -
 152 -
 153 <i>(u,v)</i> is a back edge
 154 -
 155 -
 156 finish edge <i>(u,v)</i>
 157 -
 158 finish vertex <i>u</i>
 159 -
 160 </pre>
 161 </td>
 162 </tr>
 163 </table>
 164
 165
 166
 167 <H3>Where Defined</H3>
 168
 169 <P>
 170 <a href="../../../boost/graph/undirected_dfs.hpp"><TT>boost/graph/undirected_dfs.hpp</TT></a>
 171
 172 <h3>Parameters</h3>
 173
 174 IN: <tt>Graph&amp; g</tt>
 175 <blockquote>
 176   An undirected graph. The graph type must
 177   be a model of <a href="./IncidenceGraph.html">Incidence Graph</a>,
 178   <a href="./VertexListGraph.html">Vertex List Graph</a>,
 179   and <a href="./EdgeListGraph.html">Edge List Graph</a>.<br>
 180
 181   <b>Python</b>: The parameter is named <tt>graph</tt>.
 182 </blockquote>
 183
 184
 185 <h3>Named Parameters</h3>
 186
 187 IN: <tt>visitor(DFSVisitor vis)</tt>
 188 <blockquote>
 189   A visitor object that is invoked inside the algorithm at the
 190   event-points specified by the <a href="./DFSVisitor.html">DFS
 191   Visitor</a> concept. The visitor object is passed by value <a
 192   href="#1">[1]</a>. <br> <b>Default:</b>
 193   <tt>dfs_visitor&lt;null_visitor&gt;</tt><br>
 194
 195   <b>Python</b>: The parameter should be an object that derives from
 196   the <a href="DFSVisitor.html#python"><tt>DFSVisitor</tt></a> type of
 197   the graph.
 198 </blockquote>
 199
 200 UTIL/OUT: <tt>vertex_color_map(VertexColorMap vertex_color)</tt>
 201 <blockquote>
 202   This is used by the algorithm to keep track of its progress through
 203   the graph. The type <tt>VertexColorMap</tt> must be a model of <a
 204   href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write
 205   Property Map</a> and its key type must be the graph's vertex
 206   descriptor type and the value type of the color map must model
 207   <a href="./ColorValue.html">ColorValue</a>.<br>
 208   <b>Default:</b> an <a
 209   href="../../property_map/doc/iterator_property_map.html">
 210   </tt>iterator_property_map</tt></a> created from a
 211   <tt>std::vector</tt> of <tt>default_color_type</tt> of size
 212   <tt>num_vertices(g)</tt> and using the <tt>i_map</tt> for the index
 213   map.<br>
 214
 215   <b>Python</b>: The color map must be a <tt>vertex_color_map</tt> for
 216   the graph.
 217 </blockquote>
 218
 219 UTIL: <tt>edge_color_map(EdgeColorMap edge_color)</tt>
 220 <blockquote>
 221   This is used by the algorithm to keep track of which edges
 222   have been visited. The type <tt>EdgeColorMap</tt> must be a model of <a
 223   href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write
 224   Property Map</a> and its key type must be the graph's edge
 225   descriptor type and the value type of the color map must model
 226   <a href="./ColorValue.html">ColorValue</a>.<br>
 227   <b>Default:</b> none.<br>
 228
 229   <b>Python</b>: The color map must be an <tt>edge_color_map</tt> for
 230   the graph.
 231 </blockquote>
 232
 233 IN: <tt>root_vertex(typename
 234 graph_traits&lt;VertexListGraph&gt;::vertex_descriptor start)</tt>
 235 <blockquote>
 236   This specifies the vertex that the depth-first search should
 237   originate from. The type is the type of a vertex descriptor for the
 238   given graph.<br>
 239   <b>Default:</b> <tt>*vertices(g).first</tt>
 240 </blockquote>
 241
 242 IN: <tt>vertex_index_map(VertexIndexMap i_map)</tt>
 243 <blockquote>
 244   This maps each vertex to an integer in the range <tt>[0,
 245   num_vertices(g))</tt>. This parameter is only necessary when the
 246   default color property map is used. The type <tt>VertexIndexMap</tt>
 247   must be a model of <a
 248   href="../../property_map/doc/ReadablePropertyMap.html">Readable Property
 249   Map</a>. The value type of the map must be an integer type. The
 250   vertex descriptor type of the graph needs to be usable as the key
 251   type of the map.<br>
 252
 253   <b>Default:</b> <tt>get(vertex_index, g)</tt>
 254     Note: if you use this default, make sure your graph has
 255     an internal <tt>vertex_index</tt> property. For example,
 256     <tt>adjacenty_list</tt> with <tt>VertexList=listS</tt> does
 257     not have an internal <tt>vertex_index</tt> property.
 258    <br>
 259
 260   <b>Python</b>: Unsupported parameter.
 261 </blockquote>
 262
 263 <P>
 264
 265 <H3><A NAME="SECTION001340300000000000000">
 266 Complexity</A>
 267 </H3>
 268
 269 <P>
 270 The time complexity is <i>O(E + V)</i>.
 271
 272 <P>
 273
 274 <h3>Visitor Event Points</h3>
 275
 276 <ul>
 277
 278 <li><b><tt>vis.initialize_vertex(s, g)</tt></b> is invoked on every
 279   vertex of the graph before the start of the graph search.
 280
 281 <li><b><tt>vis.start_vertex(s, g)</tt></b> is invoked on the source
 282   vertex once before the start of the search.
 283
 284 <li><b><tt>vis.discover_vertex(u, g)</tt></b> is invoked when a vertex
 285   is encountered for the first time.
 286
 287 <li><b><tt>vis.examine_edge(e, g)</tt></b> is invoked on every out-edge
 288   of each vertex after it is discovered.
 289
 290 <li><b><tt>vis.tree_edge(e, g)</tt></b> is invoked on each edge as it
 291   becomes a member of the edges that form the search tree. If you
 292   wish to record predecessors, do so at this event point.
 293
 294 <li><b><tt>vis.back_edge(e, g)</tt></b> is invoked on the back edges in
 295   the graph.
 296
 297 <li><b><tt>vis.finish_edge(e, g)</tt></b> is invoked on the back edges in
 298   the graph as well as on each tree edge after its target vertex is finished.
 299
 300 <li><b><tt>vis.finish_vertex(u, g)</tt></b> is invoked on a vertex after
 301   all of its out edges have been added to the search tree and all of
 302   the adjacent vertices have been discovered (but before their
 303   out-edges have been examined).
 304
 305 </ul>
 306
 307
 308 <H3>Example</H3>
 309
 310 <P>
 311 An example is in <a href="../example/undirected_dfs.cpp">
 312 <TT>examples/undirected_dfs.cpp</TT></a>.
 313
 314 <h3>See Also</h3>
 315
 316 <a href="./depth_first_search.html"><tt>depth_first_search</tt></a>
 317
 318 <h3>Notes</h3>
 319
 320 <p><a name="1">[1]</a>
 321   Since the visitor parameter is passed by value, if your visitor
 322   contains state then any changes to the state during the algorithm
 323   will be made to a copy of the visitor object, not the visitor object
 324   passed in. Therefore you may want the visitor to hold this state by
 325   pointer or reference.
 326
 327 <br>
 328 <HR>
 329 <TABLE>
 330 <TR valign=top>
 331 <TD nowrap>Copyright &copy; 2000-2001</TD><TD>
 332 <A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>,
 333 Indiana University (<A
 334 HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br>
 335 <A HREF="http://www.boost.org/people/liequan_lee.htm">Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@cs.indiana.edu">llee@cs.indiana.edu</A>)<br>
 336 <A HREF="http://www.osl.iu.edu/~lums">Andrew Lumsdaine</A>,
 337 Indiana University (<A
 338 HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
 339 </TD></TR></TABLE>
 340
 341 </BODY>
 342 </HTML>