Topological Sort and Cycle Detection

You have a list of tasks and some of them depend on others. You want an order to do them in where nothing starts before the things it needs are finished. That is a topological sort, and it only works on a DAG, for a reason that becomes obvious the moment you try it on something with a loop.

Every build system does this. So does npm, so does a spreadsheet recalculating cells, so does a course catalogue working out prerequisites.

The graph you are sorting

Switch this to the DAG tab. Every arrow means "must come before". A points at B and D, so A has to be done first. E has arrows coming in from both B and D, so it waits for both.

One valid order here is A, B, D, E, C. So is A, D, B, E, C. Topological orders are usually not unique, and any of them is a correct answer. When two tasks have no dependency between them, their relative order genuinely does not matter.

Kahn's algorithm: peel off what is ready

The in-degree of a node is how many arrows point at it, which here means how many unfinished things it is waiting on. A node with in-degree 0 is waiting on nothing, so it is ready to go right now.

So: collect every node with in-degree 0. Take one, output it, and remove its outgoing arrows. Removing those arrows might drop some other node to in-degree 0, which means that node just became ready. Repeat until you run out.

function topologicalSort(nodes, adj) {
  const inDegree = new Map(nodes.map((n) => [n, 0]));
  for (const node of nodes) {
    for (const next of adj.get(node) ?? []) {
      inDegree.set(next, inDegree.get(next) + 1);
    }
  }

  // Everything that depends on nothing can start immediately.
  const ready = nodes.filter((n) => inDegree.get(n) === 0);
  const order = [];

  while (ready.length > 0) {
    const node = ready.shift();
    order.push(node);

    for (const next of adj.get(node) ?? []) {
      inDegree.set(next, inDegree.get(next) - 1);
      if (inDegree.get(next) === 0) ready.push(next); // now unblocked
    }
  }

  // Anything left still has an unmet dependency, which on a finite
  // graph can only mean those nodes depend on each other in a loop.
  if (order.length !== nodes.length) {
    throw new Error("Cycle detected: no valid order exists");
  }
  return order;
}

The cycle check is free

That last check is worth dwelling on, because you get cycle detection without writing any extra code. If the loop finishes and some nodes never made it out, those nodes are all still waiting on something. On a finite graph, the only way for that to happen is for them to be waiting on each other, directly or through a chain.

auth  →  logger
logger →  config
config →  auth

Every one of these has in-degree 1. Nothing ever reaches 0,
so the ready list starts empty and the algorithm outputs nothing.
That is your circular dependency error, and this is how your
package manager finds it.

The DFS version

There is a second way that some people find neater. Run a DFS. When a node has finished exploring all of its descendants, push it onto a list. Reverse the list at the end and you have a topological order.

The reason it works: a node is only finished after everything it points to is finished, so it lands earlier in the finish list than all of its dependencies. Reversing puts it in front of them, which is exactly what you wanted.

function topoDfs(nodes, adj) {
  const state = new Map(nodes.map((n) => [n, "unseen"]));
  const finished = [];

  function visit(node) {
    if (state.get(node) === "done") return;
    // Meeting a node we're still in the middle of means we
    // walked in a circle and came back to it.
    if (state.get(node) === "visiting") throw new Error("Cycle detected");

    state.set(node, "visiting");
    for (const next of adj.get(node) ?? []) visit(next);
    state.set(node, "done");
    finished.push(node);
  }

  for (const node of nodes) visit(node);
  return finished.reverse();
}

Three states rather than a plain visited set is the important detail here. "Visiting" means this node is on the current path, still in progress. Bumping into one of those is a back edge, which is a cycle. Bumping into a "done" node is fine, that is just a shortcut to something already handled.

Check yourself