Function topologicalSort

scripts/graph_utils.ts:76–110

(graph: Graph)

 * you can only move forward in the list, not backward.
 */
export function topologicalSort(graph: Graph) {
  // We can't use a standard sorting algorithm because
  // often, two packages won't have any dependency relationship
  // between each other, meaning they are incomparable.
  verifyGraph(graph);
  const sorted: string[] = [];

  while (sorted.length < Object.keys(graph).length) {
    // Find nodes not yet in 'sorted' that have edges
    // only to nodes already in 'sorted'
    const emptyNodes = Object.entries(graph)
                           .filter(([node, edges]) => {
                             if (sorted.includes(node)) {
                               return false;
                             }
                             for (const edge of edges) {
                               if (!sorted.includes(edge)) {
                                 return false;
                               }
                             }
                             return true;
                           })
                           .map(([node, edges]) => node);

    // If there are no such nodes, then the graph has a cycle.
    if (emptyNodes.length === 0) {
      throw new Error('Dependency graph has a cycle.');
    }

    for (let node of emptyNodes) {
      sorted.push(node);
    }
  }
  return sorted;
}

/**
 * Find all subnodes in the subgraph generated by taking the transitive