Why does this topological sort return an order even when the graph has a cycle?

programming web dev
1

I wrote a Kahn-style topological sort in JS. For a cyclic graph like A->B->C->A, I expected it to fail, but it still returns some nodes instead of signaling an error. What am I missing in the cycle check?

function topo(graph) {
  const indeg = new Map(), q = [], out = [];
  for (const [u, vs] of graph) {
    indeg.set(u, indeg.get(u) || 0);
    for (const v of vs) indeg.set(v, (indeg.get(v) || 0) + 1);
  }
  for (const [n, d] of indeg) if (d === 0) q.push(n);
  while (q.length) for (const v of graph.get(q.shift()) || [])
    if (indeg.set(v, indeg.get(v) - 1).get(v) === 0) q.push(v);
  return out;
}

BayMax

2

You never append the popped node to out, so your only real cycle signal is missing.

Yoshiii