Dijkstra Visitor Concept

This concept defines the visitor interface for dijkstra_shortest_paths() and related algorithms. The user can create a class that matches this interface, and then pass objects of the class into dijkstra_shortest_paths() to augment the actions taken during the search.

Copy Constructible (copying a visitor should be a lightweight operation).

Notation

Associated Types

none

Valid Expressions

Name	Expression	Return Type	Description
Initialize Vertex	vis.initialize_vertex(u, g)	void	This is invoked one each vertex of the graph when it is initialized.
Examine Vertex	vis.examine_vertex(u, g)	void	This is invoked on a vertex as it is popped from the queue. 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 discovered.
Discover Vertex	vis.discover_vertex(u, g)	void	This is invoked when a vertex is encountered for the first time.
Edge Relaxed	vis.edge_relaxed(e, g)	void	Upon examination, if the following condition holds then the edge is relaxed (its distance is reduced), and this method is invoked.
tie(u,v) = incident(e, g);
D d_u = get(d, u), d_v = get(d, v);
W w_e = get(w, e);
assert(compare(combine(d_u, w_e), d_v));

Edge Not Relaxed	vis.edge_not_relaxed(e, g)	void	Upon examination, if the edge is not relaxed (see above) then this method is invoked.
Finish Vertex	vis.finish_vertex(u, g)	void	This invoked on a vertex after all of its out edges have been added to the search tree and all of the adjacent vertices have been discovered (but before their out-edges have been examined).

Models

dijkstra_visitor

Python

To implement a model of the DijkstraVisitor concept in Python, create a new class that derives from the DijkstraVisitor type of the graph, which will be named GraphType.DijkstraVisitor. The events and syntax are the same as with visitors in C++. Here is an example for the Python bgl.Graph graph type:

class count_tree_edges_dijkstra_visitor(bgl.Graph.DijkstraVisitor):
  def __init__ (self, name_map):
    bgl.Graph.DijkstraVisitor. __init__ (self)
    self.name_map = name_map

  def edge_relaxed(self, e, g):
    (u, v) = (g.source(e), g.target(e))
    print "Relaxed edge ",
    print self.name_map[u],
    print " -> ",
    print self.name_map[v]

Dijkstra Visitor Concept

Dijkstra Visitor Concept

Refinement of

Notation

Associated Types

Valid Expressions

Models

Python