Function transposeGraph

scripts/graph_utils.ts:52–68

(graph: Graph)

 * Transpose a directed graph i.e. reverse the direction of the edges.
 */
export function transposeGraph(graph: Graph) {
  verifyGraph(graph);
  const transposed: Graph<Set<string>> = {};
  for (const [nodeName, connectedNodes] of Object.entries(graph)) {
    for (const connectedNode of connectedNodes) {
      if (!transposed[connectedNode]) {
        transposed[connectedNode] = new Set();
      }
      if (!transposed[nodeName]) {
        // Make sure the node itself ends up in the transposed graph.
        transposed[nodeName] = new Set();
      }
      transposed[connectedNode].add(nodeName);
    }
  }
  return transposed;
}

/**
 * Topologically sort a directed acyclic graph.