[ceph.git] / ceph / src / boost / libs / graph / doc / breadth_first_visit.html

<HTML>
<!--
     Copyright (c) Jeremy Siek 2000, 2001
    
     Distributed under the Boost Software License, Version 1.0.
     (See accompanying file LICENSE_1_0.txt or copy at
     http://www.boost.org/LICENSE_1_0.txt)
  -->
<Head>
<Title>Boost Graph Library: Breadth-First Visit</Title>
<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 
        ALINK="#ff0000"> 
<IMG SRC="../../../boost.png" 
     ALT="C++ Boost" width="277" height="86"> 

<BR Clear>

<H1><A NAME="sec:bfv"><img src="figs/python.gif" alt="(Python)"/>
<TT>breadth_first_visit</TT>
</H1>

<P>
<PRE>
  template &lt;class <a href="./IncidenceGraph.html">IncidenceGraph</a>, class P, class T, class R&gt;
  void breadth_first_visit(IncidenceGraph& G, 
    typename graph_traits&lt;IncidenceGraph&gt;::vertex_descriptor s, 
    const bgl_named_params&lt;P, T, R&gt;&amp; params);

  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;
  void breadth_first_visit
    (const IncidenceGraph&amp; g, 
     typename graph_traits&lt;IncidenceGraph&gt;::vertex_descriptor s, 
     Buffer&amp; 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&amp; g</tt>
<blockquote>
  A directed or undirected graph. The graph type must
  be a model of <a href="./IncidenceGraph.html">Incidence Graph</a>.<br>

  <b>Python</b>: The parameter is named <tt>graph</tt>.
</blockquote>

IN: <tt>vertex_descriptor s</tt>
<blockquote>
  The source vertex where the search is started.<br>

  <b>Python</b>: The parameter is named <tt>root_vertex</tt>.
</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&lt;null_visitor&gt;</tt><br>

  <b>Python</b>: The parameter should be an object that derives from
  the <a href="BFSVisitor.html#python"><tt>BFSVisitor</tt></a> type of the graph.
</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/doc/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><br>

  <b>Python</b>: The color map must be a <tt>vertex_color_map</tt> for
  the graph.
</blockquote>

UTIL: <tt>buffer(Buffer&amp; 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><br>

  <b>Python</b>: The buffer must derive from the <a
  href="./Buffer.html">Buffer</a> type for the graph.
</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.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 &copy; 2000-2001</TD><TD>
<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>)
</TD></TR></TABLE>

</BODY>
</HTML>
Commit	Line	Data
7c673cae FG	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
	36	This function is basically the same as <tt>breadth_first_search()</tt>
	37	except that the color markers are not initialized in the
	38	algorithm. The user is responsible for making sure the color for every
	39	vertex is white before calling the algorithm. With this difference,
	40	the graph type is only required to be an <a
	41	href="./IncidenceGraph.html">Incidence Graph</a> instead of a <a
	42	href="./VertexListGraph.html">Vertex List Graph</a>. Also, this
	43	difference allows for more flexibility in the color property map. For
	44	example, one could use a map that only implements a partial function
	45	on the vertices, which could be more space efficient when the search
	46	only 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
	56	IN: <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
	64	IN: <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
74	IN: <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
86	UTIL/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
100	UTIL: <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">
117	Complexity</A>
118	</H3>
119
120	<P>
121	The 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>