Class: RGL::Graph::TarjanSccVisitor

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

Overview

This RGL::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, #finished_vertex?, #follow_edge?, included, #reset

Methods included from RGL::GraphVisitor::ClassMethods

#def_event_handlers

Constructor Details

#initialize(g) ⇒ TarjanSccVisitor

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



50
51
52
53
54
55
56
57
58
 
# File 'lib/rgl/connected_components.rb', line 50

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.



46
47
48
 
# File 'lib/rgl/connected_components.rb', line 46

def comp_map
  @comp_map
end

Instance Method Details

#handle_examine_vertex(v) ⇒ Object 



60
61
62
63
64
65
66
 
# File 'lib/rgl/connected_components.rb', line 60

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 



68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
 
# File 'lib/rgl/connected_components.rb', line 68

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.



91
92
93
 
# File 'lib/rgl/connected_components.rb', line 91

def num_comp
  @c_index
end