doublepushout

Double pushout (DPO) is a formal framework for graph transformation based on category-theoretic pushouts. In DPO, a rule is represented as a span L <- K -> R, where L describes the pattern to be deleted or replaced, R describes what will be added, and K is the interface graph that is preserved during the transformation. A host graph G can be transformed by a match m: L -> G, which must satisfy the gluing condition (also called the dangling condition). This condition ensures that removing the part L\K does not leave edges whose endpoints have been deleted.

The transformation proceeds via two pushouts in a commutative diagram. First, a pushout is formed from the maps K -> L and K -> G, yielding an intermediate graph D that represents the deletion of L\K from G. Second, a pushout is formed from the maps K -> R and K -> D, producing the result graph H, which is G with the specified replacement glued in along K. The preserved part K is the interface that remains invariant through the rewrite.

DPO relies on the existence of pushouts and pushout complements, typically in adhesive categories such as graphs or typed graphs. This framework supports locality and modularity of transformations and provides formal properties like parallelism and, under suitable conditions, confluence.

In comparison with the single-pushout (SPO) approach, DPO imposes stricter matching requirements to avoid dangling edges, yielding different transformation behaviours. DPO is widely used in model transformation, software engineering, and graph-based representations, offering a rigorous basis for defining and analyzing rule-based graph rewriting.

---