Reachability bitsets: precompute directed paths for a fixed graph

Operational case

A six-node directed network has a cycle through zero, one, and two, then a one-way route from two through four to five. Node zero reaches five, but five cannot reach zero. Starting at one yields reachable nodes zero, one, two, four, and five. If the diagonal bit is omitted, self-reachability can depend on whether a cycle happens to exist, changing the stated query contract. Adding a new road after precomputation can expose paths absent from several rows; this example offers no incremental repair and must be rebuilt from the new graph.

Working Python program

class ReachabilitySnapshot:
    def __init__(self, vertex_count, directed_edges):
        if vertex_count < 0:
            raise ValueError("negative vertex count")
        self.count = vertex_count
        self.rows = [1 << vertex for vertex in range(vertex_count)]
        for source, target in directed_edges:
            self._check(source)
            self._check(target)
            self.rows[source] |= 1 << target
        for intermediate in range(vertex_count):
            through = self.rows[intermediate]
            for source in range(vertex_count):
                if self.rows[source] & (1 << intermediate):
                    self.rows[source] |= through

    def _check(self, vertex):
        if not 0 <= vertex < self.count:
            raise ValueError("vertex outside graph")

    def reaches(self, source, target):
        self._check(source)
        self._check(target)
        return bool(self.rows[source] & (1 << target))

    def reachable_from(self, source):
        self._check(source)
        row = self.rows[source]
        return [vertex for vertex in range(self.count) if row & (1 << vertex)]


if __name__ == "__main__":
    routes = ReachabilitySnapshot(6, [(0, 1), (1, 2), (2, 0), (2, 4), (4, 5)])
    print(routes.reaches(0, 5), routes.reaches(5, 0))
    print(routes.reachable_from(1))

Output

True False
[0, 1, 2, 4, 5]

Time, space, and tradeoff

The loop runs O(V squared) Python row tests and up to O(V squared) big-integer unions; a row spans O(V) bits, so the machine-word model is O(V cubed divided by word width) work and O(V squared) bits of storage. Python big integers allocate and scan multiple internal words, so a bit test is not a strict hardware O(1) claim for unbounded V. Listing every destination costs O(V). Breadth-first search costs O(V+E) for one source on demand and may be preferable for a large graph with few reachability queries.

Common Mistakes

• Do not confuse directed reachability with undirected connectivity.
• Do not leave out each vertex's self bit when zero-edge paths count.
• Do not reuse this matrix after graph topology changes.
• Do not claim Python big-integer operations cost one CPU instruction for arbitrary graph size.

Connected lessons

• Graphs
• Data Structures
• Dense graph bitsets: adjacency and common neighbors
• Graphs: adjacency lists and breadth-first reachability
• CSR graphs: pack sparse neighbors for repeated scans
• Projects
• Quizzes

Compare its input and update contract with CSR delta overlays: stage road edits before compaction, Gap labels: compare dispatch order across middle inserts, Skew heaps: meld priorities by swapping child paths, then complete the structure audit and decision quiz.

Condensation DAGs: compress directed cycles before path queries adds a related structure with a different operation boundary.