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 (DAG).

The iterator can also be applied to undirected graph or to a DG graph which contains a cycle. In this case, the Iterator does not reach all vertices. The implementation of acyclic? uses this fact.

Instance Attribute Summary

Attributes included from GraphWrapper

#graph

Instance Method Summary collapse

Constructor Details

#initialize(g) ⇒ TopsortIterator

Returns a new instance of TopsortIterator.



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

def initialize (g)
  super(g)
  set_to_begin
end

Instance Method Details

#at_beginning? ⇒ Boolean

:nodoc: FIXME

Returns:

  • (Boolean) 


51
 
# File 'lib/rgl/topsort.rb', line 51

def at_beginning?; true;            end

#at_end? ⇒ Boolean

:nodoc:

Returns:

  • (Boolean) 


52
 
# File 'lib/rgl/topsort.rb', line 52

def at_end?;       @waiting.empty?; end

#basic_forward ⇒ Object

:nodoc:



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

def basic_forward       # :nodoc:
  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

:nodoc:



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

def set_to_begin        # :nodoc:
  @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