RD -> RDoc contributed by Lyle Johnson

git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@4878 b2dd03c8-39d4-4d8f-98ff-823fe69b080e

1 files changed, 175 insertions, 182 deletions

diff --git a/lib/tsort.rb b/lib/tsort.rb
index 3bf8c33bbf..82d3f3a385 100644
--- a/lib/tsort.rb
+++ b/lib/tsort.rb
@@ -1,189 +1,150 @@
-=begin
-= tsort.rb
-
-tsort.rb provides a module for topological sorting and
-strongly connected components.
-
-== Example
-
-  require 'tsort'
-
-  class Hash
-    include TSort
-    alias tsort_each_node each_key
-    def tsort_each_child(node, &block)
-      fetch(node).each(&block)
-    end
-  end
-
-  {1=>[2, 3], 2=>[3], 3=>[], 4=>[]}.tsort
-  #=> [3, 2, 1, 4]
-
-  {1=>[2], 2=>[3, 4], 3=>[2], 4=>[]}.strongly_connected_components
-  #=> [[4], [2, 3], [1]]
-
-== TSort module
-TSort implements topological sorting using Tarjan's algorithm for
-strongly connected components.
-
-TSort is designed to be able to use with any object which can be interpreted
-as a directed graph.
-TSort requires two methods to interpret a object as a graph:
-tsort_each_node and tsort_each_child.
-
-* tsort_each_node is used to iterate for all nodes over a graph.
-* tsort_each_child is used to iterate for child nodes of a given node.
-
-The equality of nodes are defined by eql? and hash since
-TSort uses Hash internally.
-
-=== methods
---- tsort 
-    returns a topologically sorted array of nodes.
-    The array is sorted from children to parents:
-    I.e. the first element has no child and the last node has no parent.
-
-    If there is a cycle, (({TSort::Cyclic})) is raised.
-
---- tsort_each {|node| ...}
-    is the iterator version of the (({tsort})) method.
-    (({((|obj|)).tsort_each})) is similar to (({((|obj|)).tsort.each})) but
-    modification of ((|obj|)) during the iteration may cause unexpected result.
-
-    (({tsort_each})) returns (({nil})).
-    If there is a cycle, (({TSort::Cyclic})) is raised.
-
---- strongly_connected_components
-    returns strongly connected components as an array of array of nodes.
-    The array is sorted from children to parents.
-    Each elements of the array represents a strongly connected component.
-
---- each_strongly_connected_component {|nodes| ...}
-    is the iterator version of the (({strongly_connected_components})) method.
-    (({((|obj|)).each_strongly_connected_component})) is similar to
-    (({((|obj|)).strongly_connected_components.each})) but
-    modification of ((|obj|)) during the iteration may cause unexpected result.
-
-    (({each_strongly_connected_component})) returns (({nil})).
-
---- each_strongly_connected_component_from(node) {|nodes| ...}
-    iterates over strongly connected component in the subgraph reachable from 
-    ((|node|)).
-
-    Return value is unspecified.
-
-    (({each_strongly_connected_component_from})) doesn't call
-    (({tsort_each_node})).
-
---- tsort_each_node {|node| ...}
-    should be implemented by a extended class.
-
-    (({tsort_each_node})) is used to iterate for all nodes over a graph.
-
---- tsort_each_child(node) {|child| ...}
-    should be implemented by a extended class.
-
-    (({tsort_each_child})) is used to iterate for child nodes of ((|node|)).
-
-== More Realistic Example
-Very simple `make' like tool can be implemented as follows:
-
-  require 'tsort'
-
-  class Make
-    def initialize
-      @dep = {}
-      @dep.default = []
-    end
-
-    def rule(outputs, inputs=[], &block)
-      triple = [outputs, inputs, block]
-      outputs.each {|f| @dep[f] = [triple]}
-      @dep[triple] = inputs
-    end
-
-    def build(target)
-      each_strongly_connected_component_from(target) {|ns|
-        if ns.length != 1
-          fs = ns.delete_if {|n| Array === n}
-          raise TSort::Cyclic.new("cyclic dependencies: #{fs.join ', '}")
-        end
-        n = ns.first
-        if Array === n
-          outputs, inputs, block = n
-          inputs_time = inputs.map {|f| File.mtime f}.max
-          begin
-            outputs_time = outputs.map {|f| File.mtime f}.min
-          rescue Errno::ENOENT
-            outputs_time = nil
-          end
-          if outputs_time == nil ||
-             inputs_time != nil && outputs_time <= inputs_time
-            sleep 1 if inputs_time != nil && inputs_time.to_i == Time.now.to_i
-            block.call
-          end
-        end
-      }
-    end
-
-    def tsort_each_child(node, &block)
-      @dep[node].each(&block)
-    end
-    include TSort
-  end
-
-  def command(arg)
-    print arg, "\n"
-    system arg
-  end
-
-  m = Make.new
-  m.rule(%w[t1]) { command 'date > t1' }
-  m.rule(%w[t2]) { command 'date > t2' }
-  m.rule(%w[t3]) { command 'date > t3' }
-  m.rule(%w[t4], %w[t1 t3]) { command 'cat t1 t3 > t4' }
-  m.rule(%w[t5], %w[t4 t2]) { command 'cat t4 t2 > t5' }
-  m.build('t5')
-
-== Bugs
-
-* (('tsort.rb')) is wrong name because this library uses
-  Tarjan's algorithm for strongly connected components.
-  Although (('strongly_connected_components.rb')) is correct but too long,
-
-== References
-R. E. Tarjan, 
-Depth First Search and Linear Graph Algorithms,
-SIAM Journal on Computing, Vol. 1, No. 2, pp. 146-160, June 1972.
-
-#@Article{Tarjan:1972:DFS,
-#  author =       "R. E. Tarjan",
-#  key =          "Tarjan",
-#  title =        "Depth First Search and Linear Graph Algorithms",
-#  journal =      j-SIAM-J-COMPUT,
-#  volume =       "1",
-#  number =       "2",
-#  pages =        "146--160",
-#  month =        jun,
-#  year =         "1972",
-#  CODEN =        "SMJCAT",
-#  ISSN =         "0097-5397 (print), 1095-7111 (electronic)",
-#  bibdate =      "Thu Jan 23 09:56:44 1997",
-#  bibsource =    "Parallel/Multi.bib, Misc/Reverse.eng.bib",
-#}
-=end
+#!/usr/bin/env ruby
+#--
+# tsort.rb - provides a module for topological sorting and strongly connected components.
+#++
+#
+
+#
+# TSort implements topological sorting using Tarjan's algorithm for
+# strongly connected components.
+#
+# TSort is designed to be able to be used with any object which can be interpreted
+# as a directed graph.
+# TSort requires two methods to interpret an object as a graph:
+# tsort_each_node and tsort_each_child:
+#
+# * tsort_each_node is used to iterate for all nodes over a graph.
+# * tsort_each_child is used to iterate for child nodes of a given node.
+#
+# The equality of nodes are defined by eql? and hash since
+# TSort uses Hash internally.
+#
+# == A Simple Example
+#
+# The following example demonstrates how to mix the TSort module into an
+# existing class (in this case, Hash). Here, we're treating each key in
+# the hash as a node in the graph, and so we simply alias the required
+# #tsort_each_node method to Hash's #each_key method. For each key in the
+# hash, the associated value is an array of the node's child nodes. This
+# choice in turn leads to our implementation of the required #tsort_each_child
+# method, which fetches the array of child nodes and then iterates over that
+# array using the user-supplied block.
+#
+#  require 'tsort'
+#
+#  class Hash
+#    include TSort
+#    alias tsort_each_node each_key
+#    def tsort_each_child(node, &block)
+#      fetch(node).each(&block)
+#    end
+#  end
+#
+#  {1=>[2, 3], 2=>[3], 3=>[], 4=>[]}.tsort
+#  #=> [3, 2, 1, 4]
+#
+#  {1=>[2], 2=>[3, 4], 3=>[2], 4=>[]}.strongly_connected_components
+#  #=> [[4], [2, 3], [1]]
+#
+# == A More Realistic Example
+#
+# A very simple `make' like tool can be implemented as follows:
+#
+#  require 'tsort'
+#
+#  class Make
+#    def initialize
+#      @dep = {}
+#      @dep.default = []
+#    end
+#
+#    def rule(outputs, inputs=[], &block)
+#      triple = [outputs, inputs, block]
+#      outputs.each {|f| @dep[f] = [triple]}
+#      @dep[triple] = inputs
+#    end
+#
+#    def build(target)
+#      each_strongly_connected_component_from(target) {|ns|
+#        if ns.length != 1
+#          fs = ns.delete_if {|n| Array === n}
+#          raise TSort::Cyclic.new("cyclic dependencies: #{fs.join ', '}")
+#        end
+#        n = ns.first
+#        if Array === n
+#          outputs, inputs, block = n
+#          inputs_time = inputs.map {|f| File.mtime f}.max
+#          begin
+#            outputs_time = outputs.map {|f| File.mtime f}.min
+#          rescue Errno::ENOENT
+#            outputs_time = nil
+#          end
+#          if outputs_time == nil ||
+#             inputs_time != nil && outputs_time <= inputs_time
+#            sleep 1 if inputs_time != nil && inputs_time.to_i == Time.now.to_i
+#            block.call
+#          end
+#        end
+#      }
+#    end
+#
+#    def tsort_each_child(node, &block)
+#      @dep[node].each(&block)
+#    end
+#    include TSort
+#  end
+#
+#  def command(arg)
+#    print arg, "\n"
+#    system arg
+#  end
+#
+#  m = Make.new
+#  m.rule(%w[t1]) { command 'date > t1' }
+#  m.rule(%w[t2]) { command 'date > t2' }
+#  m.rule(%w[t3]) { command 'date > t3' }
+#  m.rule(%w[t4], %w[t1 t3]) { command 'cat t1 t3 > t4' }
+#  m.rule(%w[t5], %w[t4 t2]) { command 'cat t4 t2 > t5' }
+#  m.build('t5')
+#
+# == Bugs
+#
+# * 'tsort.rb' is wrong name because this library uses
+#   Tarjan's algorithm for strongly connected components.
+#   Although 'strongly_connected_components.rb' is correct but too long.
+#
+# == References
+#
+# R. E. Tarjan, "Depth First Search and Linear Graph Algorithms",
+# <em>SIAM Journal on Computing</em>, Vol. 1, No. 2, pp. 146-160, June 1972.
+#
 
 module TSort
   class Cyclic < StandardError
   end
 
+  #
+  # Returns a topologically sorted array of nodes.
+  # The array is sorted from children to parents, i.e.
+  # the first element has no child and the last node has no parent.
+  #
+  # If there is a cycle, TSort::Cyclic is raised.
+  #
   def tsort
     result = []
     tsort_each {|element| result << element}
     result
   end
 
-  def tsort_each
+  #
+  # The iterator version of the #tsort method.
+  # <tt><em>obj</em>.tsort_each</tt> is similar to <tt><em>obj</em>.tsort.each</tt>, but
+  # modification of _obj_ during the iteration may lead to unexpected results.
+  #
+  # #tsort_each returns +nil+.
+  # If there is a cycle, TSort::Cyclic is raised.
+  #
+  def tsort_each # :yields: node
     each_strongly_connected_component {|component|
       if component.size == 1
         yield component.first
@@ -193,13 +154,27 @@ module TSort
     }
   end
 
+  #
+  # Returns strongly connected components as an array of arrays of nodes.
+  # The array is sorted from children to parents.
+  # Each elements of the array represents a strongly connected component.
+  #
   def strongly_connected_components
     result = []
     each_strongly_connected_component {|component| result << component}
     result
   end
 
-  def each_strongly_connected_component
+  #
+  # The iterator version of the #strongly_connected_components method.
+  # <tt><em>obj</em>.each_strongly_connected_component</tt> is similar to
+  # <tt><em>obj</em>.strongly_connected_components.each</tt>, but
+  # modification of _obj_ during the iteration may lead to unexpected results.
+  #
+  #
+  # #each_strongly_connected_component returns +nil+.
+  #
+  def each_strongly_connected_component # :yields: nodes
     id_map = {}
     stack = []
     tsort_each_node {|node|
@@ -212,7 +187,15 @@ module TSort
     nil
   end
 
-  def each_strongly_connected_component_from(node, id_map={}, stack=[])
+  #
+  # Iterates over strongly connected component in the subgraph reachable from 
+  # _node_.
+  #
+  # Return value is unspecified.
+  #
+  # #each_strongly_connected_component_from doesn't call #tsort_each_node.
+  #
+  def each_strongly_connected_component_from(node, id_map={}, stack=[]) # :yields: nodes
     minimum_id = node_id = id_map[node] = id_map.size
     stack_length = stack.length
     stack << node
@@ -239,11 +222,21 @@ module TSort
     minimum_id
   end
 
-  def tsort_each_node
+  #
+  # Should be implemented by a extended class.
+  #
+  # #tsort_each_node is used to iterate for all nodes over a graph.
+  #
+  def tsort_each_node # :yields: node
     raise NotImplementedError.new
   end
 
-  def tsort_each_child(node)
+  #
+  # Should be implemented by a extended class.
+  #
+  # #tsort_each_child is used to iterate for child nodes of _node_.
+  #
+  def tsort_each_child(node) # :yields: child
     raise NotImplementedError.new
   end
 end
@@ -251,7 +244,7 @@ end
 if __FILE__ == $0
   require 'test/unit'
 
-  class Hash
+  class Hash # :nodoc:
     include TSort
     alias tsort_each_node each_key
     def tsort_each_child(node, &block)
@@ -259,7 +252,7 @@ if __FILE__ == $0
     end
   end
 
-  class Array
+  class Array # :nodoc:
     include TSort
     alias tsort_each_node each_index
     def tsort_each_child(node, &block)
@@ -267,7 +260,7 @@ if __FILE__ == $0
     end
   end
 
-  class TSortTest < Test::Unit::TestCase
+  class TSortTest < Test::Unit::TestCase # :nodoc:
     def test_dag
       h = {1=>[2, 3], 2=>[3], 3=>[]}
       assert_equal([3, 2, 1], h.tsort)