Why does this topological sort say there's a cycle when there isn't?

[sora]

Hey everyone, I’m wiring up a small build-order helper for plugin loading, and I’m trying to keep it simple with Kahn’s algorithm instead of a DFS version because I want clearer failure output when there really is a cycle.

function order(nodes, edges) {
  const indegree = new Map();
  const graph = new Map();

  for (const n of nodes) {
    indegree.set(n, 0);
    graph.set(n, []);
  }

  for (const [a, b] of edges) {
    graph.get(a).push(b);
    indegree.set(a, indegree.get(a) + 1);
  }

  const queue = [];
  for (const [n, d] of indegree) {
    if (d === 0) queue.push(n);
  }

  const out = [];
  while (queue.length) {
    const cur = queue.shift();
    out.push(cur);
    for (const next of graph.get(cur)) {
      indegree.set(next, indegree.get(next) - 1);
      if (indegree.get(next) === 0) queue.push(next);
    }
  }

  return out.length === nodes.length ? out : null;
}

Why does this return null on a valid dependency list, and what am I counting in the wrong direction here?

Sora

[Quelly]

You’re bumping indegree on the wrong node. For an edge a -> b, b gets +1, not a.

Right now you’re counting outgoing edges, so the queue starts with sinks instead of nodes with no prerequisites. That can leave valid nodes unprocessed and make it return null.

js
for (const [a, b] of edges) {
  graph.get(a).push(b);
  indegree.set(b, indegree.get(b) + 1);
}

So if A -> B, A should go first, and B starts with indegree 1 until A is removed. Also, if this grows, queue.shift() is worth replacing with an index-based queue since shift() gets slow fast.

Quelly

[Ellen1979]

@Quelly the “queue starts with sinks” bit is the giveaway, and one small caveat is this also blows up quietly if an edge mentions a node not preseeded in nodes, so validate that or initialize on the fly.

Ellen

Ellen