GRW — Graph Rewriting in Rust

GRW is an embedded graph rewriting system that runs inside a Rust process. It provides type-safe domain-specific languages for graph construction, transactional mutation, and morphism-based pattern matching.

The Three DSLs

• mgraph! — graph literal (like vec!) for constructing graphs declaratively
• modify! — transactional graph mutation: add/remove/change nodes and edges atomically
• search! — graph pattern matching iterator with morphism control

A link between two nodes can hold a composite value: several typed parts, included, excluded and searched for one at a time.

All DSL fragments are plain Rust structs — they can be constructed, composed, and manipulated programmatically before being passed to the macros or the underlying from_fragment() / modify() / compile() functions directly.

The graph and modify DSLs — mgraph!, vgraph! and modify! — are macro_rules! macros that overload Rust operators (^, >>, <<, &, !) to express graph edge semantics. search! and pattern! are procedural macros whose pattern grammar lives in the grw_pattern crate; they, the #[grw::repl] attribute, #[derive(Val)] and #[derive(Part)] come from grw_derive, a required dependency of grw.

Quick Example

use grw::*;
use grw::graph::edge;

// construct a triangle
let g: graph::MUndir0 = mgraph![
    N(0) ^ (N(1) ^ (N(2) ^ n(0)))
].unwrap();

// search for edges (Mono morphism)
let session = search![&g,
    get(Mono) { N(0) ^ N(1) }
].unwrap();

for m in &session {
    let a = m.get(0).unwrap();
    let b = m.get(1).unwrap();
    println!("{:?} — {:?}", a, b);
}

Links

• GitHub
• Codeberg

Graph Model

A graph MGraph<NV, ER> is parameterized by two type parameters:

• NV — node value type (use () for no attributes)
• ER — edge relation type, which determines the edge topology

Edge Types

GRW supports three edge relation types:

Between any two nodes, there can be at most one edge per slot. This means:

• Undirected graphs allow 1 edge per node pair
• Directed graphs allow 2 edges per node pair (one in each direction)
• Anydirected graphs allow 3 edges per node pair (both directions + undirected)

If you need several relations between the same pair with the same orientation, make the edge value a composite: one link holding several typed parts, at most one per kind.

Type Aliases

Common configurations have convenient aliases:

// Undirected
type MUndir0      = MGraph<(), edge::Undir<()>>;      // no attributes
type MUndirN<NV>  = MGraph<NV, edge::Undir<()>>;      // node values only
type MUndirE<EV>  = MGraph<(), edge::Undir<EV>>;      // edge values only
type MUndir<N, E> = MGraph<NV, edge::Undir<EV>>;      // both

// Directed
type MDir0         = MGraph<(), edge::Dir<()>>;
type MDirN<NV>     = MGraph<NV, edge::Dir<()>>;
type MDirE<EV>     = MGraph<(), edge::Dir<EV>>;
type MDir<NV, EV>  = MGraph<NV, edge::Dir<EV>>;

// Anydirected
type MAnydir0         = MGraph<(), edge::Anydir<()>>;
type MAnydirN<NV>     = MGraph<NV, edge::Anydir<()>>;
type MAnydirE<EV>     = MGraph<(), edge::Anydir<EV>>;
type MAnydir<NV, EV>  = MGraph<NV, edge::Anydir<EV>>;

Node and Edge Access

// count
g.node_count()
g.edge_count()

// check existence
g.has(0)              // node by Id
g.has((0, 1))         // edge between nodes

// get values
g.get(0)              // Option<&NV>
g.get_mut(edge::undir::E::U(0, 1))  // Option<&mut EV> — edge values only

// iterate
for (nid, val) in g.node_iter() { /* ... */ }
for (edef, val) in g.edge_iter() { /* ... */ }

// adjacency
g.is_adjacent(0, 1)

// edge relation (typed access to all edges between a pair)
let rel = g.rel((0, 1));   // returns Rel with typed slot access

get_mut takes edge keys only. A node value cannot be mutated in place — it feeds the index tables, so it changes only through modify!, which releases the old keys and claims the new ones in the same transaction.

mgraph! — Construction

The mgraph! macro constructs a graph from a declarative description of nodes and edges.

DSL Primitives

Operator Precedence

The edge operators (^, >>, <<) are left-associative in Rust. This has an important consequence:

• Flat chaining N(0) ^ N(1) ^ N(2) creates a star — all edges radiate from node 0
• Grouping N(0) ^ (N(1) ^ N(2)) creates a path — 0 connects to 1, 1 connects to 2

This is because N(0) ^ N(1) returns node 0 (with an edge to 1 attached), so the next ^ N(2) adds another edge from 0.

Undirected Graphs

Path (grouping)

use grw::graph::{self, MGraph, edge};

// path: 0 — 1 — 2
let g: MGraph<(), edge::Undir<()>> = mgraph![
    N(0) ^ (N(1) ^ N(2))
].unwrap();

Triangle (back-reference)

// triangle: chain + n() closes the cycle
let g: MGraph<(), edge::Undir<()>> = mgraph![
    N(0) ^ (N(1) ^ (N(2) ^ n(0)))
].unwrap();

Star (flat chaining)

// star: flat chaining fans out from one node
let g: MGraph<(), edge::Undir<()>> = mgraph![
    N(0) ^ N(1)
         ^ N(2)
         ^ N(3)
         ^ N(4)
].unwrap();

With Values

// node values
let g: MGraph<&str, edge::Undir<()>> = mgraph![
    N(0).val("alice") ^ (N(1).val("bob") ^ N(2).val("carol"))
].unwrap();

// edge values — & E().val(...) before direction operator
let g: MGraph<(), edge::Undir<f64>> = mgraph![
    N(0) & E().val(1.5) ^ (N(1) & E().val(2.0) ^ N(2))
].unwrap();

// both
let g: MGraph<&str, edge::Undir<u32>> = mgraph![
    N(0).val("a") & E().val(10) ^ N(1).val("b")
].unwrap();

Composite Edge Values

When the edge value is a composite (for example TypeSet<P>), E().include(p).include(q) builds one link holding both parts; naming one kind twice on a link is a typed build error. See Composite Values.

Anonymous Nodes

// ids assigned automatically
let g: MGraph<(), edge::Undir<()>> = mgraph![N_() ^ N_() ^ N_()].unwrap();

Directed Graphs

// path: 0 → 1 → 2
let g: MGraph<(), edge::Dir<()>> = mgraph![
    N(0) >> (N(1) >> N(2))
].unwrap();

// fan-out: flat chaining from one node
let g: MGraph<(), edge::Dir<()>> = mgraph![
    N(0) >> N(1)
         >> N(2)
         >> N(3)
].unwrap();

// bidirectional: n() references existing nodes
let g: MGraph<(), edge::Dir<()>> = mgraph![
    N(0) >> N(1),
    n(1) >> n(0),
].unwrap();

// incoming edges with <<
let g: MGraph<(), edge::Dir<()>> = mgraph![
    N(0) << N(1),   // edge from 1 to 0
].unwrap();

Anydirected Graphs

Mix undirected and directed edges in one graph:

let g: MGraph<(), edge::Anydir<()>> = mgraph![
    N(0) ^ (N(1) >> N(2)),  // 0 — 1 → 2
    N(3) << n(2),            // 2 → 3
].unwrap();

// all three edge types between one pair
let g: MGraph<(), edge::Anydir<()>> = mgraph![
    N(0) ^ N(1),         // undirected
    n(0) >> n(1),        // directed 0 → 1
    n(1) >> n(0),        // directed 1 → 0
].unwrap();

Turbofish Syntax

When the type can’t be inferred, use the turbofish form:

let g = mgraph![<(), grw::graph::edge::Undir<()>>; N(0) ^ N(1)].unwrap();

Multiple Fragments

Use commas to separate disconnected components or back-references:

// two separate edges, then connect them
let g: MGraph<(), edge::Undir<()>> = mgraph![
    N(0) ^ N(1),
    N(2) ^ N(3),
    n(0) ^ n(2),
].unwrap();

modify! — Mutation

modify! applies transactional changes to an existing graph — adding nodes, removing nodes, adding/removing edges, and swapping values — all atomically. It returns a Modification describing everything that changed.

DSL Primitives

Adding Nodes and Edges

use grw::graph::{self, MGraph, edge};

let mut g: MGraph<(), edge::Undir<()>> = MGraph::default();

// add two connected nodes
modify!(g, [N(1) ^ N(2)]).unwrap();
assert_eq!(g.node_count(), 2);
assert_eq!(g.edge_count(), 1);

// connect new node to existing
modify!(g, [X(0) ^ N(3)]).unwrap();
assert_eq!(g.node_count(), 3);
assert_eq!(g.edge_count(), 2);

let mut g: MGraph<(), edge::Dir<()>> = MGraph::default();

// directed path
modify!(g, [N(1) >> (N(2) >> N(3))]).unwrap();
assert_eq!(g.node_count(), 3);
assert_eq!(g.edge_count(), 2);

let mut g: MGraph<(), edge::Undir<()>> = MGraph::default();

// triangle via back-reference
modify!(g, [N(1) ^ (N(2) ^ (N(3) ^ n(1)))]).unwrap();
assert_eq!(g.node_count(), 3);
assert_eq!(g.edge_count(), 3);

With Values

let mut g: MGraph<&str, edge::Undir<u32>> = MGraph::default();

// node and edge values
modify!(g, [
    N(1).val("a") & E().val(42u32) ^ N(2).val("b")
]).unwrap();
assert_eq!(g.node_count(), 2);
assert_eq!(g.edge_count(), 1);

// isolated node
modify!(g, [N(3).val("c")]).unwrap();
assert_eq!(g.node_count(), 3);

Removing Nodes and Edges

let mut g: MGraph<(), edge::Undir<()>> = MGraph::default();
modify!(g, [N(1) ^ N(2) ^ N(3)]).unwrap();

// remove node 1 (and its edges)
modify!(g, [!X(1)]).unwrap();
assert_eq!(g.node_count(), 2);

let mut g: MGraph<(), edge::Dir<()>> = MGraph::default();
modify!(g, [N(1) >> N(2)]).unwrap();

// remove edge, keep both nodes
modify!(g, [X(0) & !e() >> x(1)]).unwrap();
assert_eq!(g.node_count(), 2);
assert_eq!(g.edge_count(), 0);

Updating Values

A node value changes only through modify! — there is no get_mut for one — because the swap must release the value’s old index keys and claim its new ones, and adjust the degree tables, in the same transaction.

let mut g: MGraph<&str, edge::Undir<()>> = MGraph::default();
modify!(g, [N(1).val("old")]).unwrap();
assert_eq!(g.get(0), Some(&"old"));

// swap node value
modify!(g, [X(0).val("new")]).unwrap();
assert_eq!(g.get(0), Some(&"new"));

let mut g: MGraph<(), edge::Undir<u32>> = MGraph::default();
modify!(g, [N(1) & E().val(100u32) ^ N(2)]).unwrap();

// swap edge value
modify!(g, [X(0) & e().val(200u32) ^ X(1)]).unwrap();

Parts of a Composite Link

On a graph whose edge value is a composite, a link changes part by part: E().include(p), E().exclude::<T>() and E().exclude_kind(k), while !e() still deletes the whole link. The combinator decides what a link with no parts left means — TypeSet removes it. Refusals are typed (PartRejected, PartNotHeld, PartConflict). See Composite Values.

Modification Result

The returned Modification struct contains:

• new_node_ids — mapping from local ids to real graph ids
• added_edges — edges that were created
• removed_nodes / removed_edges — what was deleted
• swapped_node_vals / swapped_edge_vals — old values that were replaced

let mut g: MGraph<(), edge::Undir<()>> = MGraph::default();
let result = modify!(g, [N(1) ^ N(2)]).unwrap();

// the local id 1 was assigned a real graph node id
let real_id = result.new_node_ids[&LocalId(1)];

Color Legend for Diagrams

Throughout this documentation:

• Blue — added or changed elements
• Red dashed — removed elements
• Black — existing, unchanged elements

search! — Pattern Matching

search! compiles a pattern into a query and iterates over all morphism-valid mappings from pattern nodes to target graph nodes. Patterns are organized into clusters — get (required) and ban (forbidden substructures).

DSL Primitives

Basic Usage

When search! receives a graph reference, it creates a Session that you iterate with a for loop:

use grw::*;
use grw::graph::edge;

// target graph: triangle
let g: graph::MUndir0 = mgraph![
    N(0) ^ (N(1) ^ (N(2) ^ n(0)))
].unwrap();

// search for edges
let session = search![&g,
    get(Mono) {
        N(0) ^ N(1)
    }
].unwrap();

for m in &session {
    let a = m.get(0).unwrap();
    let b = m.get(1).unwrap();
    println!("{:?} — {:?}", a, b);
}

The Match Struct

Each iteration yields a Match — a mapping from pattern node local ids to graph node ids.

for m in &session {
    // get a specific pattern node's graph mapping
    let node_id: id::N = m.get(0).unwrap();

    // iterate all (pattern_local_id, graph_node_id) pairs
    for &(lid, nid) in m.iter() {
        println!("pattern {} → graph {:?}", lid.0, nid);
    }

    // just the graph node ids
    let graph_nodes: Vec<id::N> = m.values().collect();
}

TranslatedMatch

For richer access to node values and adjacencies, use translate():

for m in &session {
    let tm = session.translate(&m);

    // node with its value
    if let Some((nid, val)) = tm.node(0) {
        println!("pattern 0 → graph {:?} val={:?}", nid, val);
    }

    // all matched nodes with values
    for (lid, nid, val) in tm.nodes() {
        println!("{} → {:?} = {:?}", lid.0, nid, val);
    }
}

Ban Clusters

Ban clusters define forbidden substructures. If the ban pattern matches, the overall match is rejected. A ban is checked as a whole (“not all of these together”); the difference from banning single edges with !E(), and how a pinned node aims a ban at one specific graph node, is spelled out in Negation, Bans And Pins.

// find edges whose endpoints do NOT share a common neighbor
let session = search![&g,
    get(Mono) {
        N(0) ^ N(1)
    },
    ban(Mono) {
        n(0) ^ N(2),
        n(1) ^ n(2),
    }
].unwrap();

The n(0) and n(1) in the ban cluster refer back to the nodes defined in the get cluster. The ban says: “reject this match if nodes 0 and 1 share a common neighbor (node 2).”

Sequential vs Parallel

The Session supports two iteration modes:

// sequential — lazy iterator, one match at a time
for m in session.iter() { /* ... */ }

// also works via IntoIterator
for m in &session { /* ... */ }

// parallel — uses rayon, collects all matches
let all: Vec<Match> = session.par_iter().collect();

session.iter() is single-threaded lazy backtracking — yields one match at a time. Use this when you want to process matches as a stream or stop early.

session.par_iter() partitions the search space across threads via rayon. Use this for large graphs where you need all matches and have cores to spare.

Value Predicates

Filter matches based on node or edge values:

// find nodes where x > 10.0
let session = search![&g,
    get(Mono) {
        N(0).test(|p: &Point| p.x > 10.0) ^ N(1)
    }
].unwrap();

Parts of a Composite Link

When the edge value is a composite, a pattern edge asks the link for the parts it must hold: E().has::<T>(), chained .has::<A>().has::<B>(), a .test on the part just named, and !E().has::<T>(). Terms on one pair and slot merge into one constraint, and a pattern that could never match is a typed error of the query. See Composite Values.

Context Nodes

X(name = node_id) pins a pattern node to a specific graph node, named on the left and given its target on the right:

use grw::graph::{edge, MGraph};
use grw::{mgraph, search};

let g: MGraph<(), edge::Undir<()>> = mgraph![N(0) ^ (N(1) ^ (N(2) ^ n(0)))].unwrap();
let hub = grw::id::N(1);
let session = search![&g, get(Mono) { X(h = hub) ^ N(o) }].unwrap();
let mut neighbours: Vec<_> = session.iter().map(|m| m.get(1).unwrap()).collect();
neighbours.sort();
assert_eq!(neighbours, vec![grw::id::N(0), grw::id::N(2)]);

X(h = hub) is pinned to graph node 1 — the search only looks for nodes connected to it.

A bare X(5) or X(c) inside search![&g, ..] is a translated node with no target: the macro compiles it to an unresolved search, and building the session fails at runtime with error::Search::BoundPatternInSession. Use the pinned form above, or drop the graph and do the binding by hand — search![<NV, ER>; get(Mono) { X(5) ^ N(0) }] yields a Search::Unresolved whose bind(..) supplies the targets before the search runs.

Negation, Bans And Pins

!E() bans one edge: the match is rejected only if that specific edge exists. !X(name = id) bans a node together with every edge attached to it in that term — node and edges are one ban, checked as a unit.

That grouping is what separates “none of these” from “not all of these together”. Several independent !Es add up: each is checked on its own, so the match survives only when every one of them is absent — “none of these edges may exist”. A single !X (or an explicit ban { } block) instead bans the whole configuration it names: the ban only fires when everything inside it holds at once, so it’s satisfied — and the match survives — as soon as just one piece is missing. Two nodes p and q, both possibly connected to a node pinned to id 5, but only p actually is, show the difference:

use grw::graph::{edge, MGraph};
use grw::search::{Pattern, Session};
use grw::{mgraph, pattern};

let g: MGraph<(), edge::Undir<()>> = mgraph![N(0), N(1), N(2), n(0) ^ n(2)].unwrap();
let (p_id, q_id, five) = (grw::id::N(0), grw::id::N(1), grw::id::N(2));

// "not all of these together": one ban_only node shared by both edges.
let and_form: Pattern<(), edge::Undir<()>> = pattern![
    get(Mono) { N(p), N(q) },
    ban(Mono) { n(p) ^ N(c), n(q) ^ n(c) }
].unwrap();
let and_session =
    Session::from_pattern(&and_form, &g, &[("p", p_id), ("q", q_id), ("c", five)]).unwrap();
assert_eq!(and_session.iter().count(), 1); // only p—5 holds, so the ban can't fire

// "none of these": two separate bans, each pinned to the same node 5.
let or_form: Pattern<(), edge::Undir<()>> = pattern![
    get(Mono) { N(p), N(q) },
    ban(Mono) { n(p) ^ N(c1) },
    ban(Mono) { n(q) ^ N(c2) }
].unwrap();
let or_session =
    Session::from_pattern(&or_form, &g, &[("p", p_id), ("q", q_id), ("c1", five), ("c2", five)]).unwrap();
assert_eq!(or_session.iter().count(), 0); // p—5 alone is enough to fire the first ban

pattern! rejects X(..) outright (see Stored Patterns And Pinning), so a ban-only position pinned by external id — rather than by .val()/.test()/.key() — is spelled with a plain, named N(c) and bound afterwards through Session::from_pattern’s pins, exactly as and_form/or_form do above.

A pin on a banned position aims the ban at one specific node instead of the whole graph: “p must not be connected like this to Alice” is not the same claim as “p must not be connected like this to anyone”. Say p1 blocks Alice, p2 blocks only Bob, and p3 blocks nobody:

use grw::graph::{edge, MGraph};
use grw::{mgraph, search};

let g: MGraph<bool, edge::Dir<()>> = mgraph![
    N(0).val(true), N(1).val(true), N(2).val(true),
    N(3).val(false), N(4).val(false),
    n(0) >> n(3), // p1 -> alice
    n(1) >> n(4)  // p2 -> bob
].unwrap();
let alice = grw::id::N(3);

let session = search![&g,
    get(Mono) { N(p).val(true) >> (!X(a = alice)).test(|_: &bool| true) }
].unwrap();
let mut survivors: Vec<_> = session.iter().map(|m| m.get(0).unwrap()).collect();
survivors.sort();
assert_eq!(survivors, vec![grw::id::N(1), grw::id::N(2)]); // p2 and p3 — only p1 blocks Alice

Only p1 is dropped: the ban is checked against node alice specifically, not against every node p happens to reach. The pinned node itself, a, is never part of the match — it has no place in the get cluster’s mapping, so m.get(..) for it returns nothing; only the surviving p shows up in survivors.

Named Nodes

N(name) defines a pattern node by name instead of by integer id; n(name) refers back to it. Names lower to integer local ids at macro expansion: indices are assigned starting one past the largest integer id used anywhere in the pattern (or from 0 if no integer ids are used). Every stored Pattern carries a Names table pairing each name with its LocalId; look one up with pattern.lid("name").

use grw::graph::{edge, Graph, MGraph};
use grw::search::{Pattern, RevCsr, Seq};
use grw::{mgraph, pattern};

#[derive(Debug, Clone, Copy, PartialEq)]
enum Role { Signer, Provider }

let g: MGraph<Role, edge::Dir<()>> = mgraph![N(0).val(Role::Signer) >> N(1).val(Role::Provider)].unwrap();
let p: Pattern<Role, edge::Dir<()>> = pattern![get(Mono) { N(s: Role::Signer) >> N(p: Role::Provider) }].unwrap();
let indexed = g.index(RevCsr);
let matches: Vec<_> = Seq::search(p.query(), &indexed).unwrap().collect();
assert_eq!(matches.len(), 1);
for m in &matches {
    assert_eq!(m[p.lid("s").unwrap()], grw::id::N(0));
    assert_eq!(m[p.lid("p").unwrap()], grw::id::N(1));
}

A duplicate definition in a cluster, an undefined reference, or X(..) used inside pattern! are all compile errors — caught while expanding the macro, before the pattern ever runs. Looking up a name that isn’t in the pattern (pattern.lid("nope")) is a runtime error instead: error::Search::UnknownName.

Value Patterns

N(id: pattern) and N(name: pattern) require the node’s value to match a Rust pattern — anything valid on the right of a match arm: Some(1), Kind::A { .. }, 1..=5, A | B. E(pattern) does the same for an edge’s value.

use grw::graph::{edge, Graph, MGraph};
use grw::search::{Pattern, RevCsr, Seq};
use grw::{mgraph, pattern};

#[derive(Debug, Clone, Copy, PartialEq)]
enum Shape { Circle(u8), Square(u8) }

let g: MGraph<Shape, edge::Undir<u8>> =
    mgraph![N(0).val(Shape::Circle(1)) & E().val(7u8) ^ N(1).val(Shape::Square(2))].unwrap();
let nodes: Pattern<Shape, edge::Undir<u8>> =
    pattern![get(Mono) { N(c: Shape::Circle(_)) ^ N(s: Shape::Square(2)) }].unwrap();
let edges: Pattern<Shape, edge::Undir<u8>> = pattern![get(Mono) { N(a) & E(7) ^ N(b) }].unwrap();
let indexed = g.index(RevCsr);
assert_eq!(Seq::search(nodes.query(), &indexed).unwrap().count(), 1);
assert_eq!(Seq::search(edges.query(), &indexed).unwrap().count(), 2);

pattern![..] builds a Pattern<NV, ER> without a graph: it rejects X(..) context nodes at compile time (pattern!: context nodes X(..) are not allowed; use search![&g, ...]) and returns Result<Pattern<NV, ER>, error::Search>, giving you query(), names(), and lid().

Key Predicates

A node with an index declared on the target graph can be matched by key instead of by value predicate: .key(index, value) seeds the match with exactly the index’s hit set for that key, .key_in(index, [values]) unions the hits for several keys. Both exist on N/X (free, context, and negated-context nodes) in the same typestate slot as .test, and .test after .key/.key_in composes into a conjunction — the closure is evaluated only on the nodes the key already selected, not on the whole graph. A macro grammar form — N(a: key(INDEX, expr)) / N(a: key_in(INDEX, [exprs])), and X(name = id : key(INDEX, expr)) on a pinned context node — binds identically to the method-call form.

use grw::graph::index::{Cardinality, IndexDecl, IndexName};
use grw::graph::{edge, MGraph};
use grw::{mgraph, search};

const BY_VAL: IndexName = IndexName("by_val");

let g: MGraph<u32, edge::Undir<()>> = mgraph![
    N(0).val(10u32) ^ (N(1).val(20u32) ^ N(2).val(30u32))
].unwrap();
let g = g.with_indices(vec![
    IndexDecl::new(BY_VAL, Cardinality::Unique, |v: &u32| Some(*v)),
]).unwrap();

// method form and macro form bind identically
let by_key = search![&g, get(Mono) { N(a).key(BY_VAL, 20u32) ^ N(b) }].unwrap();
let macro_form = search![&g, get(Mono) { N(a: key(BY_VAL, 20u32)) ^ N(b) }].unwrap();
assert_eq!(by_key.iter().count(), 2); // 20—10 and 20—30
assert_eq!(macro_form.iter().count(), 2);

// key_in unions its hits
let in_set = search![&g, get(Mono) { N(a).key_in(BY_VAL, [10u32, 30u32]) ^ N(b) }].unwrap();
assert_eq!(in_set.iter().count(), 2); // 10—20 and 30—20

// a pinned context node can carry a key check too, narrowing the pin itself
let ten = grw::id::N(0);
let pinned = search![&g, get(Mono) { X(c = ten : key(BY_VAL, 10u32)) ^ N(o) }].unwrap();
assert_eq!(pinned.iter().count(), 1);

The Result change

Because a key predicate is checked against the graph’s catalogue before any matching starts, every entry point that can begin a search now returns Result<_, error::Search> instead of the bare iterator or output — even for a pattern with no key predicate at all, since the check happens at the same call: Seq::search, Seq::search_bound, Seq::search_watched, Par::search, and Par::search_bound. search![&g, ..] already returned a Result (it always could fail to build a Session), so that call site is unchanged; only the lower-level, index-explicit calls shown in Index Tiers gained the ?/.unwrap().

Two errors come out of that check, both naming the offending index:

• error::Search::IndexMissing { index } — the pattern names an index the graph doesn’t carry at all.
• error::Search::KeyTagMismatch { index } — the graph has that index, but it was declared over a different key type than the one .key/.key_in serialized here.

use grw::graph::index::IndexName;
use grw::graph::{edge, MGraph};
use grw::search::{error, RevCsr, Search, Seq};
use grw::{mgraph, search, Graph as _};

const BY_VAL: IndexName = IndexName("by_val");

let plain: MGraph<u32, edge::Undir<()>> = mgraph![N(0).val(10u32)].unwrap();
let Search::Resolved(r) = search![<u32, edge::Undir<()>>;
    get(Mono) { N(a).key(BY_VAL, 10u32) }
].unwrap() else { panic!() };

let indexed = plain.index(RevCsr);
let Err(error::Search::IndexMissing { index }) = Seq::search(r.query(), &indexed) else {
    panic!("expected IndexMissing")
};
assert_eq!(index, BY_VAL);

Session::candidate_pool(idx) exposes the resolved pool for pattern node idx as a diagnostic accessor: the ids a key predicate narrowed that node to, or the ids a closure predicate admits. It is None when the node carries no predicate at all, or when idx is not a pattern node of the session’s query — it never panics on an out-of-range index.

Stored Patterns And Pinning

A Pattern from pattern![..] compiles its query once and shares it: search![&g, p] runs it as written and borrows p, so search![&g, p] again — over the same graph or a different one — runs the same compiled query with no rebuild, and search![&g, p with X(a = id), X(b = id), ..] pins named nodes to concrete graph ids first. Pattern is Clone: cloning shares the compiled query behind an Arc rather than recompiling it. A pin on a node inside a ban cluster restricts the ban to that one node; see Negation, Bans And Pins.

use grw::graph::{edge, MGraph};
use grw::search::Pattern;
use grw::{mgraph, pattern, search};

let g: MGraph<u8, edge::Undir<()>> = mgraph![N(0).val(1u8) ^ (N(1).val(2u8) ^ N(2).val(3u8))].unwrap();
let p: Pattern<u8, edge::Undir<()>> = pattern![get(Mono) { N(a) ^ N(b) }].unwrap();
let middle = grw::id::N(1);
let s = search![&g, p with X(a = middle)].unwrap();
assert_eq!(s.iter().count(), 2);

Pinning the same name twice, literally, in one with clause is a compile error (node `a` pinned twice). Everything downstream of that is checked at runtime once the target ids are known: an unknown name is error::Search::UnknownName, pinning the same name twice through the manual Session::from_pattern API is error::Search::Bind (BindError::Duplicate, naming the pinned node), pinning to a graph node that doesn’t exist is error::Search::TargetMissing, and two different pins landing on the same target node under an injective morphism is error::Search::Bind (BindError::Collision).

Variable-Length Paths

Prefix a pattern node with .. and the edge becomes a variable-length path. Everything else about the pattern stays the same — a path drops in anywhere an edge can.

..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

Traversal: dfs / bfs / drive

dfs() yields deepest trails first, bfs() shortest first. Both are lazy — each next() computes exactly one complete path by backtracking.

drive(f) steers a DFS: at each expansion step, the closure receives the number of candidate continuations n and answers with an Explore decision — or None to prune the tip.

Length bounds: len

.len(bounds) constrains the number of edges in the path. Any usize range works, and a bare usize means an exact length:

.len(3)       // exactly 3 edges
.len(2..5)    // 2, 3 or 4
.len(2..=4)   // same, inclusive
.len(1..)     // at least one (the default)
.len(0..)     // include the trivial self-path when from == to

Navigation: Dijkstra / AStar

navigate(nav) orders results by cost instead of traversal order. The navigator supplies a non-negative per-edge cost; A* adds an admissible per-node heuristic that steers exploration without changing which path is cheapest.

let cfg = Config::new(())
    .navigate(Dijkstra::weighted(|ms: &u32| *ms as f64));

let (cost, path) = g
    .path_navigate(N(0), N(3), outgoing, cfg, &constraint)
    .next()
    .unwrap();

Two result modes:

Guards

.guard(pred) rejects paths (including partial ones) during the walk. The predicate receives the path tip-first as a lazy, allocation-free view — decide from a short suffix and return early:

.dfs().guard(|p| !p.contains(id::N(2)))

Steering with Explore

The drive closure picks which continuation indices 0..n to expand:

Paths inside search!

Inside a pattern, the path’s endpoints are pattern nodes and the morphism governs the intermediates: a Mono path can’t reuse nodes bound elsewhere in the match, a SubIso path additionally rejects branched intermediates. Bind both endpoints to the same node and paths become cycle detection:

let session = search![&g,
    get(Homo) { N(0), N(1) },            // endpoints may collapse
    get(Mono) { n(0) >> ..n(1).dfs().len(1..) }
].unwrap();

let cycles = session.iter()
    .filter(|m| m[0] == m[1] && !m.path(0).is_empty())
    .count();

Consuming path results

One Match fixes the endpoints — but several concrete paths may realize the same binding. They hang off the match, per path edge:

m.path(0)          // &[id::N] — full node sequence of the first path edge
m.path_count(0)    // how many alternatives were found
m.next_paths()     // step to the next combination (odometer, rightmost first)

next_paths_injective() additionally keeps intermediates across different path edges mutually distinct — that is how Mono/SubIso semantics extend to multi-path matches.

Standalone iterators are plain: g.path_search(..) yields Vec<id::N> per next(), g.path_navigate(..) yields (cost, Vec<id::N>) in non-decreasing cost order.

Mixing Clusters & Morphisms

Every cluster carries its own morphism — and patterns may combine clusters freely. This page defines exactly what such mixtures mean, one rule at a time, with the corner cases drawn out.

The distinctness rule

Two pattern nodes may bind the same target node iff they are not both injective.

Nodes defined in an injective cluster (Iso, SubIso, EpiMono, Mono) form one injective population: pairwise distinct, across all clusters. Nodes defined in a free cluster (Homo, Epi) reserve nothing and respect no reservations — in both directions:

Distinctness is never implicit. If you need two nodes to be genuinely different, put both in the injective population — that is the only guarantee. Conversely, a Homo node means “some node, possibly one you already matched.”

A node’s morphism comes from its defining cluster

N(x) defines a node; n(x) references it. References never tighten:

grw::search![<NV, ER>;
    get(Homo) { N(0), N(1) },                       // 0, 1 are free
    get(Mono) { n(0) ^ ..n(1).dfs().len(1..) }      // referencing them
]                                                    // does not change that

Nodes 0 and 1 stay free even though a Mono cluster uses them — which is exactly what lets this pattern find cycles: both path endpoints may bind the same node.

Free nodes never add multiplicity

The subtlest consequence. Consider a Mono edge plus a free witness:

get(Mono) { N(0) ^ N(1) },       // an edge A—B
get(Homo) { N(2) ^ n(0) }        // "and 0 has a neighbor"

You might read this as “node 0 has a second neighbor besides 1.” It does not say that: node 2 is free and not adjacent to 1, so m(2) = m(1) is always available — the target edge serving 0—1 serves 2—0 too.

The pattern’s true meaning: “edge 0—1 exists, and 0 has some neighbor” — trivially satisfied by node 1 itself. Want a genuinely second neighbor? Define node 2 in a Mono cluster.

Counting inherits this. Free-node matches include every aliased configuration. If you are counting distinct structures — fan-outs, distinct witnesses — use injective clusters.

Collapsing onto a neighbor needs a self-loop

A free node can never collapse onto a node it is adjacent to in the pattern, unless the target has a self-loop — its own edge would have to map to x—x:

Self-loops are first-class in the graph model (N(0) ^ n(0)), so this is a real capability — but on loop-free targets, adjacent free nodes are effectively distinct.

Paths under mixed morphisms

Variable-length paths interact with the population rule in three ways:

• Interiors are always node-simple. A path never revisits a node, regardless of morphism — Homo paths are simple paths, not walks. Endpoints may still close into a cycle (above).
• Interiors avoid the injective population only. A path may pass through a target that a free node happens to occupy; it may never pass through an injective binding.
• Cross-path interior sharing is morphism-driven. Two path edges in a Mono cluster must use disjoint interiors; in a Homo cluster they may share.

Surjective clusters (Epi, EpiMono)

Surjectivity is checked against the whole query’s bindings: every target node must be the image of some pattern node. Two nuances:

• Free clusters’ bindings count toward coverage.
• Path interiors do not count. A path edge asserts “a path exists” — its interior nodes are witnesses, not part of the pattern’s image. An Epi pattern whose explicit nodes cannot cover the target has no matches, even if its paths sweep every node.

Advanced: induced morphisms in mixtures

SubIso and Iso add the induced axis: extra target edges between matched nodes are forbidden. In a mixed pattern, the axis it is measured against is the injective population — the same population the distinctness rule builds:

Induced-ness holds between a SubIso/Iso node and every injective binding. For a node i in an induced cluster and any node j bound injectively — in any injective cluster, not just i’s own — a target edge m(i)—m(j) is legal only if the pattern has i—j. Bindings from free clusters (Homo, Epi) are invisible to the check: they neither trigger it nor are protected by it.

So an induced node’s neighbourhood is pinned exactly against everything the pattern promised to keep distinct, and left unconstrained against everything it did not. A free node may sit on a target neighbour of an induced node without rejecting the match — that target edge simply is not part of what induced-ness reads. Mixing induced clusters with free clusters is rarely what you want; prefer Mono + Homo mixtures unless you specifically need exact neighborhoods.

Rules of thumb

1. Distinct entities → one injective population. Any number of clusters; injectivity composes across them.
2. “Possibly the same node” → Homo. That is its entire purpose.
3. Counting distinct structures → no free nodes in the counted part.
4. Cycles → free endpoints + an injective path cluster referencing them.

Composite Values

Between two nodes a graph holds at most one link per slot (see Graph Model). When one link must say several things at once — two nodes that are related in more than one way — its value is a composite: a set of typed parts, at most one part per kind. The link stays one link; its value grows and shrinks part by part.

The Composite trait is the contract: build a value from one part, list its parts, look one up by kind, include a part, exclude a kind. Each refusal is the combinator’s own typed error. grw ships one combinator, TypeSet<P>, and a downstream crate can write its own.

The snippets in this chapter share these imports and declarations:

use grw::prelude::*;
use grw::composite::{Included, KindOf, Kinded, Removed, TypeSet};
use grw::edge::{Anydir, Dir};
use grw::graph::{Graph, MGraph};
use grw::modify::error::{apply, Apply, Modify};
use grw::id;

Declaring the parts: #[derive(Part)]

Each variant of a part enum is one kind, and holds exactly one payload type:

#[derive(Debug, Clone, PartialEq)]
pub struct Signs {
    pub since: u32,
}

#[derive(Debug, Clone, PartialEq)]
pub struct Uses {
    pub service: u32,
}

#[derive(Debug, Clone, PartialEq, Part)]
pub enum Rel {
    Signs(Signs),
    Uses(Uses),
}

pub type Link = TypeSet<Rel>;

#[derive(Part)] generates a fieldless kind enum (RelKind { Signs, Uses }), implements Kinded for Rel, From<Signs> / From<Uses> for Rel, and PartOf<Signs> / PartOf<Uses>, which name the static kind of each payload type. From those, every composite over Rel answers by type: get::<Signs>(), include(Uses { .. }), exclude::<Signs>() (the Typed trait) and, in patterns, has::<Signs>(). The derive refuses a struct, a generic enum, a variant that is not a single-field tuple variant, and two variants with the same payload type.

A part type does not need the derive: any type implementing Kinded can be the part of a TypeSet, and is then used through the raw-part forms (include(part), exclude_kind(kind), has_kind(kind)).

TypeSet

TypeSet<P> keeps its parts in kind order, one per kind. Including an equal part is Included::Held and changes nothing; including a different part of a kind already held is refused (KindPresent); excluding a kind not held is refused (NotHeld); excluding the last part leaves nothing, and the link is removed.

let link = Link::from_part(Rel::from(Signs { since: 2023 }));
let Ok(Included::Added(link)) = link.include(Uses { service: 7 }) else {
    panic!("Uses is new to the link");
};

assert_eq!(link.get::<Signs>(), Some(&Signs { since: 2023 }));
assert_eq!(link.parts().count(), 2);
assert_eq!(link.include(Uses { service: 7 }).ok(), Some(Included::Held));
assert_eq!(link.include(Uses { service: 8 }).err().map(|refused| refused.kind), Some(RelKind::Uses));
assert_eq!(link.exclude::<Uses>().ok(), Some(Removed::Remains(Link::from_part(Rel::from(Signs { since: 2023 })))));

Part operations work wherever the value a slot holds is a composite. On a Dir or Undir graph that is the edge value itself. On an Anydir<U, D> graph the operator picks the slot, and with it the value the part belongs to: see Anydir graphs.

Building: mgraph! / vgraph!

E().include(p) puts a part on the link; further .include(q) calls add more parts to the same link. Naming one kind twice on one link is a typed build error (graph::error::Part::Repeated), even when the two parts are equal.

let g = mgraph![<(), Dir<Link>>;
    N(0) & E().include(Signs { since: 2023 }).include(Uses { service: 7 }) >> N(1),
    n(1) & E().include(Uses { service: 9 }) >> N(2),
]
.unwrap();
assert_eq!(g.edge_count(), 2);

let twice = mgraph![<(), Dir<Link>>;
    N(0) & E().include(Signs { since: 2023 }).include(Signs { since: 2024 }) >> N(1)
];
assert!(twice.is_err());

E().val(whole) still takes a whole composite value as given.

Changing: modify!

let mut g = mgraph![<(), Dir<Link>>;
    N(0) & E().include(Signs { since: 2023 }) >> N(1),
    n(1) & E().include(Uses { service: 9 }) >> N(2),
]
.unwrap();

modify!(g, [X(0) & E().include(Uses { service: 7 }) >> x(1)]).unwrap();
modify!(g, [X(0) & E().include(Uses { service: 4 }) >> x(2)]).unwrap();
modify!(g, [X(0) & E().exclude::<Signs>() >> x(1)]).unwrap();
modify!(g, [X(1) & E().exclude_kind(RelKind::Uses) >> x(2)]).unwrap();
modify!(g, [X(0) & !e() >> x(2)]).unwrap();

assert_eq!(g.edge_count(), 1);
let (_, link) = g.edges_between(id::N(0), id::N(1)).next().unwrap();
assert_eq!(link.get::<Uses>(), Some(&Uses { service: 7 }));
assert_eq!(link.get::<Signs>(), None);

Part operations on one pair in one modify! fold in order into one change of the link: an add, a value swap, a removal, or nothing when the result equals the stored value.

Refusals

refused carries the combinator’s own refusal, unchanged; read it back by naming the combinator: refused.of::<Link>(). A refused batch applies nothing.

let mut g = mgraph![<(), Dir<Link>>; N(0) & E().include(Signs { since: 2023 }) >> N(1)].unwrap();

match modify!(g, [X(0) & E().include(Signs { since: 1999 }) >> x(1)]).err() {
    Some(Modify::Apply(Apply::Edge(apply::Edge::PartRejected { refused, .. }))) => {
        assert_eq!(refused.of::<Link>().map(|r| r.kind), Some(RelKind::Signs));
    }
    other => panic!("expected PartRejected, got {other:?}"),
}

match modify!(g, [X(0) & E().exclude::<Uses>() >> x(1)]).err() {
    Some(Modify::Apply(Apply::Edge(apply::Edge::PartNotHeld { refused, .. }))) => {
        assert_eq!(refused.of::<Link>().map(|r| r.kind), Some(RelKind::Uses));
    }
    other => panic!("expected PartNotHeld, got {other:?}"),
}

let whole = Link::from_part(Rel::from(Uses { service: 7 }));
let both = modify!(g, [X(0) & e().val(whole) >> x(1), x(0) & E().exclude::<Signs>() >> x(1)]);
assert!(matches!(both.err(), Some(Modify::Apply(Apply::Edge(apply::Edge::PartConflict(_, _))))));

A combinator of your own

What an empty composite means is the combinator’s decision. TypeSet says the link is gone. A combinator that keeps a hollow link says otherwise — this one answers Removed::Remains with no parts left:

#[derive(Debug, thiserror::Error)]
#[error("the link already holds another {0:?}")]
pub struct OtherPartHeld<K: std::fmt::Debug>(pub K);

#[derive(Debug, thiserror::Error)]
#[error("the link holds no {0:?}")]
pub struct NothingToExclude<K: std::fmt::Debug>(pub K);

#[derive(Debug, Clone, PartialEq)]
pub struct KeepHollow<P> {
    parts: Vec<P>,
}

impl<P: Kinded> KeepHollow<P> {
    pub fn is_hollow(&self) -> bool {
        self.parts.is_empty()
    }

    fn at(&self, kind: &P::Kind) -> Result<usize, usize> {
        self.parts.binary_search_by(|held| held.kind().cmp(kind))
    }
}

impl<P: Kinded + Clone + PartialEq> Composite for KeepHollow<P> {
    type Part = P;
    type IncludeRefused = OtherPartHeld<P::Kind>;
    type ExcludeRefused = NothingToExclude<P::Kind>;

    fn from_part(part: P) -> Self {
        KeepHollow { parts: vec![part] }
    }

    fn parts(&self) -> impl Iterator<Item = &P> {
        self.parts.iter()
    }

    fn part(&self, kind: &KindOf<Self>) -> Option<&P> {
        self.at(kind).ok().map(|i| &self.parts[i])
    }

    fn with_part(&self, part: P) -> Result<Included<Self>, OtherPartHeld<P::Kind>> {
        match self.at(&part.kind()) {
            Ok(i) if self.parts[i] == part => Ok(Included::Held),
            Ok(_) => Err(OtherPartHeld(part.kind())),
            Err(i) => {
                let mut parts = self.parts.clone();
                parts.insert(i, part);
                Ok(Included::Added(KeepHollow { parts }))
            }
        }
    }

    fn without_part(&self, kind: &KindOf<Self>) -> Result<Removed<Self>, NothingToExclude<P::Kind>> {
        match self.at(kind) {
            Ok(i) => {
                let mut parts = self.parts.clone();
                parts.remove(i);
                Ok(Removed::Remains(KeepHollow { parts }))
            }
            Err(_) => Err(NothingToExclude(kind.clone())),
        }
    }
}

The graph DSLs and the engine work with any Composite:

let mut g = mgraph![<(), Dir<KeepHollow<Rel>>>;
    N(0) & E().include(Signs { since: 2023 }) >> N(1)
]
.unwrap();

modify!(g, [X(0) & E().exclude::<Signs>() >> x(1)]).unwrap();

assert_eq!(g.edge_count(), 1);
assert!(g.edges_between(id::N(0), id::N(1)).all(|(_, link)| link.is_hollow()));

Searching: has

The examples search this graph:

fn hub() -> MGraph<(), Dir<Link>> {
    mgraph![<(), Dir<Link>>;
        N(0) & E().include(Signs { since: 2021 }) >> N(1),
        n(0) & E().include(Signs { since: 2022 }) >> N(2),
        n(0) & E().include(Signs { since: 2023 }) >> N(3),
        n(1) & E().include(Signs { since: 2024 }) >> n(2),
        n(2) & E().include(Uses { service: 7 }) >> n(3),
    ]
    .unwrap()
}

let g = hub();

let signed = search![&g, get(Mono) { N(0) & E().has::<Signs>() >> N(1) }].unwrap();
assert_eq!(signed.iter().count(), 4);

let recent = search![&g, get(Mono) {
    N(0) & E().has::<Signs>().test(|s: &Signs| s.since >= 2023) >> N(1)
}]
.unwrap();
assert_eq!(recent.iter().count(), 2);

let raw = search![&g, get(Mono) {
    N(0) & E().has_kind(RelKind::Uses).test(|p: &Rel| matches!(p, Rel::Uses(u) if u.service == 7)) >> N(1)
}]
.unwrap();
assert_eq!(raw.iter().count(), 1);

let whole = search![&g, get(Mono) { N(0) & E().test(|v: &Link| v.parts().count() == 1) >> N(1) }].unwrap();
assert_eq!(whole.iter().count(), 5);

has::<T>() compiles only where the link’s value has a T part, and a .test closure must take the part its has named.

!E().has::<T>() and !E() differ exactly where a pair is linked by some other part:

let g = hub();

let no_uses = search![&g, get(Mono) {
    N(0) & E().has::<Signs>() >> N(1),
    n(0) & E().has::<Signs>() >> N(2),
    n(1) & !E().has::<Uses>() >> n(2)
}]
.unwrap();
assert_eq!(no_uses.iter().count(), 5);

let no_link = search![&g, get(Mono) {
    N(0) & E().has::<Signs>() >> N(1),
    n(0) & E().has::<Signs>() >> N(2),
    n(1) & !E() >> n(2)
}]
.unwrap();
assert_eq!(no_link.iter().count(), 4);

Terms on one pair merge

All terms on one pair and slot within a cluster become one constraint on the link — a conjunction. E().has::<A>() beside !E().has::<B>() means “holds A and not B”, as one pattern edge:

let g = hub();

let merged = search![&g, get(Mono) {
    N(0) & E().has::<Signs>() >> N(1),
    n(0) & !E().has::<Uses>() >> n(1)
}]
.unwrap();
assert_eq!(merged.query().edge_count(), 1);
assert_eq!(merged.iter().count(), 4);

let contradiction = search![&g, get(Mono) {
    N(0) & E().has::<Signs>() >> N(1),
    n(0) & !E().has::<Signs>() >> n(1)
}];
assert!(contradiction.is_err());

The query refuses what could never match, with typed errors of search::error::Edge:

• PartRepeated — one kind required twice on one link;
• Contradictory — what one term requires another forbids: !E() beside a positive term, or an untested !E().has::<A>()… beside a term that requires every part it names;
• ConflictingPred — a ban cluster putting a part term on a pattern edge its get cluster already declared.

Anydir graphs: the operator picks the slot

An Anydir<U, D> graph holds an undirected value U and a directed value D between the same two nodes, each in its own slot (its edge value is AnyVal<U, D>). include, exclude, exclude_kind, has and has_kind wait for the operator: on ^ they work on the U held in the undirected slot, on >> / << on the D held in the directed slot. The graph literal’s include waits the same way. The two values may be different composites:

#[derive(Debug, Clone, PartialEq)]
pub struct Knows {
    pub since: u32,
}

#[derive(Debug, Clone, PartialEq, Part)]
pub enum Tie {
    Knows(Knows),
}

pub type Bond = TypeSet<Tie>;

let mut g = mgraph![<(), Anydir<Bond, Link>>;
    N(0) & E().include(Knows { since: 2019 }) ^ N(1),
    n(0) & E().include(Signs { since: 2023 }) >> n(1),
]
.unwrap();
assert_eq!(g.edge_count(), 2);

modify!(g, [X(0) & E().include(Uses { service: 7 }) >> x(1), x(1) & E().exclude::<Knows>() ^ x(0)]).unwrap();
assert_eq!(g.edge_count(), 1);

let known = search![&g, get(Mono) { N(0) & E().has::<Knows>() ^ N(1) }].unwrap();
assert_eq!(known.iter().count(), 0);
let used = search![&g, get(Mono) { N(0) & E().has::<Signs>().has::<Uses>() >> N(1) }].unwrap();
assert_eq!(used.iter().count(), 1);

A part the slot’s value cannot hold does not compile: E().include(Signs { .. }) on ^ names a part of Rel, not of Tie, and so does E().has::<Signs>() on ^. Everything else is as on Dir: an equal part changes nothing, a batch that ends where it started writes nothing, and the refusals are the slot value’s own, read back with refused.of::<Bond>() on ^ and refused.of::<Link>() on >> / <<. A value of the other class held in a slot (only a whole-value op can put one there) is refused with apply::Edge::SlotClass.

Outside search!, has and has_kind on a bare E() come from the grw::search::dsl::Seek trait, which has to be in scope; use grw::prelude::*; brings it in together with mgraph!, vgraph!, modify!, search!, pattern!, #[derive(Val)], #[derive(Part)], Typed and Composite.

Persistence

A composite value is saved as its parts in kind order; the snapshot format is unchanged (still v3), and the file header’s edge layout hash tells a composite file from any other. load / load_with remain strict: a non-canonical part order is refused, never re-sorted.

A snapshot written while each link held one plain value P loads into a TypeSet<P> graph through the explicit promoting path only — each old link becomes a one-part link. The part type here implements Kinded by hand:

use grw::prelude::*;
use grw::composite::Kinded;

#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Val, serde::Serialize, serde::Deserialize)]
pub enum Role {
    Owner,
    Reader,
}

#[derive(Debug, Clone, PartialEq, Val, serde::Serialize, serde::Deserialize)]
pub struct Grant {
    pub role: Role,
    pub since: u32,
}

impl Kinded for Grant {
    type Kind = Role;

    fn kind(&self) -> Role {
        self.role
    }
}

use grw::graph::VGraph;
use promoted::{Grant, Role};

let old: MGraph<(), Dir<Grant>> = mgraph![<(), Dir<Grant>>;
    N(0) & E().val(Grant { role: Role::Owner, since: 2020 }) >> N(1)
]
.unwrap();
let path = std::env::temp_dir().join(format!("grw_book_promoted_{}.grw", std::process::id()));
old.save(&path).unwrap();

assert!(MGraph::<(), Dir<TypeSet<Grant>>>::load(&path).is_err());
let g: MGraph<(), Dir<TypeSet<Grant>>> = MGraph::load_promoting(&path).unwrap();
let (_, link) = g.edges_between(id::N(0), id::N(1)).next().unwrap();
assert_eq!(link.parts().count(), 1);
let v: VGraph<(), Dir<TypeSet<Grant>>> = VGraph::load_promoting(&path).unwrap();
assert_eq!(v.edge_count(), 1);

std::fs::remove_file(&path).unwrap();

load_promoting_with(path, decls) restores indices as load_with does. A file whose edge values are neither the composite nor its part is refused.

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.

Indices

A graph can maintain keyed node indices — tables that map a value-derived key straight to the node(s) that hold it, instead of scanning every node to find them. MGraph and VGraph expose the identical API: with_indices, add_index, drop_index, catalogue, plus index_hit/catalogue/ index_decls from the Graph trait.

Declaring an index

An index is an IndexDecl<NV>: a name, a cardinality, and a key extractor.

use grw::graph::index::{Cardinality, IndexDecl, IndexName};
use grw::graph::{MGraph, edge};

const BY_VAL: IndexName = IndexName("by_val");
const BY_BUCKET: IndexName = IndexName("by_bucket");

let g: MGraph<u32, edge::Undir<()>> = grw::mgraph![
    N(0).val(10u32) ^ N(1).val(20u32) ^ N(2).val(30u32)
].unwrap();

let g = g.with_indices(vec![
    IndexDecl::new(BY_VAL, Cardinality::Unique, |v: &u32| Some(*v)),
    IndexDecl::new(BY_BUCKET, Cardinality::Multi, |v: &u32| Some(*v % 20)),
]).unwrap();

IndexDecl::new(name, cardinality, extractor) accepts any Fn(&NV) -> Option<K> where K: Serialize + 'static; returning None excludes that node from the index entirely. Cardinality::Unique means at most one node per key — a value collision refuses the whole call with graph::error::Index::NotUnique { index, nodes }. Cardinality::Multi groups every node sharing a key under it. with_indices builds every table with one scan of the graph; a duplicate name among the declarations is graph::error::Index::DuplicateName.

Maintaining an index

Add or drop an index on a graph that already has data:

use grw::graph::index::{Cardinality, IndexDecl, IndexName};
use grw::graph::{MGraph, edge};

const BY_PARITY: IndexName = IndexName("by_parity");

let mut g: MGraph<u32, edge::Undir<()>> = grw::mgraph![
    N(0).val(10u32) ^ N(1).val(20u32)
].unwrap();

g.add_index(IndexDecl::new(BY_PARITY, Cardinality::Multi, |v: &u32| Some(*v % 2))).unwrap();
let dropped = g.drop_index(BY_PARITY).unwrap();
assert_eq!(dropped.name(), BY_PARITY);

add_index scans once to build the new table and fails the same way with_indices does on a Unique collision. drop_index fails with graph::error::Index::NoSuchIndex for a name that isn’t declared.

From here on, every declared index is maintained inside modify! — as part of the same atomic transaction as the rest of the batch, not a follow-up step:

use grw::graph::index::{Cardinality, IndexDecl, IndexName};
use grw::graph::{MGraph, edge};
use grw::modify;

const BY_VAL: IndexName = IndexName("by_val");

let g: MGraph<u32, edge::Undir<()>> = grw::mgraph![N(0).val(10u32)].unwrap();
let mut g = g.with_indices(vec![
    IndexDecl::new(BY_VAL, Cardinality::Unique, |v: &u32| Some(*v)),
]).unwrap();

// a batch that would give two nodes the same unique key is refused whole
let Err(err) = modify!(g, [N(1).val(10u32), N(2).val(20u32)]) else { panic!("expected Err") };
assert!(matches!(
    err,
    grw::modify::error::Modify::Apply(grw::modify::error::Apply::Index(
        grw::modify::error::apply::Index::DuplicateKey { index, .. }
    )) if index == BY_VAL
));
assert_eq!(g.node_count(), 1); // nothing was written, not even node 2

DuplicateKey { index, existing } names the offending index and the node that already owns the key; when a batch collides on more than one index the one reported is whichever comes first in catalogue (alphabetical-by-name) order. This is the same all-or-nothing rule every other modify! failure follows — see modify! — Mutation.

Hitting an index

index_hit(name, key, tag) is a Graph trait method, so it works identically on MGraph and VGraph:

use grw::Graph as _;
use grw::graph::index::{Cardinality, IndexDecl, IndexHit, IndexName, KeyBytes, KeyTag};
use grw::graph::{MGraph, edge};

const BY_BUCKET: IndexName = IndexName("by_bucket");

let g: MGraph<u32, edge::Undir<()>> = grw::mgraph![
    N(0).val(1u32) ^ N(1).val(21u32) ^ N(2).val(2u32)
].unwrap();
let g = g.with_indices(vec![
    IndexDecl::new(BY_BUCKET, Cardinality::Multi, |v: &u32| Some(*v % 20)),
]).unwrap();

match g.index_hit(BY_BUCKET, &KeyBytes::of(&1u32), KeyTag::of::<u32>()).unwrap() {
    IndexHit::Many(set) => assert_eq!(set.len(), 2), // nodes 0 and 1 both key to 1
    _ => panic!("expected a Many hit"),
};

IndexHit is One(id::N) for a Unique hit, Many(IdView<'_>) for a Multi hit with at least one member, or None for a key nothing holds. IdView is a borrowed read view over the hit set — iter() (yielding id::N), len(), is_empty(), and contains(id::N); the set behind it stays crate-private, so grw’s public surface never exposes the bitmap representation. index_hit fails with graph::error::Index::NoSuchIndex for an unknown name and graph::error::Index::KeyTagMismatch { index, expected, got } when the key’s type doesn’t match the type the index was declared over — KeyTag identifies a Rust type, not just a byte length, so passing a u64 key against a u32-keyed index is rejected rather than silently comparing the wrong bytes.

catalogue() lists every declared index — name, cardinality, and tag — in alphabetical-by-name order, regardless of declaration order. index_decls() returns the same information as owned IndexDecl<NV> values (extractor closures included), which is how MGraph::from_graph and VGraph::from_mgraph/to_mgraph carry a source’s indices across a representation change without re-declaring them by hand.

Key predicates in search

search!/pattern! reach these same tables directly from a pattern node with .key(index, value) / .key_in(index, [values]), seeding the search with the index’s hit set instead of scanning every node — see Key Predicates.

Persistence

The .grw snapshot format carries the whole catalogue and every table alongside the graph — see Persistence. save writes them, load refuses a file whose catalogue is non-empty (naming the indices that need declarations — a plain load has nothing to check the file against), and load_with(path, decls) verifies the file’s catalogue against decls and restores the tables straight from the file, with no rescan of node values at all.

Morphisms

A morphism is a mapping from pattern nodes to target nodes that preserves edges — if two nodes are connected in the pattern, their mapped counterparts must be connected in the target.

The question is: how strict is the mapping? Three independent axes control this.

The Three Axes

Injective (one-to-one)

No two pattern nodes map to the same target node. Each match “uses up” a target node.

Real-world: assigning people to desks — each desk holds one person.

Surjective (covers everything)

Every target node must be hit by at least one pattern node. No target node left unmapped.

Real-world: every desk must have someone sitting at it.

Induced (exact neighborhood)

No extra edges allowed between matched nodes beyond what the pattern specifies. The pattern describes the exact local structure.

Real-world: the people at these desks talk to exactly who the org chart says — no side conversations.

The Six Morphisms

The Lattice

These form a partial order. Going up adds constraints, going down relaxes them.

         Iso
        /   \
    SubIso  EpiMono
       \   / \   /
        Mono   Epi
          \   /
           Homo

• Up = more constrained, down = more relaxed
• SubIso = Mono + induced
• EpiMono = Mono + surjective
• Iso = SubIso + surjective = EpiMono + induced

The meet() of two morphisms is the most relaxed morphism that satisfies both. This is used internally when multiple clusters share nodes.

When to Use What

Isomorphism — “Are these two graphs identical?” Graph comparison, canonical forms, symmetry detection. Both graphs must have the same number of nodes, same edges, nothing extra.

Subgraph Isomorphism — “Does this shape appear inside that graph?” The workhorse of pattern matching. Find a triangle in a social network, a motif in a protein structure, a substructure in a molecule. The matched region must look exactly like the pattern — no extra connections between matched nodes.

Monomorphism — “Can I embed this pattern without node conflicts?” Like SubIso but relaxed: extra edges between matched nodes are allowed. Good when you care about required connections but don’t mind if the matched nodes have additional relationships. Often easier to compute.

Epimorphism — “Does the pattern cover the entire target?” Every target node must be matched. Useful for coverage analysis, tiling, or ensuring nothing is left unmatched. Pattern can collapse multiple nodes onto one target.

EpiMono — “Is this a relabeling with possible extra edges?” Bijective but non-induced. Same number of nodes, one-to-one mapping, but the target may have edges the pattern doesn’t mention. Arises naturally when a node participates in both Mono and Epi constraints.

Homomorphism — “Can this pattern be projected onto that graph?” Most relaxed. Multiple pattern nodes can collapse to one target node. Graph coloring is a homomorphism to a complete graph. Useful for abstract structural queries where you care about connectivity patterns, not exact node identity.

Index Tiers

Before the search engine can match patterns, it needs a data structure for fast neighbor lookups. When you use search![&g, ...], the graph is indexed automatically with RevCsr. For manual control, you can index explicitly.

Tiers

Automatic Indexing

The search! macro with a graph reference handles indexing for you:

// RevCsr index is built automatically
let session = search![&g,
    get(Mono) { N(0) ^ N(1) }
].unwrap();

Manual Indexing

For repeated searches on the same graph, index once and reuse:

use grw::search::{Search, Seq, Par, RevCsr, RevCsrVal};

let Search::Resolved(r) = search![<(), edge::Undir<()>>;
    get(Mono) { N(0) ^ N(1) }
].unwrap() else { panic!() };

// index once
let indexed = g.index(RevCsr);

// search many times
let count1 = Seq::search(r.query(), &indexed).unwrap().count();
let count2 = Seq::search(r.query(), &indexed).unwrap().count();

RevCsrVal for Node Value Predicates

When your search pattern uses node value predicates (.val(..), .test(..)), RevCsrVal pre-groups nodes by their value in the CSR structure (value_groups: NV -> [id::N]), so evaluating a predicate only visits the value groups that actually pass it instead of every node:

let indexed = g.index(RevCsrVal);

This trades more memory for faster node-predicate evaluation during search.

Key Predicates Bypass The Scan

A .key/.key_in predicate never touches value_groups at all, on any tier: it resolves straight through the graph’s own index tables (Graph::index_hit), producing a candidate pool directly instead of scanning node values.

Persistence

GRW graphs can be saved to and loaded from binary .grw files (format version 3), with layout validation and an integrity check over the whole file.

Save and Load

use std::path::Path;

// save
g.save(Path::new("my_graph.grw")).unwrap();

// load
let g2: graph::MUndir0 = MGraph::load(Path::new("my_graph.grw")).unwrap();

VGraph::save/load write and read exactly the same format — there is one .grw layout, not two; see Versioned Graphs for what crosses that door and what doesn’t.

Binary Format (v3)

A file is a fixed header, a section table, six content sections, and a trailer:

1. Header — magic GRW\0, version: u16 (= 3), graph_kind: u8 (0 = MGraph, 1 = VGraph), edge_kind: u8, node/edge counts, layout hashes for NV and EV, then the type name strings (for error messages), then a section_count: u16 and that many (tag, offset, len) entries — always all seven, even when a section is empty.
2. Nodes / Edges — fixed-width rows for live nodes/edges only, sorted by slot ascending. Every row carries a gen: u64 field; it is real for a VGraph-sourced file and always 0 for an MGraph-sourced one — the byte layout never branches on graph_kind, only its meaning does.
3. Adjacency — (neighbor, edge) pairs, contiguous per node in node order; a node’s row carries a byte offset into this section and a pair count.
4. Values — one heap of bincode bytes, node values first (in node order) then edge values (in edge order), each addressed by byte offset and length from the node/edge rows.
5. Free — one bincode blob: node_free/edge_free (each the holes below next_node/next_edge, not the full allocator state), next_node: u32, next_edge: u32, and a real version: u64 (always 0 for an MGraph-sourced file).
6. Indices — see below.
7. Trailer — 32 bytes, the SHA-256 of every byte before it (header through the indices section, including the section table itself). Verified before any section body is parsed, so a flipped byte inside a section surfaces as a trailer-mismatch error, never a downstream parse error. The fixed header and the section table are read before the check runs, so corruption there surfaces first as a structural error — “invalid magic”, “unsupported version”, “unknown section tag”, or a truncated/out-of-range section range — rather than as a trailer mismatch. Every one of those errors names the file it came from.

use grw::graph::persist;

let header = persist::read_header(Path::new("my_graph.grw")).unwrap();
assert_eq!(header.version, 3);
assert_eq!(header.sections.len(), 7);

read_header reads only the header and the section table (and, inside the indices section, only the catalogue — never a table body), so it can inspect a file’s shape and catalogue without loading the graph at all. Being header-only, it does not verify the trailer: what it reports is what the bytes claim. load/load_with verify the trailer before parsing any section body.

Indices

If a graph carries indices, save writes the whole catalogue and every table into the indices section: a catalogue header (each declared index’s name, cardinality, and key tag) followed, in the same order, by one table per index. load refuses such a file, naming every index that needs a declaration — a plain load has nothing to check the file against — so use load_with to both verify and restore them:

use grw::graph::index::{Cardinality, IndexDecl, IndexName};
use grw::graph::{MGraph, edge};

const BY_VAL: IndexName = IndexName("by_val");

let g: MGraph<u32, edge::Undir<()>> = grw::mgraph![N(0).val(10u32)].unwrap();
let g = g.with_indices(vec![
    IndexDecl::new(BY_VAL, Cardinality::Unique, |v: &u32| Some(*v)),
]).unwrap();
g.save(Path::new("indexed.grw")).unwrap();

let g2: MGraph<u32, edge::Undir<()>> = MGraph::load_with(Path::new("indexed.grw"), vec![
    IndexDecl::new(BY_VAL, Cardinality::Unique, |v: &u32| Some(*v)),
]).unwrap();
assert_eq!(g2.catalogue().len(), 1);

load_with checks the file’s catalogue against the declarations you pass — by name, order-independent — before restoring the tables directly from the parsed bytes, with no rescan of node values: a missing declaration, an extra one, or a key-type mismatch (KeyTag) are each a distinct, named error. Plain load on such a file is itself an error, naming every index that needs a declaration. See Indices for the declaration API itself.

Layout Validation

When loading, GRW validates that the types match:

• Edge kind must match (can’t load a directed graph as undirected)
• Layout hash for node values must match
• Layout hash for edge values must match

// this will fail: type mismatch
let result = MGraph::<i64, edge::Undir<i64>>::load(Path::new("u32_graph.grw"));
// Error: "node value layout mismatch: file has type `u32`, expected `i64`"

The layout hash is computed from the type’s field names, types, and structure using FNV hashing. This catches:

• Wrong types (u32 vs i64)
• Reordered fields
• Added/removed fields

Errors

Every save, load*, read_header and convert answers a persist::Error { path, reason }: the file it read or wrote, and a typed Reason — Io, Format (magic, version, section tag or range, truncation, trailer hash, cardinality, UTF-8), EdgeKind, Layout { side, .. }, Catalogue (an undeclared, unheld or mismatched index), Value { site, source } for a node value, edge value, free section or index set bincode refused, Promotion and V2.

use grw::graph::persist::{Layout, Reason, Side};

let Err(err) = MGraph::<i64, edge::Undir<i64>>::load(Path::new("u32_graph.grw")) else { panic!("a u32 file is refused as i64") };
assert!(matches!(err.reason, Reason::Layout(Layout { side: Side::Node, .. })));

Reads are strict: every value, the free section and every index set must be consumed exactly by its decode, so a slice with bytes left over is a Reason::Value naming its site. Writes are the plain bincode::serialize output, so every file grw has written still reads.

Composite Edge Values

A composite edge value such as TypeSet<P> is saved as its parts in kind order, under its own layout hash, so the format is still v3. A file written while each link held a plain P fails the strict edge layout check; it loads into a TypeSet<P> graph only through the explicit load_promoting/load_promoting_with (on MGraph and VGraph), each old link becoming a one-part link. See Composite Values.

Loading an old file: convert

A file written by the pre-v3 format is rejected by load/load_with/ read_header with a message naming convert:

use grw::graph::persist;

let report = persist::convert::<(), edge::Dir<()>>(
    Path::new("old_v2.grw"),
    Path::new("upgraded_v3.grw"),
).unwrap();
let g: graph::MDir0 = MGraph::load(Path::new("upgraded_v3.grw")).unwrap();
assert_eq!(report.node_count, g.node_count() as u64);

convert reads the old file in full and writes it back out in the current format at the destination path; the source is untouched.

Memory-Mapped Loading

load() uses memmap2 for memory-mapped file access: the header and section table are parsed first, then each section is read directly from the mmap.

The Val Trait

save() and load() require both NV and EV to implement the Val trait (for layout hash computation). Primitive types ((), bool, u8–u64, i8–i64, f32, f64, String) implement Val automatically. For custom structs, use #[derive(Val)]:

use grw::Val;

#[derive(Val, serde::Serialize, serde::Deserialize)]
struct MyNode {
    x: f64,
    y: f64,
    label: String,
}

Watcher

The Watcher trait provides an observer pattern for graph mutations and search events. Implement it to receive callbacks when the graph changes or when the search engine makes decisions.

The Watcher Trait

pub trait Watcher<NV, E: Edge> {
    const ACTIVE: bool = true;

    // Search events
    fn on_bind(&mut self, step: usize, pattern_node: LocalId, graph_node: id::N) -> Control;
    fn on_unbind(&mut self, step: usize, pattern_node: LocalId);
    fn on_edge_test(&mut self, ...) -> Control;
    fn on_ban_verdict(&mut self, cluster: usize, verdict: BanVerdict) -> Control;
    fn on_match(&mut self, mapping: &[(LocalId, id::N)]) -> Control;

    // Mutation events
    fn on_node_added(&mut self, id: id::N, val: &NV);
    fn on_node_removed(&mut self, id: id::N);
    fn on_node_changed(&mut self, id: id::N, val: &NV);
    fn on_edge_added(&mut self, id: id::E, n1: id::N, n2: id::N, slot: &E::Slot, val: &E::Val);
    fn on_edge_removed(&mut self, id: id::E);
    fn on_edge_changed(&mut self, id: id::E, val: &E::Val);
}

Control Flow

Watcher callbacks return Control:

• Control::Continue — keep going
• Control::Pause — pause (for interactive debugging)
• Control::Stop — abort the search

Silent Watcher

Silent is a no-op implementation with ACTIVE: bool = false. The compiler optimizes all callbacks away when Silent is used:

use grw::watch::Silent;
// Silent is used by default — zero overhead

WatchedGraph

To observe mutations, wrap the graph with a watcher:

let mut watcher = MyWatcher::new();
let mut watched = g.watched(&mut watcher);

// mutations through watched notify the watcher
watched.modify(ops).unwrap();

// watcher received on_node_added, on_edge_added, etc.

Ban Verdicts

During search, ban clusters report their outcomes:

• BanVerdict::Fired — the ban pattern matched, rejecting the candidate
• BanVerdict::SharedEdgeFail — shared edge check eliminated the candidate
• BanVerdict::NoCandidate — no valid mapping for the ban pattern

Morphism Cheat Sheet

Visual Examples

Pattern: path A — B — C (3 nodes, 2 edges). Target: triangle 0 — 1 — 2 — 0 (3 nodes, 3 edges).

Mapping: A→0, B→1, C→2

The required edges (A—B, B—C) are present in the target. But there’s an extra edge 0—2 that the pattern doesn’t mention.

Mono: accept — extra edge is fine

SubIso: reject — extra edge violates induced constraint

Collapsing: A→0, B→1, C→1

C maps to the same target node as B — a collapse.

Homo: accept — collapse allowed

Surjectivity: pattern A—B on target 0—1—2

A two-node pattern on a three-node target. Node 2 is left uncovered.

Quick Decision Guide

Do I need each pattern node to match a different target node?

• Yes → injective (Iso, SubIso, EpiMono, Mono)
• No → non-injective (Epi, Homo)

Do I need every target node to be matched?

• Yes → surjective (Iso, EpiMono, Epi)
• No → non-surjective (SubIso, Mono, Homo)

Do I care about extra edges between matched nodes?

• Yes, reject them → induced (Iso, SubIso)
• No, allow them → non-induced (EpiMono, Mono, Epi, Homo)

Complexity

In practice, real-world graphs have structure (bounded degree, sparsity, value predicates) that makes these tractable with backtracking and pruning. Small patterns on large graphs are fast.

Pattern Syntax Quick Reference

• N(name) / n(name) — named pattern node / reference, alongside integer N(id) / n(id)
• N(id: pattern) / N(name: pattern) — node value must match a Rust pattern
• E(pattern) — edge value must match a Rust pattern
• E().has::<T>() / E().has_kind(k) — the link holds a part of that kind; .test(|t: &T| ..) reads that part
• !E().has::<T>() — no link holding that part; !E() — no link at all
• X(name = node_id) / X(name = node_id : pattern) — context node pinned to a graph node, optionally value-checked
• pattern![..] — graph-free Pattern; rejects X(..)
• search![&g, p] / search![&g, p with X(a = id), X(b = id), ..] — run a stored pattern, optionally pinning named nodes