Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_34_1/libs/graph/doc/depth_first_search.html @ 33

Last change on this file since 33 was 29, checked in by landauf, 17 years ago

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