Module RGL::GraphVisitor
In: lib/rgl/traversal.rb

Module GraphVisitor defines the BGL BFS Visitor Concept).

Visitors provide a mechanism for extending an algorithm (i.e., for customizing what is done at each step of the algorithm). They allow users to insert their own operations at various steps within a graph algorithm.

Graph algorithms typically have multiple event points where one may want to insert a call-back. Therefore, visitors have several methods that correspond to the various event points. Each algorithm has a different set of event points. The following are common to both DFS and BFS search.

 * examine_vertex
 * finish_vertex
 * examine_edge
 * tree_edge
 * back_edge
 * forward_edge

These methods are all called handle_* and can be set to appropriate blocks, using the methods set_*_event_handler, which are defined for each event mentioned above.

As an alternative, you can also override the handle_* methods in a subclass, to configure the algorithm (as an example, see TarjanSccVisitor).

During a graph traversal, vertices are colored using the colors :GRAY (when waiting) and :BLACK when finished. All other vertices are :WHITE. The color_map is also maintained in the visitor.

Methods

Included Modules

GraphWrapper

Attributes

color_map  [R] 

Public Class methods

Visitor Event Points

Answer the distance to the start vertex.

Create a new GraphVisitor on graph.

Public Instance methods

Attach a map to the visitor which records the distance of a visited vertex to the start vertex.

This is similar to BGLs distance_recorder.

After the distance_map is attached, the visitor has a new method distance_to_root, which answers the distance to the start vertex.

Returns true if vertex v is colored :BLACK (i.e. finished).

Mark each vertex unvisited (i.e. :WHITE)

[Validate]