module RGL::GraphVisitor
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 * examine_edge * tree_edge * back_edge * forward_edge * finish_vertex
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.
Attributes
Public Class Methods
# File lib/rgl/graph_visitor.rb 125 def self.included(base) 126 base.extend ClassMethods # when GraphVisitor is included into a class/module, add class methods as well 127 end
Create a new GraphVisitor
on graph.
# File lib/rgl/graph_visitor.rb 43 def initialize(graph) 44 super(graph) 45 reset 46 end
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.
# File lib/rgl/graph_visitor.rb 75 def attach_distance_map(map = Hash.new(0)) 76 @distance_map = map 77 78 # add distance map support to the current visitor instance 79 extend(DistanceMapSupport) 80 end
Returns true if vertex v is colored :BLACK (i.e. finished).
# File lib/rgl/graph_visitor.rb 56 def finished_vertex?(v) 57 @color_map[v] == :BLACK 58 end
Mark each vertex unvisited (i.e. :WHITE)
# File lib/rgl/graph_visitor.rb 50 def reset 51 @color_map = Hash.new(:WHITE) 52 end