1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
|
<HTML>
<!--
-- Copyright (c) Jeremy Siek 2000, 2001
--
-- Permission to use, copy, modify, distribute and sell this software
-- and its documentation for any purpose is hereby granted without fee,
-- provided that the above copyright notice appears in all copies and
-- that both that copyright notice and this permission notice appear
-- in supporting documentation. Silicon Graphics makes no
-- representations about the suitability of this software for any
-- purpose. It is provided "as is" without express or implied warranty.
-->
<Head>
<Title>Boost Graph Library: Breadth-First Visit</Title>
<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
ALINK="#ff0000">
<IMG SRC="../../../c++boost.gif"
ALT="C++ Boost" width="277" height="86">
<BR Clear>
<H1><A NAME="sec:bfv">
<TT>breadth_first_visit</TT>
</H1>
<P>
<PRE>
template <class <a href="./IncidenceGraph.html">IncidenceGraph</a>, class P, class T, class R>
void breadth_first_visit(IncidenceGraph& G,
typename graph_traits<IncidenceGraph>::vertex_descriptor s,
const bgl_named_params<P, T, R>& params);
template <class <a href="./IncidenceGraph.html">IncidenceGraph</a>, class <a href="./Buffer.html">Buffer</a>, class <a href="./BFSVisitor.html">BFSVisitor</a>, class ColorMap>
void breadth_first_visit
(const IncidenceGraph& g,
typename graph_traits<IncidenceGraph>::vertex_descriptor s,
Buffer& Q, BFSVisitor vis, ColorMap color)
</PRE>
This function is basically the same as <tt>breadth_first_search()</tt>
except that the color markers are not initialized in the
algorithm. The user is responsible for making sure the color for every
vertex is white before calling the algorithm. With this difference,
the graph type is only required to be an <a
href="./IncidenceGraph.html">Incidence Graph</a> instead of a <a
href="./VertexListGraph.html">Vertex List Graph</a>. Also, this
difference allows for more flexibility in the color property map. For
example, one could use a map that only implements a partial function
on the vertices, which could be more space efficient when the search
only reaches a small portion of the graph.
<H3>Where Defined</H3>
<P>
<a href="../../../boost/graph/breadth_first_search.hpp"><TT>boost/graph/breadth_first_search.hpp</TT></a>
<h3>Parameters</h3>
IN: <tt>IncidenceGraph& g</tt>
<blockquote>
A directed or undirected graph. The graph type must
be a model of <a href="./IncidenceGraph.html">Incidence Graph</a>.
</blockquote>
IN: <tt>vertex_descriptor s</tt>
<blockquote>
The source vertex where the search is started.
</blockquote>
<h3>Named Parameters</h3>
IN: <tt>visitor(BFSVisitor vis)</tt>
<blockquote>
A visitor object that is invoked inside the algorithm at the
event-points specified by the <a href="BFSVisitor.html">BFS
Visitor</a> concept. The visitor object is passed by value <a
href="#1">[1]</a>.<br> <b>Default:</b>
<tt>bfs_visitor<null_visitor></tt>
</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/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> <tt>get(vertex_color, g)</tt>
</blockquote>
UTIL: <tt>buffer(Buffer& Q)</tt>
<blockquote>
The queue used to determine the order in which vertices will be
discovered. If a FIFO queue is used, then the traversal will
be according to the usual BFS ordering. Other types of queues
can be used, but the traversal order will be different.
For example Dijkstra's algorithm can be implemented
using a priority queue. The type <tt>Buffer</tt> must be a model of
<a href="./Buffer.html">Buffer</a>.<br>
<b>Default:</b> <tt>boost::queue</tt>
</blockquote>
<H3><A NAME="SECTION001330300000000000000">
Complexity</A>
</H3>
<P>
The time complexity is <i>O(E)</i>.
<P>
<h3>Visitor Event Points</h3>
<ul>
<li><b><tt>vis.initialize_vertex(v, g)</tt></b> is invoked on every vertex
before the start of the search.
<li><b><tt>vis.examine_vertex(u, g)</tt></b>r is invoked in each
vertex as it is removed from the queue.
<li><b><tt>vis.examine_edge(e, g)</tt></b> is invoked on every out-edge
of each vertex immediately after the vertex is removed from the queue.
<li><b><tt>vis.tree_edge(e, g)</tt></b> is invoked (in addition to
<tt>examine_edge()</tt>) if the edge is a tree edge. The
target vertex of edge <tt>e</tt> is discovered at this time.
<li><b><tt>vis.discover_vertex(u, g)</tt></b> is invoked the first time the
algorithm encounters vertex <i>u</i>. All vertices closer to the
source vertex have been discovered, and vertices further from the
source have not yet been discovered.
<li><b><tt>vis.non_tree_edge(e, g)</tt></b> is invoked (in addition to
<tt>examine_edge()</tt>) if the edge is not a tree edge.
<li><b><tt>vis.gray_target(e, g)</tt></b> is invoked (in addition to
<tt>non_tree_edge()</tt>) if the target vertex is colored gray at the
time of examination. The color gray indicates that
the vertex is currently in the queue.
<li><b><tt>vis.black_target(e, g)</tt></b> is invoked (in addition to
<tt>non_tree_edge()</tt>) if the target vertex is colored black at the
time of examination. The color black indicates that the
vertex is no longer in the queue.
<li><b><tt>vis.finish_vertex(u, g)</tt></b> is invoked after all of the out
edges of <i>u</i> have been examined and all of the adjacent vertices
have been discovered.
</ul>
<h3>See Also</h3>
<a href="./breadth_first_search.html"><tt>breadth_first_search()</tt></a>,
<a href="./bfs_visitor.html"><tt>bfs_visitor</tt></a>, and
<a href="./depth_first_search.html"><tt>depth_first_search()</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="../../../people/jeremy_siek.htm">Jeremy Siek</A>, Indiana University (<A HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)
</TD></TR></TABLE>
</BODY>
</HTML>
|
