summaryrefslogtreecommitdiff
path: root/lib/tsort.rb
diff options
context:
space:
mode:
authordrbrain <drbrain@b2dd03c8-39d4-4d8f-98ff-823fe69b080e>2006-08-04 18:05:50 +0000
committerdrbrain <drbrain@b2dd03c8-39d4-4d8f-98ff-823fe69b080e>2006-08-04 18:05:50 +0000
commit52c034aecb365c6cf2a41b8648c3e87fb335fdaf (patch)
tree199813273b1cd9a90b40e3dc797303d0e5f8c67b /lib/tsort.rb
parent4db2df633cc784c40e21b3df38fe9a6dd1b0ff0b (diff)
Documentation cleanup.
Includes patches by Hugh Sasse: * ping.rb * weakref.rb * mailread.rb git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@10668 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
Diffstat (limited to 'lib/tsort.rb')
-rw-r--r--lib/tsort.rb151
1 files changed, 76 insertions, 75 deletions
diff --git a/lib/tsort.rb b/lib/tsort.rb
index f52d0996c6..a014e7f6c2 100644
--- a/lib/tsort.rb
+++ b/lib/tsort.rb
@@ -8,10 +8,11 @@
# 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 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.
@@ -30,82 +31,82 @@
# 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]]
+# 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')
+# 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
#