boost_1_45_0/libs/graph/doc/depth_first_search.html - nest-learning-thermostat/5.0/boost - Git at Google

 <HTML>
 <!--
      Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 2000

      Distributed under the Boost Software License, Version 1.0.
      (See accompanying file LICENSE_1_0.txt or copy at
      http://www.boost.org/LICENSE_1_0.txt)
   -->
 <Head>
 <Title>Boost Graph Library: Depth-First Search</Title>
 <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
         ALINK="#ff0000">
 <IMG SRC="../../../boost.png"
      ALT="C++ Boost" width="277" height="86">

 <BR Clear>

 <H1><A NAME="sec:depth-first-search"></A><img src="figs/python.gif" alt="(Python)"/>
 <TT>depth_first_search</TT>
 </H1>

 <P>
 <PRE>
 <i>// named parameter version</i>
 template &lt;class Graph, class class P, class T, class R&gt;
 void depth_first_search(Graph&amp; G,
   const bgl_named_params&lt;P, T, R&gt;&amp; params);

 <i>// non-named parameter version</i>
 template &lt;class Graph, class <a href="DFSVisitor.html">DFSVisitor</a>, class ColorMap&gt;
 void depth_first_search(const Graph&amp; g, DFSVisitor vis, ColorMap color)

 template &lt;class Graph, class <a href="DFSVisitor.html">DFSVisitor</a>, class ColorMap&gt;
 void depth_first_search(const Graph&amp; g, DFSVisitor vis, ColorMap color,
                         typename graph_traits&lt;Graph&gt;::vertex_descriptor start)

 </PRE>

 <p>
 The <tt>depth_first_search()</tt> function performs a depth-first
 traversal of the vertices in a directed graph.  When
 possible, a depth-first traversal chooses a vertex adjacent to the
 current vertex to visit next. If all adjacent vertices have already
 been discovered, or there are no adjacent vertices, then the algorithm
 backtracks to the last vertex that had undiscovered neighbors. Once
 all reachable vertices have been visited, the algorithm selects from
 any remaining undiscovered vertices and continues the traversal. The
 algorithm finishes when all vertices have been visited. Depth-first
 search is useful for categorizing edges in a graph, and for imposing
 an ordering on the vertices. Section <a
 href="./graph_theory_review.html#sec:dfs-algorithm">Depth-First
 Search</a> describes the various properties of DFS and walks through
 an example.
 </p>

 <p>
 Similar to BFS, color markers are used to keep track of which vertices
 have been discovered. White marks vertices that have yet to be
 discovered, gray marks a vertex that is discovered but still has
 vertices adjacent to it that are undiscovered. A black vertex is
 discovered vertex that is not adjacent to any white vertices.
 <p>

 <p>
 The <tt>depth_first_search()</tt> function invokes user-defined
 actions at certain event-points within the algorithm. This provides a
 mechanism for adapting the generic DFS algorithm to the many
 situations in which it can be used.  In the pseudo-code below, the
 event points for DFS are the labels on
 the right. The user-defined actions must be provided in the form of a
 visitor object, that is, an object whose type meets the requirements
 for a <a href="./DFSVisitor.html">DFS Visitor</a>. In the pseudo-code
 we show the algorithm computing predecessors <i>p</i>, discover time
 <i>d</i> and finish time <i>t</i>.  By default, the
 <tt>depth_first_search()</tt> function does not compute these
 properties, however there are pre-defined visitors such as <a
 href="./predecessor_recorder.html"><tt>predecessor_recorder</tt></a>
 and <a href="./time_stamper.html"><tt>time_stamper</tt></a> that can
 be used to do this.
 </p>

 <table>
 <tr>
 <td valign="top">
 <pre>
 DFS(<i>G</i>)
   <b>for</b> each vertex <i>u in V</i>
     <i>color[u] :=</i> WHITE
     <i>p[u] = u</i>
   <b>end for</b>
   <i>time := 0</i>
   <b>if</b> there is a starting vertex <i>s</i>
     <b>call</b> DFS-VISIT(<i>G</i>, <i>s</i>)
   <b>for</b> each vertex <i>u in V</i>
     <b>if</b> <i>color[u] =</i> WHITE
       <b>call</b> DFS-VISIT(<i>G</i>, <i>u</i>)
   <b>end for</b>
   return (<i>p</i>,<i>d_time</i>,<i>f_time</i>) <br>
 DFS-VISIT(<i>G</i>, <i>u</i>)
   <i>color[u] :=</i> GRAY
   <i>d_time[u] := time := time + 1</i>
   <b>for</b> each <i>v in Adj[u]</i>
     <b>if</b> (<i>color[v] =</i> WHITE)
       <i>p[v] = u</i>
       <b>call</b> DFS-VISIT(<i>G</i>, <i>v</i>)
     <b>else if</b> (<i>color[v] =</i> GRAY)
       <i>...</i>
     <b>else if</b> (<i>color[v] =</i> BLACK)
       <i>...</i>
   <b>end for</b>
   <i>color[u] :=</i> BLACK
   <i>f_time[u] := time := time + 1</i>
 <pre>
 </td>
 <td valign="top">
 <pre>
 -
 -
 initialize vertex <i>u</i>
 -
 -
 -
 -
 start vertex <i>s</i>
 -
 -
 start vertex <i>u</i>
 -
 -
 -
 -
 discover vertex <i>u</i>
 -
 examine edge <i>(u,v)</i>
 -
 <i>(u,v)</i> is a tree edge
 -
 -
 <i>(u,v)</i> is a back edge
 -
 <i>(u,v)</i> is a cross or forward edge
 -
 finish vertex <i>u</i>
 -
 </pre>
 </td>
 </tr>
 </table>


 <H3>Where Defined</H3>

 <P>
 <a href="../../../boost/graph/depth_first_search.hpp"><TT>boost/graph/depth_first_search.hpp</TT></a>

 <h3>Parameters</h3>

 IN: <tt>Graph&amp; g</tt>
 <blockquote>
   A directed graph. The graph type must
   be a model of <a href="./IncidenceGraph.html">Incidence Graph</a>
   and <a href="./VertexListGraph.html">Vertex List Graph</a>.<br>

   <b>Python</b>: The parameter is named <tt>graph</tt>.
 </blockquote>


 <h3>Named Parameters</h3>

 IN: <tt>visitor(DFSVisitor vis)</tt>
 <blockquote>
   A visitor object that is invoked inside the algorithm at the
   event-points specified by the <a href="./DFSVisitor.html">DFS
   Visitor</a> concept. The visitor object is passed by value <a
   href="#1">[1]</a>. <br> <b>Default:</b>
   <tt>dfs_visitor&lt;null_visitor&gt;</tt><br>

   <b>Python</b>: The parameter should be an object that derives from
   the <a href="DFSVisitor.html#python"><tt>DFSVisitor</tt></a> type of
   the graph.
 </blockquote>

 UTIL/OUT: <tt>color_map(ColorMap color)</tt>
 <blockquote>
   This is used by the algorithm to keep track of its progress through
   the graph. The type <tt>ColorMap</tt> must be a model of <a
   href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write
   Property Map</a> and its key type must be the graph's vertex
   descriptor type and the value type of the color map must model
   <a href="./ColorValue.html">ColorValue</a>.<br>
   <b>Default:</b> an <a
   href="../../property_map/doc/iterator_property_map.html">
   </tt>iterator_property_map</tt></a> created from a
   <tt>std::vector</tt> of <tt>default_color_type</tt> of size
   <tt>num_vertices(g)</tt> and using the <tt>i_map</tt> for the index
   map.<br>

    <b>Python</b>: The color map must be a <tt>vertex_color_map</tt> for
   the graph.
 </blockquote>

 IN: <tt>root_vertex(typename
 graph_traits&lt;VertexListGraph&gt;::vertex_descriptor start)</tt>
 <blockquote>
   This specifies the vertex that the depth-first search should
   originate from. The type is the type of a vertex descriptor for the
   given graph.<br>
   <b>Default:</b> <tt>*vertices(g).first</tt><br>
 </blockquote>

 IN: <tt>vertex_index_map(VertexIndexMap i_map)</tt>
 <blockquote>
   This maps each vertex to an integer in the range <tt>[0,
   num_vertices(g))</tt>. This parameter is only necessary when the
   default color property map is used. The type <tt>VertexIndexMap</tt>
   must be a model of <a
   href="../../property_map/doc/ReadablePropertyMap.html">Readable Property
   Map</a>. The value type of the map must be an integer type. The
   vertex descriptor type of the graph needs to be usable as the key
   type of the map.<br>

   <b>Default:</b> <tt>get(vertex_index, g)</tt>.
     Note: if you use this default, make sure your graph has
     an internal <tt>vertex_index</tt> property. For example,
     <tt>adjacency_list</tt> with <tt>VertexList=listS</tt> does
     not have an internal <tt>vertex_index</tt> property.<br>

   <b>Python</b>: Unsupported parameter.
 </blockquote>

 <P>

 <H3><A NAME="SECTION001340300000000000000">
 Complexity</A>
 </H3>

 <P>
 The time complexity is <i>O(E + V)</i>.

 <P>

 <h3>Visitor Event Points</h3>

 <ul>

 <li><b><tt>vis.initialize_vertex(s, g)</tt></b> is invoked on every
   vertex of the graph before the start of the graph search.

 <li><b><tt>vis.start_vertex(s, g)</tt></b> is invoked on the source
   vertex once before the start of the search.

 <li><b><tt>vis.discover_vertex(u, g)</tt></b> is invoked when a vertex
   is encountered for the first time.

 <li><b><tt>vis.examine_edge(e, g)</tt></b> is invoked on every out-edge
   of each vertex after it is discovered.

 <li><b><tt>vis.tree_edge(e, g)</tt></b> is invoked on each edge as it
   becomes a member of the edges that form the search tree. If you
   wish to record predecessors, do so at this event point.

 <li><b><tt>vis.back_edge(e, g)</tt></b> is invoked on the back edges in
   the graph.

 <li><b><tt>vis.forward_or_cross_edge(e, g)</tt></b> is invoked on
   forward or cross edges in the graph. In an undirected graph this
   method is never called.

 <li><b><tt>vis.finish_vertex(u, g)</tt></b> is invoked on a vertex after
   all of its out edges have been added to the search tree and all of
   the adjacent vertices have been discovered (but before their
   out-edges have been examined).

 </ul>


 <H3>Example</H3>

 <P>
 The example in <a href="../example/dfs-example.cpp">
 <TT>examples/dfs-example.cpp</TT></a> shows DFS applied to the graph in
 <A HREF="./graph_theory_review.html#fig:dfs-example">Figure 1</A>.

 <h3>See Also</h3>

 <a href="./depth_first_visit.html"><tt>depth_first_visit</tt></a>
 <a href="./undirected_dfs.html"><tt>undirected_dfs</tt></a>

 <h3>Notes</h3>

 <p><a name="1">[1]</a>
   Since the visitor parameter is passed by value, if your visitor
   contains state then any changes to the state during the algorithm
   will be made to a copy of the visitor object, not the visitor object
   passed in. Therefore you may want the visitor to hold this state by
   pointer or reference.

 <br>
 <HR>
 <TABLE>
 <TR valign=top>
 <TD nowrap>Copyright &copy; 2000-2001</TD><TD>
 <A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>,
 Indiana University (<A
 HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br>
 <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>
 <A HREF="http://www.osl.iu.edu/~lums">Andrew Lumsdaine</A>,
 Indiana University (<A
 HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
 </TD></TR></TABLE>

 </BODY>
 </HTML>
	<HTML>
	<!--
	Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 2000

	Distributed under the Boost Software License, Version 1.0.
	(See accompanying file LICENSE_1_0.txt or copy at
	http://www.boost.org/LICENSE_1_0.txt)
	-->
	<Head>
	<Title>Boost Graph Library: Depth-First Search</Title>
	<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
	ALINK="#ff0000">
	<IMG SRC="../../../boost.png"
	ALT="C++ Boost" width="277" height="86">

	<BR Clear>

	<H1><A NAME="sec:depth-first-search"></A><img src="figs/python.gif" alt="(Python)"/>
	<TT>depth_first_search</TT>
	</H1>

	<P>
	<PRE>
	<i>// named parameter version</i>
	template <class Graph, class class P, class T, class R>
	void depth_first_search(Graph& G,
	const bgl_named_params<P, T, R>& params);

	<i>// non-named parameter version</i>
	template <class Graph, class <a href="DFSVisitor.html">DFSVisitor</a>, class ColorMap>
	void depth_first_search(const Graph& g, DFSVisitor vis, ColorMap color)

	template <class Graph, class <a href="DFSVisitor.html">DFSVisitor</a>, class ColorMap>
	void depth_first_search(const Graph& g, DFSVisitor vis, ColorMap color,
	typename graph_traits<Graph>::vertex_descriptor start)

	</PRE>

	<p>
	The <tt>depth_first_search()</tt> function performs a depth-first
	traversal of the vertices in a directed graph. When
	possible, a depth-first traversal chooses a vertex adjacent to the
	current vertex to visit next. If all adjacent vertices have already
	been discovered, or there are no adjacent vertices, then the algorithm
	backtracks to the last vertex that had undiscovered neighbors. Once
	all reachable vertices have been visited, the algorithm selects from
	any remaining undiscovered vertices and continues the traversal. The
	algorithm finishes when all vertices have been visited. Depth-first
	search is useful for categorizing edges in a graph, and for imposing
	an ordering on the vertices. Section <a
	href="./graph_theory_review.html#sec:dfs-algorithm">Depth-First
	Search</a> describes the various properties of DFS and walks through
	an example.
	</p>

	<p>
	Similar to BFS, color markers are used to keep track of which vertices
	have been discovered. White marks vertices that have yet to be
	discovered, gray marks a vertex that is discovered but still has
	vertices adjacent to it that are undiscovered. A black vertex is
	discovered vertex that is not adjacent to any white vertices.
	<p>

	<p>
	The <tt>depth_first_search()</tt> function invokes user-defined
	actions at certain event-points within the algorithm. This provides a
	mechanism for adapting the generic DFS algorithm to the many
	situations in which it can be used. In the pseudo-code below, the
	event points for DFS are the labels on
	the right. The user-defined actions must be provided in the form of a
	visitor object, that is, an object whose type meets the requirements
	for a <a href="./DFSVisitor.html">DFS Visitor</a>. In the pseudo-code
	we show the algorithm computing predecessors <i>p</i>, discover time
	<i>d</i> and finish time <i>t</i>. By default, the
	<tt>depth_first_search()</tt> function does not compute these
	properties, however there are pre-defined visitors such as <a
	href="./predecessor_recorder.html"><tt>predecessor_recorder</tt></a>
	and <a href="./time_stamper.html"><tt>time_stamper</tt></a> that can
	be used to do this.
	</p>

	<table>
	<tr>
	<td valign="top">
	<pre>
	DFS(<i>G</i>)
	<b>for</b> each vertex <i>u in V</i>
	<i>color[u] :=</i> WHITE
	<i>p[u] = u</i>
	<b>end for</b>
	<i>time := 0</i>
	<b>if</b> there is a starting vertex <i>s</i>
	<b>call</b> DFS-VISIT(<i>G</i>, <i>s</i>)
	<b>for</b> each vertex <i>u in V</i>
	<b>if</b> <i>color[u] =</i> WHITE
	<b>call</b> DFS-VISIT(<i>G</i>, <i>u</i>)
	<b>end for</b>
	return (<i>p</i>,<i>d_time</i>,<i>f_time</i>) <br>
	DFS-VISIT(<i>G</i>, <i>u</i>)
	<i>color[u] :=</i> GRAY
	<i>d_time[u] := time := time + 1</i>
	<b>for</b> each <i>v in Adj[u]</i>
	<b>if</b> (<i>color[v] =</i> WHITE)
	<i>p[v] = u</i>
	<b>call</b> DFS-VISIT(<i>G</i>, <i>v</i>)
	<b>else if</b> (<i>color[v] =</i> GRAY)
	<i>...</i>
	<b>else if</b> (<i>color[v] =</i> BLACK)
	<i>...</i>
	<b>end for</b>
	<i>color[u] :=</i> BLACK
	<i>f_time[u] := time := time + 1</i>
	<pre>
	</td>
	<td valign="top">
	<pre>
	-
	-
	initialize vertex <i>u</i>
	-
	-
	-
	-
	start vertex <i>s</i>
	-
	-
	start vertex <i>u</i>
	-
	-
	-
	-
	discover vertex <i>u</i>
	-
	examine edge <i>(u,v)</i>
	-
	<i>(u,v)</i> is a tree edge
	-
	-
	<i>(u,v)</i> is a back edge
	-
	<i>(u,v)</i> is a cross or forward edge
	-
	finish vertex <i>u</i>
	-
	</pre>
	</td>
	</tr>
	</table>



	<H3>Where Defined</H3>

	<P>
	<a href="../../../boost/graph/depth_first_search.hpp"><TT>boost/graph/depth_first_search.hpp</TT></a>

	<h3>Parameters</h3>

	IN: <tt>Graph& g</tt>
	<blockquote>
	A directed graph. The graph type must
	be a model of <a href="./IncidenceGraph.html">Incidence Graph</a>
	and <a href="./VertexListGraph.html">Vertex List Graph</a>.<br>

	<b>Python</b>: The parameter is named <tt>graph</tt>.
	</blockquote>


	<h3>Named Parameters</h3>

	IN: <tt>visitor(DFSVisitor vis)</tt>
	<blockquote>
	A visitor object that is invoked inside the algorithm at the
	event-points specified by the <a href="./DFSVisitor.html">DFS
	Visitor</a> concept. The visitor object is passed by value <a
	href="#1">[1]</a>. <br> <b>Default:</b>
	<tt>dfs_visitor<null_visitor></tt><br>

	<b>Python</b>: The parameter should be an object that derives from
	the <a href="DFSVisitor.html#python"><tt>DFSVisitor</tt></a> type of
	the graph.
	</blockquote>

	UTIL/OUT: <tt>color_map(ColorMap color)</tt>
	<blockquote>
	This is used by the algorithm to keep track of its progress through
	the graph. The type <tt>ColorMap</tt> must be a model of <a
	href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write
	Property Map</a> and its key type must be the graph's vertex
	descriptor type and the value type of the color map must model
	<a href="./ColorValue.html">ColorValue</a>.<br>
	<b>Default:</b> an <a
	href="../../property_map/doc/iterator_property_map.html">
	</tt>iterator_property_map</tt></a> created from a
	<tt>std::vector</tt> of <tt>default_color_type</tt> of size
	<tt>num_vertices(g)</tt> and using the <tt>i_map</tt> for the index
	map.<br>

	<b>Python</b>: The color map must be a <tt>vertex_color_map</tt> for
	the graph.
	</blockquote>

	IN: <tt>root_vertex(typename
	graph_traits<VertexListGraph>::vertex_descriptor start)</tt>
	<blockquote>
	This specifies the vertex that the depth-first search should
	originate from. The type is the type of a vertex descriptor for the
	given graph.<br>
	<b>Default:</b> <tt>*vertices(g).first</tt><br>
	</blockquote>

	IN: <tt>vertex_index_map(VertexIndexMap i_map)</tt>
	<blockquote>
	This maps each vertex to an integer in the range <tt>[0,
	num_vertices(g))</tt>. This parameter is only necessary when the
	default color property map is used. The type <tt>VertexIndexMap</tt>
	must be a model of <a
	href="../../property_map/doc/ReadablePropertyMap.html">Readable Property
	Map</a>. The value type of the map must be an integer type. The
	vertex descriptor type of the graph needs to be usable as the key
	type of the map.<br>

	<b>Default:</b> <tt>get(vertex_index, g)</tt>.
	Note: if you use this default, make sure your graph has
	an internal <tt>vertex_index</tt> property. For example,
	<tt>adjacency_list</tt> with <tt>VertexList=listS</tt> does
	not have an internal <tt>vertex_index</tt> property.<br>

	<b>Python</b>: Unsupported parameter.
	</blockquote>

	<P>

	<H3><A NAME="SECTION001340300000000000000">
	Complexity</A>
	</H3>

	<P>
	The time complexity is <i>O(E + V)</i>.

	<P>

	<h3>Visitor Event Points</h3>

	<ul>

	<li><b><tt>vis.initialize_vertex(s, g)</tt></b> is invoked on every
	vertex of the graph before the start of the graph search.

	<li><b><tt>vis.start_vertex(s, g)</tt></b> is invoked on the source
	vertex once before the start of the search.

	<li><b><tt>vis.discover_vertex(u, g)</tt></b> is invoked when a vertex
	is encountered for the first time.

	<li><b><tt>vis.examine_edge(e, g)</tt></b> is invoked on every out-edge
	of each vertex after it is discovered.

	<li><b><tt>vis.tree_edge(e, g)</tt></b> is invoked on each edge as it
	becomes a member of the edges that form the search tree. If you
	wish to record predecessors, do so at this event point.

	<li><b><tt>vis.back_edge(e, g)</tt></b> is invoked on the back edges in
	the graph.

	<li><b><tt>vis.forward_or_cross_edge(e, g)</tt></b> is invoked on
	forward or cross edges in the graph. In an undirected graph this
	method is never called.

	<li><b><tt>vis.finish_vertex(u, g)</tt></b> is invoked on a vertex after
	all of its out edges have been added to the search tree and all of
	the adjacent vertices have been discovered (but before their
	out-edges have been examined).

	</ul>


	<H3>Example</H3>

	<P>
	The example in <a href="../example/dfs-example.cpp">
	<TT>examples/dfs-example.cpp</TT></a> shows DFS applied to the graph in
	<A HREF="./graph_theory_review.html#fig:dfs-example">Figure 1</A>.

	<h3>See Also</h3>

	<a href="./depth_first_visit.html"><tt>depth_first_visit</tt></a>
	<a href="./undirected_dfs.html"><tt>undirected_dfs</tt></a>

	<h3>Notes</h3>

	<p><a name="1">[1]</a>
	Since the visitor parameter is passed by value, if your visitor
	contains state then any changes to the state during the algorithm
	will be made to a copy of the visitor object, not the visitor object
	passed in. Therefore you may want the visitor to hold this state by
	pointer or reference.

	<br>
	<HR>
	<TABLE>
	<TR valign=top>
	<TD nowrap>Copyright © 2000-2001</TD><TD>
	<A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>,
	Indiana University (<A
	HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br>
	<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>
	<A HREF="http://www.osl.iu.edu/~lums">Andrew Lumsdaine</A>,
	Indiana University (<A
	HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
	</TD></TR></TABLE>

	</BODY>
	</HTML>