Double-pushout approach
In computer science, double pushout graph rewriting or (DPO graph rewriting) refers to a mathematical framework for graph rewriting. It was introduced as one of the first algebraic approaches to graph rewriting in the article "Graph-grammars: An algebraic approach" (1973). It has since been generalized to allow rewriting structures which are not graphs, and to handle negative application conditions, among other extensions.
A DPO graph transformation system (or graph grammar) consists of a finite graph, which is the starting state, and a finite or countable set of labeled spans in the category of finite graphs and graph homomorphisms, which serve as derivation rules. The rule spans are generally taken to be composed of monomorphisms, but the details can vary.
Rewriting is performed in two steps: deletion and addition.
After a match from the left hand side to is fixed, nodes and edges that are not in the right hand side are deleted. The right hand side is then glued in.
Gluing graphs is in fact a pushout construction in the category of graphs, and the deletion is the same as finding a pushout complement, hence the name.
Double pushout graph rewriting allows the specification of graph transformations by specifying a pattern of fixed size and composition to be found and replaced, where part of the pattern can be preserved. The application of a rule is potentially non-deterministic: several distinct matches can be possible. These can be non-overlapping, or share only preserved items, thus showing a kind of concurrency known as parallel independence, or they may be incompatible, in which case either the applications can sometimes be executed sequentially, or one can even preclude the other.
...
Wikipedia