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) 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 = [] TSort.each_strongly_connected_component_from(1, each_child) {|scc| r << scc } assert_equal([[4], [2, 3], [1]], r) end end