Versioned Graphs

MGraph mutates in place: modify! takes &mut self and the graph you had is the graph you now have. VGraph is the same graph as a value. Every edit returns a new graph and leaves the old one exactly as it was — readable, searchable, and still yours.

let (g2, _) = g1.modify(modify![X(0).val(99u32)]).unwrap();

assert_eq!(g2.node_val(id::N(0)), Some(&99));
assert_eq!(g1.node_val(id::N(0)), Some(&1));   // g1 never moved

Nothing is copied to make that true. Nodes and edges live in a persistent 32-way trie; an edit rebuilds only the path from the root to what changed and shares every untouched subtree with its parent version. Cloning a VGraph copies a handful of trie roots and bumps some refcounts — it does not walk the graph.

That buys three things at once: snapshots you can hand to another thread without a lock, rollback that is just keeping the older binding around, and history — a version chain is nothing more than the versions you chose not to drop.

let mut history = vec![g1.clone()];
let mut g = g1;
for i in 2..6 as grw::Id {
    let (next, _) = g.modify(modify![N(i) ^ x(0)]).unwrap();
    history.push(next.clone());
    g = next;
}

let counts: Vec<usize> = history.iter().map(|h| h.node_count()).collect();
assert_eq!(counts, vec![2, 3, 4, 5, 6]);

Quick start

vgraph! is mgraph! with a versioned result — same DSL, same aliases with a V in front of them:

let g: VUndir0 = vgraph![N(0) ^ (N(1) ^ (N(2) ^ n(0)))].unwrap();
assert_eq!(g.node_count(), 3);
assert_eq!(g.edge_count(), 3);
assert_eq!(g.version(), 0);

VGraph::new() gives an empty graph at version 0.

Modifying: &self in, a new graph out

modify takes &self and returns (next_graph, Modification) — the same Modification record the mutable side returns, reporting new ids, added edges, removed nodes and swapped values.

let (g2, m) = g1.modify(modify![X(0).val(99u32)]).unwrap();
assert_eq!(m.swapped_node_vals.len(), 1);
assert_eq!(g1.version(), 0);
assert_eq!(g2.version(), 1);

Freshly added nodes report their real ids exactly as they do for MGraph:

let (g1, m) = g0.modify(modify![N(7)]).unwrap();
assert_eq!(*m.new_node_ids[&modify::LocalId(7)], 0);

The whole modify! DSL carries over unchanged — N/X/!X, E/e/!e, .val(..), back-references, all three edge kinds. The only difference is where the result lands.

Versions are yours to choose

version() reads the graph’s current version. Plain modify advances it by one. When the version number means something in your system — a transaction id, a logical clock, a commit counter — modify_versioned lets you stamp it directly:

let (g7, _) = g1.modify_versioned(modify![N(2) ^ x(0)], 7).unwrap();
assert_eq!(g7.version(), 7);
assert_eq!(g7.node_gen(id::N(2)), Some(7));   // born at 7
assert_eq!(g7.node_gen(id::N(0)), Some(1));   // untouched since 1

Versions only ever go up. A requested version that does not strictly advance the current one is refused, and no graph is produced:

let Err(err) = g5.modify_versioned(modify![N(2)], 4) else {
    panic!("a version that does not advance must be refused")
};
assert!(matches!(
    err,
    error::Modify::Version(error::Version::NotMonotonic { current: 5, requested: 4 })
));
assert_eq!(g5.version(), 5);

Monotonicity is what makes generations mean anything: a version stamped on a node is a point on a line, not a label that might come round again.

Stable identity: slot + generation

Node ids are slots, and slots are recycled — remove a node and the next insertion may land on the same id. That is fine for a graph you hold once, and a trap for anything that remembers ids across edits: a stale id::N(1) will happily resolve to a stranger.

stable_id closes it. It returns (slot, generation), where the generation is the version at which the occupant of that slot was born:

let before = g1.stable_id(id::N(1)).unwrap();
let (g2, _) = g1.modify(modify![!X(1)]).unwrap();
let (g3, _) = g2.modify(modify![N(9)]).unwrap();
let after = g3.stable_id(id::N(1)).unwrap();

assert_eq!(before.0, after.0);   // same slot, recycled
assert_ne!(before.1, after.1);   // different birth version
assert_eq!(after.1, 3);

Hold (slot, generation) rather than a bare id and a recycled slot can never impersonate the node you meant. node_gen and edge_gen read the stamp on its own when you already know the id is live.

Atomicity: an Err produces no version at all

A rejected batch is not a partial edit and not an empty one — it is no edit. There is no new graph to look at, the original is untouched, and the id space is not disturbed: a slot the failed batch would have consumed is still there for the next one.

assert!(v.modify(modify![N(9) ^ x(0), x(0) ^ x(1)]).is_err());

let (next, m) = v.modify(modify![N(7)]).unwrap();
assert_eq!(*m.new_node_ids[&modify::LocalId(7)], 2);   // slot 2, not 3
assert_eq!(next.version(), 1);
assert_eq!(v.version(), 0);

This falls out of the shape of the API rather than being defended by bookkeeping. modify builds the next graph off to the side and only hands it back on success; on failure the value it was building is simply dropped, and v — which was never borrowed mutably — is trivially intact.

The two-way door

VGraph and MGraph are two representations of one graph model, and you can cross between them at will. Convert when the workload changes: batch-build in MGraph where in-place mutation is cheapest, then freeze into a VGraph for snapshotting and sharing.

let m = v.to_mgraph();
assert_eq!(m.node_count(), v.node_count());

let back = VGraph::from_mgraph(&m);
assert_eq!(back.version(), 0);   // conversion is not an edit

Node ids survive a round trip, tombstones and all — a graph with a hole at slot 1 still has that hole afterwards, and the next insertion still fills it. Edge ids are reassigned, exactly as they are by MGraph::from_graph.

Persistence crosses the same door. There is one .grw format (v3), not two: a file written by either side loads into either side.

let (v, _) = v.modify(modify![N(9) ^ x(0)]).unwrap();
v.save(&path).unwrap();

let v2: VUndir0 = VUndir0::load(&path).unwrap();
assert_eq!(v2.version(), v.version());              // V-as-V: version round-trips
assert_eq!(v2.node_gen(id::N(9)), v.node_gen(id::N(9)));

let m: graph::MUndir0 = MGraph::load(&path).unwrap();
assert_eq!(m.node_count(), v.node_count());

Generations and version are real fields in the v3 format, not just runtime bookkeeping — loading the same file back into a VGraph restores them exactly. They are lost only crossing into MGraph: m above has no generation or version fields to hold them, so MGraph::load silently drops whatever the file carried — the one deliberate loss the format documents (MGraph::load’s own doc comment calls it out). Save m back out and load that file as a VGraph and every node’s generation reads 0: an MGraph-sourced file has no other generation to report, which is exactly MGraph’s own concept of history — it doesn’t have one.

Search is unchanged

The engine never learned about versioning. It reads targets through the Graph trait, and VGraph implements that trait, so indexing and searching a versioned graph is the same call on the same tiers with the same results:

let m_hits = Seq::search(query, &m.index(RevCsr)).unwrap().count();
let v_hits = Seq::search(query, &v.index(RevCsr)).unwrap().count();
assert_eq!(v_hits, m_hits);

Every pattern in this book — clusters, morphisms, variable-length paths, negation, watchers — applies verbatim. An index is built from a particular version; keep the version alive alongside its index and both stay valid while newer versions come and go.

What v1 deliberately leaves out

• No branch merge. Versions form a chain, and forks are ordinary values you keep around. Reconciling two divergent forks is your policy to write, not the library’s to guess.
• The engine reads through the trait, and only through it. No version-aware search, no “match against v3 as of v5”. Searching a version means searching the graph you kept.
• No garbage collection of history. A version lives exactly as long as something holds it; drop the binding and its unshared trie nodes go with it.

What versioning costs

Measured against MGraph on the same 1M-node / 2M-edge random graph (avg degree 4, median of 3 runs; cargo run --release --example graph_perf -- 1000000 3 42 reproduces it):

The pattern holds at 10k and 100k nodes too. Writes and raw trait scans pay the trie’s pointer-chasing tax — roughly an order of magnitude. Build an index and the tax vanishes: search times are within a few percent either way, because the engine runs against the index, not the store. And the row that motivates the whole design: retaining a version is four Arc bumps — 20 ns flat at any size — where snapshotting MGraph is a deep copy that grows linearly (213 µs at 10k, 3.1 ms at 100k, 29.8 ms at 1M).

VGraph has no bulk constructor by design — bulk load is one modify carrying all the ops, which still path-copies per element. If you are assembling a large graph from scratch, build it as MGraph and convert; the two-way door (VGraph::from_mgraph / to_mgraph) preserves slots and ids.