Graph rewriting · Rust
Graphs as
a first-class
expression.
Construct, transactionally mutate, and pattern-match graphs — inside a Rust process.
Three small DSLs built on macro_rules! — no procedural macros — overload Rust's operators so an edge is just ^, >>, <<. Every fragment is a plain struct you can build and compose in code.
let g: Undir0 = graph![ N(0) ^ (N(1) ^ (N(2) ^ n(0))) ].unwrap();
Three verbs
Build, mutate, match.
One macro for each thing you do to a graph. Each returns plain Rust — reach past the macro to from_fragment(), modify(), or compile() whenever you want.
Construction
A graph literal, the way vec! is a vector literal. Group fragments to chain edges; back-reference a node to close a cycle.
let g: Undir0 = graph![ N(0) ^ (N(1) ^ N(2)) ].unwrap(); // path 0 — 1 — 2
Transactional mutation
Add, remove, and rewire nodes and edges atomically. The change applies as one unit or not at all.
let mut g: Undir0 = Graph::default(); modify!(g, [N(1) ^ N(2)]).unwrap(); // node_count == 2, edge_count == 1
Pattern matching
Compile a pattern into a query and iterate every valid mapping. Cluster patterns into get (required) and ban (forbidden).
let s = search![&g, get(Mono) { N(0) ^ N(1) } ].unwrap(); // iterate every matching edge
The signature
Six morphisms, one lattice.
A morphism maps pattern nodes to target nodes while preserving edges. Three independent axes decide how strict that mapping is — and the eight combinations that matter collapse into six named morphisms, ordered from exact to anything-goes.
| Iso | Exact match — same shape, same size, same edges. |
| SubIso | Find this exact shape inside the target. |
| EpiMono | 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.
Graph model
One type, three kinds of edge.
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.