Skip to content

Commit f7c90c5

Browse files
author
Ubuntu
committed
refactory graph data structure, remove createGraphByType
1 parent a36b32d commit f7c90c5

19 files changed

+110
-140
lines changed

‎graph/apsp.go

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -52,7 +52,7 @@ func distFloydHandler(array *[][][]int, k, i, j int) {
5252
}
5353

5454
func distFloydWarShall(g weightedGraph) weightedGraph {
55-
newG := createGraphByType(g).(weightedGraph)
55+
newG := newWeightedGraph()
5656
rebuild := func(vertices []interface{}, array [][]int) {
5757
for i := range vertices {
5858
for j := range vertices {
@@ -98,7 +98,7 @@ func pathFloydWarShall(g weightedGraph) map[interface{}]weightedGraph {
9898
rebuild := func(vertices []interface{}, array [][]int) {
9999
pathForest = make(map[interface{}]weightedGraph)
100100
for i := range vertices {
101-
pathForest[vertices[i]] = createGraphByType(g).(weightedGraph)
101+
pathForest[vertices[i]] = newWeightedGraph()
102102
for j := range vertices {
103103
if pathArray[i][j] < math.MaxInt32 {
104104
//pathArray[i][j] -> j
@@ -114,7 +114,7 @@ func pathFloydWarShall(g weightedGraph) map[interface{}]weightedGraph {
114114
}
115115

116116
func johnson(g weightedGraph) weightedGraph {
117-
tempG := createGraphByType(g).(weightedGraph)
117+
tempG := newWeightedGraph()
118118
s := struct{}{}
119119
//add e{s,v}, weight is 0
120120
for _, e := range g.AllEdges() {
@@ -132,7 +132,7 @@ func johnson(g weightedGraph) weightedGraph {
132132
tempG.AddEdgeWithWeight(e, tempG.Weight(e)+spfaE[e.Start].D-spfaE[e.End].D)
133133
}
134134

135-
newG := createGraphByType(g).(weightedGraph)
135+
newG := newWeightedGraph()
136136
//exclude dummy vertex s, and iterate vertices, recover distance
137137
delete(spfaE, s)
138138
for v := range spfaE {

‎graph/apsp_test.go

Lines changed: 8 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -20,8 +20,8 @@ func apspSetup(g weightedGraph) {
2020
g.AddEdgeWithWeight(edge{4, 3}, 6)
2121
}
2222

23-
func distFloydWarShallGolden(g weightedGraph) weightedGraph {
24-
golden := createGraphByType(g).(weightedGraph)
23+
func distFloydWarShallGolden() weightedGraph {
24+
golden := newWeightedGraph()
2525
for i := 0; i < 5; i++ {
2626
golden.AddVertex(i)
2727
golden.AddEdgeWithWeight(edge{i, i}, 0)
@@ -57,7 +57,7 @@ func distFloydWarShallGolden(g weightedGraph) weightedGraph {
5757
func pathFloydWarShallGolden(g weightedGraph) map[interface{}]weightedGraph {
5858
golden := make(map[interface{}]weightedGraph)
5959
for i := 0; i < 5; i++ {
60-
golden[i] = createGraphByType(g).(weightedGraph)
60+
golden[i] = newWeightedGraph()
6161
}
6262
golden[0].AddEdgeWithWeight(edge{2, 1}, g.Weight(edge{2, 1}))
6363
golden[0].AddEdgeWithWeight(edge{3, 2}, g.Weight(edge{3, 2}))
@@ -126,15 +126,15 @@ func checkApspOutOfOrder(t *testing.T, g, gGolden weightedGraph) {
126126
}
127127

128128
func TestDistFloydWarShall(t *testing.T) {
129-
g := newAdjacencyMatrixWithWeight()
129+
g := newWeightedGraph()
130130
apspSetup(g)
131131
newG := distFloydWarShall(g)
132-
goldenG := distFloydWarShallGolden(g)
132+
goldenG := distFloydWarShallGolden()
133133
checkApspOutOfOrder(t, newG, goldenG)
134134
}
135135

136136
func TestPathFloydWarShall(t *testing.T) {
137-
g := newAdjacencyMatrixWithWeight()
137+
g := newWeightedGraph()
138138
apspSetup(g)
139139
newForest := pathFloydWarShall(g)
140140
goldenForest := pathFloydWarShallGolden(g)
@@ -144,9 +144,9 @@ func TestPathFloydWarShall(t *testing.T) {
144144
}
145145

146146
func TestJohnson(t *testing.T) {
147-
g := newAdjacencyMatrixWithWeight()
147+
g := newWeightedGraph()
148148
apspSetup(g)
149149
newG := johnson(g)
150-
goldenG := distFloydWarShallGolden(g)
150+
goldenG := distFloydWarShallGolden()
151151
checkApspOutOfOrder(t, newG, goldenG)
152152
}

‎graph/bfs.go

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -80,7 +80,7 @@ func bfsVisit(g graph, s interface{}, handler *bfsVisitHandler) {
8080
}
8181

8282
func bfs(g graph, s interface{}) (bfsGraph graph) {
83-
bfsGraph = createGraphByType(g)
83+
bfsGraph = newGraph()
8484
handler := newBFSVisitHandler()
8585
handler.EdgeHandler = func(start, end *bfsElement) {
8686
bfsGraph.AddEdge(edge{start, end})

‎graph/bfs_test.go

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -27,7 +27,7 @@ func bfsSetupGraph(g graph) {
2727
}
2828

2929
func bfsGolden(g graph) (bfsGraph graph) {
30-
bfsGraph = createGraphByType(g)
30+
bfsGraph = newGraph()
3131
vertexes := make(map[interface{}]*bfsElement)
3232
vertexes["s"] = newBFSElement("s")
3333
vertexes["s"].Dist = 0
@@ -106,7 +106,7 @@ func checkBFSGraphOutOfOrder(t *testing.T, g graph, gGolden graph) {
106106
}
107107

108108
func TestBFS(t *testing.T) {
109-
g := newAdjacencyMatrix()
109+
g := newGraph()
110110
bfsSetupGraph(g)
111111
bfsGraph := bfs(g, "s")
112112
expBfsGraph := bfsGolden(g)

‎graph/bioConnectedComp.go

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

77
func vertexBCC(g graph) (cuts graph, comps []graph) {
8-
cuts = createGraphByType(g)
8+
cuts = newGraph()
99
comps = make([]graph, 0, 0)
1010
lows := make(map[interface{}]int)
1111
children := make(map[interface{}]int)
@@ -36,7 +36,7 @@ func vertexBCC(g graph) (cuts graph, comps []graph) {
3636
if !(p.D == 1 && children[p.V] < 2) {
3737
cuts.AddVertex(p.V)
3838
}
39-
comps = append(comps, createGraphByType(g))
39+
comps = append(comps, newGraph())
4040
curEdge := edge{p.V, v.V}
4141
comps[len(comps)-1].AddEdgeBi(curEdge)
4242
for e := edgeStack.Back().Value; e != curEdge; e = edgeStack.Back().Value {
@@ -56,7 +56,7 @@ func vertexBCC(g graph) (cuts graph, comps []graph) {
5656
}
5757

5858
func edgeBCC(g graph) (bridges graph, comps []graph) {
59-
bridges = createGraphByType(g)
59+
bridges = newGraph()
6060
comps = make([]graph, 0, 0)
6161
lows := make(map[interface{}]int)
6262
edgeStack := list.New()
@@ -82,7 +82,7 @@ func edgeBCC(g graph) (bridges graph, comps []graph) {
8282
lows[p.V] = lows[v.V]
8383
}
8484
if lows[v.V] >= p.D {
85-
comp := createGraphByType(g)
85+
comp := newGraph()
8686
curEdge := edge{p.V, v.V}
8787
if lows[v.V] > p.D {
8888
bridges.AddEdgeBi(curEdge)

‎graph/bioConnectedComp_test.go

Lines changed: 10 additions & 27 deletions
Original file line numberDiff line numberDiff line change
@@ -41,11 +41,11 @@ func bccSetupGraph(g graph) {
4141
g.AddEdgeBi(edge{17, 22})
4242
}
4343

44-
func vertexBCCGolden(g graph) (cuts graph, comps []graph) {
45-
cuts = createGraphByType(g)
44+
func vertexBCCGolden() (cuts graph, comps []graph) {
45+
cuts = newGraph()
4646
comps = make([]graph, 12, 12)
4747
for i := range comps {
48-
comps[i] = createGraphByType(g)
48+
comps[i] = newGraph()
4949
}
5050

5151
cuts.AddVertex(19)
@@ -89,11 +89,11 @@ func vertexBCCGolden(g graph) (cuts graph, comps []graph) {
8989
return
9090
}
9191

92-
func edgeBCCGolden(g graph) (bridges graph, comps []graph) {
93-
bridges = createGraphByType(g)
92+
func edgeBCCGolden() (bridges graph, comps []graph) {
93+
bridges = newGraph()
9494
comps = make([]graph, 6, 6)
9595
for i := range comps {
96-
comps[i] = createGraphByType(g)
96+
comps[i] = newGraph()
9797
}
9898

9999
bridges.AddEdgeBi(edge{19, 17})
@@ -162,40 +162,23 @@ func checkBCCGraphOutOfOrder(t *testing.T, g graph, gGloden graph) {
162162
}
163163

164164
func TestVertexBCC(t *testing.T) {
165-
g := newAdjacencyMatrix()
165+
g := newGraph()
166166
bccSetupGraph(g)
167167
cuts, comps := vertexBCC(g)
168-
cutsExp, compsExp := vertexBCCGolden(g)
168+
cutsExp, compsExp := vertexBCCGolden()
169169
checkBCCGraphOutOfOrder(t, cuts, cutsExp)
170170
for i := range comps {
171171
checkBCCGraphOutOfOrder(t, comps[i], compsExp[i])
172172
}
173173
}
174174

175175
func TestEdgeBCC(t *testing.T) {
176-
g := newAdjacencyMatrix()
176+
g := newGraph()
177177
bccSetupGraph(g)
178178
bridges, comps := edgeBCC(g)
179-
bridgesExp, compsExp := edgeBCCGolden(g)
179+
bridgesExp, compsExp := edgeBCCGolden()
180180
checkBCCGraphOutOfOrder(t, bridges, bridgesExp)
181181
for i := range comps {
182182
checkBCCGraphOutOfOrder(t, comps[i], compsExp[i])
183183
}
184-
//for _, v := range bridges.AllEdges() {
185-
// t.Log(v)
186-
// t.Log(v.Start)
187-
// t.Log(v.End)
188-
//}
189-
//for i := range comps {
190-
// t.Log("comps ", i, "vertices:")
191-
// for _, v := range comps[i].AllVertices() {
192-
// t.Log(v)
193-
// }
194-
// t.Log("comps ", i, "edges:")
195-
// for _, v := range comps[i].AllEdges() {
196-
// t.Log(v)
197-
// t.Log(v.Start)
198-
// t.Log(v.End)
199-
// }
200-
//}
201184
}

‎graph/dfs.go

Lines changed: 9 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -45,11 +45,11 @@ type dfsForest struct {
4545
Comps map[*dfsElement]*dfsForest
4646
}
4747

48-
func (f *dfsForest) Init(g graph) *dfsForest {
49-
f.Trees = createGraphByType(g)
50-
f.BackEdges = createGraphByType(g)
51-
f.ForwardEdges = createGraphByType(g)
52-
f.CrossEdges = createGraphByType(g)
48+
func (f *dfsForest) Init() *dfsForest {
49+
f.Trees = newGraph()
50+
f.BackEdges = newGraph()
51+
f.ForwardEdges = newGraph()
52+
f.CrossEdges = newGraph()
5353
f.Comps = make(map[*dfsElement]*dfsForest)
5454
return f
5555
}
@@ -80,7 +80,7 @@ func (f *dfsForest) addCrossEdge(e edge) {
8080
func (f *dfsForest) getRoot(e *dfsElement) *dfsElement {
8181
root := e.FindRoot()
8282
if _, ok := f.Comps[root]; !ok {
83-
f.Comps[root] = newDFSForest(f.Trees)
83+
f.Comps[root] = newDFSForest()
8484
}
8585
return root
8686
}
@@ -150,8 +150,8 @@ func (f *dfsForest) AllEdges() []edge {
150150
return edges
151151
}
152152

153-
func newDFSForest(g graph) *dfsForest {
154-
return new(dfsForest).Init(g)
153+
func newDFSForest() *dfsForest {
154+
return new(dfsForest).Init()
155155
}
156156

157157
type dfsVisitHandler struct {
@@ -243,7 +243,7 @@ func dfsVisit(g graph, v interface{}, handler *dfsVisitHandler) {
243243
}
244244

245245
func dfs(g graph, sorter func([]interface{})) (dfsForest *dfsForest) {
246-
dfsForest = newDFSForest(g)
246+
dfsForest = newDFSForest()
247247
handler := newDFSVisitHandler()
248248
handler.BeforeDfsHandler = func(v *dfsElement) {
249249
dfsForest.AddVertex(v)

‎graph/dfs_test.go

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -23,7 +23,7 @@ func dfsSetupGraph(g graph) {
2323
}
2424

2525
func dfsGolden(g graph) *dfsForest {
26-
dfsForest := newDFSForest(g)
26+
dfsForest := newDFSForest()
2727
vertexes := make(map[interface{}]*dfsElement)
2828

2929
vertexes["u"] = newDFSElement("u")
@@ -89,7 +89,7 @@ func dfsGolden(g graph) *dfsForest {
8989
}
9090

9191
func TestDFS(t *testing.T) {
92-
g := newAdjacencyMatrix()
92+
g := newGraph()
9393
dfsSetupGraph(g)
9494
dfsGraph := dfs(g, func(vertices []interface{}) {
9595
sort.Slice(vertices, func(i, j int) bool {

‎graph/eulerCircuit_test.go

Lines changed: 8 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -28,7 +28,7 @@ func udEulerCircuitSetup(g graph) {
2828
}
2929

3030
func TestDiEulerCircuitOK(t *testing.T) {
31-
g := newAdjacencyMatrix()
31+
g := newGraph()
3232
diEulerCircuitSetup(g)
3333
for i := 0; i < 3; i++ {
3434
path := eulerCircuit(g)
@@ -41,7 +41,7 @@ func TestDiEulerCircuitOK(t *testing.T) {
4141
}
4242

4343
func TestDiEulerCircuitWithSingleVertex(t *testing.T) {
44-
g := newAdjacencyMatrix()
44+
g := newGraph()
4545
diEulerCircuitSetup(g)
4646
g.AddVertex(6)
4747
path := eulerCircuit(g)
@@ -52,7 +52,7 @@ func TestDiEulerCircuitWithSingleVertex(t *testing.T) {
5252
}
5353

5454
func TestDiEulerCircuitWithSingleVertexLoop(t *testing.T) {
55-
g := newAdjacencyMatrix()
55+
g := newGraph()
5656
diEulerCircuitSetup(g)
5757
g.AddEdgeBi(edge{6, 6})
5858
path := eulerCircuit(g)
@@ -63,7 +63,7 @@ func TestDiEulerCircuitWithSingleVertexLoop(t *testing.T) {
6363
}
6464

6565
func TestDiEulerCircuitWithNonCircuit(t *testing.T) {
66-
g := newAdjacencyMatrix()
66+
g := newGraph()
6767
diEulerCircuitSetup(g)
6868
g.AddEdge(edge{6, 1})
6969
path := eulerCircuit(g)
@@ -72,7 +72,7 @@ func TestDiEulerCircuitWithNonCircuit(t *testing.T) {
7272
t.Fail()
7373
}
7474

75-
g = newAdjacencyMatrix()
75+
g = newGraph()
7676
diEulerCircuitSetup(g)
7777
g.AddEdge(edge{1, 6})
7878
path = eulerCircuit(g)
@@ -83,7 +83,7 @@ func TestDiEulerCircuitWithNonCircuit(t *testing.T) {
8383
}
8484

8585
func TestUdEulerCircuitOK(t *testing.T) {
86-
g := newAdjacencyMatrix()
86+
g := newGraph()
8787
udEulerCircuitSetup(g)
8888
path := eulerCircuit(g)
8989
pathExp := eulerCircuitGolden()
@@ -94,7 +94,7 @@ func TestUdEulerCircuitOK(t *testing.T) {
9494
}
9595

9696
func TestUdEulerCircuitWithSingleVertex(t *testing.T) {
97-
g := newAdjacencyMatrix()
97+
g := newGraph()
9898
udEulerCircuitSetup(g)
9999
g.AddVertex(6)
100100
path := eulerCircuit(g)
@@ -105,7 +105,7 @@ func TestUdEulerCircuitWithSingleVertex(t *testing.T) {
105105
}
106106

107107
func TestUdEulerCircuitWithNonCircuit(t *testing.T) {
108-
g := newAdjacencyMatrix()
108+
g := newGraph()
109109
udEulerCircuitSetup(g)
110110
g.AddEdgeBi(edge{1, 6})
111111
path := eulerCircuit(g)

‎graph/flowGraph.go

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -46,7 +46,7 @@ func updateFlow(rg, g flowGraph, rc int, edges []edge) {
4646
}
4747

4848
func edmondsKarp(g flowGraph, s interface{}, t interface{}) {
49-
residualG := createGraphByType(g).(flowGraph)
49+
residualG := newFlowGraph()
5050
for _, e := range g.AllEdges() {
5151
g.AddEdgeWithFlow(e, 0)
5252
residualG.AddEdgeWithCap(e, g.Cap(e))

‎graph/flowGraph_test.go

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -19,7 +19,7 @@ func flowGraphSetup(g flowGraph) {
1919
}
2020

2121
func flowGraphGolden(g flowGraph) flowGraph {
22-
flowG := createGraphByType(g).(flowGraph)
22+
flowG := newFlowGraph()
2323
for _, e := range g.AllEdges() {
2424
flowG.AddEdgeWithCap(e, g.Cap(e))
2525
}
@@ -79,7 +79,7 @@ func checkFlowGraphOutOfOrder(t *testing.T, g, gGolden flowGraph) {
7979
}
8080

8181
func TestEdmondsKarp(t *testing.T) {
82-
g := newAdjacencyMatrixWithFlow()
82+
g := newFlowGraph()
8383
flowGraphSetup(g)
8484
edmondsKarp(g, "s", "t")
8585
gGolden := flowGraphGolden(g)

0 commit comments

Comments
 (0)