<HTML>
<!--
     Copyright (c) 2004 Kris Beevers
    
     Distributed under the Boost Software License, Version 1.0.
     (See accompanying file LICENSE_1_0.txt or copy at
     http://www.boost.org/LICENSE_1_0.txt)
  -->
<Head>
<Title>Boost Graph Library: AStarVisitor</Title>
<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 
        ALINK="#ff0000"> 
<IMG SRC="../../../boost.png" 
     ALT="C++ Boost" width="277" height="86"> 

<BR Clear>

<H1>AStar Visitor Concept</H1>

This concept defines the visitor interface for <a
href="./astar_search.html"><tt>astar_search()</tt></a>.  Users can
define a class with the AStar Visitor interface and pass an object of
the class to <tt>astar_search()</tt>, thereby augmenting the actions
taken during the graph search.

<h3>Refinement of</h3>

<a href="../../utility/CopyConstructible.html">Copy Constructible</a>
(copying a visitor should be a lightweight operation).


<h3>Notation</h3>

<Table>
<TR>
<TD><tt>V</tt></TD>
<TD>A type that is a model of AStar Visitor.</TD>
</TR>

<TR>
<TD><tt>vis</tt></TD>
<TD>An object of type <tt>V</tt>.</TD>
</TR>

<TR>
<TD><tt>G</tt></TD>
<TD>A type that is a model of Graph.</TD>
</TR>

<TR>
<TD><tt>g</tt></TD>
<TD>An object of type <tt>const G&amp;</tt>.</TD>
</TR>

<TR>
<TD><tt>e</tt></TD>
<TD>An object of type <tt>boost::graph_traits&lt;G&gt;::edge_descriptor</tt>.</TD>
</TR>

<TR>
<TD><tt>s,u,v</tt></TD>
<TD>An object of type <tt>boost::graph_traits&lt;G&gt;::vertex_descriptor</tt>.</TD>
</TR>

<TR>
<TD><tt>d</tt></TD>
<TD>An object of type <tt>DistanceMap</tt>.</TD>
</TR>

<TR>
<TD><tt>WeightMap</tt></TD>
<TD>A type that is a model of <a
href="../../property_map/doc/ReadablePropertyMap.html">Readable Property
Map</a>.</TD>
</TR>

<TR>
<TD><tt>w</tt></TD>
<TD>An object of type <tt>WeightMap</tt>.</TD>
</TR>

</table>

<h3>Associated Types</h3>

none
<p>

<h3>Valid Expressions</h3>

<table border>
<tr>
<th>Name</th><th>Expression</th><th>Return Type</th><th>Description</th>
</tr>

<tr>
<td>Initialize Vertex</td>
<td><tt>vis.initialize_vertex(u, g)</tt></td>
<td><tt>void</tt></td>
<td>
This is invoked on each vertex of the graph when it is first
initialized (i.e., when its property maps are initialized).
</td>
</tr>

<tr>
<td>Discover Vertex</td>
<td><tt>vis.discover_vertex(u, g)</tt></td>
<td><tt>void</tt></td>
<td>
This is invoked when a vertex is first discovered and is added to the
OPEN list.
</td>
</tr>

<tr>
<td>Examine Vertex</td>
<td><tt>vis.examine_vertex(u, g)</tt></td>
<td><tt>void</tt></td>
<td>
This is invoked on a vertex as it is popped from the queue (i.e., it
has the lowest cost on the OPEN list). This happens immediately before
<tt>examine_edge()</tt> is invoked on each of the out-edges of vertex
<tt>u</tt>.
</td>
</tr>

<tr>
<td>Examine Edge</td>
<td><tt>vis.examine_edge(e, g)</tt></td>
<td><tt>void</tt></td>
<td>
This is invoked on every out-edge of each vertex after it is
examined.
</td>
</tr>


<tr>
<td>Edge Relaxed</td>
<td><tt>vis.edge_relaxed(e, g)</tt></td>
<td><tt>void</tt></td>
<td>
Upon examination, if the following condition holds then the edge is
relaxed (the distance of its target vertex is reduced) and this method
is invoked:
<blockquote>
<pre>
tie(u, s) = incident(e, g);
D d_u = get(d, u), d_v = get(d, s);
W w_e = get(w, e);
assert(compare(combine(d_u, w_e), d_s));
</pre>
</blockquote>
</td>
</tr>

<tr>
<td>Edge Not Relaxed</td>
<td><tt>vis.edge_not_relaxed(e, g)</tt></td>
<td><tt>void</tt></td>
<td>
Upon examination, if an edge is not relaxed (see above) then this
method is invoked.
</td>
</tr>

<tr>
<td>Black Target</td>
<td><tt>vis.black_target(e, g)</tt></td>
<td><tt>void</tt></td>
<td>
This is invoked when a vertex that is on the CLOSED list is
``rediscovered'' via a more efficient path and is re-added to the
OPEN list.
</td>
</tr>

<tr>
<td>Finish Vertex</td>
<td><tt>vis.finish_vertex(u, g)</tt></td>
<td><tt>void</tt></td>
<td>
This is invoked on a vertex when it is added to the CLOSED list. This
happens after all of its out-edges have been examined.
</td>
</tr>

</table>

<h3>Models</h3>

<ul>
 <li><a href="./astar_visitor.html"><tt>astar_visitor</tt></a>
</ul>


<h3>See also</h3>

<a href="./visitor_concepts.html">Visitor concepts</a>

<br>
<HR>
<TABLE>
<TR valign=top>
<TD nowrap>Copyright &copy; 2004</TD><TD>
<A HREF="http://www.cs.rpi.edu/~beevek/">Kristopher Beevers</A>,
Rensselaer Polytechnic Institute (<A
HREF="mailto:beevek@cs.rpi.edu">beevek@cs.rpi.edu</A>)
</TD></TR></TABLE>

</BODY>
</HTML>