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.



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

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) 


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

#length ⇒ int Originally defined in module GraphIterator

Returns:

  • (int)

#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