null or a real error.Cycle, in stead of a silent wrong answer;std.ArrayList and std.PriorityQueue comfort from episodes 22 and 120, and the allocator discipline from episode 7;Learn Zig Series):Two episodes ago I dropped a hint about "dependency ordering" and then made you wait while we chased weighted shortest paths. And at the very end of last episode, staring at that gray/black cycle-detection bookkeeping, I promised it was "about to pay off in a big way". Well -- this is the payoff. Today's whole topic is the answer to a question you have already asked a hundred times without naming it: given a pile of things where some must happen before others, in what order do I actually do them? Compile these files, but only after the headers they include. Install these packages, but each after its dependencies. Recalculate these spreadsheet cells, but only once the cells they reference are done. Run these build steps, these database migrations, these init tasks. Every single one of those is the same abstract problem, and the algorithm that solves it is called a topological sort. But first -- the debt. Last episode's three A* and Dijkstra exercises, in full compilable code ;-)
Exercise 1 -- return the route from A*, not just the cost. Last episode's astar handed you a bare ?u64 cost and threw the actual path away. The fix is the exact parent trick from dijkstraPath: every time relaxing an edge improves a neighbour, remember who improved it, then walk those parents backward from the target and reverse. The one A*-specific wrinkle is the stopping rule -- with an admissible heuristic we can break the instant we pop the target, because that first pop is provably optimal. I test it not by hard-coding the path but by summing the edge weights along whatever path it returns and checking they add up to the optimal cost -- a self-consistency check that catches a wrong parent link immediately:
const std = @import("std");
const Edge = struct { to: usize, weight: u32 };
const WeightedGraph = struct {
gpa: std.mem.Allocator,
adj: std.ArrayList(std.ArrayList(Edge)),
fn init(gpa: std.mem.Allocator, n: usize) !WeightedGraph {
var adj: std.ArrayList(std.ArrayList(Edge)) = .empty;
try adj.ensureTotalCapacity(gpa, n);
var i: usize = 0;
while (i < n) : (i += 1) adj.appendAssumeCapacity(.empty);
return .{ .gpa = gpa, .adj = adj };
}
fn deinit(self: *WeightedGraph) void {
for (self.adj.items) |*list| list.deinit(self.gpa);
self.adj.deinit(self.gpa);
}
fn addEdge(self: *WeightedGraph, from: usize, to: usize, weight: u32) !void {
try self.adj.items[from].append(self.gpa, .{ .to = to, .weight = weight });
try self.adj.items[to].append(self.gpa, .{ .to = from, .weight = weight });
}
fn neighbors(self: *const WeightedGraph, v: usize) []const Edge {
return self.adj.items[v].items;
}
};
const INF: u64 = std.math.maxInt(u64);
const Point = struct { x: f64, y: f64 };
fn heuristic(a: Point, b: Point) u64 {
const dx = a.x - b.x;
const dy = a.y - b.y;
return @intFromFloat(@floor(@sqrt(dx * dx + dy * dy)));
}
const AStarState = struct { f: u64, g: u64, vertex: usize };
fn aStarLess(_: void, a: AStarState, b: AStarState) std.math.Order {
return std.math.order(a.f, b.f);
}
fn astarPath(gpa: std.mem.Allocator, g: *const WeightedGraph, coords: []const Point, source: usize, target: usize) !?[]usize {
const n = g.adj.items.len;
const best = try gpa.alloc(u64, n);
defer gpa.free(best);
@memset(best, INF);
const parent = try gpa.alloc(i64, n);
defer gpa.free(parent);
@memset(parent, -1);
best[source] = 0;
var pq: std.PriorityQueue(AStarState, void, aStarLess) = .empty;
defer pq.deinit(gpa);
try pq.push(gpa, .{ .f = heuristic(coords[source], coords[target]), .g = 0, .vertex = source });
while (pq.pop()) |cur| {
if (cur.vertex == target) break; // first pop of target is optimal
if (cur.g > best[cur.vertex]) continue;
for (g.neighbors(cur.vertex)) |e| {
const ng = cur.g + e.weight;
if (ng < best[e.to]) {
best[e.to] = ng;
parent[e.to] = @intCast(cur.vertex);
const f = ng + heuristic(coords[e.to], coords[target]);
try pq.push(gpa, .{ .f = f, .g = ng, .vertex = e.to });
}
}
}
if (best[target] == INF) return null;
var path: std.ArrayList(usize) = .empty;
errdefer path.deinit(gpa);
var cur: i64 = @intCast(target);
while (cur != -1) : (cur = parent[@intCast(cur)]) {
try path.append(gpa, @intCast(cur));
}
std.mem.reverse(usize, path.items);
return try path.toOwnedSlice(gpa);
}
test "A* returns a path whose weights sum to the optimal cost" {
const gpa = std.testing.allocator;
const coords = [_]Point{
.{ .x = 0, .y = 0 },
.{ .x = 10, .y = 0 },
.{ .x = 20, .y = 0 },
.{ .x = 10, .y = 10 },
};
var g = try WeightedGraph.init(gpa, 4);
defer g.deinit();
try g.addEdge(0, 1, 10);
try g.addEdge(1, 2, 10);
try g.addEdge(0, 3, 15);
try g.addEdge(3, 2, 15);
const maybe = try astarPath(gpa, &g, &coords, 0, 2);
try std.testing.expect(maybe != null);
const path = maybe.?;
defer gpa.free(path);
var total: u64 = 0;
for (0..path.len - 1) |i| {
for (g.neighbors(path[i])) |e| {
if (e.to == path[i + 1]) {
total += e.weight;
break;
}
}
}
try std.testing.expectEqual(@as(u64, 20), total);
try std.testing.expectEqual(@as(usize, 0), path[0]);
try std.testing.expectEqual(@as(usize, 2), path[path.len - 1]);
}
Keep that WeightedGraph handy -- the next two solutions lean on the same shape.
Exercise 2 -- reject negative weights loudly. I warned you Dijkstra produces silent nonsense on negative edges, because the "once popped, a vertex is finalised" argument collapses the moment a later negative detour can lower a locked-in distance. The professional move is not to hope callers behave -- it is to make the precondition enforceable. So we switch Edge.weight to a signed i64, and at the very top of the function we scan every edge and bail with a real error.NegativeWeight before we compute a single distance. An algorithm's preconditions belong in the type system and the error set, not in a comment nobody reads:
const std = @import("std");
const Edge = struct { to: usize, weight: i64 };
const WeightedGraph = struct {
gpa: std.mem.Allocator,
adj: std.ArrayList(std.ArrayList(Edge)),
fn init(gpa: std.mem.Allocator, n: usize) !WeightedGraph {
var adj: std.ArrayList(std.ArrayList(Edge)) = .empty;
try adj.ensureTotalCapacity(gpa, n);
var i: usize = 0;
while (i < n) : (i += 1) adj.appendAssumeCapacity(.empty);
return .{ .gpa = gpa, .adj = adj };
}
fn deinit(self: *WeightedGraph) void {
for (self.adj.items) |*list| list.deinit(self.gpa);
self.adj.deinit(self.gpa);
}
fn addEdge(self: *WeightedGraph, from: usize, to: usize, weight: i64) !void {
try self.adj.items[from].append(self.gpa, .{ .to = to, .weight = weight });
try self.adj.items[to].append(self.gpa, .{ .to = from, .weight = weight });
}
fn neighbors(self: *const WeightedGraph, v: usize) []const Edge {
return self.adj.items[v].items;
}
};
const INF: u64 = std.math.maxInt(u64);
const State = struct { dist: u64, vertex: usize };
fn stateLess(_: void, a: State, b: State) std.math.Order {
return std.math.order(a.dist, b.dist);
}
const DijkstraError = error{ NegativeWeight, OutOfMemory };
fn dijkstraChecked(gpa: std.mem.Allocator, g: *const WeightedGraph, source: usize) DijkstraError![]u64 {
const n = g.adj.items.len;
for (0..n) |u| {
for (g.neighbors(u)) |e| {
if (e.weight < 0) return error.NegativeWeight;
}
}
const dist = try gpa.alloc(u64, n);
errdefer gpa.free(dist);
@memset(dist, INF);
dist[source] = 0;
var pq: std.PriorityQueue(State, void, stateLess) = .empty;
defer pq.deinit(gpa);
try pq.push(gpa, .{ .dist = 0, .vertex = source });
while (pq.pop()) |cur| {
if (cur.dist > dist[cur.vertex]) continue;
for (g.neighbors(cur.vertex)) |e| {
const nd = cur.dist + @as(u64, @intCast(e.weight));
if (nd < dist[e.to]) {
dist[e.to] = nd;
try pq.push(gpa, .{ .dist = nd, .vertex = e.to });
}
}
}
return dist;
}
test "dijkstra rejects a graph containing a negative edge" {
const gpa = std.testing.allocator;
var g = try WeightedGraph.init(gpa, 3);
defer g.deinit();
try g.addEdge(0, 1, 4);
try g.addEdge(1, 2, -2);
try std.testing.expectError(error.NegativeWeight, dijkstraChecked(gpa, &g, 0));
}
test "dijkstra still works when all weights are non-negative" {
const gpa = std.testing.allocator;
var g = try WeightedGraph.init(gpa, 3);
defer g.deinit();
try g.addEdge(0, 1, 4);
try g.addEdge(1, 2, 2);
const dist = try dijkstraChecked(gpa, &g, 0);
defer gpa.free(dist);
try std.testing.expectEqual(@as(u64, 6), dist[2]);
}
The @intCast(e.weight) from i64 to u64 is safe precisely because the scan already guaranteed no weight is negative -- the guard and the cast are two halves of one contract. That is Zig making you prove the thing before you rely on it.
Exercise 3 -- count the vertices each algorithm expands. The whole reason A* exists is that it touches fewer vertices than Dijkstra to reach the same answer, and there is no better way to feel that than to count. I thread an expanded counter through both, incremented once per non-stale pop, and return it in a little Counted struct next to the cost. Then I build a grid, put source and target at opposite corners, and assert two things: same optimal cost, and A* expands no more than Dijkstra:
const std = @import("std");
const Edge = struct { to: usize, weight: u32 };
const WeightedGraph = struct {
gpa: std.mem.Allocator,
adj: std.ArrayList(std.ArrayList(Edge)),
fn init(gpa: std.mem.Allocator, n: usize) !WeightedGraph {
var adj: std.ArrayList(std.ArrayList(Edge)) = .empty;
try adj.ensureTotalCapacity(gpa, n);
var i: usize = 0;
while (i < n) : (i += 1) adj.appendAssumeCapacity(.empty);
return .{ .gpa = gpa, .adj = adj };
}
fn deinit(self: *WeightedGraph) void {
for (self.adj.items) |*list| list.deinit(self.gpa);
self.adj.deinit(self.gpa);
}
fn addEdge(self: *WeightedGraph, from: usize, to: usize, weight: u32) !void {
try self.adj.items[from].append(self.gpa, .{ .to = to, .weight = weight });
try self.adj.items[to].append(self.gpa, .{ .to = from, .weight = weight });
}
fn neighbors(self: *const WeightedGraph, v: usize) []const Edge {
return self.adj.items[v].items;
}
};
const INF: u64 = std.math.maxInt(u64);
const Point = struct { x: f64, y: f64 };
fn heuristic(a: Point, b: Point) u64 {
const dx = a.x - b.x;
const dy = a.y - b.y;
return @intFromFloat(@floor(@sqrt(dx * dx + dy * dy)));
}
const State = struct { dist: u64, vertex: usize };
fn stateLess(_: void, a: State, b: State) std.math.Order {
return std.math.order(a.dist, b.dist);
}
const AStarState = struct { f: u64, g: u64, vertex: usize };
fn aStarLess(_: void, a: AStarState, b: AStarState) std.math.Order {
return std.math.order(a.f, b.f);
}
const Counted = struct { cost: ?u64, expanded: usize };
fn dijkstraCounted(gpa: std.mem.Allocator, g: *const WeightedGraph, source: usize, target: usize) !Counted {
const n = g.adj.items.len;
const dist = try gpa.alloc(u64, n);
defer gpa.free(dist);
@memset(dist, INF);
dist[source] = 0;
var pq: std.PriorityQueue(State, void, stateLess) = .empty;
defer pq.deinit(gpa);
try pq.push(gpa, .{ .dist = 0, .vertex = source });
var expanded: usize = 0;
while (pq.pop()) |cur| {
if (cur.dist > dist[cur.vertex]) continue;
expanded += 1;
if (cur.vertex == target) return .{ .cost = cur.dist, .expanded = expanded };
for (g.neighbors(cur.vertex)) |e| {
const nd = cur.dist + e.weight;
if (nd < dist[e.to]) {
dist[e.to] = nd;
try pq.push(gpa, .{ .dist = nd, .vertex = e.to });
}
}
}
return .{ .cost = null, .expanded = expanded };
}
fn astarCounted(gpa: std.mem.Allocator, g: *const WeightedGraph, coords: []const Point, source: usize, target: usize) !Counted {
const n = g.adj.items.len;
const best = try gpa.alloc(u64, n);
defer gpa.free(best);
@memset(best, INF);
best[source] = 0;
var pq: std.PriorityQueue(AStarState, void, aStarLess) = .empty;
defer pq.deinit(gpa);
try pq.push(gpa, .{ .f = heuristic(coords[source], coords[target]), .g = 0, .vertex = source });
var expanded: usize = 0;
while (pq.pop()) |cur| {
if (cur.g > best[cur.vertex]) continue;
expanded += 1;
if (cur.vertex == target) return .{ .cost = cur.g, .expanded = expanded };
for (g.neighbors(cur.vertex)) |e| {
const ng = cur.g + e.weight;
if (ng < best[e.to]) {
best[e.to] = ng;
const f = ng + heuristic(coords[e.to], coords[target]);
try pq.push(gpa, .{ .f = f, .g = ng, .vertex = e.to });
}
}
}
return .{ .cost = null, .expanded = expanded };
}
test "on a grid, A* expands no more vertices than Dijkstra" {
const gpa = std.testing.allocator;
const W = 8;
const n = W * W;
var g = try WeightedGraph.init(gpa, n);
defer g.deinit();
const coords = try gpa.alloc(Point, n);
defer gpa.free(coords);
for (0..W) |r| {
for (0..W) |c| {
const id = r * W + c;
coords[id] = .{ .x = @floatFromInt(c), .y = @floatFromInt(r) };
if (c + 1 < W) try g.addEdge(id, id + 1, 1);
if (r + 1 < W) try g.addEdge(id, id + W, 1);
}
}
const dj = try dijkstraCounted(gpa, &g, 0, n - 1);
const as = try astarCounted(gpa, &g, coords, 0, n - 1);
try std.testing.expectEqual(dj.cost, as.cost); // identical optimal cost
try std.testing.expect(as.expanded <= dj.expanded); // A* never explores more
}
Debt paid ;-) That as.expanded <= dj.expanded is the whole moral of A* compressed into one assertion. Now -- ordering.
Forget the intimidating name for a second. Imagine a directed graph where an edge u -> v means "u must come before v". A topological sort (or topological order, or topo order for short) is any arrangement of all the vertices in a single line such that every arrow points forward -- no edge ever points backward from a later vertex to an earlier one. That's it. That's the entire definition. If you can lay the vertices out left to right so all arrows point rightward, that layout is a topological sort.
Two things follow immediately, and both matter. First: a topological order only exists if the graph has no cycles. If a must come before b, b before c, and c before a, there is no line you can draw -- somebody always ends up behind someone they were supposed to precede. A directed graph with no cycles has a special name, a DAG (directed acyclic graph), and "topological sort exists" and "the graph is a DAG" are literally the same statement. Second: the order is usually not unique. If two tasks have no dependency between them, either can go first. Building a project you might compile module A then B, or B then A, and both are perfectly valid -- the topo sort only constrains what it must.
The classic mental picture is getting dressed. Socks before shoes, underwear before trousers, shirt before jacket -- but socks and shirt have no relation, so you can do them in either order. A topological sort is any valid dressing sequence. Ask a compiler to order its translation units, ask apt or cargo to order package installs, ask a spreadsheet to order cell recalculation, ask a Makefile to order its targets -- all of them are computing a topological sort of a dependency DAG, whether they call it that or not.
We are back on the plain directed unweighted graph from episode 118 -- topo sort does not care about weights, only about who-points-to-whom. This is the same index-based, allocator-honest adjacency list we have used the entire graph arc, and for topo sort we will always construct it with directed = true:
const std = @import("std");
const Graph = struct {
gpa: std.mem.Allocator,
adj: std.ArrayList(std.ArrayList(usize)),
directed: bool,
fn init(gpa: std.mem.Allocator, n: usize, directed: bool) !Graph {
var adj: std.ArrayList(std.ArrayList(usize)) = .empty;
try adj.ensureTotalCapacity(gpa, n);
var i: usize = 0;
while (i < n) : (i += 1) adj.appendAssumeCapacity(.empty);
return .{ .gpa = gpa, .adj = adj, .directed = directed };
}
fn deinit(self: *Graph) void {
for (self.adj.items) |*list| list.deinit(self.gpa);
self.adj.deinit(self.gpa);
}
fn addEdge(self: *Graph, from: usize, to: usize) !void {
try self.adj.items[from].append(self.gpa, to);
if (!self.directed) try self.adj.items[to].append(self.gpa, from);
}
fn neighbors(self: *const Graph, v: usize) []const usize {
return self.adj.items[v].items;
}
};
Nothing new here -- if you did episode 119's exercises this type is muscle memory by now. An edge addEdge(u, v) on a directed graph reads as "u must precede v". Onwards to the first of two classic algorithms.
The first approach, published by Arthur Kahn in 1962, is beautifully intuitive and it is really just BFS in disguise. The key concept is in-degree: the number of edges pointing into a vertex, i.e. the number of prerequisites it is still waiting on. A vertex with in-degree zero has nothing blocking it -- it can go right now. So the algorithm is: compute everyone's in-degree, drop all the zero-in-degree vertices into a queue, and then repeatedly pull one out, emit it, and "remove" it from the graph by decrementing the in-degree of each of its neighbours. Any neighbour whose in-degree just hit zero has had its last prerequisite satisfied, so it joins the queue. Peel, decrement, repeat -- like pulling the outer layer off an onion until nothing is left.
fn topoSortKahn(gpa: std.mem.Allocator, g: *const Graph) !?[]usize {
const n = g.adj.items.len;
const indeg = try gpa.alloc(usize, n);
defer gpa.free(indeg);
@memset(indeg, 0);
for (0..n) |u| {
for (g.neighbors(u)) |v| indeg[v] += 1;
}
var queue: std.ArrayList(usize) = .empty;
defer queue.deinit(gpa);
for (0..n) |v| {
if (indeg[v] == 0) try queue.append(gpa, v);
}
var order: std.ArrayList(usize) = .empty;
errdefer order.deinit(gpa);
var head: usize = 0;
while (head < queue.items.len) {
const u = queue.items[head];
head += 1;
try order.append(gpa, u);
for (g.neighbors(u)) |v| {
indeg[v] -= 1;
if (indeg[v] == 0) try queue.append(gpa, v);
}
}
if (order.items.len != n) {
order.deinit(gpa);
return null; // fewer than n emitted -> a cycle swallowed the rest
}
return try order.toOwnedSlice(gpa);
}
The head index marching through queue.items is the same FIFO-without-shifting trick we used for BFS last arc -- no dequeue-from-front cost, we just remember where we are. But look at the last four lines, because they hide the cleverest thing about Kahn's algorithm: it detects cycles for free. If the graph has a cycle, the vertices caught in that cycle each perpetually wait on another cycle member, so their in-degree never reaches zero, so they never enter the queue, so they never get emitted. We emitted fewer than n vertices -- and that shortfall is the cycle detector. No separate pass, no extra colouring, just a count. When that happens we return null: "no topological order exists". A very Zig way to say it would be an optional slice, where null cleanly means "there is nothing valid to return".
The second classic method comes from a completely different direction and yet lands on the same answer -- which is one of those quietly satisfying facts about this problem. Run a depth-first search, and the moment a vertex is fully finished (all its descendants explored), push it onto a list. When the DFS completes, reverse that list. That reversed finish-order is a valid topological sort. Why? Because a vertex only finishes after every vertex it can reach has already finished -- so in finish-order, things you depend on finish before you, and reversing flips that into "you before the things that depend on you".
And here is where last episode's promise gets cashed. To do this iteratively (no recursion, no stack-overflow risk on a deep graph) and to detect cycles at the same time, we use the exact three-colour scheme from the ep120 directed-cycle exercise: white = untouched, gray = on the path we are currently exploring, black = fully finished. Following an edge into a gray vertex means we looped back onto our own active path -- a cycle -- and topo sort is impossible, so we bail with error.Cycle. This time I return a real error rather than null, just to show both idioms; either is honest:
const TopoError = error{ Cycle, OutOfMemory };
fn topoSortDfs(gpa: std.mem.Allocator, g: *const Graph) TopoError![]usize {
const n = g.adj.items.len;
const Color = enum(u8) { white, gray, black };
const color = try gpa.alloc(Color, n);
defer gpa.free(color);
@memset(color, .white);
var order: std.ArrayList(usize) = .empty;
errdefer order.deinit(gpa);
const Frame = struct { v: usize, idx: usize };
var stack: std.ArrayList(Frame) = .empty;
defer stack.deinit(gpa);
for (0..n) |start| {
if (color[start] != .white) continue;
try stack.append(gpa, .{ .v = start, .idx = 0 });
color[start] = .gray;
while (stack.items.len > 0) {
const top = &stack.items[stack.items.len - 1];
const nbs = g.neighbors(top.v);
if (top.idx < nbs.len) {
const w = nbs[top.idx];
top.idx += 1;
switch (color[w]) {
.gray => return error.Cycle, // back-edge onto the active path
.white => {
color[w] = .gray;
try stack.append(gpa, .{ .v = w, .idx = 0 });
},
.black => {}, // already finished, nothing to do
}
} else {
color[top.v] = .black; // children exhausted -> finished
try order.append(gpa, top.v);
stack.items.len -= 1;
}
}
}
std.mem.reverse(usize, order.items);
return try order.toOwnedSlice(gpa);
}
The Frame struct carrying a per-vertex idx is what lets us do a recursive algorithm iteratively -- idx remembers which neighbour we visit next, and when idx runs off the end of the neighbour list, the vertex's children are exhausted, so we paint it black, record it as finished, and pop the frame. The errdefer order.deinit(gpa) matters here: on the return error.Cycle path the partially-built order list must be freed, and errdefer fires exactly on error returns -- no leak, even on the failure path. That gray/black machinery I made you carry over from last episode was not busywork; it is the literal engine of two different algorithms.
A topological order has exactly one defining property: for every edge u -> v, u appears before v in the output. Everything else is freedom. So the perfect validator does not check the order against some "expected" answer (there are usually many valid answers!) -- it checks that one rule directly. Record each vertex's position in the output, then confirm every edge points forward:
fn isValidTopoOrder(gpa: std.mem.Allocator, g: *const Graph, order: []const usize) !bool {
const n = g.adj.items.len;
if (order.len != n) return false;
const pos = try gpa.alloc(usize, n);
defer gpa.free(pos);
for (order, 0..) |v, i| pos[v] = i;
for (0..n) |u| {
for (g.neighbors(u)) |v| {
if (pos[u] >= pos[v]) return false; // u must sit strictly before v
}
}
return true;
}
test "a real build order: dependencies come before dependents" {
const gpa = std.testing.allocator;
// 0 = libc, 1 = libm (needs libc), 2 = app (needs libm + libc), 3 = tests (needs app)
var g = try Graph.init(gpa, 4, true);
defer g.deinit();
try g.addEdge(0, 1); // libc -> libm
try g.addEdge(0, 2); // libc -> app
try g.addEdge(1, 2); // libm -> app
try g.addEdge(2, 3); // app -> tests
const order = try topoSortDfs(gpa, &g);
defer gpa.free(order);
try std.testing.expect(try isValidTopoOrder(gpa, &g, order));
try std.testing.expectEqual(@as(usize, 0), order[0]); // libc must be first
try std.testing.expectEqual(@as(usize, 3), order[order.len - 1]); // tests must be last
}
That little four-node graph is a real build dependency in miniature: a C runtime, a math library that needs it, an app that needs both, and a test binary that needs the app. libc has nothing before it (in-degree zero) so it lands first; tests has nothing after it so it lands last; and the middle two can only sit in the one order their dependencies allow. This is exactly what a build system does before it hands work to the compiler.
Hand-built tests are good, but we learned a sharper discipline in this arc: generate hundreds of random inputs and assert a property that must hold for all of them. The trick for generating a random DAG (which we need, since only DAGs have topo orders) is delightfully cheap -- only ever add edges from a lower-numbered vertex to a higher-numbered one. Such a graph cannot contain a cycle, because every edge increases the vertex index and you can never get back down. Then we run both algorithms and assert both outputs are valid topological orders -- each algorithm quietly acting as a cross-check on the other:
test "property: kahn and dfs both produce valid topological orders on random DAGs" {
const gpa = std.testing.allocator;
var prng = std.Random.DefaultPrng.init(0xDA6);
const rand = prng.random();
var round: usize = 0;
while (round < 200) : (round += 1) {
const n = rand.intRangeAtMost(usize, 1, 20);
var g = try Graph.init(gpa, n, true);
defer g.deinit();
const m = rand.intRangeAtMost(usize, 0, 40);
for (0..m) |_| {
const a = rand.uintLessThan(usize, n);
const b = rand.uintLessThan(usize, n);
if (a < b) try g.addEdge(a, b); // forward-only edges -> guaranteed DAG
}
const k = (try topoSortKahn(gpa, &g)).?;
defer gpa.free(k);
const d = try topoSortDfs(gpa, &g);
defer gpa.free(d);
try std.testing.expect(try isValidTopoOrder(gpa, &g, k));
try std.testing.expect(try isValidTopoOrder(gpa, &g, d));
}
}
Two hundred random DAGs, and both algorithms produce a valid order every single time -- often two different valid orders for the same graph, which is precisely the point about non-uniqueness. Because it all runs on std.testing.allocator, any leaked order list or neighbour buffer fails the round too. This "two implementations, one property" setup is one of my favourite testing shapes: if I had introduced a subtle bug in only one of them, the mismatch would surface here, and the property tells me which invariant broke rather than just "the numbers differ".
Non-uniqueness is mathematically fine but operationally annoying -- a build system that emits its tasks in a different order every run is a debugging nightmare and wrecks reproducible builds. The fix is to break ties deterministically. Take Kahn's algorithm, and where it used a plain FIFO queue of ready vertices, swap in a min-priority-queue (the very std.PriorityQueue we met last episode). Now, among all vertices that are currently ready, we always emit the smallest id first. The result is the unique lexicographically smallest topological order -- same algorithm, one data-structure swap:
fn usizeLess(_: void, a: usize, b: usize) std.math.Order {
return std.math.order(a, b);
}
fn topoSortLexicographic(gpa: std.mem.Allocator, g: *const Graph) !?[]usize {
const n = g.adj.items.len;
const indeg = try gpa.alloc(usize, n);
defer gpa.free(indeg);
@memset(indeg, 0);
for (0..n) |u| {
for (g.neighbors(u)) |v| indeg[v] += 1;
}
var pq: std.PriorityQueue(usize, void, usizeLess) = .empty;
defer pq.deinit(gpa);
for (0..n) |v| {
if (indeg[v] == 0) try pq.push(gpa, v);
}
var order: std.ArrayList(usize) = .empty;
errdefer order.deinit(gpa);
while (pq.pop()) |u| {
try order.append(gpa, u);
for (g.neighbors(u)) |v| {
indeg[v] -= 1;
if (indeg[v] == 0) try pq.push(gpa, v);
}
}
if (order.items.len != n) {
order.deinit(gpa);
return null;
}
return try order.toOwnedSlice(gpa);
}
test "lexicographic topo sort emits the smallest ready id first" {
const gpa = std.testing.allocator;
var g = try Graph.init(gpa, 4, true);
defer g.deinit();
// 2 must come before 0 and before 1; 3 is free
try g.addEdge(2, 0);
try g.addEdge(2, 1);
const order = (try topoSortLexicographic(gpa, &g)).?;
defer gpa.free(order);
try std.testing.expect(try isValidTopoOrder(gpa, &g, order));
try std.testing.expectEqual(@as(usize, 2), order[0]); // only 2 and 3 start ready; 2 < 3
try std.testing.expectEqual(@as(usize, 3), order[order.len - 1]);
}
Notice the cost changed: plain Kahn is O(V + E), but the heap makes the lexicographic variant O(V + E log V) -- the log V is the price of that deterministic tie-break. Whether it is worth paying is a real engineering judgement: reproducible-build tooling absolutely wants it, a one-shot dependency resolver probably does not. What I love is how small the diff is -- one queue becomes one priority queue and the algorithm's shape is otherwise untouched. That is the payoff of understanding the mechanism in stead of memorising a recipe.
I want to dwell on cycle handling for a moment, because beginners treat it as an annoying edge case and experts treat it as the point. When your build tool says "circular dependency detected: A needs B needs C needs A", that message is the topological sort failing on purpose and telling you something true about your project. Both our implementations catch it, by two different mechanisms worth contrasting -- Kahn's by the emitted-count shortfall, DFS's by the gray back-edge:
test "both algorithms reject a cyclic graph" {
const gpa = std.testing.allocator;
var g = try Graph.init(gpa, 3, true);
defer g.deinit();
try g.addEdge(0, 1);
try g.addEdge(1, 2);
try g.addEdge(2, 0); // 0 -> 1 -> 2 -> 0, a cycle
// Kahn: signals impossibility with null
try std.testing.expect((try topoSortKahn(gpa, &g)) == null);
// DFS: signals impossibility with a real error
try std.testing.expectError(error.Cycle, topoSortDfs(gpa, &g));
}
Which style you prefer is a genuine API design choice. ?[]usize is lighter and composes nicely with Zig's orelse, but it throws away why it failed. error.Cycle carries intent and rides the normal try machinery, and in a real tool you would probably want to go further and return which vertices form the cycle so you can print a useful message -- the gray-vertex stack at the moment of detection literally is that cycle, waiting to be read off. That is a natural extension, and, well, it is one of today's exercises ;-)
In C, you bring your own everything. In-degrees live in a malloc'd int array, the ready set is usually a hand-rolled stack or a fixed ring buffer, and the DFS variant is often written recursively -- which is fine until a pathological input blows the call stack, at which point you rewrite it iteratively with an explicit stack, exactly as we did here from the start. There is no testing.allocator watching your back, so the forgotten free on the cycle-detected early return is a classic leak. The algorithm is identical; the bookkeeping is all yours.
In Rust, the petgraph crate ships toposort out of the box, returning a Result whose Err variant hands you a vertex involved in a cycle -- notice that is the error.Cycle-plus-payload design I just called the "real tool" version. Roll your own and you would use a VecDeque for Kahn's queue and a Vec<u8> or an enum for the colours; Rust's Option<Vec<usize>> is the precise twin of our ?[]usize, and the borrow checker steers you toward the same index-based graph we have used all series, because holding references into the adjacency list while mutating the queue is the aliasing it forbids.
In Go, the standard library has no graph type, so you write the adjacency list as a map[int][]int or [][]int, the queue as a slice you append to and reslice, and the garbage collector spares you the defer deinit entirely. container/heap gives you the priority queue for the lexicographic variant, at the cost of that famously verbose five-method interface. And because this is Go, someone will suggest running independent branches of the DFS on separate goroutines -- which, as with parallel BFS two episodes back, is real work for surprisingly little payoff below enormous graph sizes. Four languages, one algorithm, and the DAG-or-nothing precondition is the same load-bearing truth in every one of them. Bam, jonguh ;-)
Report the actual cycle, not just its existence. Extend topoSortDfs so that on detecting a back-edge into a gray vertex, it returns the list of vertices forming the cycle in stead of a bare error.Cycle. The vertices currently on the stack, from the gray target up to the top, are the cycle -- read them off before you return. Test it on 0 -> 1 -> 2 -> 0 and confirm you get {0, 1, 2} in some rotation.
All topological orders of a small DAG. Write a function that returns every valid topological order (not just one) by backtracking: at each step, try each currently-ready vertex, recurse, then undo. On the "getting dressed" graph this shows you concretely how many valid sequences exist. Warning: the count explodes with graph size, so cap it at, say, 8 vertices and enjoy watching the combinatorics bite.
Longest dependency chain. On a DAG, the longest path (the "critical path" in project scheduling) can be found in O(V + E) by processing vertices in topological order and relaxing longest[v] = max(longest[v], longest[u] + 1) for each edge u -> v. Implement it on top of topoSortKahn, and test that on the libc/libm/app/tests build graph the longest chain has length 4 (libc -> libm -> app -> tests).
We can now flatten any dependency DAG into a runnable order two different ways, break ties deterministically, and catch impossible cycles honestly -- a genuinely load-bearing tool that sits under compilers, package managers, schedulers and spreadsheets. But notice the assumption we leaned on the whole time: we knew the edges up front and asked our ordering question once. Real systems are messier. Edges arrive one at a time as a graph is built, and the question you ask over and over is not "what is the full order" but something far more primitive: are these two things connected yet -- are they already in the same group? You might ask that millions of times while a structure grows, far too often to re-run a full traversal for each query. There is a data structure for exactly that, so small you could write it on a napkin and so fast its running time is, for all practical purposes, a flat constant per operation. It feels like cheating the first time you meet it, and it is where we go next ;-)
Bedankt voor het lezen, en tot de volgende keer!
@scipio