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