# 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

- `astar_visitor`

### See also

Visitor concepts

Copyright © 2004 | Kristopher Beevers, Rensselaer Polytechnic Institute (beevek@cs.rpi.edu)