Skip to content

Commit d396892

Browse files
author
Ubuntu
committed
add bio graph max match;refactory tests
1 parent f7c90c5 commit d396892

12 files changed

+216
-219
lines changed

‎graph/apsp_test.go

Lines changed: 13 additions & 41 deletions
Original file line numberDiff line numberDiff line change
@@ -1,11 +1,11 @@
11
package graph
22

33
import (
4-
"sort"
54
"testing"
65
)
76

8-
func apspSetup(g weightedGraph) {
7+
func apspSetup() weightedGraph {
8+
g := newWeightedGraph()
99
for i := 0; i < 5; i++ {
1010
g.AddVertex(i)
1111
}
@@ -18,6 +18,7 @@ func apspSetup(g weightedGraph) {
1818
g.AddEdgeWithWeight(edge{3, 0}, 2)
1919
g.AddEdgeWithWeight(edge{3, 2}, -5)
2020
g.AddEdgeWithWeight(edge{4, 3}, 6)
21+
return g
2122
}
2223

2324
func distFloydWarShallGolden() weightedGraph {
@@ -88,54 +89,26 @@ func pathFloydWarShallGolden(g weightedGraph) map[interface{}]weightedGraph {
8889
}
8990

9091
func checkApspOutOfOrder(t *testing.T, g, gGolden weightedGraph) {
91-
edges := g.AllEdges()
92-
//finish time increase order
93-
vertexes := g.AllVertices()
94-
sort.Slice(edges, func(i, j int) bool {
95-
if edges[i].End.(int) == edges[j].End.(int) {
96-
return edges[i].Start.(int) < edges[j].Start.(int)
97-
}
98-
return edges[i].End.(int) < edges[j].End.(int)
99-
})
100-
101-
sort.Slice(vertexes, func(i, j int) bool {
102-
return vertexes[i].(int) < vertexes[j].(int)
103-
})
104-
105-
expEdges := gGolden.AllEdges()
106-
expVertices := gGolden.AllVertices()
107-
108-
sort.Slice(expEdges, func(i, j int) bool {
109-
if expEdges[i].End.(int) == expEdges[j].End.(int) {
110-
return expEdges[i].Start.(int) < expEdges[j].Start.(int)
111-
}
112-
return expEdges[i].End.(int) < expEdges[j].End.(int)
113-
})
114-
115-
sort.Slice(expVertices, func(i, j int) bool {
116-
return expVertices[i].(int) < expVertices[j].(int)
117-
})
118-
119-
compareGraph(t, vertexes, expVertices, edges, expEdges)
120-
for _, e := range expEdges {
121-
if g.Weight(e) != gGolden.Weight(e) {
122-
t.Log(e, "weight Error! exp :", gGolden.Weight(e), "actual: ", g.Weight(e))
123-
t.FailNow()
92+
comparator := func(t *testing.T, v, vExp []interface{}, e, eExp []edge) {
93+
for _, e := range eExp {
94+
if g.Weight(e) != gGolden.Weight(e) {
95+
t.Log(e, "weight Error! exp :", gGolden.Weight(e), "actual: ", g.Weight(e))
96+
t.FailNow()
97+
}
12498
}
12599
}
100+
checkGraphOutOfOrderInInt(t, g, gGolden, comparator)
126101
}
127102

128103
func TestDistFloydWarShall(t *testing.T) {
129-
g := newWeightedGraph()
130-
apspSetup(g)
104+
g := apspSetup()
131105
newG := distFloydWarShall(g)
132106
goldenG := distFloydWarShallGolden()
133107
checkApspOutOfOrder(t, newG, goldenG)
134108
}
135109

136110
func TestPathFloydWarShall(t *testing.T) {
137-
g := newWeightedGraph()
138-
apspSetup(g)
111+
g := apspSetup()
139112
newForest := pathFloydWarShall(g)
140113
goldenForest := pathFloydWarShallGolden(g)
141114
for v := range newForest {
@@ -144,8 +117,7 @@ func TestPathFloydWarShall(t *testing.T) {
144117
}
145118

146119
func TestJohnson(t *testing.T) {
147-
g := newWeightedGraph()
148-
apspSetup(g)
120+
g := apspSetup()
149121
newG := johnson(g)
150122
goldenG := distFloydWarShallGolden()
151123
checkApspOutOfOrder(t, newG, goldenG)

‎graph/bfs_test.go

Lines changed: 4 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -5,7 +5,8 @@ import (
55
"testing"
66
)
77

8-
func bfsSetupGraph(g graph) {
8+
func bfsSetupGraph() graph {
9+
g := newGraph()
910
g.AddVertex("r")
1011
g.AddVertex("s")
1112
g.AddVertex("t")
@@ -24,6 +25,7 @@ func bfsSetupGraph(g graph) {
2425
g.AddEdgeBi(edge{"x", "u"})
2526
g.AddEdgeBi(edge{"x", "y"})
2627
g.AddEdgeBi(edge{"u", "y"})
28+
return g
2729
}
2830

2931
func bfsGolden(g graph) (bfsGraph graph) {
@@ -106,8 +108,7 @@ func checkBFSGraphOutOfOrder(t *testing.T, g graph, gGolden graph) {
106108
}
107109

108110
func TestBFS(t *testing.T) {
109-
g := newGraph()
110-
bfsSetupGraph(g)
111+
g := bfsSetupGraph()
111112
bfsGraph := bfs(g, "s")
112113
expBfsGraph := bfsGolden(g)
113114
checkBFSGraphOutOfOrder(t, bfsGraph, expBfsGraph)

‎graph/bioConnectedComp_test.go

Lines changed: 9 additions & 42 deletions
Original file line numberDiff line numberDiff line change
@@ -1,11 +1,11 @@
11
package graph
22

33
import (
4-
"sort"
54
"testing"
65
)
76

8-
func bccSetupGraph(g graph) {
7+
func bccSetupGraph() graph {
8+
g := newGraph()
99
for i := 0; i < 23; i++ {
1010
g.AddVertex(i)
1111
}
@@ -39,6 +39,7 @@ func bccSetupGraph(g graph) {
3939
g.AddEdgeBi(edge{20, 21})
4040
g.AddEdgeBi(edge{21, 19})
4141
g.AddEdgeBi(edge{17, 22})
42+
return g
4243
}
4344

4445
func vertexBCCGolden() (cuts graph, comps []graph) {
@@ -129,56 +130,22 @@ func edgeBCCGolden() (bridges graph, comps []graph) {
129130
return
130131
}
131132

132-
func checkBCCGraphOutOfOrder(t *testing.T, g graph, gGloden graph) {
133-
edges := g.AllEdges()
134-
//finish time increase order
135-
vertexes := g.AllVertices()
136-
sort.Slice(edges, func(i, j int) bool {
137-
if edges[i].Start.(int) == edges[j].Start.(int) {
138-
return edges[i].End.(int) < edges[j].End.(int)
139-
}
140-
return edges[i].Start.(int) < edges[j].Start.(int)
141-
})
142-
143-
sort.Slice(vertexes, func(i, j int) bool {
144-
return vertexes[i].(int) < vertexes[j].(int)
145-
})
146-
147-
expEdges := gGloden.AllEdges()
148-
expVertices := gGloden.AllVertices()
149-
150-
sort.Slice(expEdges, func(i, j int) bool {
151-
if expEdges[i].Start.(int) == expEdges[j].Start.(int) {
152-
return expEdges[i].End.(int) < expEdges[j].End.(int)
153-
}
154-
return expEdges[i].Start.(int) < expEdges[j].Start.(int)
155-
})
156-
157-
sort.Slice(expVertices, func(i, j int) bool {
158-
return expVertices[i].(int) < expVertices[j].(int)
159-
})
160-
161-
compareGraph(t, vertexes, expVertices, edges, expEdges)
162-
}
163-
164133
func TestVertexBCC(t *testing.T) {
165-
g := newGraph()
166-
bccSetupGraph(g)
134+
g := bccSetupGraph()
167135
cuts, comps := vertexBCC(g)
168136
cutsExp, compsExp := vertexBCCGolden()
169-
checkBCCGraphOutOfOrder(t, cuts, cutsExp)
137+
checkGraphOutOfOrderInInt(t, cuts, cutsExp, nil)
170138
for i := range comps {
171-
checkBCCGraphOutOfOrder(t, comps[i], compsExp[i])
139+
checkGraphOutOfOrderInInt(t, comps[i], compsExp[i], nil)
172140
}
173141
}
174142

175143
func TestEdgeBCC(t *testing.T) {
176-
g := newGraph()
177-
bccSetupGraph(g)
144+
g := bccSetupGraph()
178145
bridges, comps := edgeBCC(g)
179146
bridgesExp, compsExp := edgeBCCGolden()
180-
checkBCCGraphOutOfOrder(t, bridges, bridgesExp)
147+
checkGraphOutOfOrderInInt(t, bridges, bridgesExp, nil)
181148
for i := range comps {
182-
checkBCCGraphOutOfOrder(t, comps[i], compsExp[i])
149+
checkGraphOutOfOrderInInt(t, comps[i], compsExp[i], nil)
183150
}
184151
}

‎graph/dfs_test.go

Lines changed: 30 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -5,7 +5,8 @@ import (
55
"testing"
66
)
77

8-
func dfsSetupGraph(g graph) {
8+
func dfsSetupGraph() graph {
9+
g := newGraph()
910
g.AddVertex("u")
1011
g.AddVertex("v")
1112
g.AddVertex("w")
@@ -20,6 +21,7 @@ func dfsSetupGraph(g graph) {
2021
g.AddEdge(edge{"w", "y"})
2122
g.AddEdge(edge{"w", "z"})
2223
g.AddEdge(edge{"z", "z"})
24+
return g
2325
}
2426

2527
func dfsGolden(g graph) *dfsForest {
@@ -88,9 +90,34 @@ func dfsGolden(g graph) *dfsForest {
8890
return dfsForest
8991
}
9092

93+
func checkDFSGraphOutOfOrder(t *testing.T, g graph, gGolden graph) {
94+
edges := g.AllEdges()
95+
//finish time increase order
96+
vertexes := g.AllVertices()
97+
sort.Slice(edges, func(i, j int) bool {
98+
return edges[i].Start.(*dfsElement).D < edges[j].Start.(*dfsElement).D
99+
})
100+
101+
sort.Slice(vertexes, func(i, j int) bool {
102+
return vertexes[i].(*dfsElement).D < vertexes[j].(*dfsElement).D
103+
})
104+
105+
expEdges := gGolden.AllEdges()
106+
expVertices := gGolden.AllVertices()
107+
108+
sort.Slice(expEdges, func(i, j int) bool {
109+
return expEdges[i].Start.(*dfsElement).D < expEdges[j].Start.(*dfsElement).D
110+
})
111+
112+
sort.Slice(expVertices, func(i, j int) bool {
113+
return expVertices[i].(*dfsElement).D < expVertices[j].(*dfsElement).D
114+
})
115+
116+
compareGraph(t, vertexes, expVertices, edges, expEdges)
117+
}
118+
91119
func TestDFS(t *testing.T) {
92-
g := newGraph()
93-
dfsSetupGraph(g)
120+
g := dfsSetupGraph()
94121
dfsGraph := dfs(g, func(vertices []interface{}) {
95122
sort.Slice(vertices, func(i, j int) bool {
96123
return vertices[i].(string) < vertices[j].(string)

‎graph/eulerCircuit_test.go

Lines changed: 14 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -5,31 +5,34 @@ import (
55
"testing"
66
)
77

8-
func diEulerCircuitSetup(g graph) {
8+
func diEulerCircuitSetup() graph {
9+
g := newGraph()
910
g.AddEdge(edge{2, 3})
1011
g.AddEdge(edge{2, 5})
1112
g.AddEdge(edge{3, 4})
1213
g.AddEdge(edge{1, 2})
1314
g.AddEdge(edge{4, 2})
1415
g.AddEdge(edge{5, 1})
16+
return g
1517
}
1618

1719
func eulerCircuitGolden() []edge {
1820
return []edge{{2, 3}, {3, 4}, {4, 2}, {2, 5}, {5, 1}, {1, 2}}
1921
}
2022

21-
func udEulerCircuitSetup(g graph) {
23+
func udEulerCircuitSetup() graph {
24+
g := newGraph()
2225
g.AddEdgeBi(edge{2, 3})
2326
g.AddEdgeBi(edge{2, 5})
2427
g.AddEdgeBi(edge{3, 4})
2528
g.AddEdgeBi(edge{1, 2})
2629
g.AddEdgeBi(edge{4, 2})
2730
g.AddEdgeBi(edge{5, 1})
31+
return g
2832
}
2933

3034
func TestDiEulerCircuitOK(t *testing.T) {
31-
g := newGraph()
32-
diEulerCircuitSetup(g)
35+
g := diEulerCircuitSetup()
3336
for i := 0; i < 3; i++ {
3437
path := eulerCircuit(g)
3538
pathExp := eulerCircuitGolden()
@@ -41,8 +44,7 @@ func TestDiEulerCircuitOK(t *testing.T) {
4144
}
4245

4346
func TestDiEulerCircuitWithSingleVertex(t *testing.T) {
44-
g := newGraph()
45-
diEulerCircuitSetup(g)
47+
g := diEulerCircuitSetup()
4648
g.AddVertex(6)
4749
path := eulerCircuit(g)
4850
if path != nil {
@@ -52,8 +54,7 @@ func TestDiEulerCircuitWithSingleVertex(t *testing.T) {
5254
}
5355

5456
func TestDiEulerCircuitWithSingleVertexLoop(t *testing.T) {
55-
g := newGraph()
56-
diEulerCircuitSetup(g)
57+
g := diEulerCircuitSetup()
5758
g.AddEdgeBi(edge{6, 6})
5859
path := eulerCircuit(g)
5960
if path != nil {
@@ -63,17 +64,15 @@ func TestDiEulerCircuitWithSingleVertexLoop(t *testing.T) {
6364
}
6465

6566
func TestDiEulerCircuitWithNonCircuit(t *testing.T) {
66-
g := newGraph()
67-
diEulerCircuitSetup(g)
67+
g := diEulerCircuitSetup()
6868
g.AddEdge(edge{6, 1})
6969
path := eulerCircuit(g)
7070
if path != nil {
7171
t.Log("expect: nil", ", actual :", path)
7272
t.Fail()
7373
}
7474

75-
g = newGraph()
76-
diEulerCircuitSetup(g)
75+
g = diEulerCircuitSetup()
7776
g.AddEdge(edge{1, 6})
7877
path = eulerCircuit(g)
7978
if path != nil {
@@ -83,8 +82,7 @@ func TestDiEulerCircuitWithNonCircuit(t *testing.T) {
8382
}
8483

8584
func TestUdEulerCircuitOK(t *testing.T) {
86-
g := newGraph()
87-
udEulerCircuitSetup(g)
85+
g := udEulerCircuitSetup()
8886
path := eulerCircuit(g)
8987
pathExp := eulerCircuitGolden()
9088
if !reflect.DeepEqual(path, pathExp) {
@@ -94,8 +92,7 @@ func TestUdEulerCircuitOK(t *testing.T) {
9492
}
9593

9694
func TestUdEulerCircuitWithSingleVertex(t *testing.T) {
97-
g := newGraph()
98-
udEulerCircuitSetup(g)
95+
g := udEulerCircuitSetup()
9996
g.AddVertex(6)
10097
path := eulerCircuit(g)
10198
if path != nil {
@@ -105,8 +102,7 @@ func TestUdEulerCircuitWithSingleVertex(t *testing.T) {
105102
}
106103

107104
func TestUdEulerCircuitWithNonCircuit(t *testing.T) {
108-
g := newGraph()
109-
udEulerCircuitSetup(g)
105+
g := udEulerCircuitSetup()
110106
g.AddEdgeBi(edge{1, 6})
111107
path := eulerCircuit(g)
112108
if path != nil {

0 commit comments

Comments
 (0)