GrGen.NET: transformation of structures made easy.
The Graph Rewrite Generator offers declarative languages for graph modeling, pattern matching, and rewriting, as well as rule control; brought to life by a compiler emitting highly efficient assemblies and a rapid prototyping environment offering graphical and step-wise debugging.
» Known uses
GrGen.NET is a programming tool for graph transformation,
which eases the transformation of complex graph structured data as e.g. required in model transformation, computer linguistics, or modern compiler construction,
comparable to other programming tools like parser generators which ease the task of formal language recognition,
or relational databases which ease the task of persistent data storage and querying.
Graph rewriting is the high-level way of processing pointer structures.
GrGen.NET allows you to work at the abstraction level of graphs,
with declarative pattern matching and rewriting, on a visualization of your mesh/network of objects,
instead of low level pointer structure fiddling, chasing objects by following references in the debugger.
GrGen.NET (Graph Rewrite Generator, see Wikipedia for an explanation of graph rewriting, deutsch: Graphersetzung)
features an intuitive and expressive domain specific specification language for graph rewriting and implements a modification of the theoretically well-founded SPO approach to graph rewriting (DPO available as well).
The program code generated by GrGen executes very fast and is easy to invoke through a comfortable API.
According to a benchmark introduced by Varr贸
the performance of rewriting, especially of the potentially costly pattern matching, is at least one order of magnitude faster than of any other known system.
In most cases GrGen.NET outperformes the other systems even by some complexity classes.
We achieve this by using specially tailored data structures and by a dynamically optimizing approach to subgraph matching,
which means that the pattern matchers can be recompiled at runtime to maximally exploit the structure of the actual present host graph.
In this context we use the concept of search plans to represent different matching strategies.
By stating a cost model we understand the generation of good search plans as an optimization problem, which we solve heuristically.
In contrast to systems like Fujaba our pattern matching algorithm is fully automatic and does not need be tuned or partly be implemented by hand.
Due to its textual specification languages, you can easily generate GrGen-specifications on your own, or diff specification changes.
A while ago we re-implemented the original GrGen system (written in Java/C, yielding a C based virtual machine interpreting the matcher).
The result of this effort is the new GrGen.NET system for graph rewriting (written in Java/C#, yielding C# code implementing the matcher).
Its core is the Graph Rewrite Generator, which turns declarative rewrite
specifications into .NET assemblies performing the rewrites.
The GrGen.NET system consists of the generator written in Java and C#, a graph backend
written in C# and the .NET assemblies generated by the generator.
The system - available under Windows and Linux - is open source licensed under LGPL v3,
you find the code in the download section (public mercurial repository).
Structure of the GrGen.NET system
The process of graph rewriting can be divided into four steps:
Representing a graph according to a model (creating an instance graph),
searching a pattern aka finding a match,
performing changes to the matched spot in the host graph,
and, finally, selecting which rule(s) to apply where next.
We have organized the presentation of the features of GrGen.NET according to this breakdown of graph rewriting.
- The graph model (meta-model) supports:
- Typed nodes and edges, with multiple inheritance on types
- Directed multigraphs (supporting multiple edges of the same type between two
- Undirected and arbitrarily directed edges
- Node and edge types can be equipped with typed attributes (like structs), of the commonly known elementary types or of some container types
- Connection assertions to restrict the "shape" of graphs
- Turing complete language for checking complex conditions
- The pattern language supports:
- Plain isomorphic subgraph matching (injective mapping)
- Homomorphic matching for a selectable set of pattern elements, so that they may match (non-injectively) the same graph element
- Type conditions (including instanceof-like type expressions)
- Attribute conditions (e.g. arithmetic-,boolean-,string- or set-expressions on the attributes)
- User-defined functions for complex attribute conditions, and graph querying
- Subgraph extraction and graph comparison operators (graph isomorphism)
- Nested patterns, specifying negative and positive application conditions as well as iterated, optional, or alternative structures
- Subpatterns for pattern reuse, allowing via recursion to match substructures of arbitrary depth (e.g. iterated paths) and breadth (e.g multinodes)
- Parameter passing to rules and subpatterns
- The rewrite language supports:
- Keeping, adding and deleting graph elements according to the SPO approach
- Choosing out of three additional rule application semantics: DPO or exact patterns only or induced subgraphs only
- Retyping of nodes/edges (a more general version of casts known from common programming languages)
- Creation of new nodes/edges of only dynamically known types or as exact copies of other nodes/edges
- Two modes of specification: A rule can either express changes to be made to the match or replace the whole match
- Attribute re-/calculation (assigning the result of e.g. arithmetic expressions to the attributes)
- User-defined procedures for complex attribute assignments, and graph manipulations
- A rewrite part for the nested patterns and subpatterns, so that complex structures can not only get matched (parsing), but also get rewritten (transduction)
- Embedded graph rewrite sequences capable of calling other rules (with access to the nodes/edges of the rule)
- Emitting user-defined text to stdout or files during the rewrite steps
- Visited flags and storages to communicate between rule applications using state
- Parameter passing out of rules and subpatterns
- The rule application control language (xgrs: extended graph rewrite sequences) supports:
- Rule execution
- Logical and sequential connectives
- Decisions and loops for control-flow orchestration of the rule applications
- Variables for data-flow orchestration of the rule applications
- A computations sublanguage offering basic graph querying and manipulation
- -- as well as visited flags and storages management
- Extended control (e.g decisions, transactions, backtracking, indeterministic choice)
- Sequence definitions (for procedural abstraction of rule application strategies)
- These constructs combined allow to easily program unfolding searches or state space enumerations
- The rapid prototyping environment
These were the features of the core of the GrGen.NET-System,
the generator grgen.exe and its languages plus its runtime environment libGr.
In addition, the GrGen.NET system offers a shell application, the GrShell,
which features commands for:
The debugging and graph visualisation commands are implemented in cooperation with the graph viewer yComp;
combined with the expressive rules they allowed us to win both of the GraBaTs live contests held (GraBaTs 2008, GraBaTs 2009),
which were measuring the expressiveness and rapid prototyping abilities of the competing graph based tools.
- graph management,
- graph import and export,
- graph validation,
- direct graph manipulation,
- graph change recording and replaying,
- graph and model queries,
- highly customizable graph visualisation (including automagically nested graphs keeping large graphs understandable),
- graph rewrite sequence execution,
- debugging (step-by-step execution of the sequences, highlighting the matches of the rules in the graph, and their changes to the graph).
Alternatively to GrShell, you can include the graph model and rewrite rules directly into your code and/or access them through LibGr.
This way you can build your own applications with a graph rewriting core in a .NET language of your choice.
The other way round you can include C#-code into your specifications by using external types or calling external functions and procedures, as well as sequences.
Koch snowflake generation debugging in GrGen.NET (GrShell, yComp); rule, match highlighted
Koch snowflake generation debugging in GrGen.NET (GrShell, yComp); rule, rewrite highlighted
An excerpt from the model file of the GrGen.NET specification solving the Antworld-challenge posed at Grabats 08
An excerpt from the rule file of the GrGen.NET specification solving the Antworld-challenge posed at Grabats 08
You can download a binary package of GrGen.NET and the outdated GrGen C:
This benchmark was introduced by Gergely Varr贸. The benchmark itself is described in a tech report. A more high-level description as well as runtimes for several graph rewrite systems are given in a paper by Gergely Varr贸, Andy Sch眉rr, and Daniel Varr贸.
Extensive benchmark results can be found on a website maintained by Gergely Varr贸. The original measurements carryied out by Varr贸 contained some flaws, being described in our paper On Improvements of the Varro Benchmark for Graph Transformation Tools. The figures below reflect the improvements suggested by this paper. To get a better insight at the performace of the faster tools we performed measurements far beyond the size suggested by Varr贸.
Note the logarithmic scaling of the time axis.
Note the logarithmic scaling of the time and the size axis.
Note the logarithmic scaling of the time and the size axis.
The benchmark was conducted using the LGSP backend of GrGen.NET on an AMD Athlon(tm) XP 3000+ running SuSE Linux 9.3 with 1 GiB main memory.
The runtime displayed includes the whole rule applications i.e.: matching, rewriting, cleanup, and the overhead executing the rewrite sequences.
This is a small selection of papers on GrGen and GrGen.NET, a full list is available here:
- Gei脽, Batz, Grund, Hack, Szalkowski, GrGen: A Fast SPO-Based Graph Rewriting Tool
- Kroll, Gei脽: Developing Graph Transformations with GrGen.NET
- Batz, Kroll, Gei脽: A First Experimental Evaluation of Search Plan Driven Graph Pattern Matching
- Hoffmann, Jakumeit, Gei脽: Graph Rewrite Rules with Structural Recursion
- Gei脽: Graphersetzung mit Anwendungen im 脺bersetzerbau (Diss., dt.)
- Jakumeit, Buchwald, Kroll: GrGen.NET
This is a list of some projects using GrGen.NET or papers describing GrGen employments:
- The AutoModel and SaleMX projects - Natural Language to UML
- The booggie project - Graph grammars for the domain of mechanical engineering
- Skalch - Sketching for scala, a compiler for programs with holes
- The GMoC tool and the locutor project - Are concerned with the management of change on collections of documents
- GRAPE - Implements SHAPE and Palladian grammars from the domain of architecture
- Sch枚sser, Gei脽: Graph Rewriting for Hardware Dependent Program Optimizations
- Gelhausen, Derre, Gei脽: Customizing GrGen.NET for Model Transformation
- Schimmel, Gelhausen, Schaefer: Gene Expression with General Purpose Graph Rewriting Systems
- Bedaride, Gardent: Semantic Normalisation: a Framework and an Experiment
- Van Gorp, Eshuis: Transforming Process Models: executable rewrite rules versus a formalized Java program
- BPMN operational semantics in GrGen, a series of screencasts by Pieter van Gorp
- Buchwald, Zwinkau: Instruction Selection by Graph Transformation
This is a link to the homepage of the previous release of GrGen. It is outdated and will not be maintained or updated, but may be of historical interest.
- Release of GrGen.NET V4.0
- Release of GrGen.NET V3.5
- Release of GrGen.NET V3.0
- Release of GrGen.NET V2.6
- Release of GrGen.NET V2.5
- Release of GrGen.NET V2.1
- Release of GrGen.NET V2.0
- Release of GrGen.NET V1.4
- Release of the MOF Suite for GrGen.NET V1.0
- Release of GrGen.NET V1.3
- Release of GrGen.NET V1.2
- First public beta of GrGen.NET
- GrGen has its own domain www.grgen.net
- Last release of C based GrGen
- ICGT 2006: An article stating that GrGen is the world's fastest automatic graph transformation system
- First release of C based GrGen
- Sebastian Hack and Rubino Geiss initiate the development of GrGen
Questions, suggestions, bugs? Feel free to contact the GrGen.NET developers at