1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
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
|
