ceph/src/boost/libs/graph/doc/astar_search.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: A* Heuristic Search</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><A NAME="sec:astar"></A>
  19 <TT>astar_search</TT>
  20 </H1>
  21
  22
  23 <P>
  24 <PRE>
  25 <i>// Named parameter interfaces</i>
  26 template &lt;typename VertexListGraph,
  27           typename AStarHeuristic,
  28           typename P, typename T, typename R&gt;
  29 void
  30 astar_search
  31   (const VertexListGraph &amp;g,
  32    typename graph_traits&lt;VertexListGraph&gt;::vertex_descriptor s,
  33    <a href="AStarHeuristic.html">AStarHeuristic</a> h, const bgl_named_params&lt;P, T, R&gt;&amp; params);
  34
  35 template &lt;typename VertexListGraph,
  36           typename AStarHeuristic,
  37           typename P, typename T, typename R&gt;
  38 void
  39 astar_search_no_init
  40   (const IncidenceGraph &amp;g,
  41    typename graph_traits&lt;VertexListGraph&gt;::vertex_descriptor s,
  42    <a href="AStarHeuristic.html">AStarHeuristic</a> h, const bgl_named_params&lt;P, T, R&gt;&amp; params);
  43
  44 template &lt;typename VertexListGraph,
  45           typename AStarHeuristic,
  46           typename P, typename T, typename R&gt;
  47 void
  48 astar_search_tree
  49   (const VertexListGraph &amp;g,
  50    typename graph_traits&lt;VertexListGraph&gt;::vertex_descriptor s,
  51    <a href="AStarHeuristic.html">AStarHeuristic</a> h, const bgl_named_params&lt;P, T, R&gt;&amp; params);
  52
  53 template &lt;typename VertexListGraph,
  54           typename AStarHeuristic,
  55           typename P, typename T, typename R&gt;
  56 void
  57 astar_search_no_init_tree
  58   (const IncidenceGraph &amp;g,
  59    typename graph_traits&lt;VertexListGraph&gt;::vertex_descriptor s,
  60    <a href="AStarHeuristic.html">AStarHeuristic</a> h, const bgl_named_params&lt;P, T, R&gt;&amp; params);
  61
  62 <i>// Non-named parameter interface</i>
  63 template &lt;typename VertexListGraph, typename AStarHeuristic,
  64           typename <a href="AStarVisitor.html">AStarVisitor</a>, typename PredecessorMap,
  65           typename CostMap, typename DistanceMap,
  66           typename WeightMap, typename VertexIndexMap,
  67           typename ColorMap,
  68           typename <a href="http://www.sgi.com/tech/stl/BinaryPredicate.html">CompareFunction</a>, typename <a href="http://www.sgi.com/tech/stl/BinaryFunction.html">CombineFunction</a>,
  69           typename CostInf, typename CostZero&gt;
  70 inline void
  71 astar_search
  72   (const VertexListGraph &amp;g,
  73    typename graph_traits&lt;VertexListGraph&gt;::vertex_descriptor s,
  74    AStarHeuristic h, AStarVisitor vis,
  75    PredecessorMap predecessor, CostMap cost,
  76    DistanceMap distance, WeightMap weight,
  77    VertexIndexMap index_map, ColorMap color,
  78    CompareFunction compare, CombineFunction combine,
  79    CostInf inf, CostZero zero);
  80
  81 template &lt;typename VertexListGraph, typename AStarHeuristic,
  82           typename <a href="AStarVisitor.html">AStarVisitor</a>, typename PredecessorMap,
  83           typename CostMap, typename DistanceMap,
  84           typename WeightMap,
  85           typename <a href="http://www.sgi.com/tech/stl/BinaryPredicate.html">CompareFunction</a>, typename <a href="http://www.sgi.com/tech/stl/BinaryFunction.html">CombineFunction</a>,
  86           typename CostInf, typename CostZero&gt;
  87 inline void
  88 astar_search_tree
  89   (const VertexListGraph &amp;g,
  90    typename graph_traits&lt;VertexListGraph&gt;::vertex_descriptor s,
  91    AStarHeuristic h, AStarVisitor vis,
  92    PredecessorMap predecessor, CostMap cost,
  93    DistanceMap distance, WeightMap weight,
  94    CompareFunction compare, CombineFunction combine,
  95    CostInf inf, CostZero zero);
  96
  97 <i>// Versions that do not initialize property maps (used for implicit graphs)</i>
  98 template &lt;typename IncidenceGraph, typename AStarHeuristic,
  99           typename <a href="AStarVisitor.html">AStarVisitor</a>, typename PredecessorMap,
 100           typename CostMap, typename DistanceMap,
 101           typename WeightMap, typename ColorMap,
 102           typename VertexIndexMap,
 103           typename <a href="http://www.sgi.com/tech/stl/BinaryPredicate.html">CompareFunction</a>, typename <a href="http://www.sgi.com/tech/stl/BinaryFunction.html">CombineFunction</a>,
 104           typename CostInf, typename CostZero&gt;
 105 inline void
 106 astar_search_no_init
 107   (const IncidenceGraph &amp;g,
 108    typename graph_traits&lt;IncidenceGraph&gt;::vertex_descriptor s,
 109    AStarHeuristic h, AStarVisitor vis,
 110    PredecessorMap predecessor, CostMap cost,
 111    DistanceMap distance, WeightMap weight,
 112    ColorMap color, VertexIndexMap index_map,
 113    CompareFunction compare, CombineFunction combine,
 114    CostInf inf, CostZero zero);
 115
 116 <b>Note that the index_map and color parameters are swapped in
 117 astar_search_no_init() relative to astar_search(); the named parameter
 118 interfaces are not affected.</b>
 119
 120 template &lt;typename IncidenceGraph, typename AStarHeuristic,
 121           typename <a href="AStarVisitor.html">AStarVisitor</a>, typename PredecessorMap,
 122           typename CostMap, typename DistanceMap,
 123           typename WeightMap,
 124           typename <a href="http://www.sgi.com/tech/stl/BinaryPredicate.html">CompareFunction</a>, typename <a href="http://www.sgi.com/tech/stl/BinaryFunction.html">CombineFunction</a>,
 125           typename CostInf, typename CostZero&gt;
 126 inline void
 127 astar_search_no_init_tree
 128   (const IncidenceGraph &amp;g,
 129    typename graph_traits&lt;IncidenceGraph&gt;::vertex_descriptor s,
 130    AStarHeuristic h, AStarVisitor vis,
 131    PredecessorMap predecessor, CostMap cost,
 132    DistanceMap distance, WeightMap weight,
 133    CompareFunction compare, CombineFunction combine,
 134    CostInf inf, CostZero zero);
 135 </PRE>
 136
 137 <P>
 138 This algorithm implements a heuristic search on a weighted, directed
 139 or undirected graph for the case where all edge weights are
 140 non-negative.
 141 </P>
 142
 143 <P>
 144 The A* algorithm is a <i>heuristic graph search algorithm</i>: an A*
 145 search is "guided" by a <i>heuristic function</i>.  A heuristic
 146 function <i>h(v)</i> is one which estimates the cost from a non-goal
 147 state (<i>v</i>) in the graph to some goal state, <i>g</i>.
 148 Intuitively, A* follows paths (through the graph) to the goal that are
 149 estimated by the heuristic function to be the best paths.  Unlike
 150 best-first search, A* takes into account the known cost from the start
 151 of the search to <i>v</i>; the paths A* takes are guided by a function
 152 <i>f(v) = g(v) + h(v)</i>, where <i>h(v)</i> is the heuristic
 153 function, and <i>g(v)</i> (sometimes denoted <i>c(s, v)</i>) is the
 154 known cost from the start to <i>v</i>.  Clearly, the efficiency of A*
 155 is highly dependent on the heuristic function with which it is used.
 156 </P>
 157
 158 <P>
 159 The A* algorithm is very similar to Dijkstra's Shortest Paths
 160 algorithm.  This implementation finds all the shortest paths from the
 161 start vertex to every other vertex by creating a search tree,
 162 examining vertices according to their remaining cost to some goal, as
 163 estimated by a heuristic function.  Most commonly, A* is used to find
 164 some specific goal vertex or vertices in a graph, after which the
 165 search is terminated.
 166 </P>
 167
 168 <P>
 169 A* is particularly useful for searching <i>implicit</i> graphs.
 170 Implicit graphs are graphs that are not completely known at the
 171 beginning of the search.  Upon visiting a vertex, its neighbors are
 172 "generated" and added to the search.  Implicit graphs are particularly
 173 useful for searching large state spaces -- in game-playing scenarios
 174 (e.g. chess), for example -- in which it may not be possible to store
 175 the entire graph.  Implicit searches can be performed with this
 176 implementation of A* by creating special visitors that generate
 177 neighbors of newly-expanded vertices.  Please note that
 178 <tt>astar_search_no_init()</tt> or <tt>astar_search_no_init_tree()</tt> must be
 179 used for implicit graphs; the basic
 180 <tt>astar_search()</tt> function requires a graph that models
 181 the <a href="VertexListGraph.html">Vertex List Graph</a> concept.  Both
 182 versions
 183 also require the graph type to model the <a
 184 href="IncidenceGraph.html">Incidence Graph</a> concept.
 185 </P>
 186
 187 <P>
 188 For the non-tree versions of the algorithm,
 189 this implementation of A* is based on an OPEN/CLOSED list formulation.
 190 Vertices on the OPEN list have been ``discovered''
 191 by the algorithm, but not ``expanded'' (we have not discovered their
 192 adjacent vertices).  Vertices on the CLOSED list have been completely
 193 examined by our search (we have expanded them and added their children
 194 to the OPEN list).  Vertices that are on neither list have not been
 195 encountered in any context so far in our search.  A major advantage of
 196 this formulation of the A* algorithm over other approaches is that it
 197 avoids ``cycles'' in the state space; the search will not become
 198 trapped by loops in the graph.  The OPEN/CLOSED lists are implemented
 199 using BGL's vertex coloring mechanisms.  Vertices in OPEN are colored
 200 gray, vertices in CLOSED are colored black, and undiscovered vertices
 201 are colored white.  For the versions of the algorithm whose names end in
 202 <tt>_tree</tt>, all vertices are assumed to always be white, leading to
 203 checking for repeated vertices being done using the distance map.  If a dummy
 204 value is used for the distance map and the graph contains cycles, the algorithm
 205 will probably enter an infinite loop.
 206 </P>
 207
 208 <P>
 209 The criteria for expanding a vertex on the OPEN list is that it has
 210 the lowest <i>f(v) = g(v) + h(v)</i> value of all vertices on OPEN.
 211 Cost information about vertices is stored in a property map.
 212 </P>
 213
 214 <P>
 215 The following is the pseudocode for the A* heuristic search algorithm.
 216 In the pseudocode, <i>h</i> is the heuristic function, <i>w</i> is the
 217 edge weight, <i>d</i> is the distance of a vertex from <i>s</i>, and
 218 <i>Q</i> is a priority queue, sorted by <i>f</i>, the estimated cost
 219 to the goal of the path through a vertex.  <i>p</i> is a predecessor
 220 map.  The visitor event points for the algorithm are indicated by the
 221 labels on the right.
 222 </P>
 223
 224 <table>
 225 <tr>
 226 <td valign="top">
 227 <pre>
 228 A*(<i>G</i>, <i>s</i>, <i>h</i>)
 229   <b>for</b> each vertex <i>u in V</i>
 230     <i>d[u] := f[u] := infinity</i>
 231     <i>color[u] :=</i> WHITE
 232     <i>p[u] := u</i>
 233   <b>end for</b>
 234   <i>color[s] :=</i> GRAY
 235   <i>d[s] := 0</i>
 236   <i>f[s] := h(s)</i>
 237   INSERT(<i>Q, s</i>)
 238   <b>while</b> (<i>Q != &Oslash;</i>)
 239     <i>u :=</i> EXTRACT-MIN(<i>Q</i>)
 240     <b>for</b> each vertex <i>v in Adj[u]</i>
 241       <b>if</b> (<i>w(u,v) + d[u] &lt; d[v]</i>)
 242         <i>d[v] := w(u,v) + d[u]</i>
 243         <i>f[v] := d[v] + h(v)</i>
 244         <i>p[v] := u</i>
 245         <b>if</b> (<i>color[v] =</i> WHITE)
 246           <i>color[v] :=</i> GRAY
 247           INSERT(<i>Q, v</i>)
 248         <b>else if</b> (<i>color[v] =</i> BLACK)
 249           <i>color[v] :=</i> GRAY
 250           INSERT(<i>Q, v</i>)
 251         <b>end if</b>
 252       <b>else</b>
 253         <i>...</i>
 254     <b>end for</b>
 255     <i>color[u] :=</i> BLACK
 256   <b>end while</b>
 257 </pre>
 258 </td>
 259 <td valign="top">
 260 <pre>
 261
 262 initialize vertex <i>u</i>
 263
 264
 265
 266
 267
 268
 269
 270 discover vertex <i>s</i>
 271
 272 examine vertex <i>u</i>
 273 examine edge <i>(u,v)</i>
 274
 275 edge <i>(u,v)</i> relaxed
 276
 277
 278
 279
 280 discover vertex <i>v</i>
 281
 282
 283 reopen vertex <i>v</i>
 284
 285
 286 edge <i>(u,v)</i> not relaxed
 287
 288 finish vertex <i>u</i>
 289 </pre>
 290 </td>
 291 </tr>
 292 </table>
 293
 294 <h3>Where Defined</h3>
 295
 296 <a href="../../../boost/graph/astar_search.hpp"><tt>boost/graph/astar_search.hpp</tt></a>
 297
 298 <h3>Parameters</h3>
 299
 300 IN: <tt>const VertexListGraph&amp; g</tt>
 301 <blockquote>
 302   The graph object on which the algorithm will be applied for <tt>astar_search()</tt>.  The type
 303   <tt>VertexListGraph</tt> must be a model of the <a
 304   href="VertexListGraph.html">
 305   Vertex List Graph</a> and <a href="IncidenceGraph.html">Incidence Graph</a>
 306   concepts.
 307 </blockquote>
 308
 309 IN: <tt>const IncidenceGraph&amp; g</tt>
 310 <blockquote>
 311   The graph object on which the algorithm will be applied for <tt>astar_search_no_init()</tt>.  The type
 312   <tt>IncidenceGraph</tt> must be a model of the
 313   <a href="IncidenceGraph.html">Incidence Graph</a>
 314   concept.
 315 </blockquote>
 316
 317 IN: <tt>vertex_descriptor s</tt>
 318 <blockquote>
 319   The start vertex for the search.  All distances will be calculated
 320   from this vertex, and the shortest paths tree (recorded in the
 321   predecessor map) will be rooted at this vertex.
 322 </blockquote>
 323
 324 IN: <tt>AStarHeuristic h</tt>
 325 <blockquote>
 326   The heuristic function that guides the search.  The type
 327   <tt>AStarHeuristic</tt> must be a model of the <a href="AStarHeuristic.html">AStarHeuristic</a>
 328   concept.
 329 </blockquote>
 330
 331 <h3>Named Parameters</h3>
 332
 333 IN: <tt>weight_map(WeightMap w_map)</tt>
 334 <blockquote>
 335    The weight or ``length'' of each edge in the graph.  The weights
 336    must all be non-negative; the algorithm will throw a <a
 337    href="./exception.html#negative_edge"><tt>negative_edge</tt></a>
 338    exception if one of the edges is negative.  The type
 339    <tt>WeightMap</tt> must be a model of <a
 340    href="../../property_map/doc/ReadablePropertyMap.html"><tt>Readable
 341    Property Map</tt></a>.  The edge descriptor type of the graph needs
 342    to be usable as the key type for the weight map.  The value type
 343    for this map must be the same as the value type of the distance
 344    map.<br>
 345    <b>Default:</b> <tt>get(edge\_weight, g)</tt>
 346 </blockquote>
 347
 348 IN: <tt>vertex_index_map(VertexIndexMap i_map)</tt>
 349 <blockquote>
 350   This maps each vertex to an integer in the range <tt>[0,
 351   num_vertices(g))</tt>.  This is necessary in non-tree versions of the
 352   algorithm for efficient updates of
 353   the heap data structure when an edge is relaxed.  The type
 354   <tt>VertexIndexMap</tt> must be a model of <a
 355   href="../../property_map/doc/ReadablePropertyMap.html"><tt>Readable
 356   Property Map</tt></a>.  The value type of the map must be an integer
 357   type.  The vertex descriptor type of the graph needs to be usable as
 358   the key type of the map.<br>
 359
 360   <b>Default:</b> <tt>get(vertex_index, g)</tt>.
 361    Note: if you use this default, make sure your graph has
 362    an internal <tt>vertex_index</tt> property. For example,
 363    <tt>adjacency_list</tt> with <tt>VertexList=listS</tt> does
 364    not have an internal <tt>vertex_index</tt> property.
 365 </blockquote>
 366
 367 OUT: <tt>predecessor_map(PredecessorMap p_map)</tt>
 368 <blockquote>
 369
 370   The predecessor map records the edges in the minimum spanning tree.
 371   Upon completion of the algorithm, the edges <tt>(p[u],u)</tt> for
 372   all <tt>u</tt> in <tt>V</tt> are in the minimum spanning tree.  If
 373   <tt>p[u] = u</tt> then <tt>u</tt> is either the start vertex or a
 374   vertex that is not reachable from the start.  The
 375   <tt>PredecessorMap</tt> type must be a <a
 376   href="../../property_map/doc/ReadWritePropertyMap.html"><tt>Read/Write
 377   Property Map</tt></a> with key and vertex types the same as the
 378   vertex descriptor type of the graph.<br>
 379
 380   <b>Default:</b> <tt>dummy_property_map</tt>
 381 </blockquote>
 382
 383 UTIL/OUT: <tt>distance_map(DistanceMap d_map)</tt>
 384 <blockquote>
 385
 386   The shortest path weight from the start vertex <tt>s</tt> to each
 387   vertex in the graph <tt>g</tt> is recorded in this property map.
 388   The shortest path weight is the sum of the edge weights along the
 389   shortest path.  The type <tt>DistanceMap</tt> must be a model of <a
 390   href="../../property_map/doc/ReadWritePropertyMap.html"><tt>Read/Write
 391   Property Map</tt></a>.  The vertex descriptor type of the graph
 392   needs to be usable as the key type of the distance map.  The value
 393   type of the distance map is the element type of a <a
 394   href="./Monoid.html"><tt>Monoid</tt></a> formed with the
 395   <tt>combine</tt> function object and the zero object for the
 396   identity element.  Also the distance value type must have a <a
 397   href="http://www.sgi.com/tech/stl/StrictWeakOrdering.html"><tt>StrictWeakOrdering</tt></a>
 398   provided by the <tt>compare</tt> function object.  A
 399   <tt>constant_writable_property_map</tt> returning the infinity value can be
 400   used for this parameter in tree versions of the algorithm when the graph does
 401   not contain a directed cycle.<br>
 402
 403   <b>Default:</b> <tt>shared_array_property_map</tt>
 404   with the same value type as the
 405   <tt>WeightMap</tt>, and of size <tt>num_vertices(g)</tt>, and using
 406   the <tt>i_map</tt> for the index map.
 407 </blockquote>
 408
 409 UTIL/OUT: <tt>rank_map(CostMap c_map)</tt>
 410 <blockquote>
 411
 412   The <i>f</i>-value for each vertex.  The <i>f</i>-value is defined
 413   as the sum of the cost to get to a vertex from the start vertex, and
 414   the estimated cost (as returned by the heuristic function
 415   <tt>h</tt>) from the vertex to a goal.  The type <tt>CostMap</tt>
 416   must be a model of <a
 417   href="../../property_map/doc/ReadWritePropertyMap.html"><tt>Read/Write
 418   Property Map</tt></a> in non-tree versions of the algorithm, and <a
 419   href="../../property_map/doc/WritablePropertyMap.html"><tt>Writable Property
 420   Map</tt></a> in tree versions of the algorithm.  The vertex descriptor type
 421   of the graph
 422   needs to be usable as the key type of the distance map.  The value
 423   type of the distance map is the element type of a <a
 424   href="./Monoid.html"><tt>Monoid</tt></a> formed with the
 425   <tt>combine</tt> function object and the zero object for the
 426   identity element.  Also the distance value type must have a <a
 427   href="http://www.sgi.com/tech/stl/StrictWeakOrdering.html"><tt>StrictWeakOrdering</tt></a>
 428   provided by the <tt>compare</tt> function object.  The value type
 429   for this map must be the same as the value type for the distance
 430   map.  In tree versions of the algorithm, <tt>null_property_map</tt> can be
 431   used for this parameter.<br>
 432
 433   <b>Default:</b> <tt>shared_array_property_map</tt>
 434   with the same value type as the
 435   <tt>DistanceMap</tt>, and of size <tt>num_vertices(g)</tt>, and using
 436   the <tt>i_map</tt> for the index map.
 437 </blockquote>
 438
 439 UTIL/OUT: <tt>color_map(ColorMap c_map)</tt>
 440 <blockquote>
 441
 442   This is used during the execution of non-tree versions of the algorithm to
 443   mark the
 444   vertices, indicating whether they are on the OPEN or CLOSED lists.
 445   The vertices start out white and become gray when they are inserted
 446   into the OPEN list.  They then turn black when they are examined and
 447   placed on the CLOSED list.  At the end of the algorithm, vertices
 448   reachable from the source vertex will have been colored black.  All
 449   other vertices will still be white.  The type <tt>ColorMap</tt> must
 450   be a model of <a
 451   href="../../property_map/doc/ReadWritePropertyMap.html"><tt>Read/Write
 452   Property Map</tt></a>.  A vertex descriptor must be usable as the
 453   key type of the map, and the value type of the map must be a model
 454   of <a href="./ColorValue.html"><tt>Color Value</tt></a>.<br>
 455
 456   <b>Default:</b> <tt>shared_array_property_map</tt>
 457   of value type <tt>default_color_type</tt>, with size
 458   <tt>num_vertices(g)</tt>, and using
 459   the <tt>i_map</tt> for the index map.
 460 </blockquote>
 461
 462 IN: <tt>distance_compare(CompareFunction cmp)</tt>
 463 <blockquote>
 464
 465   This function is use to compare distances to determine which vertex
 466   is closer to the start vertex, and to compare <i>f</i>-values to
 467   determine which vertex on the OPEN list to examine next.  The
 468   <tt>CompareFunction</tt> type must be a model of <a
 469   href="http://www.sgi.com/tech/stl/BinaryPredicate.html"><tt>Binary
 470   Predicate</tt></a> and have argument types that match the value type
 471   of the <tt>DistanceMap</tt> property map.<br>
 472
 473   <b>Default:</b> <tt>std::less&lt;D&gt;</tt> with <tt>D = typename
 474   property_traits&lt;DistanceMap&gt;::value_type</tt>.
 475 </blockquote>
 476
 477 IN: <tt>distance_combine(CombineFunction cmb)</tt>
 478 <blockquote>
 479
 480   This function is used to combine distances to compute the distance
 481   of a path, and to combine distance and heuristic values to compute
 482   the <i>f</i>-value of a vertex.  The <tt>CombineFunction</tt> type
 483   must be a model of <a
 484   href="http://www.sgi.com/tech/stl/BinaryFunction.html"><tt>Binary
 485   Function</tt></a>.  Both argument types of the binary function must
 486   match the value type of the <tt>DistanceMap</tt> property map (which
 487   is the same as that of the <tt>WeightMap</tt> and <tt>CostMap</tt>
 488   property maps).  The result type must be the same type as the
 489   distance value type.<br>
 490
 491   <b>Default:</b> <tt>std::plus&lt;D&gt;</tt> with <tt>D = typename
 492   property_traits&lt;DistanceMap&gt;::value_type</tt>.
 493 </blockquote>
 494
 495 IN: <tt>distance_inf(D inf)</tt>
 496 <blockquote>
 497
 498   The <tt>inf</tt> object must be the greatest value of any <tt>D</tt>
 499   object.  That is, <tt>compare(d, inf) == true</tt> for any <tt>d !=
 500   inf</tt>.  The type <tt>D</tt> is the value type of the
 501   <tt>DistanceMap</tt>.<br>
 502
 503   <b>Default:</b> <tt>std::numeric_limits&lt;D&gt;::max()</tt>
 504 </blockquote>
 505
 506 IN: <tt>distance_zero(D zero)</tt>
 507 <blockquote>
 508
 509   The <tt>zero</tt> value must be the identity element for the <a
 510   href="./Monoid.html"><tt>Monoid</tt></a> formed by the distance
 511   values and the <tt>combine</tt> function object.  The type
 512   <tt>D</tt> is the value type of the <tt>DistanceMap</tt>.<br>
 513
 514   <b>Default</b>: <tt>D()</tt> with <tt>D = typename
 515   property_traits&lt;DistanceMap&gt;::value_type</tt>.
 516 </blockquote>
 517
 518 OUT: <tt>visitor(AStarVisitor v)</tt>
 519 <blockquote>
 520
 521   Use this to specify actions that you would like to happen during
 522   certain event points within the algorithm.  The type
 523   <tt>AStarVisitor</tt> must be a model of the <a
 524   href="AStarVisitor.html"><tt>AStarVisitor</tt></a> concept. The
 525   visitor object is passed by value <a href="#1">[1]</a>.<br>
 526
 527   <b>Default:</b> <tt>astar_visitor&lt;null_visitor&gt;</tt>
 528 </blockquote>
 529
 530 <H3>Complexity</H3>
 531
 532 <P>
 533 The time complexity is <i>O((E + V) log V)</i>.
 534
 535 <h3>Visitor Event Points</h3>
 536
 537 <ul>
 538 <li><b><tt>vis.initialize_vertex(u, g)</tt></b>
 539   is invoked on each vertex in the graph before the start of the
 540   algorithm.
 541 <li><b><tt>vis.discover_vertex(v, g)</tt></b>
 542   is invoked when a vertex is first discovered and is added to the
 543   OPEN list.
 544 <li><b><tt>vis.examine_vertex(u, g)</tt></b>
 545   is invoked when a vertex is popped from
 546   the queue (i.e., it has the lowest cost on the OPEN list).
 547 <li><b><tt>vis.examine_edge(e, g)</tt></b>
 548   is invoked on each out-edge of a vertex immediately after it is
 549   examined.
 550 <li><b><tt>vis.edge_relaxed(e, g)</tt></b>
 551   is invoked on edge <i>(u,v)</i> if <i>d[u] + w(u,v) &lt; d[v]</i>.
 552 <li><b><tt>vis.edge_not_relaxed(e, g)</tt></b>
 553   is invoked if the edge is not relaxed (see above).
 554 <li><b><tt>vis.black_target(e, g)</tt></b>
 555    is invoked when a vertex that is on the CLOSED list is
 556   "rediscovered" via a more efficient path, and is re-added to the
 557   OPEN list.
 558 <li><b><tt>vis.finish_vertex(u, g)</tt></b>
 559   is invoked on a vertex when it is added to the CLOSED list, which
 560   happens after all of its out edges have been examined.
 561 </ul>
 562
 563 <H3>Example</H3>
 564
 565 <P>
 566 See <a href="../example/astar-cities.cpp">
 567 <TT>example/astar-cities.cpp</TT></a> for an example of
 568 using A* search.
 569
 570 <H3>Notes</H3>
 571
 572 <a name="1">[1]</a> Since the visitor parameter is passed by value, if
 573 your visitor contains state then any changes to the state during the
 574 algorithm will be made to a copy of the visitor object, not the
 575 visitor object passed in.  Therefore you may want the visitor to hold
 576 this state by pointer or reference.
 577
 578 <br>
 579 <HR>
 580 <TABLE>
 581 <TR valign=top>
 582 <TD nowrap>Copyright &copy; 2004</TD><TD>
 583 <A HREF="http://www.cs.rpi.edu/~beevek/">Kristopher Beevers</A>,
 584 Rensselaer Polytechnic Institute (<A
 585 HREF="mailto:beevek@cs.rpi.edu">beevek@cs.rpi.edu</A>)
 586 </TD></TR></TABLE>
 587
 588 </BODY>
 589 </HTML>