Method: Topiary.sort

Defined in:
lib/topiary.rb

.sort(node_list) ⇒ Object

Sorts node_list according to Kahn's Algorithm (from Wikipedia) which runs in linear time:

L 


25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
 
# File 'lib/topiary.rb', line 25

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 "Leftover edges found: this graph has a cycle"
    end
  end

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