ceph/src/boost/libs/graph/doc/BellmanFordVisitor.html

   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&lt;G&gt;::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&lt;G&gt;::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 &copy; 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>