DFSVisitor
This GraphVisitor is used by strongly_connected_components to compute the strongly connected components of a directed graph.
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
# 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
# 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
Generated with the Darkfish Rdoc Generator 2.