Build a graph, mutate it transactionally, run patterns over it, consume the matches — one loop, inside a Rust process.
Three small DSLs overload Rust's operators so an edge is just ^, >>, << — and a variable-length path is just ... mgraph! and modify! are macro_rules!; search! is a procedural macro from grw_derive.
A microservice fleet: services are nodes, calls are directed edges, latencies are edge values. A deploy sneaks in a circular dependency — patterns find it, modify! removes it, navigation proves the deploy still paid off. Every snippet below is extracted from tests/site_story.rs and runs in the test suite.
act 2 modify! — the deploy, one atomic transaction
// add a cache between orders and db — plus an
// accidental callback edge billing → ordersgrw::modify!(g, [
X(2) & E().val(1) >> N(0).val("cache"),
n(0) & E().val(2) >> x(3),
x(4) & E().val(5) >> x(2)
]).unwrap();
// applies as one unit — or not at all
act 3 · search!
Ask the graph questions.
Each query is drawn in pattern space: amber nodes are what you bind, rose is what must not exist, dashes are variable-length paths.
// entry points: nobody calls themsearch![&g, get(Mono) {
!N(1) >> N(0)
}]
// → only the gateway
// redundant shortcut: chain + direct edgesearch![&g, get(Mono) {
N(0) >> N(1),
n(1) >> N(2),
n(0) >> n(2)
}] // orders → billing → db, plus orders → db
// circular dependenciessearch![&g,
get(Homo) { N(0), N(1) },
get(Mono) { n(0) >> ..n(1).dfs().len(1..) }
] // Homo lets 0 and 1 collapse onto one node
consume the Match — addressed by your own numbering
for m in &session {
let caller = m[0]; // Index: absence = buglet callee = m.get(1).unwrap(); // Option: tolerantlet tm = session.translate(&m); // ids → valueslet (_, name) = tm.node(LocalId(0)).unwrap();
}
// cycles: filter on the mapping itself,
// and read the concrete path behind the edge
session.iter()
.filter(|m| m[0] == m[1] && !m.path(0).is_empty())
.count() // 1 — billing → orders closed a loop
act 4 modify! — remove the edge, prove it's gone
grw::modify!(g, [x(4) & !e() >> x(2)]).unwrap();
// re-run the same cycle pattern:
session.iter()
.filter(|m| m[0] == m[1] && !m.path(0).is_empty())
.count() // 0 — fleet is acyclic again
act 5 navigate — the deploy still paid off
let cfg = Config::new(())
.navigate(Dijkstra::weighted(|ms: &u32| *ms asf64));
let (cost, path) = g
.path_navigate(N(0), N(3), outgoing, cfg, &constraint)
.next()
.unwrap();
// before the deploy: gw → orders → billing → db = 8 ms
// after: gw → orders → cache → db = 6 ms
Variable-length paths
A path is just ..
Prefix a pattern node with .. and the edge becomes a variable-length path: traversal, length bounds, or cost-ordered navigation — all lazy, one path per next(). Full chapter in the book →
..n(1).dfs() // deepest-first simple paths
..n(1).bfs().len(3..10) // shortest-first, 3–9 edges
..n(1).navigate(Dijkstra::counted()) // cheapest by hop count
..n(1).navigate(Dijkstra::weighted(|ev: &EV| ev.cost)) // cheapest by edge weight
..n(1).navigate(AStar::new(|ev| ev.cost, |n| h(n))).all() // every simple path, cost-ordered
..n(1).dfs().guard(|p| !p.contains(N(2))) // prune paths mid-walk
..n(1).drive(|n| Some(Explore::One(0))) // steer expansion per depth
Measured, not claimed
Against VF3.
Head-to-head with vf3lib — the reference subgraph-isomorphism implementation — via its C++ API, using its bulk ARGLoader path. GRW runs each search four ways: enumerate yields every Match (what you pay when you consume bindings); count never materializes one — each sequential and parallel (8 cores / 16 threads). Every cell's five counts are verified equal before any timer is trusted. Cells are speedup vs VF3, time in parens.
nodes
morphism
matches
VF3
seq
seq count
par
par count
10,458
subiso
1.95M
377ms
2.6× (146ms)
7.2× (53ms)
19× (20ms)
44× (8.6ms)
10,458
mono
344k
70ms
3.5× (20ms)
16× (4.4ms)
16× (4.2ms)
59× (1.2ms)
104,374
subiso
3.50M
844ms
3.0× (280ms)
7.4× (115ms)
19× (45ms)
36× (23ms)
104,374
mono
3.50M
805ms
4.0× (199ms)
18× (46ms)
24× (34ms)
50× (16ms)
253,122
subiso
8.53M
2.29s
3.2× (721ms)
7.0× (326ms)
22× (105ms)
38× (60ms)
253,122
mono
8.53M
2.22s
4.5× (492ms)
19× (115ms)
26× (85ms)
64× (35ms)
503,122
subiso
17.2M
4.80s
3.1× (1.54s)
6.4× (755ms)
22× (219ms)
36× (133ms)
503,122
mono
17.3M
4.59s
4.4× (1.05s)
19× (245ms)
29× (159ms)
66× (69ms)
1,013,122
subiso
34.7M
10.08s
2.8× (3.58s)
5.9× (1.71s)
18× (573ms)
29× (351ms)
1,013,122
mono
34.7M
9.66s
4.5× (2.15s)
17× (579ms)
26× (368ms)
62× (156ms)
iso is not tabulated: on this corpus it reduces to microsecond-scale pattern-vs-pattern checks (GRW 2–3× ahead) — too small to time against parallel variants. Counting a million-node graph's 34.7M mono matches takes 156 ms. Loading it: ~0.3 s for GRW (82 ms load + 203 ms CSR index) vs ~4 s for the vf3 build. Heaviest pattern per tier shown; pattern sizes capped on large graphs (subiso/mono ≤ 3 nodes from 29k up); one machine, single runs. All rows use the mutable store (MGraph); the versioned store reaches the same index at 3.7× build cost and searches at parity — measured below. Full protocol: grw_vf3_tests — clone, ./gen_data.sh, cargo build --release, ./bench_all.sh.
Mutable vs versioned.
GRW ships two stores behind one read trait: MGraph, built with mgraph!, mutates in place; VGraph, built with vgraph! — same DSL, versioned result — is persistent — every modify returns a new version, old versions stay live, structure is shared. The price is paid on writes and raw scans; through the search index the two are indistinguishable — and keeping a version costs 20 ns, flat, at any size. 1M nodes / 2M edges, median of 3:
measurement
MGraph
VGraph
V / M
bulk build
602ms
10.49s
17.4×
1000 small modifies
1.7ms
23.2ms
13.5×
full edge scan
1.9ms
25.0ms
13.2×
index build (CSR)
208ms
777ms
3.7×
search (triangle, mono)
1.41s
1.45s
1.03×
snapshot / keep a version
29.8ms
20ns
~0
Same story at 10k and 100k nodes: search within 4% either way, version retention flat at 20 ns while a deep copy grows linearly (213 µs → 3.1 ms → 29.8 ms). Reproduce: cargo run --release --example graph_perf -- 1000000 3 42 in the grw repo.
The book
Each piece, in depth.
Every feature on this page has a full chapter — syntax tables, edge cases, and runnable examples.
A Graph<NV, ER> is parameterized by its node-value type and its edge relation. The relation picks which operators are legal and how many edges can sit between any two nodes.
^
edge::Undir<EV>
One undirected edge between two nodes. Slot: UND.
>> <<
edge::Dir<EV>
Up to two directed edges — one incoming, one outgoing. Slots: SRC, TGT.
^ >> <<
edge::Anydir<EV>
All three at once — undirected plus both directions. Slots: UND, SRC, TGT.
The theory underneath
Six morphisms, one lattice.
Every get and ban above names one of these. A morphism maps pattern nodes to target nodes while preserving edges; three independent axes decide how strict that mapping is, and they collapse into six named morphisms, ordered from exact to anything-goes. Chapter →
Bijection, but extra edges between matched nodes are OK.
Mono
Each pattern node gets a unique target; extra edges OK.
Epi
Must cover all target nodes; can collapse pattern nodes.
Homo
Anything goes — just preserve edges.
Going up the lattice adds constraints; going down relaxes them. The meet() of two morphisms is the most relaxed one that still satisfies both. Clusters with different morphisms compose under one rule — two nodes may share a target iff they are not both injective — with the nuances drawn out in Mixing Clusters & Morphisms.