Why is this topological sort saying there's a cycle when there isn't?

programming web dev
1

Hey folks, I’m wiring up a small task runner and trying to topologically sort job dependencies before execution, but this version keeps flagging a cycle on a graph that should be valid. I wanted something quick and simple, but now I’m not sure if I’m mutating the wrong thing.

function topoSort(graph) {
  const indegree = {};
  const queue = [];
  const result = [];

  for (const node in graph) {
    indegree[node] = 0;
  }

  for (const node in graph) {
    for (const dep of graph[node]) {
      indegree[dep] = (indegree[dep] || 0) + 1;
    }
  }

  for (const node in indegree) {
    if (indegree[node] === 0) queue.push(node);
  }

  while (queue.length) {
    const node = queue.shift();
    result.push(node);

    for (const dep of graph[node] || []) {
      indegree[dep]--;
      if (indegree[dep] === 0) queue.push(dep);
    }
  }

  if (result.length !== Object.keys(indegree).length) {
    throw new Error("Cycle detected");
  }

  return result;
}

console.log(
  topoSort({
    build: ["test", "lint"],
    test: ["deploy"],
    lint: ["deploy"],
    deploy: []
  })
);

What am I modeling backwards here that makes this report a cycle instead of returning a valid order?

WaffleFries :grinning_face:

2

@WaffleFries yup, the graph is backwards for the way your Kahn loop is using it.

Right now your input is job -> prerequisites, but the loop treats each edge like job -> jobs unlocked after this one. Concrete example: if build -> test means “build waits on test”, then processing build should definitely not unlock test — it should be the other way around.

Use the dependency count as each node’s indegree, then keep a reverse list so finishing test can unlock build:


js
function topoSort(graph) {
  const indegree = {};
  const reverse = {};
  const queue = [];
  const result = [];

  for (const node in graph) {
    indegree[node] = graph[node].length;
    reverse[node] ||= [];

    for (const dep of graph[node]) {
      reverse[dep] ||= [];
      reverse[dep].push(node);
      indegree[dep] ||= 0;
    }
  }

  for (const node in indegree) {
    if (indegree[node] === 0) queue.push(node);
  }

  while (queue.length) {
    const node = queue.shift();
    result.push(node);

    for (const next of reverse[node]) {
      indegree[next]--;
      if (indegree[next] === 0) queue.push(next);
    }
  }

  if (result.length !== Object.keys(indegree).length) {
    throw new Error("Cycle detected");
  }

  return result;
}

With your sample, that gives a valid order like ["deploy", "test", "lint", "build"] or ["deploy", "lint", "test", "build"]. If you want, you can also flip the original graph up front and keep the more standard “node → outgoing edges” version, but the reverse-list fix is the smallest patch.

Arthur