CSR delta overlays: stage road edits before compaction

Last updated: 5 Oct 20269 min read

tutorial

Compressed sparse row storage packs sorted neighbors of each source vertex into one target array and an offset table. A road editor cannot insert one target without shifting later packed rows. A delta overlay leaves the base untouched, records added edges and tombstones for deleted base edges, and merges those three sources when serving a neighbor query. Deleting an edge that exists only in the added set cancels its addition. Adding a deleted base edge cancels its tombstone. Compaction writes the logical graph into fresh CSR arrays, then clears both overlays. This example models directed, simple edges; an undirected road would require paired updates.

Operational case

The base has road zero to one and zero to three. A dispatch edit removes zero to one and adds zero to four, so the logical neighbors of zero are three and four before compaction. Rebuilding produces the same answer and new offsets. If a previously staged addition is removed before compaction, it must not become a base tombstone; similarly, adding a deleted base edge must clear its tombstone. A reader that accesses only packed targets while edits are pending sees an obsolete snapshot, so the query path and version boundary must be explicit.

Working Python program

class RoadGraphOverlay:
    def __init__(self, vertex_count, road_edges):
        if vertex_count < 0:
            raise ValueError("negative vertex count")
        self.count = vertex_count
        self.offsets, self.targets = self._pack(road_edges)
        self.added = {}
        self.deleted = {}

    def _validate(self, source, target):
        if not (0 <= source < self.count and 0 <= target < self.count):
            raise ValueError("road endpoint outside graph")

    def _pack(self, road_edges):
        rows = [set() for _ in range(self.count)]
        for source, target in road_edges:
            self._validate(source, target)
            rows[source].add(target)
        offsets, targets = [0], []
        for row in rows:
            targets.extend(sorted(row))
            offsets.append(len(targets))
        return offsets, targets

    def neighbors(self, source):
        if not 0 <= source < self.count:
            raise ValueError("source outside graph")
        base = self.targets[self.offsets[source]:self.offsets[source + 1]]
        return sorted((set(base) - self.deleted.get(source, set())) | self.added.get(source, set()))

    def add_road(self, source, target):
        self._validate(source, target)
        self.deleted.setdefault(source, set()).discard(target)
        if target not in self.targets[self.offsets[source]:self.offsets[source + 1]]:
            self.added.setdefault(source, set()).add(target)

    def remove_road(self, source, target):
        self._validate(source, target)
        self.added.setdefault(source, set()).discard(target)
        if target in self.targets[self.offsets[source]:self.offsets[source + 1]]:
            self.deleted.setdefault(source, set()).add(target)

    def compact(self):
        edges = [(source, target) for source in range(self.count) for target in self.neighbors(source)]
        self.offsets, self.targets = self._pack(edges)
        self.added.clear()
        self.deleted.clear()


if __name__ == "__main__":
    roads = RoadGraphOverlay(5, [(0, 1), (0, 3), (1, 2), (3, 4)])
    roads.remove_road(0, 1)
    roads.add_road(0, 4)
    print(roads.neighbors(0), roads.neighbors(3))
    roads.compact()
    print(roads.neighbors(0), roads.offsets)

Output

[3, 4] [4]
[3, 4] [0, 2, 3, 3, 4, 4]

Time, space, and tradeoff

Building or compacting from E logical edges costs O(V+E log D) here because every vertex's degree-D row is sorted, and uses O(V+E) base storage. A neighbor read copies its base row and combines overlay sets, then sorts the result, costing O(D+ A + T + R log R) for base degree D, staged additions A, tombstones T, and result size R. Python list membership checks in add and remove cost O(D). Overlay storage grows with un-compacted edits. This is a single-process model without atomic publication; a real concurrent graph reader needs a snapshot or synchronization protocol.

Common Mistakes

Do not query the packed base alone while edits are staged.
Do not store an added edge and a tombstone for the same logical edge.
Do not treat one directed edit as an undirected road update.
Do not clear overlays before the rebuilt CSR arrays are ready.

Connected lessons

Compare its input and update contract with Reachability bitsets: precompute directed paths for a fixed graph, 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.

data structures

range-query-structures