algorithms/graph/bioConnectedComp.go at master · shady831213/algorithms · GitHub

Name: algorithms/graph/bioConnectedComp.go at master · shady831213/algorithms · GitHub
Rating: 4.9 (316 reviews)
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
package graph

import (
"container/list"
)

funcvertexBCC(ggraph) (cutsgraph, comps []graph) {
cuts=newGraph()
comps=make([]graph, 0, 0)
lows:=make(map[interface{}]int)
children:=make(map[interface{}]int)
edgeStack:=list.New()
handler:=newDFSVisitHandler()
handler.BeforeDfsHandler=func(v*dfsElement) {
lows[v.V] =v.D
 }
handler.TreeEdgeHandler=func(start, end*dfsElement) {
children[start.V]++
edgeStack.PushBack(edge{start.V, end.V})
 }
handler.BackEdgeHandler=func(start, end*dfsElement) {
ifend.D<lows[start.V] &&start.P!=end {
edgeStack.PushBack(edge{start.V, end.V})
lows[start.V] =end.D
 }
 }
handler.AfterDfsHandler=func(v*dfsElement) {
p:=v.P
ifp==nil {
return
 }
iflows[v.V] <lows[p.V] {
lows[p.V] =lows[v.V]
 }
iflows[v.V] >=p.D {
if!(p.D==1&&children[p.V] <2) {
cuts.AddVertex(p.V)
 }
comps=append(comps, newGraph())
curEdge:=edge{p.V, v.V}
comps[len(comps)-1].AddEdgeBi(curEdge)
fore:=edgeStack.Back().Value; e!=curEdge; e=edgeStack.Back().Value {
edgeStack.Remove(edgeStack.Back())
comps[len(comps)-1].AddEdgeBi(e.(edge))
 }
edgeStack.Remove(edgeStack.Back())
 }
 }

for_, v:=rangeg.AllVertices() {
if!handler.Elements.exist(v) {
dfsVisit(g, v, handler)
 }
 }
return
}

funcedgeBCC(ggraph) (bridgesgraph, comps []graph) {
bridges=newGraph()
comps=make([]graph, 0, 0)
lows:=make(map[interface{}]int)
edgeStack:=list.New()
handler:=newDFSVisitHandler()
handler.BeforeDfsHandler=func(v*dfsElement) {
lows[v.V] =v.D
 }
handler.TreeEdgeHandler=func(start, end*dfsElement) {
edgeStack.PushBack(edge{start.V, end.V})
 }
handler.BackEdgeHandler=func(start, end*dfsElement) {
ifend.D<lows[start.V] &&start.P!=end {
edgeStack.PushBack(edge{start.V, end.V})
lows[start.V] =end.D
 }
 }
handler.AfterDfsHandler=func(v*dfsElement) {
p:=v.P
ifp==nil {
return
 }
iflows[v.V] <lows[p.V] {
lows[p.V] =lows[v.V]
 }
iflows[v.V] >=p.D {
comp:=newGraph()
curEdge:=edge{p.V, v.V}
iflows[v.V] >p.D {
bridges.AddEdgeBi(curEdge)
 } else {
//excluding bridge
comp.AddEdgeBi(curEdge)
 }
fore:=edgeStack.Back().Value; e!=curEdge; e=edgeStack.Back().Value {
edgeStack.Remove(edgeStack.Back())
comp.AddEdgeBi(e.(edge))
 }
edgeStack.Remove(edgeStack.Back())
//if component is not empty, push it to the slice
iflen(comp.AllVertices()) !=0 {
comps=append(comps, comp)
 }
 }

 }

for_, v:=rangeg.AllVertices() {
if!handler.Elements.exist(v) {
dfsVisit(g, v, handler)
 }
 }
return
}