module Topiary

{Topiary} provides a topological sort function for Directed Acyclic Graphs.

Constants

VERSION

Public Class Methods

sort(node_list) click to toggle source

Sorts node_list according to Kahn's Algorithm ([from Wikipedia](en.wikipedia.org/wiki/Topological_sorting)) which runs in linear time:

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edge
while S is non-empty do
    remove a node n from S
    add n to tail of L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    return error (graph has at least one cycle)
else
    return L (a topologically sorted order)
# File lib/topiary.rb, line 29
def self.sort(node_list)
  l = []
  s = Set.new(node_list.select{|n| n.needs.empty?})

  node_list.each(&:begin!)

  while not s.empty?
    n = s.first
    s.delete n
    l << n
    n.feeds.to_a.each do |m|
      n.feeds.delete m
      m.needs.delete n
      if m.needs.empty?
        s << m
      end
    end
  end

  # Make sure there were no cycles
  node_list.each do |n2|
    if n2.needs.any? or n2.feeds.any?
      raise InvalidGraph, "Leftover edges found: this graph has a cycle"
    end
  end

  l
ensure
  node_list.each(&:restore!)
end