Parent

Files

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.

# 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

Public Instance Methods

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

Return the number of components found so far.

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

[Validate]

Generated with the Darkfish Rdoc Generator 2.