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