Class: Deptree::Visitor::Kahn

Inherits:
Object
  • Object
show all
Defined in:
lib/deptree/visitor/kahn.rb

Instance Method Summary collapse

Constructor Details

#initialize(nodes) ⇒ Kahn

Returns a new instance of Kahn.



4
5
6
 
# File 'lib/deptree/visitor/kahn.rb', line 4

def initialize(nodes)
  @nodes = nodes
end

Instance Method Details

#compute_incoming_edges(nodes) ⇒ Object 



31
32
33
34
35
36
37
38
39
40
41
42
 
# File 'lib/deptree/visitor/kahn.rb', line 31

def compute_incoming_edges(nodes)
  incoming = {}
  nodes.each { |node| incoming[node] = 0 }

  nodes.each do |node|
    node.prerequisites.each do |child|
      incoming[child] += 1
    end
  end

  incoming
end

#incoming ⇒ Object 



27
28
29
 
# File 'lib/deptree/visitor/kahn.rb', line 27

def incoming
  @incoming||= compute_incoming_edges(@nodes)
end

#topsort ⇒ Object 



8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
# File 'lib/deptree/visitor/kahn.rb', line 8

def topsort
  sorted = []
  queue = incoming.keys.select { |node| incoming[node].zero? }

  fail CircularDependencyError if queue.empty?

  while (node = queue.shift) do
    sorted << node
    node.prerequisites.each do |child|
      incoming[child] -= 1
      queue.push(child) if incoming[child].zero?
    end
  end

  fail CircularDependencyError unless incoming.values.all?(&:zero?)

  sorted.reverse
end