Module: Topiary

Defined in:
lib/topiary.rb,
lib/topiary/edge.rb,
lib/topiary/graph.rb,
lib/topiary/version.rb,
lib/topiary/exceptions.rb,
lib/topiary/directed_graph.rb

Overview

Topiary provides a topological sort function for Directed Acyclic Graphs.

Defined Under Namespace

Classes: DirectedGraph, Edge, Graph, InvalidGraph, Node, TopiaryError

Constant Summary collapse

VERSION = 
'1.0.3'.freeze

Class Method Summary collapse

Class Method Details

.sort(node_list) ⇒ Object

Sorts node_list according to Kahn's Algorithm (from Wikipedia) 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)



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
55
56
57
58
 
# 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