Universitšt Karlsruhe
GrGen: A Fast SPO-Based Graph Rewriting Tool

Conference Article

[GBGHS06]Rubino Geiß, Gernot Veit Batz, Daniel Grund, Sebastian Hack, Adam M. Szalkowski, GrGen: A Fast SPO-Based Graph Rewriting Tool, A. Corradini and H. Ehrig and U. Montanari and L. Ribeiro and G. Rozenberg (Ed.), Graph Transformations - ICGT 2006, p. 383 -- 397, Springer, 2006 (Natal, Brasil).


Graph rewriting is a powerful technique that requires graph pattern matching, which is an NP-complete problem. We present GrGen, a generative programming system for graph rewriting. GrGen applies heuristic optimizations making it at least one order of magnitude faster than any other tool known to us, according to Varr\'o's benchmark. Our graph rewriting tool implements the well-founded single-pushout approach. We define the notion of search plans to represent different matching strategies and equip these search plans with a cost model, taking the present host graph into account. The task of selecting a good search plan is then viewed as an optimization problem. For the ease of use, GrGen features an expressive specification language and generates program code with a convenient interface.

[Generate bibTeX entry]




Prof. Sebastian Hack
Dr. Rubino Geiß
Former Students
Gernot Veit Batz
Daniel Grund
Adam M. Szalkowski