3 Copyright (c) Jeremy Siek 2000
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)
10 <Title>Boost Graph Library: Depth-First Visit
</Title>
11 <BODY BGCOLOR=
"#ffffff" LINK=
"#0000ee" TEXT=
"#000000" VLINK=
"#551a8b"
13 <IMG SRC=
"../../../boost.png"
14 ALT=
"C++ Boost" width=
"277" height=
"86">
18 <H2><A NAME=
"sec:dfs"></A>
19 <img src=
"figs/python.gif" alt=
"(Python)"/>
20 <TT>depth_first_visit
</TT>
26 template
<class
<a href=
"./IncidenceGraph.html">IncidenceGraph
</a>, class
<a href=
"./DFSVisitor.html">DFSVisitor
</a>, class ColorMap
>
27 void depth_first_visit(IncidenceGraph& g,
28 typename graph_traits
<IncidenceGraph
>::vertex_descriptor s,
29 DFSVisitor
& vis, ColorMap color)
31 template
<class
<a href=
"./IncidenceGraph.html">IncidenceGraph
</a>, class
<a href=
"./DFSVisitor.html">DFSVisitor
</a>, class ColorMap,
32 class TerminatorFunc
>
33 void depth_first_visit(IncidenceGraph& g,
34 typename graph_traits
<IncidenceGraph
>::vertex_descriptor s,
35 DFSVisitor
& vis, ColorMap color, TerminatorFunc func = TerminatorFunc())
39 This function visits all of the vertices in the same connected
40 component as the source vertex
<tt>s
</tt>, using the
<a
41 href=
"./graph_theory_review.html#sec:dfs-algorithm">depth-first
42 pattern
</a>. The main purpose of the function is for the
43 implementation of
<TT>depth_first_search()
</TT> though sometimes it is
47 The
<tt>DFSVisitor
</tt> supplied by the user determines what
48 actions are taken at each event-point within the algorithm.
51 The
<tt>ColorMap
</tt> is used by the algorithm to keep track
52 of which vertices have been visited.
54 <p>The second variant can be used, for example, to find all marked vertices
55 reachable from a start vertex by a path which does not contain any another
61 <h3>Where Defined:
</h3>
63 <a href=
"../../../boost/graph/depth_first_search.hpp"><TT>boost/graph/depth_first_search.hpp
</TT></a>
68 IN
<tt>IncidenceGraph
& g
</tt>
70 A directed or undirected graph. The graph's type must be a model of
71 <a href=
"./IncidenceGraph.html">Incidence Graph
</a>.
<br>
73 <b>Python
</b>: The parameter is named
<tt>graph
</tt>.
76 IN:
<tt>vertex_descriptor s
</tt>
78 The source vertex from which to start the search.
<br>
80 <b>Python
</b>: The parameter is named
<tt>root_vertex
</tt>.
83 IN:
<tt>DFSVisitor visitor
</tt>
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>
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
95 UTIL:
<tt>ColorMap color
</tt>
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>
104 <b>Python
</b>: The color map must be a
<tt>vertex_color_map
</tt> for
108 IN:
<tt>TerminatorFunc func
</tt>
110 A function object callable with two parameters - the descriptor of
111 vertex and the graph instance - and returning bool. The call is made
112 immediately after call to 'discover_vertex' visitor
113 event. If
<tt>true
</tt> is returned, the out edges of the vertex are
114 not examined, as if they don't exist.
<br>
116 <b>Python
</b>: Unsupported parameter.
122 Time complexity is
<i>O(E)
</i>.
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.
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>)