From 608221c21edb345e4eeeca85385d2e149c3baa30 Mon Sep 17 00:00:00 2001 From: eunhhu Date: Sun, 4 Oct 2026 14:24:12 +0100 Subject: Measure 018 stage 2: a graph search in one event, the pairs, and runs to compare across machines (033) --- research/experiments/033-computing/graph.aup | 56 ++++++++++++++++++++++++++++ 1 file changed, 56 insertions(+) create mode 100644 research/experiments/033-computing/graph.aup (limited to 'research/experiments/033-computing/graph.aup') diff --git a/research/experiments/033-computing/graph.aup b/research/experiments/033-computing/graph.aup new file mode 100644 index 0000000..a19d96d --- /dev/null +++ b/research/experiments/033-computing/graph.aup @@ -0,0 +1,56 @@ +# The graph of research 118 (docs/design/018 stage 2): edges keyed by +# from * 1048576 + to, loaded in bulk as rows; a breadth first search in +# one event, its queue and what it has seen the event's own lists. +record Edge { + link = 0 + to = 0 +} +record Seen { + node = 0 + depth = 0 +} +record Step { + node = 0 +} +state edges: list of Edge by link +state nodes = 0 +state hops = -1 +state reached = 0 +input size = message { + nodes: u32 +} +input load = message { + rows: list of Edge +} +input route = message { + from: u32 + to: u32 +} +on size { + nodes = size.nodes +} +on load { + for r in load.rows { + edges.add(Edge { ..r }) + } +} +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 { + 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 } + reached = seen.count +} +view far = hops +view found = reached -- cgit v1.2.3