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
|
package grok
import "testing"
func TestReverseList(t *testing.T) {
var array = []string{"A", "B", "C", "D"}
var expectedArray = []string{"D", "C", "B", "A"}
arrayReversed := reverseList(array)
if !sliceEquals(arrayReversed, expectedArray) {
t.Fatalf("reversedList is %+v, expected : %+v", arrayReversed, expectedArray)
}
}
func TestSortGraph(t *testing.T) {
var g = graph{}
g["7"] = []string{"11", "8"}
g["5"] = []string{"11"}
g["3"] = []string{"8", "10"}
g["11"] = []string{"2", "9", "10"}
g["8"] = []string{"9", "10"}
g["2"] = []string{}
g["9"] = []string{}
g["10"] = []string{}
validOrders := [][]string{
{"3", "5", "7", "8", "11", "10", "9", "2"},
{"3", "5", "7", "8", "11", "2", "10", "9"},
{"3", "5", "7", "8", "11", "9", "2", "10"},
{"7", "3", "8", "5", "11", "10", "9", "2"},
{"3", "5", "7", "11", "2", "8", "10", "9"},
{"5", "7", "11", "2", "3", "8", "10", "9"},
}
order, cycle := sortGraph(g)
if cycle != nil {
t.Fatal("cycle detected while not expected")
}
for _, expectedOrder := range validOrders {
if sliceEquals(order, expectedOrder) {
return
}
}
t.Fatalf("sorted graph is %+v, expected a order like: %+v", order, validOrders[0])
}
func TestSortGraphWithCycle(t *testing.T) {
var g = graph{}
g["7"] = []string{"11", "8"}
g["5"] = []string{"11"}
g["3"] = []string{"8", "10"}
g["11"] = []string{"2", "9", "10"}
g["8"] = []string{"9", "10"}
g["2"] = []string{}
g["9"] = []string{"3"}
g["10"] = []string{}
validCycles := [][]string{
{"3", "9", "8"},
{"8", "3", "9"},
{"9", "8", "3"},
}
_, cycle := sortGraph(g)
if cycle == nil {
t.Fatal("cycle not detected while sorting graph")
}
for _, expectedCycle := range validCycles {
if sliceEquals(cycle, expectedCycle) {
return
}
}
t.Fatalf("cycle have %+v, expected %+v", cycle, validCycles[0])
}
func sliceEquals(a, b []string) bool {
if len(a) != len(b) {
return false
}
for i := range a {
if a[i] != b[i] {
return false
}
}
return true
}
|
