class RGL::Graph::TarjanSccVisitor
This {GraphVisitor} is used by {#strongly_connected_components} to compute the strongly connected components of a directed graph.
Attributes
Public Class Methods
Source
# File lib/rgl/connected_components.rb 50 def initialize(g) 51 super g 52 @root_map = {} 53 @comp_map = {} 54 @discover_time_map = {} 55 @dfs_time = 0 56 @c_index = 0 57 @stack = [] 58 end
Creates a new TarjanSccVisitor
for graph g, which should be directed.
Calls superclass method
Public Instance Methods
Source
# File lib/rgl/connected_components.rb 60 def handle_examine_vertex(v) 61 @root_map[v] = v 62 @comp_map[v] = -1 63 @dfs_time += 1 64 @discover_time_map[v] = @dfs_time 65 @stack.push(v) 66 end
Source
# File lib/rgl/connected_components.rb 68 def handle_finish_vertex(v) 69 # Search adjacent vertex w with earliest discover time 70 root_v = @root_map[v] 71 72 graph.each_adjacent(v) do |w| 73 if @comp_map[w] == -1 74 root_v = min_discover_time(root_v, @root_map[w]) 75 end 76 end 77 78 @root_map[v] = root_v 79 80 if root_v == v # v is topmost vertex of a SCC 81 begin # pop off all vertices until v 82 w = @stack.pop 83 @comp_map[w] = @c_index 84 end until w == v 85 @c_index += 1 86 end 87 end
Source
# File lib/rgl/connected_components.rb 91 def num_comp 92 @c_index 93 end
Return the number of components found so far.
Private Instance Methods
Source
# File lib/rgl/connected_components.rb 97 def min_discover_time(u, v) 98 @discover_time_map[u] < @discover_time_map[v] ? u : v 99 end