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 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
Public Instance Methods
handle_examine_vertex(v)
click to toggle 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
handle_finish_vertex(v)
click to toggle 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
num_comp()
click to toggle source
Return the number of components found so far.
# File lib/rgl/connected_components.rb 91 def num_comp 92 @c_index 93 end
Private Instance Methods
min_discover_time(u, v)
click to toggle 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