graph_utils.ts

// Copyright 2023 Google LLC. All Rights Reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
// =============================================================================

import * as fs from 'fs';
import * as path from 'path';

export const DEPENDENCY_GRAPH = JSON.parse(
  fs.readFileSync(path.join(__dirname, 'package_dependencies.json'), 'utf8'));

// This is a reverse dependencies graph. Each entry in the graph lists the
// packages that depend on it.
export const REVERSE_DEPENDENCY_GRAPH = transposeGraph(DEPENDENCY_GRAPH);

// Topologically sort the dependency tree and arrange
// steps in dependency order.
export const DEPENDENCY_ORDER = topologicalSort(DEPENDENCY_GRAPH);

export type Graph<V extends Iterable<string> = Iterable<string>> = {
  [node: string]: V
}

/**
 * Verify that an object is a valid graph.
 */
export function verifyGraph(graph: Graph) {
  const nodes = new Set(Object.keys(graph));
  for (const [node, edges] of Object.entries(graph)) {
    for (const edge of edges) {
      if (!nodes.has(edge)) {
        throw new Error(
            `Graph edge ${edge} of node ${node} not found in the 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.
 *
 * Returns a list of graph nodes such that, by following edges,
 * 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
 * closure at `node`.
 */
export function findSubgraph(node: string, graph: Graph, subnodes = new Set()) {
  const directSubnodes = graph[node];
  if (directSubnodes) {
    for (const directSubnode of directSubnodes) {
      if (!subnodes.has(directSubnode)) {
        subnodes.add(directSubnode);
        findSubgraph(directSubnode, graph, subnodes);
      }
    }
  }

  return subnodes;
}

/**
 * Find the transitive closure of dependencies of the given packages.
 */
export function findDeps(packages: Iterable<string>): Set<string> {
  return new Set(
      [...packages]
          .map(packageName => findSubgraph(packageName, DEPENDENCY_GRAPH))
          .reduce((a, b) => [...a, ...b], []));
}

/**
 * Find the reverse dependencies of the given packages, i.e. find the
 * set of packages that include at least one of the given packages in
 * their transitive closure of dependencies.
 */
export function findReverseDeps(packages: Iterable<string>): Set<string> {
  return new Set(
    [...packages]
      .map(packageName => findSubgraph(packageName, REVERSE_DEPENDENCY_GRAPH))
      .reduce((a, b) => [...a, ...b], []));
}