Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_33_1/libs/graph/doc/BFSVisitor.html @ 12

Last change on this file since 12 was 12, checked in by landauf, 18 years ago

added boost
File size: 5.5 KB
Line 
1<HTML>
2<!--
3  -- Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 2000
4  --
5  -- Permission to use, copy, modify, distribute and sell this software
6  -- and its documentation for any purpose is hereby granted without fee,
7  -- provided that the above copyright notice appears in all copies and
8  -- that both that copyright notice and this permission notice appear
9  -- in supporting documentation.  We make no
10  -- representations about the suitability of this software for any
11  -- purpose.  It is provided "as is" without express or implied warranty.
12  -->
13<Head>
14<Title>Boost Graph Library: BFSVisitor</Title>
15<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 
16        ALINK="#ff0000"> 
17<IMG SRC="../../../boost.png" 
18     ALT="C++ Boost" width="277" height="86"> 
19
20<BR Clear>
21
22<H1><img src="figs/python.gif" alt="(Python)"/>BFS Visitor Concept</H1>
23
24This concept defines the visitor interface for <a
25href="./breadth_first_search.html"><tt>breadth_first_search()</tt></a>.
26Users can define a class with the BFS Visitor interface and pass and
27object of the class to <tt>breadth_first_search()</tt>, thereby
28augmenting the actions taken during the graph search.
29
30<h3>Refinement of</h3>
31
32<a href="../../utility/CopyConstructible.html">Copy Constructible</a>
33(copying a visitor should be a lightweight operation).
34
35
36<h3>Notation</h3>
37
38<Table>
39<TR>
40<TD><tt>V</tt></TD>
41<TD>A type that is a model of BFS Visitor.</TD>
42</TR>
43
44<TR>
45<TD><tt>vis</tt></TD>
46<TD>An object of type <tt>V</tt>.</TD>
47</TR>
48
49<TR>
50<TD><tt>G</tt></TD>
51<TD>A type that is a model of Graph.</TD>
52</TR>
53
54<TR>
55<TD><tt>g</tt></TD>
56<TD>An object of type <tt>G</tt>.</TD>
57</TR>
58
59<TR>
60<TD><tt>e</tt></TD>
61<TD>An object of type <tt>boost::graph_traits&lt;G&gt;::edge_descriptor</tt>.</TD>
62</TR>
63
64<TR>
65<TD><tt>s,u</tt></TD>
66<TD>An object of type <tt>boost::graph_traits&lt;G&gt;::vertex_descriptor</tt>.</TD>
67</TR>
68
69</table>
70
71<h3>Associated Types</h3>
72
73none
74<p>
75
76<h3>Valid Expressions</h3>
77
78<table border>
79<tr>
80<th>Name</th><th>Expression</th><th>Return Type</th><th>Description</th>
81</tr>
82
83<tr>
84<td>Initialize Vertex</td>
85<td><tt>vis.initialize_vertex(s, g)</tt></td>
86<td><tt>void</tt></td>
87<td>
88This is invoked on every vertex of the graph before the start of the
89graph search.
90</td>
91</tr>
92
93<tr>
94<td>Discover Vertex</td>
95<td><tt>vis.discover_vertex(u, g)</tt></td>
96<td><tt>void</tt></td>
97<td>
98This is invoked when a vertex is encountered for the first time.
99</td>
100</tr>
101
102<tr>
103<td>Examine Vertex</td>
104<td><tt>vis.examine_vertex(u, g)</tt></td>
105<td><tt>void</tt></td>
106<td>
107This is invoked on a vertex as it is popped from the queue. This
108happens immediately before <tt>examine_edge()</tt> is invoked
109on each of the out-edges of vertex <tt>u</tt>.
110</td>
111</tr>
112
113<tr>
114<td>Examine Edge</td>
115<td><tt>vis.examine_edge(e, g)</tt></td>
116<td><tt>void</tt></td>
117<td>
118This is invoked on every out-edge of each vertex after it is discovered.
119</td>
120</tr>
121
122
123<tr>
124<td>Tree Edge</td>
125<td><tt>vis.tree_edge(e, g)</tt></td>
126<td><tt>void</tt></td>
127<td>
128This is invoked on each edge as it becomes a member of the edges that
129form the search tree.</td>
130</tr>
131
132<tr>
133<td>Non-Tree Edge</td>
134<td><tt>vis.non_tree_edge(e, g)</tt></td>
135<td><tt>void</tt></td>
136<td>
137This is invoked on back or cross edges for directed graphs and cross
138edges for undirected graphs.
139</td>
140</tr>
141
142<tr>
143<td>Gray Target</td>
144<td><tt>vis.gray_target(e, g)</tt></td>
145<td><tt>void</tt></td>
146<td>
147This is invoked on the subset of non-tree edges who's target vertex is
148colored gray at the time of examination. The color gray indicates
149that the vertex is currently in the queue.
150</td>
151</tr>
152
153<tr>
154<td>Black Target</td>
155<td><tt>vis.black_target(e, g)</tt></td>
156<td><tt>void</tt></td>
157<td>
158This is invoked on the subset of non-tree edges who's target vertex is
159colored black at the time of examination. The color black indicates
160that the vertex has been removed from the queue.
161</td>
162</tr>
163
164<tr>
165<td>Finish Vertex</td>
166<td><tt>vis.finish_vertex(u, g)</tt></td>
167<td><tt>void</tt></td>
168<td>
169This invoked on a vertex after all of its out edges have been added to the
170search tree and all of the adjacent vertices have been discovered
171(but before the out-edges of the adjacent vertices have been examined).
172</td>
173</tr>
174
175</table>
176
177<h3>Models</h3>
178
179<ul>
180 <li><a href="./bfs_visitor.html"><tt>bfs_visitor</tt></a>
181</ul>
182
183<a name="python"></a><h3>Python</h3>
184To implement a model of the <tt>BFSVisitor</tt> concept in Python,
185create a new class that derives from the <tt>BFSVisitor</tt> type of
186the graph, which will be
187named <tt><i>GraphType</i>.BFSVisitor</tt>. The events and syntax are
188the same as with visitors in C++. Here is an example for the
189Python <tt>bgl.Graph</tt> graph type:
190
191<pre>
192class count_tree_edges_bfs_visitor(bgl.Graph.BFSVisitor):
193  def __init__(self, name_map):
194    bgl.Graph.BFSVisitor.__init__(self)
195    self.name_map = name_map
196
197  def tree_edge(self, e, g):
198    (u, v) = (g.source(e), g.target(e))
199    print "Tree edge ",
200    print self.name_map[u],
201    print " -> ",
202    print self.name_map[v]
203</pre>
204
205<h3>See also</h3>
206
207<a href="./visitor_concepts.html">Visitor concepts</a>
208
209<br>
210<HR>
211<TABLE>
212<TR valign=top>
213<TD nowrap>Copyright &copy 2000-2001</TD><TD>
214<A HREF="../../../people/jeremy_siek.htm">Jeremy Siek</A>,
215Indiana University (<A
216HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br>
217<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>
218<A HREF=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
219Indiana University (<A
220HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
221</TD></TR></TABLE>
222
223</BODY>
224</HTML> 
Note: See TracBrowser for help on using the repository browser.