summaryrefslogtreecommitdiff
path: root/test/test_tsort.rb
diff options
context:
space:
mode:
authorakr <akr@b2dd03c8-39d4-4d8f-98ff-823fe69b080e>2013-10-17 15:59:40 +0000
committerakr <akr@b2dd03c8-39d4-4d8f-98ff-823fe69b080e>2013-10-17 15:59:40 +0000
commit4c5bfb9fbd82585a0c7d7744fc3fc054cb3f4e42 (patch)
treeb7b20227660dabb6767739619051a901c136a293 /test/test_tsort.rb
parentb0c19be2849d4957d4b6b230004c9ce351ad8545 (diff)
* lib/tsort.rb (TSort.tsort): Extracted from TSort#tsort.
(TSort.tsort_each): Extracted from TSort#tsort_each. (TSort.strongly_connected_components): Extracted from TSort#strongly_connected_components. (TSort.each_strongly_connected_component): Extracted from TSort#each_strongly_connected_component. git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@43342 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
Diffstat (limited to 'test/test_tsort.rb')
-rw-r--r--test/test_tsort.rb48
1 files changed, 47 insertions, 1 deletions
diff --git a/test/test_tsort.rb b/test/test_tsort.rb
index a732064..bd60f69 100644
--- a/test/test_tsort.rb
+++ b/test/test_tsort.rb
@@ -41,7 +41,53 @@ class TSortTest < Test::Unit::TestCase # :nodoc:
a.strongly_connected_components.map {|nodes| nodes.sort})
end
- def test_noclass
+ def test_s_tsort
+ g = {1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]}
+ each_node = lambda {|&b| g.each_key(&b) }
+ each_child = lambda {|n, &b| g[n].each(&b) }
+ assert_equal([4, 2, 3, 1], TSort.tsort(each_node, each_child))
+ g = {1=>[2], 2=>[3, 4], 3=>[2], 4=>[]}
+ assert_raise(TSort::Cyclic) { TSort.tsort(each_node, each_child) }
+ end
+
+ def test_s_tsort_each
+ g = {1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]}
+ each_node = lambda {|&b| g.each_key(&b) }
+ each_child = lambda {|n, &b| g[n].each(&b) }
+ r = []
+ TSort.tsort_each(each_node, each_child) {|n| r << n }
+ assert_equal([4, 2, 3, 1], r)
+ end
+
+ def test_s_strongly_connected_components
+ g = {1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]}
+ each_node = lambda {|&b| g.each_key(&b) }
+ each_child = lambda {|n, &b| g[n].each(&b) }
+ assert_equal([[4], [2], [3], [1]],
+ TSort.strongly_connected_components(each_node, each_child))
+ g = {1=>[2], 2=>[3, 4], 3=>[2], 4=>[]}
+ assert_equal([[4], [2, 3], [1]],
+ TSort.strongly_connected_components(each_node, each_child))
+ end
+
+ def test_s_each_strongly_connected_component
+ g = {1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]}
+ each_node = lambda {|&b| g.each_key(&b) }
+ each_child = lambda {|n, &b| g[n].each(&b) }
+ r = []
+ TSort.each_strongly_connected_component(each_node, each_child) {|scc|
+ r << scc
+ }
+ assert_equal([[4], [2], [3], [1]], r)
+ g = {1=>[2], 2=>[3, 4], 3=>[2], 4=>[]}
+ r = []
+ TSort.each_strongly_connected_component(each_node, each_child) {|scc|
+ r << scc
+ }
+ assert_equal([[4], [2, 3], [1]], r)
+ end
+
+ def test_s_each_strongly_connected_component_from
g = {1=>[2], 2=>[3, 4], 3=>[2], 4=>[]}
each_child = lambda {|n, &b| g[n].each(&b) }
r = []