Module: RGL::GraphVisitor

Includes:
GraphWrapper
Included in:
BFSIterator, DFSVisitor
Defined in:
lib/rgl/traversal.rb

Overview

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.

Instance Attribute Summary collapse

Attributes included from GraphWrapper

#graph

Class Method Summary collapse

Instance Method Summary collapse

Instance Attribute Details

#color_map ⇒ Object (readonly)

Returns the value of attribute color_map.



70
71
72
 
# File 'lib/rgl/traversal.rb', line 70

def color_map
  @color_map
end

Class Method Details

.def_event_handler(m) ⇒ Object

Visitor Event Points



127
128
129
130
131
132
133
134
135
136
137
138
 
# File 'lib/rgl/traversal.rb', line 127

def self.def_event_handler (m)
  params = m =~ /edge/ ? "u,v" : "u"
  self.class_eval %{
    def handle_#{m} (#{params})
      @#{m}_event_handler.call(#{params}) if defined? @#{m}_event_handler
    end

    def set_#{m}_event_handler (&b)
      @#{m}_event_handler = b
    end
  }
end

Instance Method Details

#attach_distance_map(map = Hash.new(0)) ⇒ Object

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



100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
 
# File 'lib/rgl/traversal.rb', line 100

def attach_distance_map (map = Hash.new(0))
  @dist_map = map

  class << self

    def handle_tree_edge (u, v)
      super
      @dist_map[v] = @dist_map[u] + 1
    end

    # Answer the distance to the start vertex.

    def distance_to_root (v)
      @dist_map[v]
    end

  end	# class
end

#finished_vertex?(v) ⇒ Boolean

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

Returns:

  • (Boolean) 


87
88
89
 
# File 'lib/rgl/traversal.rb', line 87

def finished_vertex? (v)
  @color_map[v] == :BLACK
end

#follow_edge?(u, v) ⇒ Boolean

Shall we follow the edge (u,v); i.e. v has color :WHITE

Returns:

  • (Boolean) 


121
122
123
 
# File 'lib/rgl/traversal.rb', line 121

def follow_edge? (u, v)			# :nodoc:
  @color_map[v] == :WHITE
end

#initialize(graph) ⇒ Object

Create a new GraphVisitor on graph.



74
75
76
77
 
# File 'lib/rgl/traversal.rb', line 74

def initialize (graph)
  super graph
  reset
end

#reset ⇒ Object

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



81
82
83
 
# File 'lib/rgl/traversal.rb', line 81

def reset
  @color_map = Hash.new(:WHITE)
end