class Deptree::Visitor::Kahn
Public Class Methods
new(nodes)
click to toggle source
# File lib/deptree/visitor/kahn.rb, line 4 def initialize(nodes) @nodes = nodes end
Public Instance Methods
compute_incoming_edges(nodes)
click to toggle source
# 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()
click to toggle source
# File lib/deptree/visitor/kahn.rb, line 27 def incoming @incoming||= compute_incoming_edges(@nodes) end
topsort()
click to toggle source
# 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