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 <class <a href="./IncidenceGraph.html">IncidenceGraph</a>, class P, class T, class R> 25 void breadth_first_visit(IncidenceGraph& G, 26 typename graph_traits<IncidenceGraph>::vertex_descriptor s, 27 const bgl_named_params<P, T, R>& params); 28 29 template <class <a href="./IncidenceGraph.html">IncidenceGraph</a>, class <a href="./Buffer.html">Buffer</a>, class <a href="./BFSVisitor.html">BFSVisitor</a>, class ColorMap> 30 void breadth_first_visit 31 (const IncidenceGraph& g, 32 typename graph_traits<IncidenceGraph>::vertex_descriptor s, 33 Buffer& 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& 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<null_visitor></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/doc/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& 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.examine_vertex(u, g)</tt></b>r is invoked in each 129 vertex as it is removed from the queue. 130 131<li><b><tt>vis.examine_edge(e, g)</tt></b> is invoked on every out-edge 132 of each vertex immediately after the vertex is removed from the queue. 133 134<li><b><tt>vis.tree_edge(e, g)</tt></b> is invoked (in addition to 135 <tt>examine_edge()</tt>) if the edge is a tree edge. The 136 target vertex of edge <tt>e</tt> is discovered at this time. 137 138<li><b><tt>vis.discover_vertex(u, g)</tt></b> is invoked the first time the 139 algorithm encounters vertex <i>u</i>. All vertices closer to the 140 source vertex have been discovered, and vertices further from the 141 source have not yet been discovered. 142 143<li><b><tt>vis.non_tree_edge(e, g)</tt></b> is invoked (in addition to 144 <tt>examine_edge()</tt>) if the edge is not a tree edge. 145 146<li><b><tt>vis.gray_target(e, g)</tt></b> is invoked (in addition to 147 <tt>non_tree_edge()</tt>) if the target vertex is colored gray at the 148 time of examination. The color gray indicates that 149 the vertex is currently in the queue. 150 151<li><b><tt>vis.black_target(e, g)</tt></b> is invoked (in addition to 152 <tt>non_tree_edge()</tt>) if the target vertex is colored black at the 153 time of examination. The color black indicates that the 154 vertex is no longer in the queue. 155 156<li><b><tt>vis.finish_vertex(u, g)</tt></b> is invoked after all of the out 157 edges of <i>u</i> have been examined and all of the adjacent vertices 158 have been discovered. 159 160</ul> 161 162<h3>See Also</h3> 163 164<a href="./breadth_first_search.html"><tt>breadth_first_search()</tt></a>, 165<a href="./bfs_visitor.html"><tt>bfs_visitor</tt></a>, and 166<a href="./depth_first_search.html"><tt>depth_first_search()</tt></a> 167 168<h3>Notes</h3> 169 170<p><a name="1">[1]</a> 171 Since the visitor parameter is passed by value, if your visitor 172 contains state then any changes to the state during the algorithm 173 will be made to a copy of the visitor object, not the visitor object 174 passed in. Therefore you may want the visitor to hold this state by 175 pointer or reference. 176 177<br> 178<HR> 179<TABLE> 180<TR valign=top> 181<TD nowrap>Copyright © 2000-2001</TD><TD> 182<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>) 183</TD></TR></TABLE> 184 185</BODY> 186</HTML> 187
