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.
color_map | [R] |
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.