Sha256: 2658d94abc13a1972a2ffcd135a5e9ecd950a59266501ac159823d31c2054b9a
Contents?: true
Size: 1.77 KB
Versions: 4
Compression:
Stored size: 1.77 KB
Contents
# Strongly Connected Components class SCCGraph # initialize graph with n vertices def initialize(n = 0) @n, @edges = n, [] end # add directed edge def add_edge(from, to) raise "invalid params" unless (0...@n).include? from and (0...@n).include? to @edges << [from, to] end # returns list of strongly connected components # the components are sorted in topological order # O(@n + @edges.size) def scc group_num, ids = scc_ids counts = [0] * group_num ids.each { |x| counts[x] += 1 } groups = Array.new(group_num) { [] } ids.each_with_index { |x, i| groups[x] << i } groups end private 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 def csr start, elist = [0] * (@n + 1), [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 end # class alias StronglyConnectedComponents = SCCGraph SCC = SCCGraph SCCG = SCCGraph
Version data entries
4 entries across 4 versions & 1 rubygems
Version | Path |
---|---|
ac-library-rb-0.5.3 | lib/scc.rb |
ac-library-rb-0.5.2 | lib/scc.rb |
ac-library-rb-0.5.1 | lib/scc.rb |
ac-library-rb-0.5.0 | lib/scc.rb |