Class: SCC

Inherits:
Object
  • Object
show all
Defined in:
lib/scc.rb

Overview

Strongly Connected Components

Instance Method Summary collapse

Constructor Details

#initialize(n) ⇒ SCC

initialize graph with n vertices



4
5
6
7
 
# File 'lib/scc.rb', line 4

def initialize(n)
  @n = n
  @edges = Array.new(n) { [] }
end

Instance Method Details

#add(x, to = nil) ⇒ Object 



25
26
27
 
# File 'lib/scc.rb', line 25

def add(x, to = nil)
  to ? add_edge(x, to) : add_edges(x)
end

#add_edge(from, to) ⇒ Object

add directed edge



10
11
12
13
14
15
16
17
18
 
# File 'lib/scc.rb', line 10

def add_edge(from, to)
  unless 0 <= from && from < @n && 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) ⇒ Object 



20
21
22
23
 
# File 'lib/scc.rb', line 20

def add_edges(edges)
  edges.each{ |from, to| add_edge(from, to) }
  self
end

#scc ⇒ Object

returns list of strongly connected components the components are sorted in topological order O(@n + @edges.sum(&:size))



32
33
34
35
36
37
 
# File 'lib/scc.rb', line 32

def scc
  group_num, ids = scc_ids
  groups = Array.new(group_num) { [] }
  ids.each_with_index { |id, i| groups[id] << i }
  groups
end