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

   1 <HTML>
   2 <!--
   3      Copyright (c) 2004 Kris Beevers
   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: AStarVisitor</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>AStar Visitor Concept</H1>
  19
  20 This concept defines the visitor interface for <a
  21 href="./astar_search.html"><tt>astar_search()</tt></a>.  Users can
  22 define a class with the AStar Visitor interface and pass an object of
  23 the class to <tt>astar_search()</tt>, thereby augmenting the actions
  24 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
  32 <h3>Notation</h3>
  33
  34 <Table>
  35 <TR>
  36 <TD><tt>V</tt></TD>
  37 <TD>A type that is a model of AStar Visitor.</TD>
  38 </TR>
  39
  40 <TR>
  41 <TD><tt>vis</tt></TD>
  42 <TD>An object of type <tt>V</tt>.</TD>
  43 </TR>
  44
  45 <TR>
  46 <TD><tt>G</tt></TD>
  47 <TD>A type that is a model of Graph.</TD>
  48 </TR>
  49
  50 <TR>
  51 <TD><tt>g</tt></TD>
  52 <TD>An object of type <tt>const G&amp;</tt>.</TD>
  53 </TR>
  54
  55 <TR>
  56 <TD><tt>e</tt></TD>
  57 <TD>An object of type <tt>boost::graph_traits&lt;G&gt;::edge_descriptor</tt>.</TD>
  58 </TR>
  59
  60 <TR>
  61 <TD><tt>s,u,v</tt></TD>
  62 <TD>An object of type <tt>boost::graph_traits&lt;G&gt;::vertex_descriptor</tt>.</TD>
  63 </TR>
  64
  65 <TR>
  66 <TD><tt>d</tt></TD>
  67 <TD>An object of type <tt>DistanceMap</tt>.</TD>
  68 </TR>
  69
  70 <TR>
  71 <TD><tt>WeightMap</tt></TD>
  72 <TD>A type that is a model of <a
  73 href="../../property_map/doc/ReadablePropertyMap.html">Readable Property
  74 Map</a>.</TD>
  75 </TR>
  76
  77 <TR>
  78 <TD><tt>w</tt></TD>
  79 <TD>An object of type <tt>WeightMap</tt>.</TD>
  80 </TR>
  81
  82 </table>
  83
  84 <h3>Associated Types</h3>
  85
  86 none
  87 <p>
  88
  89 <h3>Valid Expressions</h3>
  90
  91 <table border>
  92 <tr>
  93 <th>Name</th><th>Expression</th><th>Return Type</th><th>Description</th>
  94 </tr>
  95
  96 <tr>
  97 <td>Initialize Vertex</td>
  98 <td><tt>vis.initialize_vertex(u, g)</tt></td>
  99 <td><tt>void</tt></td>
 100 <td>
 101 This is invoked on each vertex of the graph when it is first
 102 initialized (i.e., when its property maps are initialized).
 103 </td>
 104 </tr>
 105
 106 <tr>
 107 <td>Discover Vertex</td>
 108 <td><tt>vis.discover_vertex(u, g)</tt></td>
 109 <td><tt>void</tt></td>
 110 <td>
 111 This is invoked when a vertex is first discovered and is added to the
 112 OPEN list.
 113 </td>
 114 </tr>
 115
 116 <tr>
 117 <td>Examine Vertex</td>
 118 <td><tt>vis.examine_vertex(u, g)</tt></td>
 119 <td><tt>void</tt></td>
 120 <td>
 121 This is invoked on a vertex as it is popped from the queue (i.e., it
 122 has the lowest cost on the OPEN list). This happens immediately before
 123 <tt>examine_edge()</tt> is invoked on each of the out-edges of vertex
 124 <tt>u</tt>.
 125 </td>
 126 </tr>
 127
 128 <tr>
 129 <td>Examine Edge</td>
 130 <td><tt>vis.examine_edge(e, g)</tt></td>
 131 <td><tt>void</tt></td>
 132 <td>
 133 This is invoked on every out-edge of each vertex after it is
 134 examined.
 135 </td>
 136 </tr>
 137
 138
 139 <tr>
 140 <td>Edge Relaxed</td>
 141 <td><tt>vis.edge_relaxed(e, g)</tt></td>
 142 <td><tt>void</tt></td>
 143 <td>
 144 Upon examination, if the following condition holds then the edge is
 145 relaxed (the distance of its target vertex is reduced) and this method
 146 is invoked:
 147 <blockquote>
 148 <pre>
 149 tie(u, s) = incident(e, g);
 150 D d_u = get(d, u), d_v = get(d, s);
 151 W w_e = get(w, e);
 152 assert(compare(combine(d_u, w_e), d_s));
 153 </pre>
 154 </blockquote>
 155 </td>
 156 </tr>
 157
 158 <tr>
 159 <td>Edge Not Relaxed</td>
 160 <td><tt>vis.edge_not_relaxed(e, g)</tt></td>
 161 <td><tt>void</tt></td>
 162 <td>
 163 Upon examination, if an edge is not relaxed (see above) then this
 164 method is invoked.
 165 </td>
 166 </tr>
 167
 168 <tr>
 169 <td>Black Target</td>
 170 <td><tt>vis.black_target(e, g)</tt></td>
 171 <td><tt>void</tt></td>
 172 <td>
 173 This is invoked when a vertex that is on the CLOSED list is
 174 ``rediscovered'' via a more efficient path and is re-added to the
 175 OPEN list.
 176 </td>
 177 </tr>
 178
 179 <tr>
 180 <td>Finish Vertex</td>
 181 <td><tt>vis.finish_vertex(u, g)</tt></td>
 182 <td><tt>void</tt></td>
 183 <td>
 184 This is invoked on a vertex when it is added to the CLOSED list. This
 185 happens after all of its out-edges have been examined.
 186 </td>
 187 </tr>
 188
 189 </table>
 190
 191 <h3>Models</h3>
 192
 193 <ul>
 194  <li><a href="./astar_visitor.html"><tt>astar_visitor</tt></a>
 195 </ul>
 196
 197
 198 <h3>See also</h3>
 199
 200 <a href="./visitor_concepts.html">Visitor concepts</a>
 201
 202 <br>
 203 <HR>
 204 <TABLE>
 205 <TR valign=top>
 206 <TD nowrap>Copyright &copy; 2004</TD><TD>
 207 <A HREF="http://www.cs.rpi.edu/~beevek/">Kristopher Beevers</A>,
 208 Rensselaer Polytechnic Institute (<A
 209 HREF="mailto:beevek@cs.rpi.edu">beevek@cs.rpi.edu</A>)
 210 </TD></TR></TABLE>
 211
 212 </BODY>
 213 </HTML>