Module: RGL::GraphVisitor

Extended by:
ClassMethods
Includes:
GraphWrapper
Included in:
BFSIterator, DFSVisitor, DijkstraVisitor
Defined in:
lib/rgl/graph_visitor.rb

Overview

Module GraphVisitor defines the 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.

Defined Under Namespace

Modules: ClassMethods, DistanceMapSupport

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Instance Attribute Details

#color_map ⇒ Hash (readonly)

Returns a map which store the colors for each vertex.

Returns:

  • (Hash) —

    a map which store the colors for each vertex



40
41
42
 
# File 'lib/rgl/graph_visitor.rb', line 40

def color_map
  @color_map
end

#graph ⇒ Graph Originally defined in module GraphWrapper

Returns the wrapped graph.

Returns:

  • (Graph) —

    the wrapped graph

Class Method Details

.def_event_handlers(*events) ⇒ Object Also known as: def_event_handler Originally defined in module ClassMethods

Defines an event handler.

Instance Method Details

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

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.



76
77
78
79
80
81
 
# File 'lib/rgl/graph_visitor.rb', line 76

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

  # add distance map support to the current visitor instance
  extend(DistanceMapSupport)
end

#finished_vertex?(v) ⇒ Boolean

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

Returns:

  • (Boolean) 


57
58
59
 
# File 'lib/rgl/graph_visitor.rb', line 57

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) 


63
64
65
 
# File 'lib/rgl/graph_visitor.rb', line 63

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

#initialize(graph) ⇒ Object

Create a new GraphVisitor on graph.

Parameters:



44
45
46
47
 
# File 'lib/rgl/graph_visitor.rb', line 44

def initialize(graph)
  super(graph)
  reset
end

#reset ⇒ Object

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



51
52
53
 
# File 'lib/rgl/graph_visitor.rb', line 51

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