test/test_tsort.rb

   1 # frozen_string_literal: true
   2
   3 require 'tsort'
   4 require 'test/unit'
   5
   6 class TSortHash < Hash # :nodoc:
   7   include TSort
   8   alias tsort_each_node each_key
   9   def tsort_each_child(node, &block)
  10     fetch(node).each(&block)
  11   end
  12 end
  13
  14 class TSortArray < Array # :nodoc:
  15   include TSort
  16   alias tsort_each_node each_index
  17   def tsort_each_child(node, &block)
  18     fetch(node).each(&block)
  19   end
  20 end
  21
  22 class TSortTest < Test::Unit::TestCase # :nodoc:
  23   def test_dag
  24     h = TSortHash[{1=>[2, 3], 2=>[3], 3=>[]}]
  25     assert_equal([3, 2, 1], h.tsort)
  26     assert_equal([[3], [2], [1]], h.strongly_connected_components)
  27   end
  28
  29   def test_cycle
  30     h = TSortHash[{1=>[2], 2=>[3, 4], 3=>[2], 4=>[]}]
  31     assert_equal([[4], [2, 3], [1]],
  32       h.strongly_connected_components.map {|nodes| nodes.sort})
  33     assert_raise(TSort::Cyclic) { h.tsort }
  34   end
  35
  36   def test_array
  37     a = TSortArray[[1], [0], [0], [2]]
  38     assert_equal([[0, 1], [2], [3]],
  39       a.strongly_connected_components.map {|nodes| nodes.sort})
  40
  41     a = TSortArray[[], [0]]
  42     assert_equal([[0], [1]],
  43       a.strongly_connected_components.map {|nodes| nodes.sort})
  44   end
  45
  46   def test_s_tsort
  47     g = {1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]}
  48     each_node = lambda {|&b| g.each_key(&b) }
  49     each_child = lambda {|n, &b| g[n].each(&b) }
  50     assert_equal([4, 2, 3, 1], TSort.tsort(each_node, each_child))
  51     g = {1=>[2], 2=>[3, 4], 3=>[2], 4=>[]}
  52     assert_raise(TSort::Cyclic) { TSort.tsort(each_node, each_child) }
  53   end
  54
  55   def test_s_tsort_each
  56     g = {1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]}
  57     each_node = lambda {|&b| g.each_key(&b) }
  58     each_child = lambda {|n, &b| g[n].each(&b) }
  59     r = []
  60     TSort.tsort_each(each_node, each_child) {|n| r << n }
  61     assert_equal([4, 2, 3, 1], r)
  62
  63     r = TSort.tsort_each(each_node, each_child).map {|n| n.to_s }
  64     assert_equal(['4', '2', '3', '1'], r)
  65   end
  66
  67   def test_s_strongly_connected_components
  68     g = {1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]}
  69     each_node = lambda {|&b| g.each_key(&b) }
  70     each_child = lambda {|n, &b| g[n].each(&b) }
  71     assert_equal([[4], [2], [3], [1]],
  72                  TSort.strongly_connected_components(each_node, each_child))
  73     g = {1=>[2], 2=>[3, 4], 3=>[2], 4=>[]}
  74     assert_equal([[4], [2, 3], [1]],
  75                  TSort.strongly_connected_components(each_node, each_child))
  76   end
  77
  78   def test_s_each_strongly_connected_component
  79     g = {1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]}
  80     each_node = lambda {|&b| g.each_key(&b) }
  81     each_child = lambda {|n, &b| g[n].each(&b) }
  82     r = []
  83     TSort.each_strongly_connected_component(each_node, each_child) {|scc|
  84       r << scc
  85     }
  86     assert_equal([[4], [2], [3], [1]], r)
  87     g = {1=>[2], 2=>[3, 4], 3=>[2], 4=>[]}
  88     r = []
  89     TSort.each_strongly_connected_component(each_node, each_child) {|scc|
  90       r << scc
  91     }
  92     assert_equal([[4], [2, 3], [1]], r)
  93
  94     r = TSort.each_strongly_connected_component(each_node, each_child).map {|scc|
  95       scc.map(&:to_s)
  96     }
  97     assert_equal([['4'], ['2', '3'], ['1']], r)
  98   end
  99
 100   def test_s_each_strongly_connected_component_from
 101     g = {1=>[2], 2=>[3, 4], 3=>[2], 4=>[]}
 102     each_child = lambda {|n, &b| g[n].each(&b) }
 103     r = []
 104     TSort.each_strongly_connected_component_from(1, each_child) {|scc|
 105       r << scc
 106     }
 107     assert_equal([[4], [2, 3], [1]], r)
 108
 109     r = TSort.each_strongly_connected_component_from(1, each_child).map {|scc|
 110       scc.map(&:to_s)
 111     }
 112     assert_equal([['4'], ['2', '3'], ['1']], r)
 113   end
 114 end
 115