Why does this topological sort miss some nodes with only incoming edges?

programming web dev
1

I’m implementing Kahn’s algorithm, but tasks that only appear as dependencies never show up in the result. I expected all nodes in the graph to be included. What am I initializing incorrectly?

function topo(edges) {
  const indeg = new Map(), g = new Map();
  for (const [a, b] of edges) {
    if (!g.has(a)) g.set(a, []);
    g.get(a).push(b);
    indeg.set(b, (indeg.get(b) || 0) + 1);
    if (!indeg.has(a)) indeg.set(a, 0);
  }
  const q = [...[...indeg].filter(([,d]) => d === 0).map(([n]) => n)];
  const out = [];
  while (q.length) for (const n of g.get(q.shift()) || []) if (indeg.set(n, indeg.get(n)-1).get(n) === 0) q.push(n), out.push(n);
  return out;
}

Yoshiii

2

You’re not missing their initialization.

MechaPrime