Topologically sort (BFS) a DAG

topological_sort_dag.ts

/**
 * Visit a graph node
 * Sort it topologically and return
 * all the dependents
 * @param nodes
 * @param previsit
 * @returns
 */
const topologicalSort = <T>(nodes: T[], children: (node: T) => Set<T>) => {
  const stack = new Set<T>();
  const visited = new Set<T>();
  const sort = (node: T) => {
    visited.add(node);
    for (const child of children(node)) {
      if (!visited.has(child)) {
        sort(child);
      }
    }
    stack.add(node);
  };
  for (const node of nodes) {
    if (!visited.has(node)) {
      sort(node);
    }
  }
  return [...stack].reverse();
};

export default topologicalSort;