Algebraic approach to graph transformation

Let's start with the first talk of the seminar held on October 18, 2007 about the algebraic approach to graph transformation that can be subdivided in the single and the double pushout approach. These terms sound quite daunting, but the underlying concept is not hard to grasp. Both approaches are based on the concepts graph, production and graph grammar, that I will not introduce here in detail. Just note, that the concepts production and grammar can be understood quite closely to the analog notions in string rewriting.



In the double pushout approach DPO a production consists of three graphs. The left-hand side (lhs) graph L is the graph to be matched. The interface graph K is the so-called gluing graph, i.e. the subgraph of L that is not deleted by the production. And the right-hand side (rhs) graph R is the graph L should be replaced with. Between K and the graphs L and R morphisms l and r have to be given mainly because corresponding nodes and edges have to be identified. If this production should be applied to a host graph G a double pushout has to be constructed. Therefore we need to find a match of L in G (also a morphism, m). Next all parts of G have to be deleted that are not in L (of course we mean the images regarding the particular morphism). And finally we have to embed into the resulting graph D all parts of R that are not in L leading to the target graph H. A production can only be applied if the morphism diagram commutes and the universal pushout property holds twice -- this sounds complicated but it conforms to the intuitive understanding of graph transformation. The DPO is very nice from a mathematical point of view, however, it is not always applicable.



The single pushout approach SPO does not need a gluing graph K. A production just consists of a lhs graph L and a rhs graph R with a partial morphism inbetween. As in DPO a match of L in G has to be found. This match gets replaced by R. Nodes and edges not occurring in the rhs anymore are deleted rigorously.

The main difference between single and double pushout is the so-called dangling edge condition. Following the double pushout approach a node must not be removed if there are still edges to this node. In the single pushout approach this restriction is canceled: all dangling edges are just deleted. This deletion of edges makes the SPO quite difficult from a theoretical point of view.

Ok, so far for now. Sorry for starting with theory -- I promise that practical topics will be the focus of this blog in the future :-)

Further reading:

• Handbook of Graph Grammars and Computing by Graph Transformation, Rozenberg (ed.), 1997, World Scientific Publishing: chapters 3 and 4


• Graph Transformation in a Nutshell, Reiko Heckel, Electronic Notes in Theoretical Computer Science, Volume 148, Issue 1, Proceedings of the School of SegraVis Research Training Network on Foundations of Visual Modelling Techniques (FoVMT 2004), 2006, Pages 187-198.