Universität Karlsruhe

Das Graphersetzungs-Werkzeug. GrGen ist SPO basiert, schnell und einfach benutzbar.

The main features and concepts of GrGen (Graph Rewrite GENerator) are:

  • An expressive graph concept.
    GrGen uses an extension of labelled directed multigraphs, namely attributed typed directed multigraphs. These are directed graphs with typed nodes and edges, where between two nodes more than one edge of the same type and direction is permitted. According to its type, each node or edge has a defined set of attributes associated with it. Moreover the type system features multiple inheritance on node and edge types.
  • The ability to restrict the set of well formed host graphs.
    To restrict the set of well formed graphs, the user can give so called connection assertions. Using these, the system is able to check, whether a host graph is well formed or not.
  • Separated specification of meta model and rewrite rules.
    A meta model defines the allowed node and edge types as well as the attributes associated with each type. Furthermore it contains the mentioned connection assertions. Meta model and rewrite rules can be specified separately. This enables the developer to utilize different rule sets together with the same meta model description.
  • A notion of rewriting close to theory.
    GrGen implements a variation of the single pushout approach (SPO) to graph rewriting. The differences consist in the use of an extended graph concept, some restrictions regarding the allowed matches and the ability of graph rewrite rules to request the re-labelling (i.e. retyping) of nodes.
  • Additional matching conditions and attribute computations.
    The set of valid matches can be restricted beyond graph patterns by the assignment of attribute conditions, type constraints and negative application conditions (NACs) to every rule. Additionally attribute computations can be associated with each rule.
  • Optimization of the matching process.
    Subgraph matching is a NP-complete problem. To deal with this challenge in practice, the system is able to optimize the matching process at run time using knowledge about the current host graph.
  • A well modularized implementation.
    The structure of the generated graph rewriters yielded by GrGen arises from the separation of the following concerns: defining the type of graph elements, storing the graph data, finding the match, and performing the rewrite. This enables us to easily use various strategies for these different tasks.


Entwicklung und Einsatz in Projekten

Graph Rewriting


Prof. Sebastian Hack
Dr. Rubino Geiß
Tom Gelhausen
Gernot Veit Batz
Jakob Blomer
Sebastian Buchwald
Daniel Grund
Enno Hofmann
Edgar Jakumeit
Moritz Kroll
Christoph Mallon
Jens Müller
Andreas Schösser
Adam M. Szalkowski