Class: RGL::TopsortIterator

Inherits:
Object
  • Object
show all
Includes:
GraphIterator
Defined in:
lib/rgl/topsort.rb

Overview

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 Also:

Instance Attribute Summary

Attributes included from GraphWrapper

#graph

Instance Method Summary collapse

Methods included from GraphIterator

#length

Constructor Details

#initialize(g) ⇒ TopsortIterator

Returns a new instance of TopsortIterator.



22
23
24
25
 
# File 'lib/rgl/topsort.rb', line 22

def initialize(g)
  super(g)
  set_to_begin
end

Instance Method Details

#at_beginning? ⇒ Boolean

Returns:

  • (Boolean) 


53
54
55
 
# File 'lib/rgl/topsort.rb', line 53

def at_beginning?
  true
end

#at_end? ⇒ Boolean

Returns:

  • (Boolean) 


57
58
59
 
# File 'lib/rgl/topsort.rb', line 57

def at_end?
  @waiting.empty?
end

#basic_forward ⇒ Object 



44
45
46
47
48
49
50
51
 
# File 'lib/rgl/topsort.rb', line 44

def basic_forward
  u = @waiting.pop
  graph.each_adjacent(u) do |v|
    @inDegrees[v] -= 1
    @waiting.push(v) if @inDegrees[v].zero?
  end
  u
end

#set_to_begin ⇒ Object 



27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
 
# File 'lib/rgl/topsort.rb', line 27

def set_to_begin
  @waiting   = Array.new
  @inDegrees = Hash.new(0)

  graph.each_vertex do |u|
    @inDegrees[u] = 0 unless @inDegrees.has_key?(u)
    graph.each_adjacent(u) do |v|
      @inDegrees[v] += 1
    end
  end

  @inDegrees.each_pair do |v, indegree|
    @waiting.push(v) if indegree.zero?
  end
end