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.