class RGL::TopsortIterator
Topological Sort Iterator
The topological sort algorithm creates a linear ordering of the vertices such that if edge (u,v) appears in the graph, then u comes before v in the ordering. The graph must be a directed acyclic graph.
The iterator can also be applied to an undirected graph or to a directed graph which contains a cycle. In this case, the iterator does not reach all vertices. The implementation of {Graph#acyclic?} uses this fact.
Public Class Methods
new(g)
click to toggle source
Calls superclass method
# File lib/rgl/topsort.rb 22 def initialize(g) 23 super(g) 24 set_to_begin 25 end
Public Instance Methods
at_beginning?()
click to toggle source
# File lib/rgl/topsort.rb 53 def at_beginning? 54 true 55 end
at_end?()
click to toggle source
# File lib/rgl/topsort.rb 57 def at_end? 58 @waiting.empty? 59 end
basic_forward()
click to toggle source
@private
# File lib/rgl/topsort.rb 44 def basic_forward 45 u = @waiting.pop 46 graph.each_adjacent(u) do |v| 47 @inDegrees[v] -= 1 48 @waiting.push(v) if @inDegrees[v].zero? 49 end 50 u 51 end
set_to_begin()
click to toggle source
# File lib/rgl/topsort.rb 27 def set_to_begin 28 @waiting = Array.new 29 @inDegrees = Hash.new(0) 30 31 graph.each_vertex do |u| 32 @inDegrees[u] = 0 unless @inDegrees.has_key?(u) 33 graph.each_adjacent(u) do |v| 34 @inDegrees[v] += 1 35 end 36 end 37 38 @inDegrees.each_pair do |v, indegree| 39 @waiting.push(v) if indegree.zero? 40 end 41 end