Why does this topological sort report a cycle for a valid dependency graph?

programming web dev
1

I’m implementing Kahn’s algorithm, but some acyclic inputs return an empty result because indegree seems wrong after setup. I expect ["build","test","deploy"] for the example below. What am I counting incorrectly?

function topo(edges) {
  const indegree = new Map(), graph = new Map();
  for (const [a, b] of edges) {
    graph.set(a, (graph.get(a) || []).concat(b));
    indegree.set(a, (indegree.get(a) || 0) + 1);
    if (!indegree.has(b)) indegree.set(b, 0);
  }
  const q = [...[...indegree].filter(([, d]) => d === 0).map(([n]) => n)];
  return q;
}

Quelly

2

You’re incrementing the source node instead of the destination, so for build -> test you should add to indegree["test"], not indegree["build"], and also make sure every node exists in graph so sinks don’t disappear later.

Ellen