-
Notifications
You must be signed in to change notification settings - Fork 0
/
graph.go
102 lines (86 loc) · 1.97 KB
/
graph.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
package graph
import (
"errors"
"log"
"strconv"
)
type ordered interface {
~int | ~int8 | ~int16 | ~int32 | ~int64 | ~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~float32 | ~float64
}
type vertex interface {
string | int
}
func VertexToString(x interface{}) (string, error) {
switch typex := x.(type) {
case string:
return typex, nil
case int:
return strconv.Itoa(typex), nil
}
return "", errors.New("only allowed string or int")
}
type Edge[Vertex vertex, Weight ordered] struct {
U Vertex
V Vertex
W Weight
NotDirect bool
}
type E[Vertex vertex, Weight ordered] struct {
V Vertex
W Weight
}
type GraphAdj[Vertex vertex, Weight ordered] struct {
data map[Vertex][]*E[Vertex, Weight]
Edges []*Edge[Vertex, Weight]
HasCycle bool
NotDirect bool
Logger *log.Logger
}
type DfsRet[Vertex vertex] struct {
V Vertex
findTime int
finishTime int
}
func NewGraphAdj[Vertex vertex, Weight ordered]() GraphAdj[Vertex, Weight] {
return GraphAdj[Vertex, Weight]{
data: map[Vertex][]*E[Vertex, Weight]{},
Edges: []*Edge[Vertex, Weight]{},
Logger: log.Default(),
}
}
func (g GraphAdj[Vertex, Weight]) AddEdge(e *Edge[Vertex, Weight]) {
if g.NotDirect && !e.NotDirect {
g.Logger.Fatal("graph is undirected, but get an directed edgs", *e)
return
}
g.data[e.U] = append(g.data[e.U], &E[Vertex, Weight]{
V: e.V,
W: e.W,
})
if e.NotDirect {
g.data[e.V] = append(g.data[e.V], &E[Vertex, Weight]{
V: e.U,
W: e.W,
})
}
}
func (g GraphAdj[Vertex, Weight]) AddVertex(u Vertex) {
g.data[u] = []*E[Vertex, Weight]{}
}
// reverse the edge in Graph g and return a new Graph
func (g GraphAdj[Vertex, Weight]) Transpose() GraphAdj[Vertex, Weight] {
ret := NewGraphAdj[Vertex, Weight]()
for u, edges := range g.data {
if len(edges) > 0 {
for _, e := range edges {
ret.data[e.V] = append(ret.data[e.V], &E[Vertex, Weight]{
V: u,
W: e.W,
})
}
} else {
ret.AddVertex(u)
}
}
return ret
}