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

Instance Method Summary collapse

Constructor Details

#initialize(g) ⇒ TarjanSccVisitor

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



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

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

Instance Attribute Details

#color_map ⇒ Hash (readonly) Originally defined in module RGL::GraphVisitor

Returns a map which store the colors for each vertex.

Returns:

  • (Hash) —

    a map which store the colors for each vertex

#comp_map ⇒ Object (readonly)

Returns the value of attribute comp_map.



48
49
50
 
# File 'lib/rgl/connected_components.rb', line 48

def comp_map
  @comp_map
end

#graph ⇒ Graph Originally defined in module RGL::GraphWrapper

Returns the wrapped graph.

Returns:

  • (Graph) —

    the wrapped graph

Instance Method Details

#handle_examine_vertex(v) ⇒ Object 



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

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 



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

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.



93
94
95
 
# File 'lib/rgl/connected_components.rb', line 93

def num_comp
  @c_index
end