# 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.

## Instance Method Summary collapse

• constructor

A new instance of TopsortIterator.

• included from GraphIterator

## 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

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