Class: RGL::Graph::TarjanSccVisitor

Inherits:
DFSVisitor show all
Defined in:
lib/rgl/connected_components.rb

Overview

This GraphVisitor is used by strongly_connected_components to compute the strongly connected components of a directed graph.

Instance Attribute Summary collapse

Attributes included from RGL::GraphVisitor

#color_map

Attributes included from RGL::GraphWrapper

#graph

Instance Method Summary collapse

Methods included from RGL::GraphVisitor

#attach_distance_map, def_event_handler, #finished_vertex?, #follow_edge?, #reset

Constructor Details

#initialize(g) ⇒ TarjanSccVisitor

Creates a new TarjanSccVisitor for graph g, which should be directed.



47
48
49
50
51
52
53
54
55
 
# File 'lib/rgl/connected_components.rb', line 47

def initialize (g)
  super g
  @root_map           = {}
  @comp_map           = {}
  @discover_time_map  = {}
  @dfs_time           = 0
  @c_index            = 0
  @stack              = []
end

Instance Attribute Details

#comp_map ⇒ Object (readonly)

Returns the value of attribute comp_map.



43
44
45
 
# File 'lib/rgl/connected_components.rb', line 43

def comp_map
  @comp_map
end

Instance Method Details

#handle_examine_vertex(v) ⇒ Object 



57
58
59
60
61
62
63
 
# File 'lib/rgl/connected_components.rb', line 57

def handle_examine_vertex (v)
  @root_map[v] =  v
  @comp_map[v] =  -1
  @dfs_time    += 1
  @discover_time_map[v] = @dfs_time
  @stack.push(v)
end

#handle_finish_vertex(v) ⇒ Object 



65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
 
# File 'lib/rgl/connected_components.rb', line 65

def handle_finish_vertex (v)
  # Search adjacent vertex w with earliest discover time
  root_v = @root_map[v]
  graph.each_adjacent(v) do |w|
    if @comp_map[w] == -1
      root_v = min_discover_time(root_v, @root_map[w])
    end
  end
  @root_map[v] = root_v
  if root_v == v                  # v is topmost vertex of a SCC
    begin                         # pop off all vertices until v
      w = @stack.pop
      @comp_map[w] = @c_index
    end until w == v
    @c_index += 1
  end
end

#num_comp ⇒ Object

Return the number of components found so far.



85
86
87
 
# File 'lib/rgl/connected_components.rb', line 85

def num_comp
  @c_index
end