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