lib/rgl/topsort.rb in rgl-0.4.0 vs lib/rgl/topsort.rb in rgl-0.5.0

@@ -1,31 +1,31 @@
 # topsort.rb
 
-require 'rgl/traversal'
+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.
-
+  # 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)
+    def initialize(g)
       super(g)
       set_to_begin
     end
 
-    def set_to_begin				# :nodoc:
+    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)
@@ -37,36 +37,43 @@
       @inDegrees.each_pair do |v, indegree|
         @waiting.push(v) if indegree.zero?
       end
     end
 
-    def basic_forward				# :nodoc:
+    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:
+    def at_beginning?
+      true
+    end
 
-  end		# class TopsortIterator
+    # :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.
 
+    # 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
+  end # module Graph
+
+end # module RGL