AStar Visitor Concept
This concept defines the visitor interface for astar_search(). Users can
define a class with the AStar Visitor interface and pass an object of
the class to astar_search(), thereby augmenting the actions
taken during the graph search.
Refinement of
Copy Constructible
(copying a visitor should be a lightweight operation).
Notation
V |
A type that is a model of AStar Visitor. |
vis |
An object of type V. |
G |
A type that is a model of Graph. |
g |
An object of type G. |
e |
An object of type boost::graph_traits<G>::edge_descriptor. |
s,u,v |
An object of type boost::graph_traits<G>::vertex_descriptor. |
d |
An object of type DistanceMap. |
WeightMap |
A type that is a model of Readable Property
Map. |
w |
An object of type WeightMap. |
Associated Types
none
Valid Expressions
Name | Expression | Return Type | Description |
Initialize Vertex |
vis.initialize_vertex(u, g) |
void |
This is invoked on each vertex of the graph when it is first
initialized (i.e., when its property maps are initialized).
|
Discover Vertex |
vis.discover_vertex(u, g) |
void |
This is invoked when a vertex is first discovered and is added to the
OPEN list.
|
Examine Vertex |
vis.examine_vertex(u, g) |
void |
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
examine_edge() is invoked on each of the out-edges of vertex
u.
|
Examine Edge |
vis.examine_edge(e, g) |
void |
This is invoked on every out-edge of each vertex after it is
examined.
|
Edge Relaxed |
vis.edge_relaxed(e, g) |
void |
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:
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));
|
Edge Not Relaxed |
vis.edge_not_relaxed(e, g) |
void |
Upon examination, if an edge is not relaxed (see above), then this
method is invoked.
|
Black Target |
vis.black_target(e, g) |
void |
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.
|
Finish Vertex |
vis.finish_vertex(u, g) |
void |
This is invoked on a vertex when it is added to the CLOSED list, which
happens after all of its out edges have been examined.
|
Models
See also
Visitor concepts
|