How to Specify a Graph Transformation Approach
Reiko Heckel, Albert Zündorf · Electronic Notes in Theoretical Computer Science · 2001
Application-oriented approaches to graph transformation provide structural features beyond vertices and edges, like composition in hierarchical graphs, inheritance in object-oriented graphs, multiplicity constraints, etc. Often, these features have a specific dynamic interpretation which requires complex embedding mechanisms and context conditions. For example, the deletion of a compound node usually implies the deletion of its components. In this paper, we propose the use of a meta graph grammar for the definition of such a complex graph transformation approach. A meta graph grammar is a typed graph grammar whose type graph provides a static description of the structure of graphs, rules, and transformations of the approach. This static meta model, which is comparable to the meta model in the UML specification, is extended by a specification of the rule application operator by means of graphical embedding rules, i.e., the productions of the meta graph grammar. These embedding rules allow a concise visual description of the admissible context embeddings of a rule and of the side effects of the rule application on the context. As a case-study, a meta graph grammar for selected features of the object-oriented graph transformation approach Fujaba is given.