class RGL::Graph::TarjanSccVisitor

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

Attributes

comp_map[R]

Public Class Methods

new(g) click to toggle source

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

Calls superclass method
# 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

Public Instance Methods

handle_examine_vertex(v) click to toggle source
# 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) click to toggle source
# 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() click to toggle source

Return the number of components found so far.

# File lib/rgl/connected_components.rb, line 91
def num_comp
  @c_index
end

Private Instance Methods

min_discover_time(u, v) click to toggle source
# File lib/rgl/connected_components.rb, line 97
def min_discover_time(u, v)
  @discover_time_map[u] < @discover_time_map[v] ? u : v
end