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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
|
# 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 }
}
# The same search as a view (Pure 018's stage 3): it reads a snapshot, so
# it keeps no event from the owner, and readers search at once.
view distance(start: u32, goal: u32) {
let seen: list of Seen by node
let queue: list of Step
queue.append(Step { node: start })
seen.add(Seen { node: start })
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 })
}
}
}
return if seen.has(goal) { seen[goal].depth } else { -1 }
}
# How many nodes the first node reaches (times 1000), and how far the farthest is.
view reach {
let seen: list of Seen by node
let queue: list of Step
let farthest = 0
if nodes.count > 0 {
queue.append(Step { node: nodes.first.id })
seen.add(Seen { node: nodes.first.id })
}
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) {
let far = seen[q.node].depth + 1
seen.add(Seen { node: e.to, depth: far })
queue.append(Step { node: e.to })
farthest = max(farthest, far)
}
}
}
return seen.count * 1000 + farthest
}
view graph = "{nodes.count} nodes, {edges.count} edges"
|
