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

Condensation DAGs: compress directed cycles before path queries

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A strongly connected component groups directed vertices that can reach one another. This index finds components through a forward finish-order traversal and a reverse-graph traversal, then replaces each component with one node in a condensation graph. Edges between distinct components form a directed acyclic graph; duplicate edges collapse into one set entry. The example precomputes a reachable-component set for every component by traversing that graph. A vertex-to-vertex path query then tests whether the target's component appears in the source component's set. Vertices within the same component always reach one another, including by the zero-edge path when source equals target.

Operational case

Seven directed depots include a three-vertex cycle through zero, one, and two and a two-vertex cycle through three and four. A route from the first component can reach depot five, while depot five cannot return to depot one. The condensation has four component nodes rather than seven original vertices. Component numeric IDs depend on traversal order and are implementation details; callers should compare membership or reachability, not publish those IDs as stable depot identifiers. A changed edge can merge components or split reachability, so the entire static index needs rebuilding.

Working Python program

python
class CondensedRoutes:
    def __init__(self, vertex_count, directed_edges):
        if vertex_count < 0:
            raise ValueError("negative vertex count")
        self.count = vertex_count
        self.forward = [[] for _ in range(vertex_count)]
        reverse = [[] for _ in range(vertex_count)]
        for source, target in directed_edges:
            if not (0 <= source < vertex_count and 0 <= target < vertex_count):
                raise ValueError("edge outside graph")
            self.forward[source].append(target)
            reverse[target].append(source)
        visited, finish = set(), []
        for source in range(vertex_count):
            if source in visited:
                continue
            stack = [(source, False)]
            while stack:
                vertex, completed = stack.pop()
                if completed:
                    finish.append(vertex)
                elif vertex not in visited:
                    visited.add(vertex)
                    stack.append((vertex, True))
                    stack.extend((neighbor, False) for neighbor in self.forward[vertex] if neighbor not in visited)
        self.component = [-1] * vertex_count
        component_count = 0
        for source in reversed(finish):
            if self.component[source] != -1:
                continue
            pending = [source]
            self.component[source] = component_count
            while pending:
                vertex = pending.pop()
                for neighbor in reverse[vertex]:
                    if self.component[neighbor] == -1:
                        self.component[neighbor] = component_count
                        pending.append(neighbor)
            component_count += 1
        self.dag = [set() for _ in range(component_count)]
        for source in range(vertex_count):
            for target in self.forward[source]:
                first, second = self.component[source], self.component[target]
                if first != second:
                    self.dag[first].add(second)
        self.reachable_components = []
        for source in range(component_count):
            seen, pending = {source}, [source]
            while pending:
                for target in self.dag[pending.pop()]:
                    if target not in seen:
                        seen.add(target)
                        pending.append(target)
            self.reachable_components.append(seen)

    def reaches(self, source, target):
        if not (0 <= source < self.count and 0 <= target < self.count):
            raise ValueError("vertex outside graph")
        return self.component[target] in self.reachable_components[self.component[source]]


if __name__ == "__main__":
    index = CondensedRoutes(7, [(0, 1), (1, 2), (2, 0), (2, 3),
                                (3, 4), (4, 3), (4, 5)])
    print(len(index.dag), index.reaches(1, 5), index.reaches(5, 1))
    print(index.component[0] == index.component[2], index.component[3] == index.component[4])

Output

Output
4 True False
True True

Time, space, and tradeoff

Component discovery and DAG construction take O(V+E) time and O(V+E) space for V vertices and E edges. This model then traverses the component DAG once per component, taking O(C(C+D)) time and up to O(C squared) stored reachability entries for C components and D distinct DAG edges. A query uses expected O(1) set membership after indexing. For few queries, a direct graph search may avoid the quadratic precomputation. The iterative finish traversal avoids recursion depth, but the implementation keeps Python lists and sets rather than packed bit rows.

Common Mistakes

  • Do not treat component IDs as stable business IDs across rebuilds.
  • Do not assume weakly connected vertices can reach each other both ways.
  • Do not keep old reachability sets after adding or removing a road.
  • Do not retain self-loops as edges between distinct condensation nodes.

Connected lessons

Compare its query and update boundary with LZ78 phrase tries: emit dictionary index and next symbol, Segment-tree stabbing indexes: list intervals active at one point, Huffman trees: assign prefix codes from symbol frequencies, then complete the structure audit and decision quiz.

Block-cut indexes: separate articulation depots from cyclic road blocks adds a related structure with a different operation boundary.

data structures
range-query-structures
Storage details