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