Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_34_1/libs/graph/doc/undirected_dfs.html @ 47

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

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