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

<HTML>
<!--
     Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 2000
    
     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: Bellman Ford Visitor</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><img src="figs/python.gif" alt="(Python)"/>Bellman Ford Visitor Concept</H1>

This concept defines the visitor interface for <a
href="./bellman_ford_shortest.html"><tt>bellman_ford_shortest_paths()</tt></a>.
Users can define a class with the Bellman Ford Visitor interface and
pass and object of the class to <tt>bellman_ford_shortest_paths()</tt>,
thereby augmenting the actions taken during the graph search.

<h3>Refinement of</h3>

<a href="../../utility/CopyConstructible.html">Copy Constructible</a>
(copying a visitor should be a lightweight operation).

<h3>Notation</h3>

<Table>
<TR>
<TD><tt>V</tt></TD>
<TD>A type that is a model of Bellman Ford Visitor.</TD>
</TR>

<TR>
<TD><tt>vis</tt></TD>
<TD>An object of type <tt>V</tt>.</TD>
</TR>

<TR>
<TD><tt>G</tt></TD>
<TD>A type that is a model of Graph.</TD>
</TR>

<TR>
<TD><tt>g</tt></TD>
<TD>An object of type <tt>G</tt>.</TD>
</TR>

<TR>
<TD><tt>e</tt></TD>
<TD>An object of type <tt>boost::graph_traits&lt;G&gt;::edge_descriptor</tt>.</TD>
</TR>

<TR>
<TD><tt>s,u</tt></TD>
<TD>An object of type <tt>boost::graph_traits&lt;G&gt;::vertex_descriptor</tt>.</TD>
</TR>

</table>

<h3>Associated Types</h3>

none
<p>

<h3>Valid Expressions</h3>

<table border>
<tr>
<th>Name</th><th>Expression</th><th>Return Type</th><th>Description</th>
</tr>

<tr>
<td>Examine Edge</td>
<td><tt>vis.examine_edge(e, g)</tt></td>
<td><tt>void</tt></td>
<td>
This is invoked on every edge in the graph <tt>num_vertices(g)</tt> times.
</td>
</tr>


<tr>
<td>Edge Relaxed</td>
<td><tt>vis.edge_relaxed(e, g)</tt></td>
<td><tt>void</tt></td>
<td>
Upon examination, if the following condition holds then the edge
is relaxed (its distance is reduced), and this method is invoked.<br>
<tt>
tie(u,v) = incident(e, g);<br>
D d_u = get(d, u), d_v = get(d, v);<br>
W w_e = get(w, e);<br>
assert(compare(combine(d_u, w_e), d_v));<br>
</tt>
</td>
</tr>

<tr>
<td>Edge Not Relaxed</td>
<td><tt>edge_not_relaxed(e, g)</tt></td>
<td><tt>void</tt></td>
<td>
Upon examination, if the edge is not relaxed (see above) then
this method is invoked.
</td>
</tr>

<tr>
<td>Edge Minimized</td>
<td><tt>vis.edge_minimized(e, g)</tt></td>
<td><tt>void</tt></td>
<td>
After <tt>num_vertices(g)</tt> iterations through the edge set
of the graph are completed, one last iteration is made to test whether
each edge was minimized. If the edge is minimized then this function
is invoked.
</td>
</tr>

<tr>
<td>Edge Not Minimized</td>
<td><tt>edge_not_minimized(e, g)</tt></td>
<td><tt>void</tt></td>
<td>
If the edge is not minimized, this function is invoked. This happens
when there is a negative cycle in the graph.
</td>
</tr>

</table>


<h3>Models</h3>

<ul>
  <li><a href="./bellman_visitor.html"><tt>bellman_visitor</tt></a>
</ul>

<a name="python"></a>
<h3>Python</h3>

To implement a model of the <tt>BellmanFordVisitor</tt> concept in Python,
create a new class that derives from the <tt>BellmanFordVisitor</tt> type of
the graph, which will be
named <tt><i>GraphType</i>.BellmanFordVisitor</tt>. The events and syntax are
the same as with visitors in C++. Here is an example for the
Python <tt>bgl.Graph</tt> graph type:

<pre>
class count_tree_edges_bellman_ford_visitor(bgl.Graph.BellmanFordVisitor):
  def __init__(self, name_map):
    bgl.Graph.BellmanFordVisitor.__init__(self)
    self.name_map = name_map

  def edge_relaxed(self, e, g):
    (u, v) = (g.source(e), g.target(e))
    print "Relaxed edge ",
    print self.name_map[u],
    print " -> ",
    print self.name_map[v]
</pre>

<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>)<br>
<A HREF="http://www.boost.org/people/liequan_lee.htm">Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@cs.indiana.edu">llee@cs.indiana.edu</A>)<br>
<A HREF="http://www.osl.iu.edu/~lums">Andrew Lumsdaine</A>,
Indiana University (<A
HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
</TD></TR></TABLE>

</BODY>
</HTML>
Commit	Line	Data
7c673cae FG	1	<HTML>
	2	<!--
	3	Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 2000
	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: Bellman Ford Visitor</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><img src="figs/python.gif" alt="(Python)"/>Bellman Ford Visitor Concept</H1>
	19
	20	This concept defines the visitor interface for <a
	21	href="./bellman_ford_shortest.html"><tt>bellman_ford_shortest_paths()</tt></a>.
	22	Users can define a class with the Bellman Ford Visitor interface and
	23	pass and object of the class to <tt>bellman_ford_shortest_paths()</tt>,
	24	thereby augmenting the actions taken during the graph search.
	25
	26	<h3>Refinement of</h3>
	27
	28	<a href="../../utility/CopyConstructible.html">Copy Constructible</a>
	29	(copying a visitor should be a lightweight operation).
	30
	31	<h3>Notation</h3>
	32
	33	<Table>
	34	<TR>
	35	<TD><tt>V</tt></TD>
	36	<TD>A type that is a model of Bellman Ford Visitor.</TD>
	37	</TR>
	38
	39	<TR>
	40	<TD><tt>vis</tt></TD>
	41	<TD>An object of type <tt>V</tt>.</TD>
	42	</TR>
	43
	44	<TR>
	45	<TD><tt>G</tt></TD>
	46	<TD>A type that is a model of Graph.</TD>
	47	</TR>
	48
	49	<TR>
	50	<TD><tt>g</tt></TD>
	51	<TD>An object of type <tt>G</tt>.</TD>
	52	</TR>
	53
	54	<TR>
	55	<TD><tt>e</tt></TD>
	56	<TD>An object of type <tt>boost::graph_traits<G>::edge_descriptor</tt>.</TD>
	57	</TR>
	58
	59	<TR>
	60	<TD><tt>s,u</tt></TD>
	61	<TD>An object of type <tt>boost::graph_traits<G>::vertex_descriptor</tt>.</TD>
	62	</TR>
	63
	64	</table>
65
66	<h3>Associated Types</h3>
67
68	none
69	<p>
70
71	<h3>Valid Expressions</h3>
72
73	<table border>
74	<tr>
75	<th>Name</th><th>Expression</th><th>Return Type</th><th>Description</th>
76	</tr>
77
78	<tr>
79	<td>Examine Edge</td>
80	<td><tt>vis.examine_edge(e, g)</tt></td>
81	<td><tt>void</tt></td>
82	<td>
83	This is invoked on every edge in the graph <tt>num_vertices(g)</tt> times.
84	</td>
85	</tr>
86
87
88	<tr>
89	<td>Edge Relaxed</td>
90	<td><tt>vis.edge_relaxed(e, g)</tt></td>
91	<td><tt>void</tt></td>
92	<td>
93	Upon examination, if the following condition holds then the edge
94	is relaxed (its distance is reduced), and this method is invoked.<br>
95	<tt>
96	tie(u,v) = incident(e, g);<br>
97	D d_u = get(d, u), d_v = get(d, v);<br>
98	W w_e = get(w, e);<br>
99	assert(compare(combine(d_u, w_e), d_v));<br>
100	</tt>
101	</td>
102	</tr>
103
104	<tr>
105	<td>Edge Not Relaxed</td>
106	<td><tt>edge_not_relaxed(e, g)</tt></td>
107	<td><tt>void</tt></td>
108	<td>
109	Upon examination, if the edge is not relaxed (see above) then
110	this method is invoked.
111	</td>
112	</tr>
113
114	<tr>
115	<td>Edge Minimized</td>
116	<td><tt>vis.edge_minimized(e, g)</tt></td>
117	<td><tt>void</tt></td>
118	<td>
119	After <tt>num_vertices(g)</tt> iterations through the edge set
120	of the graph are completed, one last iteration is made to test whether
121	each edge was minimized. If the edge is minimized then this function
122	is invoked.
123	</td>
124	</tr>
125
126	<tr>
127	<td>Edge Not Minimized</td>
128	<td><tt>edge_not_minimized(e, g)</tt></td>
129	<td><tt>void</tt></td>
130	<td>
131	If the edge is not minimized, this function is invoked. This happens
132	when there is a negative cycle in the graph.
133	</td>
134	</tr>
135
136	</table>
137
138
139	<h3>Models</h3>
140
141	<ul>
142	<li><a href="./bellman_visitor.html"><tt>bellman_visitor</tt></a>
143	</ul>
144
145	<a name="python"></a>
146	<h3>Python</h3>
147
148	To implement a model of the <tt>BellmanFordVisitor</tt> concept in Python,
149	create a new class that derives from the <tt>BellmanFordVisitor</tt> type of
150	the graph, which will be
151	named <tt><i>GraphType</i>.BellmanFordVisitor</tt>. The events and syntax are
152	the same as with visitors in C++. Here is an example for the
153	Python <tt>bgl.Graph</tt> graph type:
154
155	<pre>
156	class count_tree_edges_bellman_ford_visitor(bgl.Graph.BellmanFordVisitor):
157	def __init__(self, name_map):
158	bgl.Graph.BellmanFordVisitor.__init__(self)
159	self.name_map = name_map
160
161	def edge_relaxed(self, e, g):
162	(u, v) = (g.source(e), g.target(e))
163	print "Relaxed edge ",
164	print self.name_map[u],
165	print " -> ",
166	print self.name_map[v]
167	</pre>
168
169	<br>
170	<HR>
171	<TABLE>
172	<TR valign=top>
173	<TD nowrap>Copyright © 2000-2001</TD><TD>
174	<A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>,
175	Indiana University (<A
176	HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br>
177	<A HREF="http://www.boost.org/people/liequan_lee.htm">Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@cs.indiana.edu">llee@cs.indiana.edu</A>)<br>
178	<A HREF="http://www.osl.iu.edu/~lums">Andrew Lumsdaine</A>,
179	Indiana University (<A
180	HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
181	</TD></TR></TABLE>
182
183	</BODY>
184	</HTML>