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="https://homes.cs.washington.edu/~al75">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> 185
