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 collapse

Instance Method Summary collapse

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 Attribute Details

#graph ⇒ Graph Originally defined in module GraphWrapper

Returns the wrapped graph.

Returns:

  • (Graph) —

    the wrapped graph

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

#length ⇒ int Originally defined in module GraphIterator

Returns:

  • (int)

#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