Skip to content
wannacode

Topological sorting

In short: Topological sorting orders tasks with dependencies so that each comes after its dependencies; Kahn's algorithm does it with a queue and detects a cycle if there is one.

Problem

Which one is built first

The online shop is split into seven modules. core is the shared code. db talks to the database and uses core. auth handles customer sign-in and uses core and db. catalog, cart, payments and web stand on top of them.

The build tool has to compile each module after everything it needs. If it builds cart before catalog, the compiler cannot find the catalog classes and stops.

The first solution is to write the order by hand in a script. It works until someone adds a new dependency and forgets the script. A large project has hundreds of modules.

And what if auth starts using something from web, which uses cart, which uses auth? Then each one waits for another, and the build is impossible. You want to know that at once, and to know which modules are to blame.

The idea

A dependency graph

The modules are the vertices of a directed graph (see representing a graph). We keep it as an adjacency list: for each module, what it needs.

const needs = new Map([
  ["core", []],
  ["db", ["core"]],
  ["auth", ["core", "db"]],
  ["catalog", ["db"]],
  ["cart", ["catalog", "auth"]],
  ["payments", ["auth"]],
  ["web", ["cart", "payments"]],
]);

An order in which every module comes after its dependencies is called a topological order, and finding one is topological sorting. It exists only if the graph has no cycle.

How do you find it? A module with no dependencies can be built right away. Once it is built, the modules that use it have one dependency less to wait for. The number "how many dependencies are still waiting" is the in-degree of the module.

This is Kahn’s algorithm:

  1. Count the in-degree of every module.
  2. The modules with in-degree 0 go into a queue ready.
  3. Take a module from the queue and put it in order. For everyone who uses it, decrement the in-degree. Whoever reaches 0 joins the queue.
  4. Repeat until the queue is empty.

See it

Kahn from the inside

function buildOrder(needs) {
  const indegree = new Map();
  const users = new Map();
  for (const [m, deps] of needs) {
    indegree.set(m, deps.length);
    users.set(m, []);
  }
  for (const [m, deps] of needs) {
    for (const dep of deps) users.get(dep).push(m);
  }
  const ready = [...needs.keys()].filter(
    (m) => indegree.get(m) === 0,
  );
  const order = [];
  let head = 0;
  while (head < ready.length) {
    const m = ready[head++];
    order.push(m);
    for (const user of users.get(m)) {
      indegree.set(user, indegree.get(user) - 1);
      if (indegree.get(user) === 0) ready.push(user);
    }
  }
  return order;
}

users is the reverse of needs: for each module, who uses it. Without it you would search the whole graph after every built module.

JavaScript has no built-in queue. shift() on an array moves every element, so head points at the next one and the array only grows.
const needs = new Map([
  ["core", []],
  ["db", ["core"]],
  ["auth", ["core", "db"]],
  ["catalog", ["db"]],
  ["cart", ["catalog", "auth"]],
  ["payments", ["auth"]],
  ["web", ["cart", "payments"]],
]);
console.log(`Order: ${buildOrder(needs).join(", ")}`);
Output
Order: core, db, auth, catalog, payments, cart, web

function buildOrder(needs) {
  const indegree = new Map();
  const users = new Map();
  for (const [m, deps] of needs) {
    indegree.set(m, deps.length);
    users.set(m, []);
  }
  for (const [m, deps] of needs) {
    for (const dep of deps) users.get(dep).push(m);
  }
  const ready = [...needs.keys()].filter(
    (m) => indegree.get(m) === 0,
  );
  const order = [];
  let head = 0;
  while (head < ready.length) {
    const m = ready[head++];
    order.push(m);
    for (const user of users.get(m)) {
      indegree.set(user, indegree.get(user) - 1);
      if (indegree.get(user) === 0) ready.push(user);
    }
  }
  return order;
}
Step by step, in words
  1. Seven modules. An arrow goes from a dependency to the module that uses it. The number above each module is its in-degree: how many of its dependencies are not built yet.
  2. Only core waits for nothing (in-degree 0). It goes into the queue ready.
  3. core leaves ready and is built. Everyone who uses it now waits for one dependency less: db drops to 0 and joins the queue, auth drops to 1.
  4. db is built. auth and catalog drop to 0: both have everything they need and join the queue.
  5. auth is built. payments drops to 0 and joins, cart drops to 1: it still waits for catalog.
  6. catalog is built and cart drops to 0. Now cart joins the queue too.
  7. payments is built. web drops to 1: it still waits for cart.
  8. cart is built, web drops to 0 and joins last.
  9. web is built. Nobody uses it, and the queue is empty.
  10. buildOrder returns order with 7 modules, as many as there are in needs: each one comes after its dependencies. Fewer would mean a cycle.

The queue never holds more than two modules: only those that already have everything and wait their turn.

Try it

Predict the output

The tasks of one release: style check, compile, tests, package, deploy, notification. What does buildOrder return?

const tasks = new Map([
  ["lint", []],
  ["compile", []],
  ["test", ["compile"]],
  ["package", ["compile", "lint"]],
  ["deploy", ["test", "package"]],
  ["notify", ["deploy"]],
]);
console.log(buildOrder(tasks).join(", "));
Answer

Try it

Fill in

When does a module join the queue?

for (const user of users.get(m)) {
  indegree.set(user, indegree.get(user) - 1);
  if () ready.push(user);
}

The idea

The cycle

A colleague makes auth use a helper from web:

  ["auth", ["core", "db", "web"]],

Now auth waits for web, web waits for cart, cart waits for auth. None of the three reaches in-degree 0 or joins the queue. payments waits for auth and stays behind too. The queue runs out with only 3 of the 7 modules in order.

That is also the check: fewer modules in order than in the graph means a cycle. To say which modules are to blame, start from the first unbuilt one and follow an unbuilt dependency. Every unbuilt module has at least one, so sooner or later you reach a module you have already passed:

function findCycle(needs, order) {
  const built = new Set(order);
  let m = [...needs.keys()].find((x) => !built.has(x));
  const path = [];
  while (!path.includes(m)) {
    path.push(m);
    m = needs.get(m).find((d) => !built.has(d));
  }
  return [...path.slice(path.indexOf(m)), m];
}
const order = buildOrder(needs);
if (order.length < needs.size) {
  console.log(`Built: ${order.join(", ")}`);
  console.log(`Cycle: ${findCycle(needs, order).join(" → ")}`);
} else {
  console.log(`Order: ${order.join(", ")}`);
}
Output
Built: core, db, catalog
Cycle: auth → web → cart → auth
More precisely, if you are curious

Real tools do the same and name the cycle. Gradle says "Circular dependency between the following tasks" and lists them. Maven says "The projects in the reactor contain a cyclic reference". MSBuild refuses a project that reaches itself through its references. The fix is always in the code, not in the tool: what the two modules share moves into a third one that both depend on.

findCycle finds one cycle. The modules outside it that wait for a module of the cycle (here payments) are not part of the problem but its victims. They will build as soon as the cycle is gone.

Try it

Find the bug

A colleague wrote the cycle check. With auth waiting for web, the program says:

const order = buildOrder(needs);
if (order.length === 0) {
  console.log(`Built: ${order.join(", ")}`);
  console.log(`Cycle: ${findCycle(needs, order).join(" → ")}`);
} else {
  console.log(`Order: ${order.join(", ")}`);
}
Output
Order: core, db, catalog

The build goes on with 3 modules, and 4 are silently missing. Which line has the bug?

Pick the line with the bug.

See it

The same with DFS

There is a second way, with the depth-first traversal from the DFS lesson. Before you put a module in the order, visit each of its dependencies. The module goes into order only after all of its dependencies are there. This is post-order: you write on the way back, not on the way in.

function dfsOrder(needs) {
  const order = [];
  const done = new Set();
  const onPath = new Set();
  const visit = (m) => {
    if (done.has(m)) return;
    if (onPath.has(m)) throw new Error(`Cycle at ${m}`);
    onPath.add(m);
    for (const dep of needs.get(m)) visit(dep);
    onPath.delete(m);
    done.add(m);
    order.push(m);
  };
  for (const m of needs.keys()) visit(m);
  return order;
}
const needs = new Map([
  ["core", []],
  ["db", ["core"]],
  ["auth", ["core", "db"]],
  ["catalog", ["db"]],
  ["cart", ["catalog", "auth"]],
  ["payments", ["auth"]],
  ["web", ["cart", "payments"]],
]);
console.log(`Order: ${dfsOrder(needs).join(", ")}`);
const broken = new Map([
  ["core", []],
  ["db", ["core"]],
  ["auth", ["core", "db", "web"]],
  ["catalog", ["db"]],
  ["cart", ["catalog", "auth"]],
  ["payments", ["auth"]],
  ["web", ["cart", "payments"]],
]);
try {
  dfsOrder(broken);
} catch (e) {
  console.log(e.message);
}
Output
Order: core, db, auth, catalog, cart, payments, web
Cycle at auth

The order is different: here cart comes before payments. Both orders are right, because cart and payments do not depend on each other. A topological order is rarely the only one.

The cycle is caught differently here. onPath holds the modules that DFS has started but not finished: they are on the call stack right now. If you meet one of them again, you have gone round in a circle. In the DFS lesson these are the grey vertices.

More precisely, if you are curious

Which one to pick? Both cost O(V + E): every module is processed once, every dependency is looked at once. Kahn has no recursion and naturally gives "what can start now", so build tools that build in parallel think like it. DFS is shorter when the graph is already traversed depth-first.

Recursive DFS in JavaScript throws RangeError: Maximum call stack size exceeded on a chain of about 10,000 modules. Kahn does not have this problem.

The idea

Where else

There is a topological order wherever something waits for something else:

  • Package dependencies. npm and pip resolve which versions to use, then install them so that every package comes after its own. Gradle and MSBuild build the modules of a project in topological order, and the independent ones in parallel.
  • Makefile. Each rule says which files it depends on. make builds the graph and runs the commands in such an order that every file is ready before another one needs it.
  • The spreadsheet. The cell C1 = A1 + B1 depends on A1 and B1. When A1 changes, the spreadsheet recalculates only the cells after it, in topological order. A formula that reaches itself is a cycle, and Excel says so: "circular reference".
  • Database migrations and CI jobs: every step waits for its own.

Exercise

Waves in CI

Solve it in your editor.

Waves. The CI server runs at the same time all the jobs that can already start. Write waves(needs), which returns the jobs in waves: the first wave are the jobs with no dependencies, and each next one are those whose last dependency is in the previous wave. Run it with the jobs from "Predict the output":

Output
Wave 1: lint, compile
Wave 2: test, package
Wave 3: deploy
Wave 4: notify

Hint: this is Kahn, but instead of one queue you keep the current wave and build the next one.

More tasks

  • The longest chain. How many waves does CI need at least, if it has unlimited machines? It is the longest path in the graph.
  • A stable order. Make the output the same whatever the order of needs: when several modules are ready, take the first in alphabetical order. What structure do you need instead of the queue?
  • Everyone to blame. Print all modules that are not built because of the cycle, and separate those that are in the cycle itself.

Test

Check yourself

1. What is the in-degree of a module in Kahn’s algorithm?
2. buildOrder returned 4 modules, and needs has 7. What does that mean?
3. Kahn gives core, db, auth, catalog, payments, cart, web, and DFS gives core, db, auth, catalog, cart, payments, web. Which one is right?
4. What does Kahn’s algorithm cost for V modules and E dependencies?

Made by Ivo Gergov as part of Evo Tech's campaign for accessible programming education ·