diff options
Diffstat (limited to 'test')
-rw-r--r-- | test/test_tsort.rb | 48 |
1 files changed, 47 insertions, 1 deletions
diff --git a/test/test_tsort.rb b/test/test_tsort.rb index a732064f31..bd60f696a8 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 = [] |