class AcLibraryRb::SCC
Strongly Connected Components
Public Class Methods
new(n)
click to toggle source
initialize graph with n vertices
# File lib_lock/ac-library-rb/scc.rb, line 5 def initialize(n) @n = n @edges = [] end
Public Instance Methods
add(x, to = nil)
click to toggle source
# File lib_lock/ac-library-rb/scc.rb, line 26 def add(x, to = nil) to ? add_edge(x, to) : add_edges(x) end
add_edge(from, to)
click to toggle source
add directed edge
# File lib_lock/ac-library-rb/scc.rb, line 11 def add_edge(from, to) unless 0 <= from && from < @n and 0 <= to && to < @n msg = "Wrong params: from=#{from} and to=#{to} must be in 0...#{@n}" raise ArgumentError.new(msg) end @edges << [from, to] self end
add_edges(edges)
click to toggle source
# File lib_lock/ac-library-rb/scc.rb, line 21 def add_edges(edges) edges.each{ |from, to| add_edge(from, to) } self end
scc()
click to toggle source
returns list of strongly connected components the components are sorted in topological order O(@n + @edges.size)
# File lib_lock/ac-library-rb/scc.rb, line 33 def scc group_num, ids = scc_ids groups = Array.new(group_num) { [] } ids.each_with_index { |id, i| groups[id] << i } groups end
Private Instance Methods
csr()
click to toggle source
# File lib_lock/ac-library-rb/scc.rb, line 74 def csr start = [0] * (@n + 1) elist = [nil] * @edges.size @edges.each { |(i, _)| start[i + 1] += 1 } @n.times { |i| start[i + 1] += start[i] } counter = start.dup @edges.each do |(i, j)| elist[counter[i]] = j counter[i] += 1 end [start, elist] end
scc_ids()
click to toggle source
# File lib_lock/ac-library-rb/scc.rb, line 42 def scc_ids start, elist = csr now_ord = group_num = 0 visited, low, ord, ids = [], [], [-1] * @n, [] dfs = ->(v) { low[v] = ord[v] = now_ord now_ord += 1 visited << v (start[v]...start[v + 1]).each do |i| to = elist[i] low[v] = if ord[to] == -1 dfs.(to) [low[v], low[to]].min else [low[v], ord[to]].min end end if low[v] == ord[v] loop do u = visited.pop ord[u] = @n ids[u] = group_num break if u == v end group_num += 1 end } @n.times { |i| dfs.(i) if ord[i] == -1 } ids = ids.map { |x| group_num - 1 - x } [group_num, ids] end