summaryrefslogtreecommitdiff
path: root/targets/graph.zig
blob: 987eaa5f002c878064f11827fef3de34dae56f8e (plain) (blame)
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
//! A small graph and a breadth-first search over it. `dist` and `queue` are
//! exported globals, so a tracer finds them by name and watches them fill.
//! Exits with the sum of the distances from node 0 (18).
const n = 8;
const unreached = 0xff;

const edges = [_][2]u8{ .{ 0, 1 }, .{ 0, 2 }, .{ 1, 3 }, .{ 2, 3 }, .{ 3, 4 }, .{ 4, 5 }, .{ 5, 6 }, .{ 2, 7 } };

/// Aligned so that it is one machine word to a watcher.
export var dist: [n]u8 align(8) = @splat(unreached);
export var queue: [n]u8 = @splat(0);

fn linked(a: u8, b: u8) bool {
    for (edges) |e| {
        if ((e[0] == a and e[1] == b) or (e[0] == b and e[1] == a)) return true;
    }
    return false;
}

fn bfs(start: u8) void {
    var head: usize = 0;
    var tail: usize = 1;
    queue[0] = start;
    dist[start] = 0;
    while (head < tail) : (head += 1) {
        const at = queue[head];
        for (0..n) |next| {
            if (dist[next] != unreached or !linked(at, @intCast(next))) continue;
            dist[next] = dist[at] + 1;
            queue[tail] = @intCast(next);
            tail += 1;
        }
    }
}

pub fn main() u8 {
    bfs(0);
    var sum: u8 = 0;
    for (dist) |d| sum += d;
    return sum;
}