← Data structures from scratch · Lesson 27/32

What comes first: topological order

1/8

Dependencies as arrows

A made-up study plan: Programming I (P1) before Programming II (P2); P2 before Data Structures (ED); ED and Discrete Math (MD) before Algorithms (AL); and AL before Compilers (CO). Each "before" is an arrow.

A topological order is a line-up of all the vertices where every arrow points forward: nothing shows up before something it depends on. It only exists if the graph is directed and acyclic, a DAG (directed acyclic graph). If A needs B and B needs A, there's nowhere to start.

And it's rarely unique: MD can go first or right before AL.

leccion.js

1const requisitos = [["P1", "P2"], ["P2", "ED"], ["ED", "AL"], ["MD", "AL"], ["AL", "CO"]];
2
3function esValido(orden) {
4  const pos = {};
5  orden.forEach((m, i) => { pos[m] = i; });
6  // every "before -> after" arrow has to point forward
7  return requisitos.every(([antes, despues]) => pos[antes] < pos[despues]);
8}
9
10console.log(esValido(["P1", "MD", "P2", "ED", "AL", "CO"]));
11console.log(esValido(["MD", "P1", "P2", "ED", "AL", "CO"]));
12console.log(esValido(["P1", "P2", "AL", "ED", "MD", "CO"]));

$ node leccion.js

Press RUN (or Ctrl+Enter).

What to look at

The first two orders are valid even though they differ: MD can go in several places.
The third isn't: it puts Algorithms before Data Structures and Discrete Math.

The whole lesson on one page

Dependencies as arrows

And it's rarely unique: MD can go first or right before AL.

1const requisitos = [["P1", "P2"], ["P2", "ED"], ["ED", "AL"], ["MD", "AL"], ["AL", "CO"]];
2
3function esValido(orden) {
4  const pos = {};
5  orden.forEach((m, i) => { pos[m] = i; });
6  // every "before -> after" arrow has to point forward
7  return requisitos.every(([antes, despues]) => pos[antes] < pos[despues]);
8}
9
10console.log(esValido(["P1", "MD", "P2", "ED", "AL", "CO"]));
11console.log(esValido(["MD", "P1", "P2", "ED", "AL", "CO"]));
12console.log(esValido(["P1", "P2", "AL", "ED", "MD", "CO"]));

The first two orders are valid even though they differ: MD can go in several places.
The third isn't: it puts Algorithms before Data Structures and Discrete Math.

Kahn's algorithm

The clearest way to build it is to count each vertex's in-degree: how many arrows point at it, that is, how many things it's still waiting for.

The ones with degree 0 depend on nothing: they go into a queue.
Take one out, add it to the order and subtract 1 from each vertex it points to (that requirement is now met).
Whoever reaches 0 joins the queue.

If at the end the order has fewer vertices than the graph, the missing ones are stuck in a cycle: they never reached 0. It costs O(V + E).

1const grafo = {
2  P1: ["P2"],
3  P2: ["ED"],
4  ED: ["AL"],
5  MD: ["AL"],
6  AL: ["CO"],
7  CO: [],
8};
9
10function kahn(grafo) {
11  const grado = {};
12  for (const v in grafo) grado[v] = 0;
13  for (const v in grafo) for (const w of grafo[v]) grado[w]++;
14  console.log("in-degrees:", grado);
15
16  const cola = Object.keys(grafo).filter((v) => grado[v] === 0);
17  const orden = [];
18  let cabeza = 0;
19  while (cabeza < cola.length) {
20    const v = cola[cabeza++];
21    orden.push(v);
22    for (const w of grafo[v]) {
23      grado[w]--;                      // one requirement fewer
24      if (grado[w] === 0) cola.push(w);
25    }
26  }
27  // if vertices are missing, they got stuck in a cycle
28  return orden.length === Object.keys(grafo).length ? orden : null;
29}
30
31console.log(kahn(grafo));
32console.log(kahn({ A: ["B"], B: ["C"], C: ["A"] }));

P1 and MD start at degree 0; AL starts at 2 (it's waiting on ED and MD).
Out comes [P1, MD, P2, ED, AL, CO]: AL only joins the queue once ED and MD are out.
In the triangle A → B → C → A nobody starts at 0: it returns null. (The degrees print twice because kahn is called twice.)

With DFS, and what it's for

Another way: a DFS that writes down each vertex when it finishes with everything that depends on it. That list, reversed, is a topological order. It gives a different but equally valid order (to detect cycles this way you need to tell "visiting" from "done", skipped here).

This shows up in more places than it seems: npm deciding what order to install packages in, make deciding what order to compile files in, a spreadsheet deciding what order to recalculate cells that depend on others, and a recipe deciding what order to do the steps in.

1const grafo = {
2  P1: ["P2"],
3  P2: ["ED"],
4  ED: ["AL"],
5  MD: ["AL"],
6  AL: ["CO"],
7  CO: [],
8};
9
10function topoDFS(grafo) {
11  const visto = new Set(), salida = [];
12  function visitar(v) {
13    if (visto.has(v)) return;
14    visto.add(v);
15    for (const w of grafo[v]) visitar(w);
16    salida.push(v);   // finishes after everything that depends on it
17  }
18  for (const v in grafo) visitar(v);
19  console.log("on finish:", salida);
20  return salida.reverse();
21}
22
23console.log(topoDFS(grafo));

On finish, CO comes out first (nothing depends on it) and P1 near the end.
Reversed it's [MD, P1, P2, ED, AL, CO]: different from Kahn's and also valid.