A condensation graph replaces each strongly connected component with one vertex and keeps edges between different components.
Python graph condensation: collapse directed cycles into an acyclic component graph
Operation contract
The first traversal records finish order; the reversed graph then partitions vertices in reverse finish order. Each component is sorted, and components are ordered by their smallest vertex to make the owned fixture output reproducible. Original edges map into component IDs, with internal edges removed and repeated component edges deduplicated. This changes the graph model: a path between components does not say which original edge or vertex carried a business operation.
Failure and ownership boundary
The fixture accepts an owned directed list with at most 32 vertices and 128 edges. Input is validated before traversal. Cyclic components have become individual nodes, so the returned graph has no directed cycle. Python strongly connected components: partition a directed dependency graph, Python topological sort: dependency order and cycle rejection and Python graph BFS: mark a vertex when it enters the queue answer different questions.
Working program
def condensation(vertex_count, edges):
if type(vertex_count) is not int or not 0 <= vertex_count <= 32 or type(edges) is not list or len(edges) > 128:
raise ValueError("bounded graph required")
graph, reverse = [[] for _ in range(vertex_count)], [[] for _ in range(vertex_count)]
for pair in edges:
if type(pair) is not tuple or len(pair) != 2 or any(type(vertex) is not int or not 0 <= vertex < vertex_count for vertex in pair):
raise ValueError("valid endpoints required")
source, target = pair
graph[source].append(target)
reverse[target].append(source)
seen, finished = set(), []
def finish(vertex):
seen.add(vertex)
for target in graph[vertex]:
if target not in seen:
finish(target)
finished.append(vertex)
for vertex in range(vertex_count):
if vertex not in seen:
finish(vertex)
seen.clear()
components = []
def collect(vertex, members):
seen.add(vertex)
members.append(vertex)
for target in reverse[vertex]:
if target not in seen:
collect(target, members)
for vertex in reversed(finished):
if vertex not in seen:
members = []
collect(vertex, members)
components.append(sorted(members))
components.sort(key=lambda members: members[0])
owner = {vertex: index for index, members in enumerate(components) for vertex in members}
collapsed = sorted({(owner[source], owner[target]) for source, target in edges if owner[source] != owner[target]})
return components, collapsed
print(condensation(5, [(0, 1), (1, 0), (1, 2), (2, 3), (3, 2), (3, 4)]))Output
([[0, 1], [2, 3], [4]], [(0, 1), (1, 2)])Costs and limits
Both traversals use O(V + E) work and storage. Sorting members/components/unique edges adds up to O(V log V + E log E). Original edge identity is deliberately lost in this returned summary; retain it separately when multiplicity or provenance matters.
Common Mistakes
- Discard internal component edges when constructing the DAG.
- Do not present a collapsed edge as an original edge identity.
Connected lessons
Python strongly connected components: partition a directed dependency graph, Python topological sort: dependency order and cycle rejection, Python articulation points: find vertices that separate an undirected graph.
