-
Notifications
You must be signed in to change notification settings - Fork 6
/
graph.go
125 lines (114 loc) · 2.94 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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
package dijkstra
import(
"bufio"
// "container/heap"
"log"
"os"
"strconv"
"strings"
)
type Edge struct {
tail int
head int
weight int
}
type Vertex struct {
id int
dist int
arcs map[int]int // arcs[vertex id] = weight
}
type Candidates []Vertex
func (h Candidates) Len() int { return len(h) }
func (h Candidates) Less(i, j int) bool { return h[i].dist < h[j].dist }
func (h Candidates) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h Candidates) IsEmpty() bool { return len(h) == 0 }
func (h *Candidates) Push(v Vertex) {
var changed bool
old := *h
updated := *h
// insert Vertex at the correct position (keyed by distance)
for i, w := range old {
if v.id == w.id {
if changed {
if i + 1 < len(updated) {
updated = append(updated[:i], updated[i+1:]...)
} else {
updated = updated[:i]
}
} else if v.dist < w.dist {
updated[i] = v
}
changed = true
} else if v.dist < w.dist {
changed = true
updated = append(old[:i], v)
updated = append(updated, w)
updated = append(updated, old[i + 1:]...)
}
}
if !changed {
updated = append(old, v)
}
*h = updated
}
func (h *Candidates) Pop() (v Vertex) {
old := *h
v = old[0]
*h = old[1:]
return
}
type Graph struct {
visited map[int]bool
vertices map[int]Vertex
}
func NewGraph(vs map[int]Vertex) *Graph {
g := new(Graph)
g.visited = make(map[int]bool)
g.vertices = make(map[int]Vertex)
for i, v := range vs {
v.dist = 1000000
g.vertices[i] = v
}
return g
}
func NewGraphFromFile(fn string) *Graph {
v := make(map[int]Vertex)
f, err := os.Open(fn)
if err != nil {
log.Fatal(err)
}
defer f.Close()
scanner := bufio.NewScanner(f)
for scanner.Scan() {
line := scanner.Text()
words := strings.Split(string(line), "\t")
t := words[0]
tail, err := strconv.Atoi(t)
// a Vertex is an id (tail) and a map of arcs
arcs := make(map[int]int)
for i := 1; i < len(words); i++ {
item := strings.Split(words[i], ",")
if len(item) < 2 {
break
}
h, w := item[0], item[1]
head, err := strconv.Atoi(h)
if err != nil {
log.Print(err)
}
weight, err := strconv.Atoi(w)
if err != nil {
log.Print(err)
}
arcs[head] = weight
}
v[tail] = Vertex{id: tail, arcs: arcs, dist: 0}
if err != nil {
log.Print(err)
}
err = nil
}
return NewGraph(v)
}
func (g *Graph) Len() int { return len(g.vertices) }
func (g *Graph) visit(v int) { g.visited[v] = true }