Dense graph bitsets: adjacency and common neighbors

Last updated: 4 Oct 20269 min read

tutorial

A bitset adjacency matrix stores one row of edge flags for each vertex. The bit at column j in row i means that vertex i connects to vertex j. This undirected depot graph mirrors every update across the two rows and rejects self-edges. Python integers hold each row, so the structure has no fixed machine-word vertex limit. Bitwise intersection followed by population count answers how many neighbors two depots share without materializing two Python sets. This representation is useful when the vertex set is fixed, adjacency is dense, or intersections dominate; it spends space even on absent edges.

Operational case

D-19 connects to D-26 and D-47. D-61 also connects to D-26 and D-47, so the intersection of their rows has two set bits. Deleting the D-19 to D-47 edge leaves D-19 with one neighbor, D-26, and the direct adjacency query for D-47 becomes false. Repeated connect and disconnect calls are idempotent in this implementation. A different API could reject duplicates or absent removals, but callers must know which contract they are using. Vertex additions are not supported after construction because every existing row's column layout would need to agree on the new mapping.

Working Python program

"""Undirected adjacency bitsets for fixed, dense depot IDs."""


class DepotBitGraph:
    def __init__(self, depot_ids):
        self.depot_ids = tuple(depot_ids)
        if len(set(self.depot_ids)) != len(self.depot_ids):
            raise ValueError("duplicate depot")
        self.position = {depot_id: index for index, depot_id in enumerate(self.depot_ids)}
        self.rows = [0] * len(self.depot_ids)

    def _pair(self, first, second):
        left, right = self.position[first], self.position[second]
        if left == right:
            raise ValueError("self-edge")
        return left, right

    def connect(self, first, second):
        left, right = self._pair(first, second)
        self.rows[left] |= 1 << right
        self.rows[right] |= 1 << left

    def disconnect(self, first, second):
        left, right = self._pair(first, second)
        self.rows[left] &= ~(1 << right)
        self.rows[right] &= ~(1 << left)

    def adjacent(self, first, second):
        left, right = self._pair(first, second)
        return bool(self.rows[left] & (1 << right))

    def common_neighbor_count(self, first, second):
        left, right = self._pair(first, second)
        return (self.rows[left] & self.rows[right]).bit_count()

    def neighbors(self, depot_id):
        row = self.rows[self.position[depot_id]]
        result = []
        while row:
            lowest_bit = row & -row
            result.append(self.depot_ids[lowest_bit.bit_length() - 1])
            row ^= lowest_bit
        return result


graph = DepotBitGraph(("D-19", "D-26", "D-47", "D-61"))
for first, second in (("D-19", "D-26"), ("D-19", "D-47"), ("D-61", "D-26"), ("D-61", "D-47")):
    graph.connect(first, second)
print(graph.common_neighbor_count("D-19", "D-61"))
graph.disconnect("D-19", "D-47")
print(graph.neighbors("D-19"))
print(graph.adjacent("D-19", "D-47"))

Output

2
['D-26']
False

Time, space, and tradeoff

For V vertices, a conceptual bit matrix uses V² bits, or O(V²/W) machine words of W bits, plus vertex-ID lookup storage. In Python, each row is an arbitrary-precision integer with object overhead. A row update or adjacency check may scan or copy O(V/W) words rather than being constant time for unbounded V. A common-neighbor intersection and bit count similarly cost O(V/W) word work. Enumerating D set neighbors with repeated low-bit extraction performs D big-integer operations and returns O(D) values. Sparse adjacency lists need O(V+E) entries for E edges and usually win on memory when E is small; packed CSR is better for an immutable sparse graph scan.

Common Mistakes

Do not update only one row of an undirected adjacency matrix.
Do not assume Python arbitrary-precision bit operations are constant time for every V.
Do not use V²-bit storage for a huge graph with few edges without measuring the memory cost.
Do not treat common-neighbor count as proof of connectivity or shortest-path length.

Connected lessons

Use this invariant in the dispatch audit project, then check the operations quiz.

Bitvector rank and select: count and locate set bits adds a related operation contract.

Reachability bitsets: precompute directed paths for a fixed graph adds a related structure with a different operation boundary.

data structures

range-query-structures