Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_34_1/libs/graph/doc/breadth_first_visit.html @ 29

Last change on this file since 29 was 29, checked in by landauf, 17 years ago

updated boost from 1_33_1 to 1_34_1
File size: 6.7 KB
Line 
1<HTML>
2<!--
3  -- Copyright (c) Jeremy Siek 2000, 2001
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: Breadth-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<H1><A NAME="sec:bfv"><img src="figs/python.gif" alt="(Python)"/>
19<TT>breadth_first_visit</TT>
20</H1>
21
22<P>
23<PRE>
24  template &lt;class <a href="./IncidenceGraph.html">IncidenceGraph</a>, class P, class T, class R&gt;
25  void breadth_first_visit(IncidenceGraph& G,
26    typename graph_traits&lt;IncidenceGraph&gt;::vertex_descriptor s,
27    const bgl_named_params&lt;P, T, R&gt;&amp; params);
28
29  template &lt;class <a href="./IncidenceGraph.html">IncidenceGraph</a>, class <a href="./Buffer.html">Buffer</a>, class <a href="./BFSVisitor.html">BFSVisitor</a>, class ColorMap&gt;
30  void breadth_first_visit
31    (const IncidenceGraph&amp; g,
32     typename graph_traits&lt;IncidenceGraph&gt;::vertex_descriptor s,
33     Buffer&amp; Q, BFSVisitor vis, ColorMap color)
34</PRE>
35
36This function is basically the same as <tt>breadth_first_search()</tt>
37except that the color markers are not initialized in the
38algorithm. The user is responsible for making sure the color for every
39vertex is white before calling the algorithm.  With this difference,
40the graph type is only required to be an <a
41href="./IncidenceGraph.html">Incidence Graph</a> instead of a <a
42href="./VertexListGraph.html">Vertex List Graph</a>.  Also, this
43difference allows for more flexibility in the color property map. For
44example, one could use a map that only implements a partial function
45on the vertices, which could be more space efficient when the search
46only reaches a small portion of the graph.
47
48<H3>Where Defined</H3>
49
50<P>
51<a href="../../../boost/graph/breadth_first_search.hpp"><TT>boost/graph/breadth_first_search.hpp</TT></a>
52
53
54<h3>Parameters</h3>
55
56IN: <tt>IncidenceGraph&amp; g</tt>
57<blockquote>
58  A directed or undirected graph. The graph type must
59  be a model of <a href="./IncidenceGraph.html">Incidence Graph</a>.<br>
60
61  <b>Python</b>: The parameter is named <tt>graph</tt>.
62</blockquote>
63
64IN: <tt>vertex_descriptor s</tt>
65<blockquote>
66  The source vertex where the search is started.<br>
67
68  <b>Python</b>: The parameter is named <tt>root_vertex</tt>.
69</blockquote>
70
71
72<h3>Named Parameters</h3>
73
74IN: <tt>visitor(BFSVisitor vis)</tt>
75<blockquote>
76  A visitor object that is invoked inside the algorithm at the
77  event-points specified by the <a href="BFSVisitor.html">BFS
78  Visitor</a> concept. The visitor object is passed by value <a
79  href="#1">[1]</a>.<br> <b>Default:</b>
80  <tt>bfs_visitor&lt;null_visitor&gt;</tt><br>
81
82  <b>Python</b>: The parameter should be an object that derives from
83  the <a href="BFSVisitor.html#python"><tt>BFSVisitor</tt></a> type of the graph.
84</blockquote>
85
86UTIL/OUT: <tt>color_map(ColorMap color)</tt>
87<blockquote>
88  This is used by the algorithm to keep track of its progress through
89  the graph. The type <tt>ColorMap</tt> must be a model of <a
90  href="../../property_map/ReadWritePropertyMap.html">Read/Write
91  Property Map</a> and its key type must be the graph's vertex
92  descriptor type and the value type of the color map must model
93  <a href="./ColorValue.html">ColorValue</a>.<br>
94  <b>Default:</b> <tt>get(vertex_color, g)</tt><br>
95
96  <b>Python</b>: The color map must be a <tt>vertex_color_map</tt> for
97  the graph.
98</blockquote>
99
100UTIL: <tt>buffer(Buffer&amp; Q)</tt>
101<blockquote>
102  The queue used to determine the order in which vertices will be
103  discovered.  If a FIFO queue is used, then the traversal will
104  be according to the usual BFS ordering. Other types of queues
105  can be used, but the traversal order will be different.
106  For example Dijkstra's algorithm can be implemented
107  using a priority queue. The type <tt>Buffer</tt> must be a model of
108  <a href="./Buffer.html">Buffer</a>.<br>
109  <b>Default:</b> <tt>boost::queue</tt><br>
110
111  <b>Python</b>: The buffer must derive from the <a
112  href="./Buffer.html">Buffer</a> type for the graph.
113</blockquote> 
114
115
116<H3><A NAME="SECTION001330300000000000000">
117Complexity</A>
118</H3>
119
120<P>
121The time complexity is <i>O(E)</i>.
122
123<P>
124
125<h3>Visitor Event Points</h3>
126
127<ul>
128<li><b><tt>vis.initialize_vertex(v, g)</tt></b> is invoked on every vertex
129  before the start of the search.
130
131<li><b><tt>vis.examine_vertex(u, g)</tt></b>r is invoked in each
132  vertex as it is removed from the queue.
133
134<li><b><tt>vis.examine_edge(e, g)</tt></b> is invoked on every out-edge
135  of each vertex immediately after the vertex is removed from the queue.
136
137<li><b><tt>vis.tree_edge(e, g)</tt></b> is invoked (in addition to
138  <tt>examine_edge()</tt>) if the edge is a tree edge. The
139  target vertex of edge <tt>e</tt> is discovered at this time.
140
141<li><b><tt>vis.discover_vertex(u, g)</tt></b> is invoked the first time the
142  algorithm encounters vertex <i>u</i>. All vertices closer to the
143  source vertex have been discovered, and vertices further from the
144  source have not yet been discovered.
145
146<li><b><tt>vis.non_tree_edge(e, g)</tt></b> is invoked (in addition to
147  <tt>examine_edge()</tt>) if the edge is not a tree edge.
148
149<li><b><tt>vis.gray_target(e, g)</tt></b> is invoked (in addition to
150  <tt>non_tree_edge()</tt>) if the target vertex is colored gray at the
151  time of examination. The color gray indicates that
152  the vertex is currently in the queue.
153
154<li><b><tt>vis.black_target(e, g)</tt></b> is invoked (in addition to
155  <tt>non_tree_edge()</tt>) if the target vertex is colored black at the
156  time of examination. The color black indicates that the
157  vertex is no longer in the queue.
158
159<li><b><tt>vis.finish_vertex(u, g)</tt></b> is invoked after all of the out
160  edges of <i>u</i> have been examined and all of the adjacent vertices
161  have been discovered.
162
163</ul>
164
165<h3>See Also</h3>
166
167<a href="./breadth_first_search.html"><tt>breadth_first_search()</tt></a>,
168<a href="./bfs_visitor.html"><tt>bfs_visitor</tt></a>, and
169<a href="./depth_first_search.html"><tt>depth_first_search()</tt></a>
170
171<h3>Notes</h3>
172
173<p><a name="1">[1]</a> 
174  Since the visitor parameter is passed by value, if your visitor
175  contains state then any changes to the state during the algorithm
176  will be made to a copy of the visitor object, not the visitor object
177  passed in. Therefore you may want the visitor to hold this state by
178  pointer or reference.
179
180<br>
181<HR>
182<TABLE>
183<TR valign=top>
184<TD nowrap>Copyright &copy 2000-2001</TD><TD>
185<A HREF="../../../people/jeremy_siek.htm">Jeremy Siek</A>, Indiana University (<A HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)
186</TD></TR></TABLE>
187
188</BODY>
189</HTML> 
Note: See TracBrowser for help on using the repository browser.