toposort.ts

type GraphGenerator<T> = Iterable<[T, T?]>;

interface Edges<T> {
  pred: T[];
  succ: T[];
}

export function toposort<T, G extends GraphGenerator<T>>(graph: G): T[] {
  const sorted = new Set<T>();
  const nodes = new Map<T, Edges<T>>();
  
  for (const [n, m] of graph) {
    let ne = nodes.get(n);
    if (ne === undefined) {
      ne = { pred: [], succ: [] };
      nodes.set(n, ne);
      sorted.add(n);
    }

    if (m !== undefined) {
      ne.succ.push(m);
      let me = nodes.get(m);
      if (me === undefined) {
        me = { pred: [], succ: [] };
        nodes.set(m, me);
      }
      me.pred.push(n);
      sorted.delete(m);
    }
  }

  for (const n of sorted) {
    const ne = nodes.get(n)!;
    for (const m of ne.succ) {
      const me = nodes.get(m)!;
      if (me.pred.every((p) => sorted.has(p))) {
        sorted.add(m);
      }
    }
  }
}