1<HTML> 2<!-- 3 Copyright (c) Jeremy Siek 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 Visit</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<H2><A NAME="sec:dfs"></A> 19<img src="figs/python.gif" alt="(Python)"/> 20<TT>depth_first_visit</TT> 21</H2> 22 23 24<P> 25<PRE> 26template <class <a href="./IncidenceGraph.html">IncidenceGraph</a>, class <a href="./DFSVisitor.html">DFSVisitor</a>, class ColorMap> 27void depth_first_visit(IncidenceGraph& g, 28 typename graph_traits<IncidenceGraph>::vertex_descriptor s, 29 DFSVisitor& vis, ColorMap color) 30 31template <class <a href="./IncidenceGraph.html">IncidenceGraph</a>, class <a href="./DFSVisitor.html">DFSVisitor</a>, class ColorMap, 32 class TerminatorFunc> 33void depth_first_visit(IncidenceGraph& g, 34 typename graph_traits<IncidenceGraph>::vertex_descriptor s, 35 DFSVisitor& vis, ColorMap color, TerminatorFunc func = TerminatorFunc()) 36</PRE> 37 38<P> 39This function visits all of the vertices in the same connected 40component as the source vertex <tt>s</tt>, using the <a 41href="./graph_theory_review.html#sec:dfs-algorithm">depth-first 42pattern</a>. The main purpose of the function is for the 43implementation of <TT>depth_first_search()</TT> though sometimes it is 44useful on its own. 45 46<p> 47The <tt>DFSVisitor</tt> supplied by the user determines what 48actions are taken at each event-point within the algorithm. 49 50<p> 51The <tt>ColorMap</tt> is used by the algorithm to keep track 52of which vertices have been visited. 53 54<p>The second variant can be used, for example, to find all marked vertices 55reachable from a start vertex by a path which does not contain any another 56marked vertices. 57 58 59<P> 60 61<h3>Where Defined:</h3> 62 63<a href="../../../boost/graph/depth_first_search.hpp"><TT>boost/graph/depth_first_search.hpp</TT></a> 64 65 66<h3>Parameters</h3> 67 68IN <tt>IncidenceGraph& g</tt> 69<blockquote> 70A directed or undirected graph. The graph's type must be a model of 71<a href="./IncidenceGraph.html">Incidence Graph</a>.<br> 72 73<b>Python</b>: The parameter is named <tt>graph</tt>. 74</blockquote> 75 76IN: <tt>vertex_descriptor s</tt> 77<blockquote> 78 The source vertex from which to start the search.<br> 79 80 <b>Python</b>: The parameter is named <tt>root_vertex</tt>. 81</blockquote> 82 83IN: <tt>DFSVisitor visitor</tt> 84<blockquote> 85 A visitor object that is invoked inside the algorithm at the 86 event-points specified by the <a href="./DFSVisitor.html">DFS 87 Visitor</a> concept. The visitor object is passed by value <a 88 href="#1">[1]</a>.<br> 89 90 <b>Python</b>: The parameter should be an object that derives from 91 the <a href="DFSVisitor.html#python"><tt>DFSVisitor</tt></a> type of 92 the graph. 93</blockquote> 94 95UTIL: <tt>ColorMap color</tt> 96<blockquote> 97 This is used by the algorithm to keep track of its progress through 98 the graph. The type <tt>ColorMap</tt> must be a model of <a 99 href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write 100 Property Map</a> and its key type must be the graph's vertex 101 descriptor type and the value type of the color map map must model 102 <a href="./ColorValue.html">Color Value</a>.<br> 103 104 <b>Python</b>: The color map must be a <tt>vertex_color_map</tt> for 105 the graph. 106</blockquote> 107 108IN: <tt>TerminatorFunc func</tt> 109<blockquote> 110A function object callable with two parameters - the descriptor of 111vertex and the graph instance - and returning bool. The call is made 112immediately after call to 'discover_vertex' visitor 113event. If <tt>true</tt> is returned, the out edges of the vertex are 114not examined, as if they don't exist.<br> 115 116 <b>Python</b>: Unsupported parameter. 117</blockquote> 118<P> 119 120<h3>Complexity</h3> 121 122Time complexity is <i>O(E)</i>. 123 124 125<h3>Notes</h3> 126 127<p><a name="1">[1]</a> 128 Since the visitor parameter is passed by value, if your visitor 129 contains state then any changes to the state during the algorithm 130 will be made to a copy of the visitor object, not the visitor object 131 passed in. Therefore you may want the visitor to hold this state by 132 pointer or reference. 133 134 135<br> 136<HR> 137<TABLE> 138<TR valign=top> 139<TD nowrap>Copyright © 2000-2001</TD><TD> 140<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>) 141</TD></TR></TABLE> 142 143</BODY> 144</HTML> 145
