ceph/src/boost/libs/graph/doc/DijkstraVisitor.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: Dijkstra 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)"/>Dijkstra Visitor Concept</H1>
  19
  20 This concept defines the visitor interface for <a
  21 href="./dijkstra_shortest_paths.html"><tt>dijkstra_shortest_paths()</tt></a>
  22 and related algorithms. The user can create a class that matches this
  23 interface, and then pass objects of the class into
  24 <tt>dijkstra_shortest_paths()</tt> to augment the actions taken during
  25 the search.
  26
  27 <h3>Refinement of</h3>
  28
  29 <a href="../../utility/CopyConstructible.html">Copy Constructible</a>
  30 (copying a visitor should be a lightweight operation).
  31
  32
  33 <h3>Notation</h3>
  34
  35 <Table>
  36 <TR>
  37 <TD><tt>V</tt></TD>
  38 <TD>A type that is a model of Dijkstra Visitor.</TD>
  39 </TR>
  40
  41 <TR>
  42 <TD><tt>vis</tt></TD>
  43 <TD>An object of type <tt>V</tt>.</TD>
  44 </TR>
  45
  46 <TR>
  47 <TD><tt>G</tt></TD>
  48 <TD>A type that is a model of Graph.</TD>
  49 </TR>
  50
  51 <TR>
  52 <TD><tt>g</tt></TD>
  53 <TD>An object of type <tt>G</tt>.</TD>
  54 </TR>
  55
  56 <TR>
  57 <TD><tt>e</tt></TD>
  58 <TD>An object of type <tt>boost::graph_traits&lt;G&gt;::edge_descriptor</tt>.</TD>
  59 </TR>
  60
  61 <TR>
  62 <TD><tt>s,u,v</tt></TD>
  63 <TD>An object of type <tt>boost::graph_traits&lt;G&gt;::vertex_descriptor</tt>.</TD>
  64 </TR>
  65
  66 <TR>
  67 <TD><tt>DistanceMap</tt></TD>
  68 <TD>A type that is a model of <a href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write Property Map</a>.</TD>
  69 </TR>
  70
  71 <TR>
  72 <TD><tt>d</tt></TD>
  73 <TD>An object of type <tt>DistanceMap</tt>.</TD>
  74 </TR>
  75
  76 <TR>
  77 <TD><tt>WeightMap</tt></TD>
  78 <TD>A type that is a model of <a href="../../property_map/doc/ReadWritePropertyMap.html">Readable Property Map</a>.</TD>
  79 </TR>
  80
  81 <TR>
  82 <TD><tt>w</tt></TD>
  83 <TD>An object of type <tt>WeightMap</tt>.</TD>
  84 </TR>
  85
  86 </table>
  87
  88 <h3>Associated Types</h3>
  89
  90 none
  91 <p>
  92
  93 <h3>Valid Expressions</h3>
  94
  95 <table border>
  96 <tr>
  97 <th>Name</th><th>Expression</th><th>Return Type</th><th>Description</th>
  98 </tr>
  99
 100 <tr>
 101 <td>Initialize Vertex</td>
 102 <td><tt>vis.initialize_vertex(u, g)</tt></td>
 103 <td><tt>void</tt></td>
 104 <td>
 105 This is invoked one each vertex of the graph when it is initialized.
 106 </td>
 107 </tr>
 108
 109 <tr>
 110 <td>Examine Vertex</td>
 111 <td><tt>vis.examine_vertex(u, g)</tt></td>
 112 <td><tt>void</tt></td>
 113 <td>
 114 This is invoked on a vertex as it is popped from the queue. This
 115 happens immediately before <tt>examine_edge()</tt> is invoked
 116 on each of the out-edges of vertex <tt>u</tt>.
 117 </td>
 118 </tr>
 119
 120 <tr>
 121 <td>Examine Edge</td>
 122 <td><tt>vis.examine_edge(e, g)</tt></td>
 123 <td><tt>void</tt></td>
 124 <td>
 125 This is invoked on every out-edge of each vertex after it is discovered.
 126 </td>
 127 </tr>
 128
 129 <tr>
 130 <td>Discover Vertex</td>
 131 <td><tt>vis.discover_vertex(u, g)</tt></td>
 132 <td><tt>void</tt></td>
 133 <td>
 134 This is invoked when a vertex is encountered for the first time.
 135 </td>
 136 </tr>
 137
 138 <tr>
 139 <td>Edge Relaxed</td>
 140 <td><tt>vis.edge_relaxed(e, g)</tt></td>
 141 <td><tt>void</tt></td>
 142 <td>
 143 Upon examination, if the following condition holds then the edge
 144 is relaxed (its distance is reduced), and this method is invoked.<br>
 145 <tt>
 146 tie(u,v) = incident(e, g);<br>
 147 D d_u = get(d, u), d_v = get(d, v);<br>
 148 W w_e = get(w, e);<br>
 149 assert(compare(combine(d_u, w_e), d_v));<br>
 150 </tt>
 151 </td>
 152 </tr>
 153
 154 <tr>
 155 <td>Edge Not Relaxed</td>
 156 <td><tt>vis.edge_not_relaxed(e, g)</tt></td>
 157 <td><tt>void</tt></td>
 158 <td>
 159 Upon examination, if the edge is not relaxed (see above) then
 160 this method is invoked.
 161 </td>
 162 </tr>
 163
 164 <tr>
 165 <td>Finish Vertex</td>
 166 <td><tt>vis.finish_vertex(u, g)</tt></td>
 167 <td><tt>void</tt></td>
 168 <td>
 169 This invoked on a vertex after all of its out edges have been added to the
 170 search tree and all of the adjacent vertices have been discovered
 171 (but before their out-edges have been examined).
 172 </td>
 173 </tr>
 174
 175 </table>
 176
 177 <h3>Models</h3>
 178
 179 <ul>
 180  <li><a href="./dijkstra_visitor.html"><tt>dijkstra_visitor</tt></a>
 181 </ul>
 182
 183 <a name="python"></a>
 184 <h3>Python</h3>
 185
 186 To implement a model of the <tt>DijkstraVisitor</tt> concept in Python,
 187 create a new class that derives from the <tt>DijkstraVisitor</tt> type of
 188 the graph, which will be
 189 named <tt><i>GraphType</i>.DijkstraVisitor</tt>. The events and syntax are
 190 the same as with visitors in C++. Here is an example for the
 191 Python <tt>bgl.Graph</tt> graph type:
 192
 193 <pre>
 194 class count_tree_edges_dijkstra_visitor(bgl.Graph.DijkstraVisitor):
 195   def __init__(self, name_map):
 196     bgl.Graph.DijkstraVisitor.__init__(self)
 197     self.name_map = name_map
 198
 199   def edge_relaxed(self, e, g):
 200     (u, v) = (g.source(e), g.target(e))
 201     print "Relaxed edge ",
 202     print self.name_map[u],
 203     print " -> ",
 204     print self.name_map[v]
 205 </pre>
 206
 207 <br>
 208 <HR>
 209 <TABLE>
 210 <TR valign=top>
 211 <TD nowrap>Copyright &copy; 2000-2001</TD><TD>
 212 <A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>,
 213 Indiana University (<A
 214 HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br>
 215 <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>
 216 <A HREF="http://www.osl.iu.edu/~lums">Andrew Lumsdaine</A>,
 217 Indiana University (<A
 218 HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
 219 </TD></TR></TABLE>
 220
 221 </BODY>
 222 </HTML>