Sha256: 38d099e15e636b63109aaf5f27a391db4a4eb28e10bdcd25ac309e7b3824373b
Contents?: true
Size: 1.7 KB
Versions: 9
Compression:
Stored size: 1.7 KB
Contents
# topsort.rb
require 'rgl/graph_iterator'
module RGL
# 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.
#
class TopsortIterator
include GraphIterator
def initialize(g)
super(g)
set_to_begin
end
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
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
def at_beginning?
true
end
# :nodoc: FIXME
def at_end?
@waiting.empty?
end # :nodoc:
end # class TopsortIterator
module Graph
# Returns a TopsortIterator.
#
def topsort_iterator
TopsortIterator.new(self)
end
# Returns true if the graph contains no cycles. This is only meaningful
# for directed graphs. Returns false for undirected graphs.
#
def acyclic?
topsort_iterator.length == num_vertices
end
end # module Graph
end # module RGL
Version data entries
9 entries across 9 versions & 1 rubygems