summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--lib/tsort.rb357
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)