Topological order

Eight tasks for a cup of tea, and the arrows between them. Watch the tasks with nothing left before them leave, one at a time, in a working order.

⋯34int kahn(int *order)35{36    int indeg[V] = { 0 };37    for (int u = 0; u < V; u++)38        for (const struct enode *e = out[u]; e != NULL; e = e->next)39            indeg[e->to]++;40    int queue[V];41    int head = 0, tail = 0;42    for (int u = 0; u < V; u++)43        if (indeg[u] == 0)44            queue[tail++] = u;45    int n = 0;46    while (head < tail) {47        int u = queue[head++];48        order[n++] = u;49        for (const struct enode *e = out[u]; e != NULL; e = e->next) {50            indeg[e->to]--;51            if (indeg[e->to] == 0)52                queue[tail++] = e->to;53        }54    }55    return n;56}⋯79    int order[V];80    int n = kahn(order);81    printf("Kahn:");82    for (int i = 0; i < n; i++)83        printf(" %s", name[order[i]]);84    if (n < V)85        printf(" (stopped after %d of %d: a cycle)", n, V);86    printf("\n");87    for (int u = 0; u < V; u++)

Tasks that wait on other tasks

Some jobs must be done in a certain order: the kettle is filled before it boils, and the tea is poured before it steeps. Draw each task as a vertex and each “must come before” as an arrow, an arc, from the earlier task to the later one. The graph is now directed: an arc goes one way only.

A topological order lists every task after all the tasks that point to it. For the tea, one such order is the one in the picture. It exists only when the arcs never lead in a circle back to where they started: the graph must be a directed acyclic graph, a DAG.

The code and its cost

The graph

tea.c stores the arcs as adjacency lists, as in storing a graph, but each arc only once, in the list of the task it leaves. out[u] is the list of tasks that wait on u.

const int arcs[7][2] = { { 0, 1 }, { 1, 4 }, { 2, 3 }, { 3, 4 }, { 4, 5 }, { 5, 7 }, { 6, 7 } };

Kahn’s method

A task can go next as soon as nothing still points into it. kahn counts, for every task, the arcs pointing into it, its in-degree:

int indeg[V] = { 0 };
for (int u = 0; u < V; u++)
    for (const struct enode *e = out[u]; e != NULL; e = e->next)
        indeg[e->to]++;

The counts are 0 1 0 1 2 1 0 2, for tasks 0 to 7. The tasks with no arc into them, fill-kettle, get-cup and get-milk, go into a queue, as in queues. Then the loop takes the task at the head, writes it into the order, and removes its arcs by lowering the count at the far end of each; a task whose count reaches 0 joins the queue at the tail:

while (head < tail) {
    int u = queue[head++];
    order[n++] = u;
    for (const struct enode *e = out[u]; e != NULL; e = e->next) {
        indeg[e->to]--;
        if (indeg[e->to] == 0)
            queue[tail++] = e->to;
    }
}
return n;

Taking fill-kettle frees boil. Taking get-cup frees add-bag. Taking get-milk lowers add-milk only to 1, because steep still points into it. The order comes out as fill-kettle, get-cup, get-milk, boil, add-bag, pour, steep, add-milk.

The cost

Counting walks every list once. Each task enters the queue once, when its count reaches 0, and each arc is removed once, when its task leaves. With V tasks and E arcs that is O(V + E).

Many right answers

At most moments in the clip, more than one task is free: at the start, all of fill-kettle, get-cup and get-milk. The queue takes them first come, first served, but any free task would do. A different choice gives a different order, and every one of them is right. There is no single correct topological order unless the arcs force a single chain.

The DFS method

Depth-first search gives an order too. Run it on the arcs, from every task not yet started, and list the tasks in reverse order of finishing. dfs keeps three states per task, 0 not started, 1 in progress and 2 done:

static void dfs(int u)
{
    state[u] = 1;
    for (const struct enode *e = out[u]; e != NULL; e = e->next) {
        if (state[e->to] == 0)
            dfs(e->to);
        else if (state[e->to] == 1)
            cyclic = true;
    }
    state[u] = 2;
    fin_order[nfin++] = u;
}

From fill-kettle it goes to boil, pour, steep and add-milk, which finish in the order add-milk, steep, pour, boil, fill-kettle. From get-cup it goes to add-bag, whose arc reaches pour, already done; add-bag and get-cup finish. Last, get-milk finishes alone, since add-milk is done. Reversed:

Kahn: fill-kettle get-cup get-milk boil add-bag pour steep add-milk
DFS: get-milk get-cup add-bag fill-kettle boil pour steep add-milk

It works because a task finishes only after every task it points to has finished: each is either searched from it, or done already. So in reverse order of finishing, every task comes before everything that waits on it. Both lines are topological orders, and they differ.

When there is a cycle

Compiled with -DCYCLE=1, main adds one more arc, add-milk to fill-kettle: the milk must now go in before the kettle is filled, which no order can satisfy.

Kahn: get-cup get-milk add-bag (stopped after 3 of 8: a cycle)
DFS: a cycle

Neither method loops for ever. Kahn’s method stops short: fill-kettle now waits on add-milk, so it is never free, and nothing after it is freed either. The queue empties after three tasks, and kahn returns 3, fewer than 8. The DFS method meets a task still in progress: from fill-kettle it goes five calls deep, to boil, pour, steep and add-milk, and the arc from add-milk leads back to fill-kettle, whose call has not returned. An arc to a task in progress goes back along the current path, so it closes a cycle. An arc to a task that is done, such as add-bag’s arc to pour, does not.

Running it yourself

gcc -std=c11 -Wall -Wextra -pedantic tea.c -o tea
./tea
gcc -std=c11 -Wall -Wextra -pedantic -DCYCLE=1 tea.c -o tea-cycle
./tea-cycle

Worked example

Check the DFS order arc by arc. In get-milk get-cup add-bag fill-kettle boil pour steep add-milk the tasks stand at places 1 to 8. Each arc must go from an earlier place to a later one: fill-kettle (4) to boil (5), boil (5) to pour (6), get-cup (2) to add-bag (3), add-bag (3) to pour (6), pour (6) to steep (7), steep (7) to add-milk (8), get-milk (1) to add-milk (8). All seven do.

Why the cycle variant stops after three. Once get-cup, get-milk and add-bag have left, every remaining task still waits on another: fill-kettle on add-milk, boil on fill-kettle, pour on boil, steep on pour and add-milk on steep. Those five arcs form the cycle fill-kettle, boil, pour, steep, add-milk and back to fill-kettle.

No arcs at all. Five tasks with no arcs between them can go in any order: 5! = 5 · 4 · 3 · 2 · 1 = 120 topological orders.

Two checks. Which tasks are free at the start? (fill-kettle, get-cup and get-milk: nothing points into them.) Must pour come after get-milk? (No: no chain of arcs leads from get-milk to pour. It comes earlier in both printed orders by choice, not by rule.)

Where it’s used

Build tools. A program’s files are compiled after the files they depend on, and a dependency that loops back on itself is reported.

Spreadsheets. When a cell changes, the cells that refer to it are recalculated after it, in an order that respects every reference; a formula that refers back to itself is a circular reference.

Package installers. A package is installed after the packages it needs.

Prerequisites. Planning a course of study in which some subjects must come before others.

Reference card

Platform: C11, gcc on x86-64 Linux: int 4 bytes, pointers 8, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.