Expand description
A mutable directed graph supporting incremental edge insertion and deletion.
DynamicGraph is the substrate for the streaming-update algorithms in this
module (incremental PageRank, incremental SCC). Unlike the immutable
AdjacencyList, it maintains
both the forward and reverse adjacency in lock-step and tracks the
multiplicity of every ordered pair so that remove_edge has well-defined
semantics on multigraphs: inserting a pair twice and removing it once leaves
the edge present with multiplicity one.
The structure is deliberately a thin, allocation-light wrapper: out- and
in-neighbour lists are kept de-duplicated (one entry per distinct neighbour)
with the parallel multiplicity stored alongside, so neighbour iteration is
O(deg) and degree queries are O(1)-amortised.
Structsยง
- Dynamic
Graph - Mutable directed graph with incremental add/remove and a reverse index.