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 20This concept defines the visitor interface for <a 21href="./bellman_ford_shortest.html"><tt>bellman_ford_shortest_paths()</tt></a>. 22Users can define a class with the Bellman Ford Visitor interface and 23pass and object of the class to <tt>bellman_ford_shortest_paths()</tt>, 24thereby 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 68none 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> 83This 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> 93Upon examination, if the following condition holds then the edge 94is relaxed (its distance is reduced), and this method is invoked.<br> 95<tt> 96tie(u,v) = incident(e, g);<br> 97D d_u = get(d, u), d_v = get(d, v);<br> 98W w_e = get(w, e);<br> 99assert(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> 109Upon examination, if the edge is not relaxed (see above) then 110this 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> 119After <tt>num_vertices(g)</tt> iterations through the edge set 120of the graph are completed, one last iteration is made to test whether 121each edge was minimized. If the edge is minimized then this function 122is 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> 131If the edge is not minimized, this function is invoked. This happens 132when 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 148To implement a model of the <tt>BellmanFordVisitor</tt> concept in Python, 149create a new class that derives from the <tt>BellmanFordVisitor</tt> type of 150the graph, which will be 151named <tt><i>GraphType</i>.BellmanFordVisitor</tt>. The events and syntax are 152the same as with visitors in C++. Here is an example for the 153Python <tt>bgl.Graph</tt> graph type: 154 155<pre> 156class 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>, 175Indiana University (<A 176HREF="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="https://homes.cs.washington.edu/~al75">Andrew Lumsdaine</A>, 179Indiana University (<A 180HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>) 181</TD></TR></TABLE> 182 183</BODY> 184</HTML> 185
