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.

@see Graph#topsort_iterator

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