diff options
Diffstat (limited to 'jni/ruby/test/test_tsort.rb')
-rw-r--r-- | jni/ruby/test/test_tsort.rb | 113 |
1 files changed, 113 insertions, 0 deletions
diff --git a/jni/ruby/test/test_tsort.rb b/jni/ruby/test/test_tsort.rb new file mode 100644 index 0000000..4a13a6e --- /dev/null +++ b/jni/ruby/test/test_tsort.rb @@ -0,0 +1,113 @@ +require 'tsort' +require 'test/unit' + +class TSortHash < Hash # :nodoc: + include TSort + alias tsort_each_node each_key + def tsort_each_child(node, &block) + fetch(node).each(&block) + end +end + +class TSortArray < Array # :nodoc: + include TSort + alias tsort_each_node each_index + def tsort_each_child(node, &block) + fetch(node).each(&block) + end +end + +class TSortTest < Test::Unit::TestCase # :nodoc: + def test_dag + h = TSortHash[{1=>[2, 3], 2=>[3], 3=>[]}] + assert_equal([3, 2, 1], h.tsort) + assert_equal([[3], [2], [1]], h.strongly_connected_components) + end + + def test_cycle + h = TSortHash[{1=>[2], 2=>[3, 4], 3=>[2], 4=>[]}] + assert_equal([[4], [2, 3], [1]], + h.strongly_connected_components.map {|nodes| nodes.sort}) + assert_raise(TSort::Cyclic) { h.tsort } + end + + def test_array + a = TSortArray[[1], [0], [0], [2]] + assert_equal([[0, 1], [2], [3]], + a.strongly_connected_components.map {|nodes| nodes.sort}) + + a = TSortArray[[], [0]] + assert_equal([[0], [1]], + a.strongly_connected_components.map {|nodes| nodes.sort}) + end + + 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) + + r = TSort.tsort_each(each_node, each_child).map {|n| n.to_s } + 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) + + r = TSort.each_strongly_connected_component(each_node, each_child).map {|scc| + scc.map(&:to_s) + } + 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 = [] + TSort.each_strongly_connected_component_from(1, each_child) {|scc| + r << scc + } + assert_equal([[4], [2, 3], [1]], r) + + r = TSort.each_strongly_connected_component_from(1, each_child).map {|scc| + scc.map(&:to_s) + } + assert_equal([['4'], ['2', '3'], ['1']], r) + end +end + |