Function topoSort

src/orchestration/scheduler.ts:288–311

(graph: TaskGraph)

/** Validate a graph is acyclic via Kahn's algorithm; returns topo order or null. */
export function topoSort(graph: TaskGraph): TaskId[] | null {
  const indeg = new Map<TaskId, number>();
  const adj = new Map<TaskId, TaskId[]>();
  for (const id of graph.nodes.keys()) { indeg.set(id, 0); adj.set(id, []); }
  for (const node of graph.nodes.values()) {
    for (const dep of node.dependsOn) {
      if (!graph.nodes.has(dep)) continue;
      adj.get(dep)!.push(node.id);
      indeg.set(node.id, (indeg.get(node.id) ?? 0) + 1);
    }
  }
  const queue: TaskId[] = [];
  for (const [id, d] of indeg) if (d === 0) queue.push(id);
  const order: TaskId[] = [];
  while (queue.length) {
    const id = queue.shift()!;
    order.push(id);
    for (const next of adj.get(id) ?? []) {
      indeg.set(next, indeg.get(next)! - 1);
      if (indeg.get(next) === 0) queue.push(next);
    }
  }
  return order.length === graph.nodes.size ? order : null;
}