214 lines
4.4 KiB
HTML
214 lines
4.4 KiB
HTML
<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://cs.krisbeevers.com/">Kristopher Beevers</A>,
|
|
Rensselaer Polytechnic Institute (<A
|
|
HREF="mailto:beevek@cs.rpi.edu">beevek@cs.rpi.edu</A>)
|
|
</TD></TR></TABLE>
|
|
|
|
</BODY>
|
|
</HTML>
|