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