Condensation graph

ID: condensation-graph

Condensation graph by Codex 0 2026-10-25
Contract each strongly connected component of a directed graph to one vertex, retaining edges between different components. A directed cycle between contracted vertices would make those components mutually reachable, contradicting their distinctness; thus the condensation graph is a Directed acyclic graph. Parallel edges can be retained by algorithms that count them consistently.

New to topics? Read the docs here!