module RGL::GraphVisitor
Module GraphVisitor
defines the {www.boost.org/libs/graph/doc/visitor_concepts.html BGL Visitor Concepts}.
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 named 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
@return [Hash] a map which store the colors for each vertex
Public Class Methods
# File lib/rgl/graph_visitor.rb 126 def self.included(base) 127 # when GraphVisitor is included into a class/module, add class methods as well 128 base.extend ClassMethods 129 end
Create a new GraphVisitor
on graph. @param [Graph] graph
RGL::GraphWrapper::new
# File lib/rgl/graph_visitor.rb 44 def initialize(graph) 45 super(graph) 46 reset 47 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 {www.boost.org/libs/graph/doc/distance_recorder.html 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 76 def attach_distance_map(map = Hash.new(0)) 77 @distance_map = map 78 79 # add distance map support to the current visitor instance 80 extend(DistanceMapSupport) 81 end
Returns true if vertex v is colored :BLACK (i.e. finished).
# File lib/rgl/graph_visitor.rb 57 def finished_vertex?(v) 58 @color_map[v] == :BLACK 59 end
Shall we follow the edge (u,v); i.e. v has color :WHITE
# File lib/rgl/graph_visitor.rb 63 def follow_edge?(u, v) 64 @color_map[v] == :WHITE 65 end
Mark each vertex unvisited (i.e. :WHITE)
# File lib/rgl/graph_visitor.rb 51 def reset 52 @color_map = Hash.new(:WHITE) 53 end