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

color_map[R]

@return [Hash] a map which store the colors for each vertex

Public Class Methods

included(base) click to toggle source
    # 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
new(graph) click to toggle source

Create a new GraphVisitor on graph. @param [Graph] graph

Calls superclass method RGL::GraphWrapper::new
   # File lib/rgl/graph_visitor.rb
44 def initialize(graph)
45   super(graph)
46   reset
47 end

Public Instance Methods

attach_distance_map(map = Hash.new(0)) click to toggle source

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
finished_vertex?(v) click to toggle source

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
follow_edge?(u, v) click to toggle source

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
reset() click to toggle source

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

   # File lib/rgl/graph_visitor.rb
51 def reset
52   @color_map = Hash.new(:WHITE)
53 end