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>DFS Visitor</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><img src="figs/python.gif" alt="(Python)"/>DFS Visitor Concept</H1> 19 20This concept defines the visitor interface for <a 21href="./depth_first_search.html"><tt>depth_first_search()</tt></a>. 22Users can define a class with the DFS Visitor interface and pass an 23object of the class to <tt>depth_first_search()</tt>, thereby 24augmenting the actions taken during the graph search. 25 26<h3>Refinement of</h3> 27 28<a href="../../utility/CopyConstructible.html">Copy Constructible</a> 29(copying a visitor should be a lightweight operation). 30 31<h3>Notation</h3> 32 33<Table> 34<TR> 35<TD><tt>V</tt></TD> 36<TD>A type that is a model of DFS Visitor.</TD> 37</TR> 38 39<TR> 40<TD><tt>vis</tt></TD> 41<TD>An object of type <tt>V</tt>.</TD> 42</TR> 43 44<TR> 45<TD><tt>G</tt></TD> 46<TD>A type that is a model of Graph.</TD> 47</TR> 48 49<TR> 50<TD><tt>g</tt></TD> 51<TD>An object of type <tt>G</tt>.</TD> 52</TR> 53 54<TR> 55<TD><tt>e</tt></TD> 56<TD>An object of type <tt>boost::graph_traits<G>::edge_descriptor</tt>.</TD> 57</TR> 58 59<TR> 60<TD><tt>s,u</tt></TD> 61<TD>An object of type <tt>boost::graph_traits<G>::vertex_descriptor</tt>.</TD> 62</TR> 63 64</table> 65 66<h3>Associated Types</h3> 67 68none 69<p> 70 71<h3>Valid Expressions</h3> 72 73<table border> 74<tr> 75<th>Name</th><th>Expression</th><th>Return Type</th><th>Description</th> 76</tr> 77 78<tr> 79<td>Initialize Vertex</td> 80<td><tt>vis.initialize_vertex(s, g)</tt></td> 81<td><tt>void</tt></td> 82<td> 83This is invoked on every vertex of the graph before the start of the 84graph search. 85</td> 86</tr> 87 88<tr> 89<td>Start Vertex</td> 90<td><tt>vis.start_vertex(s, g)</tt></td> 91<td><tt>void</tt></td> 92<td> 93This is invoked on the source vertex once before the start of the 94search. 95</td> 96</tr> 97 98<tr> 99<td>Discover Vertex</td> 100<td><tt>vis.discover_vertex(u, g)</tt></td> 101<td><tt>void</tt></td> 102<td> 103This is invoked when a vertex is encountered for the first time. 104</td> 105</tr> 106 107<tr> 108<td>Examine Edge</td> 109<td><tt>vis.examine_edge(e, g)</tt></td> 110<td><tt>void</tt></td> 111<td> 112This is invoked on every out-edge of each vertex after it is discovered. 113</td> 114</tr> 115 116 117<tr> 118<td>Tree Edge</td> 119<td><tt>vis.tree_edge(e, g)</tt></td> 120<td><tt>void</tt></td> 121<td> 122This is invoked on each edge as it becomes a member of the edges that 123form the search tree.</td> 124</tr> 125 126<tr> 127<td>Back Edge</td> 128<td><tt>vis.back_edge(e, g)</tt></td> 129<td><tt>void</tt></td> 130<td> 131This is invoked on the back edges in the graph. For an undirected 132graph there is some ambiguity between tree edges and back edges since 133the edge <i>(u,v)</i> and <i>(v,u)</i> are the same edge, but both the 134<tt>tree_edge()</tt> and <tt>back_edge()</tt> functions will be 135invoked. One way to resolve this ambiguity is to record the tree 136edges, and then disregard the back-edges that are already marked as 137tree edges. An easy way to record tree edges is to record 138predecessors at the <tt>tree_edge</tt> event point. 139</td> 140</tr> 141 142<tr> 143<td>Forward or Cross Edge</td> 144<td><tt>vis.forward_or_cross_edge(e, g)</tt></td> 145<td><tt>void</tt></td> 146<td> 147This is invoked on forward or cross edges in the graph. In an 148undirected graph this method is never called. 149</td> 150</tr> 151 152<tr> 153<td>Finish Edge</td> 154<td><tt>vis.finish_edge(e, g)</tt></td> 155<td><tt>void</tt></td> 156<td> 157This is invoked on each non-tree edge as well as on each tree edge after 158<tt>finish_vertex</tt> has been called on its target vertex.</td> 159</tr> 160 161<tr> 162<td>Finish Vertex</td> 163<td><tt>vis.finish_vertex(u, g)</tt></td> 164<td><tt>void</tt></td> 165<td> 166This is invoked on vertex <tt>u</tt> after <tt>finish_vertex</tt> has 167been called for all the vertices in the DFS-tree rooted at vertex 168<tt>u</tt>. If vertex <tt>u</tt> is a leaf in the DFS-tree, then 169the <tt>finish_vertex</tt> function is called on <tt>u</tt> after 170all the out-edges of <tt>u</tt> have been examined. 171</td> 172</tr> 173 174</table> 175 176<h3>Models</h3> 177 178<ul> 179 <li><a href="./dfs_visitor.html"><tt>dfs_visitor</tt></a> 180</ul> 181 182<a name="python"></a> 183<h3>Python</h3> 184 185To implement a model of the <tt>DFSVisitor</tt> concept in Python, 186create a new class that derives from the <tt>DFSVisitor</tt> type of 187the graph, which will be 188named <tt><i>GraphType</i>.DFSVisitor</tt>. The events and syntax are 189the same as with visitors in C++. Here is an example for the 190Python <tt>bgl.Graph</tt> graph type: 191 192<pre> 193class count_tree_edges_dfs_visitor(bgl.Graph.DFSVisitor): 194 def __init__(self, name_map): 195 bgl.Graph.DFSVisitor.__init__(self) 196 self.name_map = name_map 197 198 def tree_edge(self, e, g): 199 (u, v) = (g.source(e), g.target(e)) 200 print "Tree edge ", 201 print self.name_map[u], 202 print " -> ", 203 print self.name_map[v] 204</pre> 205 206<br> 207<HR> 208<TABLE> 209<TR valign=top> 210<TD nowrap>Copyright © 2000-2001</TD><TD> 211<A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>, 212Indiana University (<A 213HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br> 214<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> 215<A HREF="https://homes.cs.washington.edu/~al75">Andrew Lumsdaine</A>, 216Indiana University (<A 217HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>) 218</TD></TR></TABLE> 219 220</BODY> 221</HTML> 222