Skip to content
AITroveRead. Build. Understand.
Make this comfortable

Python graph condensation: collapse directed cycles into an acyclic component graph

Last updated: 30 Sept 20264 min read
tutorial
IntermediateBy AITrove Editorial

A condensation graph replaces each strongly connected component with one vertex and keeps edges between different components.

Download Python source kit

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

python
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

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.

python
component-condensation
Storage details