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.



24
25
26
27
 
# File 'lib/rgl/topsort.rb', line 24

def initialize(g)
  super(g)
  set_to_begin
end

Instance Method Details

#at_beginning? ⇒ Boolean

Returns:

  • (Boolean) 


55
56
57
 
# File 'lib/rgl/topsort.rb', line 55

def at_beginning?
  true
end

#at_end? ⇒ Boolean

Returns:

  • (Boolean) 


59
60
61
 
# File 'lib/rgl/topsort.rb', line 59

def at_end?
  @waiting.empty?
end

#basic_forward ⇒ Object 



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

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

#set_to_begin ⇒ Object 



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

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

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

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