blob: 6656947e96b45d06a716663d2566aa315a33d52c (
plain)
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
|
# Routes over a graph in one event each (Pure 018): breadth first, depth
# first and the nearest by weight. A node's edges are a slice of the edges
# list (keyed by from * 1048576 + to); the searches keep their queues and
# what they have seen in the event's own lists, gone when it ends.
record Node {
id = 0
}
record Edge {
link = 0
to = 0
w = 1
}
record Seen {
node = 0
depth = 0
}
record Step {
node = 0
}
record Pending {
rank = 0
}
state nodes: list of Node by id
state edges: list of Edge by link
state hops = -1
state visited = 0
state order = 0
state shortest = -1
input link = message {
from: u32
to: u32
w: u32
}
input route = message {
from: u32
to: u32
}
input walk = message {
from: u32
}
input path = message {
from: u32
to: u32
}
on link {
if !nodes.has(link.from) { nodes.add(Node { id: link.from }) }
if !nodes.has(link.to) { nodes.add(Node { id: link.to }) }
edges.add(Edge { link: link.from * 1048576 + link.to, to: link.to, w: link.w })
}
# Breadth first: the queue is read by position, every node enters it once.
on route {
let seen: list of Seen by node
let queue: list of Step
queue.append(Step { node: route.from })
seen.add(Seen { node: route.from })
for i in 0 .. nodes.count {
if i >= queue.count { break }
let q = queue.first + i
for e in edges[q.node * 1048576 .. q.node * 1048576 + 1048576] {
if !seen.has(e.to) {
seen.add(Seen { node: e.to, depth: seen[q.node].depth + 1 })
queue.append(Step { node: e.to })
}
}
}
hops = if seen.has(route.to) { seen[route.to].depth } else { -1 }
}
# Depth first: a stack, each edge pushed once at most; depth is the order a node was reached in.
on walk {
let seen: list of Seen by node
let stack: list of Step
stack.append(Step { node: walk.from })
let reached = 0
for i in 0 .. edges.count + 1 {
if stack.count == 0 { break }
let v = stack.last.node
stack.remove(stack.last)
if !seen.has(v) {
seen.add(Seen { node: v, depth: reached })
reached = reached + 1
for e in edges[v * 1048576 .. v * 1048576 + 1048576] {
if !seen.has(e.to) { stack.append(Step { node: e.to }) }
}
}
}
visited = seen.count
order = sum(s.depth * (s.node + 1) for s in seen)
}
# The nearest by weight (Dijkstra): pending ranks by dist * 1048576 + node, the nearest first.
on path {
let best: list of Seen by node
let pending: list of Pending by rank
best.add(Seen { node: path.from })
pending.add(Pending { rank: path.from })
for i in 0 .. edges.count + 1 {
if pending.count == 0 { break }
let d = floor(pending.first.rank / 1048576)
let v = pending.first.rank - d * 1048576
pending.remove(pending.first)
if best[v].depth == d {
for e in edges[v * 1048576 .. v * 1048576 + 1048576] {
let far = d + e.w
if !best.has(e.to) {
best.add(Seen { node: e.to, depth: far })
pending.add(Pending { rank: far * 1048576 + e.to })
} else if far < best[e.to].depth {
best[e.to].depth = far
pending.add(Pending { rank: far * 1048576 + e.to })
}
}
}
}
shortest = if best.has(path.to) { best[path.to].depth } else { -1 }
}
view graph = "{nodes.count} nodes, {edges.count} edges"
|
