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.

Structural Signature¶

Sig role-phrases:

Rule left graph L — Specifies the subgraph sought in the host. It is constitutive. Counterfactual: An unconstrained change script lacks this formal pattern.
Preserved interface K — Identifies nodes and edges carried through the replacement. It is constitutive. Counterfactual: A simple L→R sketch without an interface cannot express the two-pushout construction.
Rule right graph R — Specifies structure introduced after deletion around K. It is constitutive. Counterfactual: A pure pattern matcher is not a rewrite.
Admissible match m:L→G — Locates the pattern in the actual host under gluing conditions. It is constitutive. Counterfactual: A dangling-edge violation blocks the ordinary DPO step.
Pushout complement D — Represents host context after removing matched L\K while preserving K. It is constitutive. Counterfactual: Arbitrary node deletion is not automatically a valid complement.
Second pushout H — Glues R\K onto context D to produce the rewritten host. It is constitutive. Counterfactual: Without this construction there is no completed DPO derivation.

What It Is Not¶

Not an unrestricted graph edit. Matching and gluing conditions constrain each step.
Not merely L→R. K states exactly what survives replacement.
Not single-pushout rewriting. Its treatment of deletion and dangling context can differ.
Not a chemical reaction claim by itself. DPO can model hypothetical reaction patterns.
Closest near-miss. Deleting a vertex that still has an incident host edge outside the matched L resembles a legitimate node-deletion rule but fails the ordinary dangling condition; a different rewriting formalism may handle it differently.

Scope of Application¶

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 rule has a before graph L, an after graph R and a shared interface K. First remove the matched old structure outside K, provided this leaves no forbidden dangling context; then glue the new structure outside K. The two pushouts make replacement mathematically controlled. A chemical-reaction graph tool is one applied use.

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¶

Choose a graph category and rule span L←K→R.
Find a match of L in host G.
Check dangling and identification/gluing conditions.
Construct context D as the first pushout complement.
Glue R to D along K with a second pushout.
Inspect H and domain-specific invariants before another rule step.

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.

Examples¶

Canonical¶

Ehrig, Prange and Ehrig's 2006 mutual-exclusion graph grammar supplies typed rules such as setFlag and enter. In their direct derivation diagrams, L matches the current process/resource-state graph, K carries the unchanged process/resource interface, and the two pushouts remove the old status relation and glue in the new status relation. The slide sequence G₁⇒G₂⇒G₃ makes this a source-authored graph-grammar construction rather than an invented shape change.

Mapped back: Rule left graph L → matched process/resource state before a rule; Preserved interface K → process/resource nodes retained through the step; Rule right graph R → new active/check/critical-state relation; Admissible match m:L→G → rule occurrence in G₁ or G₂; Pushout complement D → host context after removing old relation; Second pushout H → next graph G₂ or G₃.

Applied / In Practice¶

Andersen and colleagues' MØD software represents molecule graphs and chemical reaction patterns as DPO rules, then applies rules to multisets of molecules to generate a reaction network. Their paper's formaldehyde/glycolaldehyde strategy example uses the package's rule application and derivation-graph visualization. This is a published computational-chemistry modeling use, not proof that every generated reaction occurs in a laboratory.

Mapped back: Rule left graph L → reactant pattern in a rule; Preserved interface K → atoms/bonds retained across reaction encoding; Rule right graph R → product-pattern graph; Admissible match m:L→G → matching reactant molecule graph(s); Pushout complement D → context after deleted bond/pattern elements; Second pushout H → resulting product graph and derivation-network edge.

Structural Tensions¶

T1 — Local Replacement versus Host Context Safety. A rule should alter only its match, but unmatched incident edges can make deletion invalid.

Diagnostic: Does the match meet the dangling condition?

T2 — Formal Generality versus Domain Constraints. DPO spans cover broad graph structures, while chemical models require atom and bond labels plus chemically meaningful rules.

Diagnostic: Which constraints belong to graph semantics versus the domain model?

T3 — Rule Expressiveness versus Derivation Explosion. More applicable rules enlarge the generated language but can make exploration combinatorially expensive.

Diagnostic: Which strategy restricts useful derivations?

Structural–Framed Character¶

The approved DAG parent is Graph Rewriting: a rule match transforms a host graph. DPO narrows the semantics to L←K→R, a pushout complement deleting outside the preserved interface, and a second pushout adding replacement structure under gluing restrictions.

Evaluative weight: Low formally; whether the rule models a useful system is separate. Human-practice-bound: Low in derivation, though modelers choose graph category and rule. Institutional origin: Algebraic graph-transformation research defines the method; admissibility is mathematical, not reputational. Vocabulary travels: Software, chemistry, and diagram models may use DPO where required pushouts exist; free-form edits do not. Import versus recognize: A derivation is recognized by its typed match and two valid pushouts; a before/after sketch imports only the replacement analogy.

Its character: A formal subtype of graph rewriting with portable interface-preservation logic and strict categorical conditions.

Structural Core vs. Domain Accent¶

Skeletal core. A local replacement preserves a declared boundary while changing internal structure. Domain-bound accent. Graph morphisms, pushout complements, gluing conditions and typed graph categories make the algebraic semantics precise. Transfer boundary. A visual before/after drawing without two pushouts has only a loose replacement analogy.

This entry is a kind of Graph rewriting.

Neighbor: single-pushout rewriting. Another categorical graph-rewrite semantics with different deletion behavior.
Neighbor: graph grammar. A set of DPO rules can generate a graph language or transition system.

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

Not to Be Confused With¶

Visual graph editor. Tell: May change graph elements without categorical rule semantics.
Single-pushout approach. Tell: Uses a different formal construction and may treat dangling edges differently.
String rewriting. Tell: Has local replacement but not graph-interface morphisms.
Chemical reaction itself. Tell: A modeled DPO rule does not experimentally establish a reaction.

References¶

Ehrig, Prange and Ehrig, “Tutorial on Graph Transformation” — typed DPO production, gluing condition and mutual-exclusion grammar (slides 23–26).
Andersen et al., “A Software Package for Chemically Inspired Graph Transformation” — DPO rule semantics and the MØD chemical-network modeling implementation.