Double-Pushout Graph Rewriting¶

A graph-rewrite semantics that preserves an interface while two pushouts delete and add matched structure.

Version: v1 · 2026-09-28 · History
Domain-specific #: 9058
Domain group: Applied Sciences & Engineering
Origin domain: Computer Science & Software Engineering
Subdomain: Algebraic Graph Transformation → Computer Science & Software Engineering

Core Idea¶

Double-pushout graph rewriting is a precise account of replacing part of a graph while preserving a specified interface. A rule is a span L←K→R; a match maps L into host G. The first pushout construction removes matched elements of L outside K and leaves context D, and the second glues in elements of R outside K to obtain H. Ehrig and colleagues show this in a typed mutual-exclusion graph grammar. Ordinary node deletion is restricted by the dangling condition.

The structure applies beyond teaching graphs. Andersen and colleagues implement DPO algorithms in MØD to model reaction patterns over molecule graphs, compose rules, and explore generated chemical networks. Their formaldehyde/glycolaldehyde example is a computational model application, not an experimental validation of every possible reaction. DPO's preserved interface and gluing check distinguish it from an arbitrary visual edit or a single-pushout variant.

How would you explain it like I'm…

Swap a Part, Keep the Plugs

Imagine changing a Lego build with a rule card. The card shows a piece to find, which parts to keep, and what to put back. You find a matching spot, take off only the parts the card says, and snap the new parts onto the kept spots. You are not allowed to pull off a piece if something else would be left hanging in the air.

Find, Remove, Glue In

Double-Pushout Graph Rewriting is a careful way to change part of a graph, a network of dots and lines. A rule has three pictures: a 'before' part, a 'kept' part, and an 'after' part. You find where the 'before' part appears in your big graph. First you remove what is in 'before' but not in 'kept', and then you glue in what is in 'after' but not in 'kept', attached at the kept pieces. You may not delete a dot if that would leave a line with a loose end. Scientists have used this idea to model chemical reactions, treating molecules as graphs.

Interface-Preserving Graph Replacement

Double-pushout (DPO) graph rewriting is a mathematical method for replacing part of a graph while preserving a specified interface. A rule is written as L ← K → R: L is the pattern to match, R is the replacement, and K is the interface they share. A match maps L into a host graph G. The first step, a pushout construction, removes the matched parts of L that aren't in K, leaving a context graph D; the second glues in the parts of R not in K, giving the result H. Deleting a node is only allowed if no edges would be left dangling, called the dangling condition. Ehrig and colleagues illustrated it with a typed graph grammar for mutual exclusion, and Andersen and colleagues used it in the MØD software to model chemical reaction patterns on molecule graphs. The preserved interface and gluing check separate DPO from a free-form visual edit or the related single-pushout approach.

Double-pushout (DPO) graph rewriting gives a precise account of replacing part of a graph while preserving a specified interface. A rule is a span L ← K → R, where K is the interface common to the left-hand side L and right-hand side R. Given a match of L into a host graph G, a first pushout construction (performed as a pushout complement) removes the matched elements of L outside K, leaving a context graph D; a second pushout glues in the elements of R outside K to produce H. The dangling condition restricts node deletion so that no edge in the host is left without an endpoint. Ehrig and colleagues demonstrate the approach with a typed mutual-exclusion graph grammar. Beyond teaching examples, Andersen and colleagues implement DPO algorithms in MØD to model reaction patterns over molecule graphs, compose rules and explore generated chemical networks; their formaldehyde and glycolaldehyde example is a computational modeling application, not experimental validation of every reaction. The preserved interface and gluing check distinguish DPO from arbitrary visual edits and from the single-pushout variant.

Scope of Application¶

The preserved interface K and gluing conditions distinguish DPO rewriting from arbitrary graph edits.

Model transformation. Rewrite typed software or process models.
Chemical graph grammars. Represent reaction patterns over molecule structures.
Formal verification. Reason about reachable graph states and invariant preservation.
Diagrammatic reasoning. Apply categorical rewrite rules to graph-like representations.

Clarity¶

A DPO graph rule matches a left graph L in a host, preserves interface K, deletes L outside K and adds R outside K through two pushouts. Dangling edges can make a match invalid. Ehrig's mutual-exclusion grammar and MØD chemical graph modeling show formal and applied uses.

Manages Complexity¶

The host graph may contain context not shown in a local rule. A seemingly simple node deletion can be invalid when an unmatched edge would dangle; identification conditions also matter. Categories of typed or attributed graphs generalize the construction, while domain-specific constraints determine whether a formally possible rewrite is semantically meaningful.

Abstract Reasoning¶

Specify L←K→R, locate a match, check gluing, form the deletion context, glue in R, then inspect the result under domain constraints.

Knowledge Transfer¶

The categorical replacement pattern works in software models, chemistry and diagrammatic formalisms when the graph category supplies the required pushouts and admissible matches. A free-form object update or a rewrite that deletes incident context without a valid complement is not literal DPO rewriting.

Relationships to Other Abstractions¶

Current abstraction Double-Pushout Graph Rewriting Domain-specific

Parents (1) — more general patterns this builds on

Double-Pushout Graph Rewriting is a kind of Graph rewriting Domain-specific

DPO is a graph-rewriting semantics with a preserved interface and two pushouts.

Hierarchy path (1) — routes to 1 parentless root

Double-Pushout Graph Rewriting → Graph rewriting → Transformation → Function (Mapping)

Neighborhood in Abstraction Space¶

Double-Pushout Graph Rewriting sits in a crowded region of the domain-specific corpus (35^th percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.

Family — Graph Structures & Algorithms (24 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-08