• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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
20This concept defines the visitor interface for <a
21href="./astar_search.html"><tt>astar_search()</tt></a>.  Users can
22define a class with the AStar Visitor interface and pass an object of
23the class to <tt>astar_search()</tt>, thereby augmenting the actions
24taken 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
73href="../../property_map/doc/ReadablePropertyMap.html">Readable Property
74Map</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
86none
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>
101This is invoked on each vertex of the graph when it is first
102initialized (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>
111This is invoked when a vertex is first discovered and is added to the
112OPEN 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>
121This is invoked on a vertex as it is popped from the queue (i.e., it
122has 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>
133This is invoked on every out-edge of each vertex after it is
134examined.
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>
144Upon examination, if the following condition holds then the edge is
145relaxed (the distance of its target vertex is reduced) and this method
146is invoked:
147<blockquote>
148<pre>
149tie(u, s) = incident(e, g);
150D d_u = get(d, u), d_v = get(d, s);
151W w_e = get(w, e);
152assert(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>
163Upon examination, if an edge is not relaxed (see above) then this
164method 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>
173This 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
175OPEN 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>
184This is invoked on a vertex when it is added to the CLOSED list. This
185happens 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://cs.krisbeevers.com/">Kristopher Beevers</A>,
208Rensselaer Polytechnic Institute (<A
209HREF="mailto:beevek@cs.rpi.edu">beevek@cs.rpi.edu</A>)
210</TD></TR></TABLE>
211
212</BODY>
213</HTML>
214