kosajaru.ts

// Compute the node priorities, which will be used to determine the order in which we perform transposed DFS.
const getNodePriorities = (
  graph: number[][],
  visited: boolean[],
  stack: number[],
  node: number
) => {
  if (visited[node]) {
    return
  }
  visited[node] = true

  for (const dest of graph[node]) {
    getNodePriorities(graph, visited, stack, dest)
  }
  // Nodes that end their DFS earlier are pushed onto the stack first and have lower priority.
  stack.push(node)
}

// Return the transpose of graph. The tranpose of a directed graph is a graph where each of the edges are flipped.
const transpose = (graph: number[][]): number[][] => {
  const transposedGraph = Array(graph.length)
  for (let i = 0; i < graph.length; ++i) {
    transposedGraph[i] = []
  }

  for (let i = 0; i < graph.length; ++i) {
    for (let j = 0; j < graph[i].length; ++j) {
      transposedGraph[graph[i][j]].push(i)
    }
  }

  return transposedGraph
}

// Computes the SCC that contains the given node
const gatherScc = (
  graph: number[][],
  visited: boolean[],
  node: number,
  scc: number[]
) => {
  if (visited[node]) {
    return
  }
  visited[node] = true
  scc.push(node)

  for (const dest of graph[node]) {
    gatherScc(graph, visited, dest, scc)
  }
}

/**
 * @function kosajaru
 * @description Given a graph, find the strongly connected components(SCC). A set of nodes form a SCC if there is a path between all pairs of points within that set.
 * @Complexity_Analysis
 * Time complexity: O(V + E). We perform two DFS twice, and make sure to visit each disconnected graph. Each DFS is O(V + E).
 * Space Complexity: O(V + E). This space is required for the transposed graph.
 * @param {[number, number][][]} graph - The graph in adjacency list form
 * @return {number[][]} - An array of SCCs, where an SCC is an array with the indices of each node within that SCC.
 * @see https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm
 */
export const kosajaru = (graph: number[][]): number[][] => {
  const visited = Array(graph.length).fill(false)

  const stack: number[] = []
  for (let i = 0; i < graph.length; ++i) {
    getNodePriorities(graph, visited, stack, i)
  }

  const transposedGraph = transpose(graph)

  const sccs = []
  visited.fill(false)
  for (let i = stack.length - 1; i >= 0; --i) {
    if (!visited[stack[i]]) {
      const scc: number[] = []
      gatherScc(transposedGraph, visited, stack[i], scc)
      sccs.push(scc)
    }
  }
  return sccs
}