Evolutionary Layout of Graph Transformation Sequences

Abstract

Graph transformation is used in various different research areas and has been implemented in several tool environments. However, the layout of graph transformation sequences is often perceived as not optimal and remains to be a difficult task. This is partly due to the slightly different requirements for layouting graph transformation sequences compared to standard graph sequences. In this paper, we clearly define these special requirements and present a layout algorithm which fulfills them. This layout algorithm allows the user to keep track of changes during transformation steps by introducing a concept of node aging and protection of senior node positions in the layout. Furthermore, this layout algorithm introduces a concept of layout patterns. We extended the well-known spring embedder layout algorithm by these new concepts and implemented the new algorithm in AGG, an environment for Attributed Graph Grammars. The layout algorithm has been tested with various graph grammars. A brief outlook describes how this layout algorithm can also be used for different kinds of graph sequences, e.g. sequences of successively developing class diagrams.