Oct 3, 2025 · Oct 3, 2025 · Oct 3, 2025 · Oct 3, 2025
diff --git a/Graphs/Condensation.js b/Graphs/Condensation.js
 /**
 * Condensation via Kosaraju's algorithm
 *
 * @see https://cp-algorithms.com/graph/strongly-connected-components.html
 * This file computes the strongly connected components (SCCs) and the
 * condensation (component DAG) for a directed graph given as an edge list.
 * It uses the project's existing Kosaraju implementation (Kosaraju.js).
 */

 import { kosaraju } from './Kosaraju.js'

 /**
 * Compute SCCs and the condensation graph (component DAG) for a directed graph.
 * @param {Array<Array<number>>} graph edges as [u, v]
 * @returns {{sccs: Array<Array<number>>, condensation: Array<Array<number>>}}
 */

 function condensation(graph) {
  // Using Kosaraju implementation to compute SCCs
  const sccs = kosaraju(graph)

  // Build adjacency map to include isolated nodes
  const g = {}
  const addNode = (n) => {
    if (!(n in g)) g[n] = new Set()
  }
  for (const [u, v] of graph) {
    addNode(u)
    addNode(v)
    g[u].add(v)
  }

  // Map node -> component index (string keys)
  const compIndex = {}
  for (let i = 0; i < sccs.length; i++) {
    for (const node of sccs[i]) compIndex[String(node)] = i
  }

  // Build condensation adjacency list (component graph)
  const condensationSets = Array.from({ length: sccs.length }, () => new Set())
  for (const u of Object.keys(g)) {
    const ci = compIndex[u]
    if (ci === undefined) continue
    for (const v of g[u]) {
      const cj = compIndex[String(v)]
      if (cj === undefined) continue
      if (ci !== cj) condensationSets[ci].add(cj)
    }
  }

  const condensation = condensationSets.map((s) => Array.from(s))

  return { sccs, condensation, compIndex }
 }

 export { condensation }

 /**
 * Time and Space Complexity
 *
 * Kosaraju's algorithm (finding SCCs) and condensation graph construction:
 *
 * - Time complexity: O(V + E)
 *   - Building the adjacency list from the input edge list: O(E)
 *   - Running Kosaraju's two DFS passes over all vertices and edges: O(V + E)
 *   - Building the component index and condensation edges: O(V + E)
 *   Overall: O(V + E), where V is the number of vertices and E is the number of edges.
 *
 * - Space complexity: O(V + E)
 *   - Adjacency lists (graph): O(V + E)
 *   - Kosaraju bookkeeping (stacks, visited sets, topo order, sccs, compIndex): O(V)
 *   - Condensation adjacency structures: O(C + E') where C <= V and E' <= E, so
 *     bounded by O(V + E).
 *   Overall: O(V + E).
 *
 * Notes:
 * - Recursion may use O(V) call-stack space in the worst case during DFS.
 * - Constants depend on the data-structures used (Sets/Arrays), but the
 *   asymptotic bounds above hold for this implementation.
 */

 /**
 * Visual diagram and usage
 *
 * Consider the directed edge list:
 *
 *   edges = [
 *     [1,2], [2,3], [3,1], // cycle among 1,2,3
 *     [2,4],               // edge from the first cycle to node 4
 *     [4,5], [5,6], [6,4]  // cycle among 4,5,6
 *   ]
 *
 * Original graph (conceptual):
 *
 *     1 --> 2 --> 4 --> 5
 *     ^     |           |
 *     |     v           v
 *     3 <-- -          6
 *
 * Strongly connected components (SCCs) in this graph:
 *
 *   SCC A: [1, 2, 3]   // a cycle 1->2->3->1
 *   SCC B: [4, 5, 6]   // a cycle 4->5->6->4
 *
 * Condensation graph (component DAG):
 *
 *   [A] ---> [B]
 *
 * Where each node in the condensation is a whole SCC from the original graph.
 *
 * Example return values from `condensation(edges)`:
 *
 *   {
 *     sccs: [[1,2,3], [4,5,6]],
 *     condensation: [[1], []], // component 0 has an edge to component 1
 *     compIndex: { '1': 0, '2': 0, '3': 0, '4': 1, '5': 1, '6': 1 }
 *   }
 *
 * Usage:
 *
 *   const edges = [[1,2],[2,3],[3,1],[2,4],[4,5],[5,6],[6,4]]
 *   const { sccs, condensation, compIndex } = condensation(edges)
 *
 * Interpretation summary:
 * - `sccs` is an array of components; each component is an array of original nodes.
 * - `condensation` is the adjacency list of the component DAG; indices refer to `sccs`.
 * - `compIndex` maps an original node (string key) to its component index.
 *
 * This ASCII diagram and mapping should make it easy to visualize how the
 * condensation function groups cycles and produces a DAG of components.
 */
diff --git a/Graphs/test/Condensation.test.js b/Graphs/test/Condensation.test.js
 import { condensation } from '../Condensation.js'

 test('Test Case 1', () => {
  const graph = [
    [1, 2],
    [2, 3],
    [3, 1],
    [2, 4],
    [4, 5],
    [5, 6],
    [6, 4]
  ]
  const { sccs } = condensation(graph)
  expect(sccs).toStrictEqual([
    [1, 3, 2],
    [4, 6, 5]
  ])
 })

 test('Test Case 2', () => {
  const graph = [
    [1, 2],
    [2, 3],
    [3, 1],
    [2, 4],
    [4, 5]
  ]
  const { sccs } = condensation(graph)
  expect(sccs).toStrictEqual([[1, 3, 2], [4], [5]])
 })
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,131 @@
		/**
		* Condensation via Kosaraju's algorithm
		*
		* @see https://cp-algorithms.com/graph/strongly-connected-components.html
		* This file computes the strongly connected components (SCCs) and the
		* condensation (component DAG) for a directed graph given as an edge list.
		* It uses the project's existing Kosaraju implementation (Kosaraju.js).
		*/

		import { kosaraju } from './Kosaraju.js'

		/**
		* Compute SCCs and the condensation graph (component DAG) for a directed graph.
		* @param {Array<Array<number>>} graph edges as [u, v]
		* @returns {{sccs: Array<Array<number>>, condensation: Array<Array<number>>}}
		*/

		function condensation(graph) {
		// Using Kosaraju implementation to compute SCCs
		const sccs = kosaraju(graph)

		// Build adjacency map to include isolated nodes
		const g = {}
		const addNode = (n) => {
		if (!(n in g)) g[n] = new Set()
		}
		for (const [u, v] of graph) {
		addNode(u)
		addNode(v)
		g[u].add(v)
		}

		// Map node -> component index (string keys)
		const compIndex = {}
		for (let i = 0; i < sccs.length; i++) {
		for (const node of sccs[i]) compIndex[String(node)] = i
		}

		// Build condensation adjacency list (component graph)
		const condensationSets = Array.from({ length: sccs.length }, () => new Set())
		for (const u of Object.keys(g)) {
		const ci = compIndex[u]
		if (ci === undefined) continue
		for (const v of g[u]) {
		const cj = compIndex[String(v)]
		if (cj === undefined) continue
		if (ci !== cj) condensationSets[ci].add(cj)
		}
		}

		const condensation = condensationSets.map((s) => Array.from(s))

		return { sccs, condensation, compIndex }
		}

		export { condensation }

		/**
		* Time and Space Complexity
		*
		* Kosaraju's algorithm (finding SCCs) and condensation graph construction:
		*
		* - Time complexity: O(V + E)
		* - Building the adjacency list from the input edge list: O(E)
		* - Running Kosaraju's two DFS passes over all vertices and edges: O(V + E)
		* - Building the component index and condensation edges: O(V + E)
		* Overall: O(V + E), where V is the number of vertices and E is the number of edges.
		*
		* - Space complexity: O(V + E)
		* - Adjacency lists (graph): O(V + E)
		* - Kosaraju bookkeeping (stacks, visited sets, topo order, sccs, compIndex): O(V)
		* - Condensation adjacency structures: O(C + E') where C <= V and E' <= E, so
		* bounded by O(V + E).
		* Overall: O(V + E).
		*
		* Notes:
		* - Recursion may use O(V) call-stack space in the worst case during DFS.
		* - Constants depend on the data-structures used (Sets/Arrays), but the
		* asymptotic bounds above hold for this implementation.
		*/

		/**
		* Visual diagram and usage
		*
		* Consider the directed edge list:
		*
		* edges = [
		* [1,2], [2,3], [3,1], // cycle among 1,2,3
		* [2,4], // edge from the first cycle to node 4
		* [4,5], [5,6], [6,4] // cycle among 4,5,6
		* ]
		*
		* Original graph (conceptual):
		*
		* 1 --> 2 --> 4 --> 5
		* ^ \| \|
		* \| v v
		* 3 <-- - 6
		*
		* Strongly connected components (SCCs) in this graph:
		*
		* SCC A: [1, 2, 3] // a cycle 1->2->3->1
		* SCC B: [4, 5, 6] // a cycle 4->5->6->4
		*
		* Condensation graph (component DAG):
		*
		* [A] ---> [B]
		*
		* Where each node in the condensation is a whole SCC from the original graph.
		*
		* Example return values from `condensation(edges)`:
		*
		* {
		* sccs: [[1,2,3], [4,5,6]],
		* condensation: [[1], []], // component 0 has an edge to component 1
		* compIndex: { '1': 0, '2': 0, '3': 0, '4': 1, '5': 1, '6': 1 }
		* }
		*
		* Usage:
		*
		* const edges = [[1,2],[2,3],[3,1],[2,4],[4,5],[5,6],[6,4]]
		* const { sccs, condensation, compIndex } = condensation(edges)
		*
		* Interpretation summary:
		* - `sccs` is an array of components; each component is an array of original nodes.
		* - `condensation` is the adjacency list of the component DAG; indices refer to `sccs`.
		* - `compIndex` maps an original node (string key) to its component index.
		*
		* This ASCII diagram and mapping should make it easy to visualize how the
		* condensation function groups cycles and produces a DAG of components.
		*/
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,30 @@
		import { condensation } from '../Condensation.js'

		test('Test Case 1', () => {
		const graph = [
		[1, 2],
		[2, 3],
		[3, 1],
		[2, 4],
		[4, 5],
		[5, 6],
		[6, 4]
		]
		const { sccs } = condensation(graph)
		expect(sccs).toStrictEqual([
		[1, 3, 2],
		[4, 6, 5]
		])
		})

		test('Test Case 2', () => {
		const graph = [
		[1, 2],
		[2, 3],
		[3, 1],
		[2, 4],
		[4, 5]
		]
		const { sccs } = condensation(graph)
		expect(sccs).toStrictEqual([[1, 3, 2], [4], [5]])
		})