singlepushout

Single pushout is a graph transformation approach in which a rewrite step is defined by a single pushout construction in a suitable category, typically graphs and graph morphisms. A rewrite rule is given by a span L <- K -> R, where L is the left-hand side, R the right-hand side, and K the interface.

To apply the rule to a host graph G, one selects a match m: L -> G that identifies an occurrence of the left-hand side inside G. The application then forms the pushout of the span K -> L and K -> G, yielding a new graph H along with the canonical maps from L and G into H. The rule’s effect is described by an induced morphism R -> H, which specifies how the right-hand side is embedded in the transformed graph.

Key properties of the single pushout approach include its permissiveness regarding deletion. If the application would create dangling edges or violate a separate constraint, the pushout construction inherently handles the transfer of information along the interface K, allowing parts of L to be removed or reconnected in G as dictated by the pushout. This means SPO does not require the dangling condition used in the double pushout approach.

Compared with the double pushout (DPO) framework, SPO typically uses one pushout and is thus often simpler and more permissive, at the cost of less control over certain well-formedness conditions. It is used in graph transformation systems, term graph rewriting, and related areas where a direct rule application is advantageous.