title: Compiled graph transformation
topics: Algorithms and Data Structures , Graphs
committee: Arend Rensink


The FMT-based open source tool GROOVE can transform graphs (using user-provided rules describing the transformations) by adding and removing nodes and edges. Since the graphs can stand for pretty much any kind of system, ranging from computer networks to games, this is a very powerful and versatile modelling formalism.

The current implementation of GROOVE is based on the interpretation of rules. Instead, one could compile rule systems to Java programs. From graph transformation tool contests, it is well known that this can result in orders of magnitude of speedup.

This (very challenging) assignment involves the implementation of a rule compiler for GROOVE. The resulting program should be able to take rule systems (possibly using only a subset of the features offered by GROOVE) and produce Java programs that, when invoked, explore the resulting state spaces exactly as GROOVE would, but with a significantly improved time and memory performance.