<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&</tt>.</TD> </TR> <TR> <TD><tt>e</tt></TD> <TD>An object of type <tt>boost::graph_traits<G>::edge_descriptor</tt>.</TD> </TR> <TR> <TD><tt>s,u,v</tt></TD> <TD>An object of type <tt>boost::graph_traits<G>::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 © 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>