Topological Sort With Cycle Detection (TypeScript)

export function topologicalSort(
  graph: Readonly<Record<string, readonly string[]>>,
): string[] {
  if (graph === null || typeof graph !== "object" || Array.isArray(graph)) {
    throw new TypeError("graph must be an object of dependency arrays");
  }

  const nodes = Object.keys(graph);
  const nodeSet = new Set(nodes);
  const indegree = new Map<string, number>();
  const outgoing = new Map<string, Set<string>>();
  for (const node of nodes) {
    indegree.set(node, 0);
    outgoing.set(node, new Set());
  }

  for (const node of nodes) {
    const dependencies = graph[node];
    if (!Array.isArray(dependencies)) {
      throw new TypeError(`dependencies for "${node}" must be an array`);
    }
    for (const dependency of dependencies) {
      if (typeof dependency !== "string") {
        throw new TypeError(`dependency for "${node}" must be a string`);
      }
      if (!nodeSet.has(dependency)) {
        throw new Error(`unknown dependency "${dependency}" for "${node}"`);
      }
      const edges = outgoing.get(dependency);
      if (edges === undefined) throw new Error("invalid graph state");
      if (edges.has(node)) continue;
      edges.add(node);
      indegree.set(node, (indegree.get(node) ?? 0) + 1);
    }
  }

  const ready = nodes
    .filter((node) => indegree.get(node) === 0)
    .sort((left, right) => left.localeCompare(right));
  const order: string[] = [];

  while (ready.length > 0) {
    const node = ready.shift();
    if (node === undefined) break;
    order.push(node);

    for (const next of outgoing.get(node) ?? []) {
      const remaining = (indegree.get(next) ?? 0) - 1;
      indegree.set(next, remaining);
      if (remaining !== 0) continue;

      let index = 0;
      while (index < ready.length && ready[index] < next) index += 1;
      ready.splice(index, 0, next);
    }
  }

  if (order.length !== nodes.length) {
    const blocked = nodes
      .filter((node) => !order.includes(node))
      .sort((left, right) => left.localeCompare(right));
    throw new Error(`cycle detected among: ${blocked.join(", ")}`);
  }
  return order;
}

const graph = {
  app: ["db", "cache"],
  db: ["config"],
  cache: ["config"],
  config: [],
};
console.log(topologicalSort(graph).join(" -> "));

try {
  topologicalSort({ a: ["b"], b: ["a"] });
} catch (error) {
  console.log(error instanceof Error ? error.message : String(error));
}

try {
  topologicalSort({ app: ["missing"] });
} catch (error) {
  console.log(error instanceof Error ? error.message : String(error));
}