-
Notifications
You must be signed in to change notification settings - Fork 121
/
Copy pathmst_test.go
119 lines (104 loc) · 3.07 KB
/
mst_test.go
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
114
115
116
117
118
119
package graph
import (
"testing"
)
func mstSetup() weightedGraph {
g := newWeightedGraph()
g.AddVertex("a")
g.AddVertex("b")
g.AddVertex("c")
g.AddVertex("d")
g.AddVertex("e")
g.AddVertex("f")
g.AddVertex("g")
g.AddVertex("h")
g.AddVertex("l")
g.AddEdgeWithWeightBi(edge{"a", "b"}, 4)
g.AddEdgeWithWeightBi(edge{"b", "c"}, 8)
g.AddEdgeWithWeightBi(edge{"c", "d"}, 7)
g.AddEdgeWithWeightBi(edge{"d", "e"}, 9)
g.AddEdgeWithWeightBi(edge{"e", "f"}, 10)
g.AddEdgeWithWeightBi(edge{"f", "g"}, 2)
g.AddEdgeWithWeightBi(edge{"g", "h"}, 1)
g.AddEdgeWithWeightBi(edge{"h", "l"}, 7)
g.AddEdgeWithWeightBi(edge{"l", "c"}, 2)
g.AddEdgeWithWeightBi(edge{"b", "h"}, 11)
g.AddEdgeWithWeightBi(edge{"c", "f"}, 4)
g.AddEdgeWithWeightBi(edge{"d", "f"}, 14)
g.AddEdgeWithWeightBi(edge{"g", "l"}, 6)
g.AddEdgeWithWeightBi(edge{"a", "h"}, 8)
return g
}
func mstGolden() weightedGraph {
t := newWeightedGraph()
t.AddEdgeWithWeightBi(edge{"a", "b"}, 4)
t.AddEdgeWithWeightBi(edge{"a", "h"}, 8)
t.AddEdgeWithWeightBi(edge{"c", "l"}, 2)
t.AddEdgeWithWeightBi(edge{"g", "h"}, 1)
t.AddEdgeWithWeightBi(edge{"g", "f"}, 2)
t.AddEdgeWithWeightBi(edge{"c", "f"}, 4)
t.AddEdgeWithWeightBi(edge{"c", "d"}, 7)
t.AddEdgeWithWeightBi(edge{"d", "e"}, 9)
return t
}
func secondaryMstGolden() weightedGraph {
t := newWeightedGraph()
t.AddEdgeWithWeightBi(edge{"a", "b"}, 4)
t.AddEdgeWithWeightBi(edge{"a", "h"}, 8)
t.AddEdgeWithWeightBi(edge{"c", "l"}, 2)
t.AddEdgeWithWeightBi(edge{"g", "h"}, 1)
t.AddEdgeWithWeightBi(edge{"g", "f"}, 2)
t.AddEdgeWithWeightBi(edge{"c", "f"}, 4)
t.AddEdgeWithWeightBi(edge{"c", "d"}, 7)
t.AddEdgeWithWeightBi(edge{"e", "f"}, 10)
return t
}
func bottleNeckSpanningTreeGolden() weightedGraph {
t := newWeightedGraph()
t.AddEdgeWithWeightBi(edge{"a", "b"}, 4)
t.AddEdgeWithWeightBi(edge{"a", "h"}, 8)
t.AddEdgeWithWeightBi(edge{"c", "l"}, 2)
t.AddEdgeWithWeightBi(edge{"g", "h"}, 1)
t.AddEdgeWithWeightBi(edge{"g", "f"}, 2)
t.AddEdgeWithWeightBi(edge{"l", "g"}, 6)
t.AddEdgeWithWeightBi(edge{"c", "d"}, 7)
t.AddEdgeWithWeightBi(edge{"d", "e"}, 9)
return t
}
func checkMstOutOfOrder(t *testing.T, g, gGolden weightedGraph) {
checkGraphOutOfOrderInString(t, g, gGolden, nil)
if g.TotalWeight() != gGolden.TotalWeight() {
t.Log("expect totalWeight :", gGolden.TotalWeight(), "actaul :", g.TotalWeight())
t.Fail()
}
}
func TestMstKruskal(t *testing.T) {
g := mstSetup()
tree := mstKruskal(g)
treeExp := mstGolden()
checkMstOutOfOrder(t, tree, treeExp)
}
func TestMstPrim(t *testing.T) {
g := mstSetup()
tree := mstPrim(g)
treeExp := mstGolden()
checkMstOutOfOrder(t, tree, treeExp)
}
func TestSecondaryMst(t *testing.T) {
g := mstSetup()
tree := secondaryMst(g)
treeExp := secondaryMstGolden()
checkMstOutOfOrder(t, tree, treeExp)
}
func TestMstReducedPrim(t *testing.T) {
g := mstSetup()
tree := mstReducedPrim(g, 2)
treeExp := mstGolden()
checkMstOutOfOrder(t, tree, treeExp)
}
func TestBottleNeckSpanningTree(t *testing.T) {
g := mstSetup()
tree := bottleNeckSpanningTree(g)
treeExp := bottleNeckSpanningTreeGolden()
checkMstOutOfOrder(t, tree, treeExp)
}