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.
GrGen.NET is a programming productivity tool for graph transformation, which eases the modification of graph-based representations, or better: allows you to work on their natural level of abstraction.
Graph representations are typically employed in engineering (blueprints, designs), model transformation (models), computer linguistics (syntax graphs, semantic nets), or compiler construction (intermediate representations, program graphs) -- but a graph is maybe the most natural representation of the data of your domain, too?
GrGen.NET allows you to work with declarative pattern matching and rewriting, instead of low level pointer structure fiddling and tedious boilerplate code.
With GrGen you work on a visualization of your network of objects, instead of chasing objects by following references in the debugger;
you see your mesh of objects and code directly against it!
The Graph Rewrite Generator (see Wikipedia for an explanation of graph rewriting, deutsch: Graphersetzung)
offers an intuitive and expressive domain-specific specification language for graph processing and implements a modification of the theoretically well-founded SPO approach to graph rewriting.
The declarative graph pattern matching and rewriting is integrated into an imperative and object-oriented programming language.
It eases graph representation processing in a similar way like
parser generators ease formal language recognition,
or relational databases ease persistent data storage and querying.
Graph rewriting is the high-level way of processing pointer structures.
(The process of graph rewriting can be divided conceptually 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.
You find it reflected in the model language, the rule language with its pattern and rewrite parts, and the sequences language.)
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).
Debugging and graph visualisation are realized 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 rapid prototyping abilities of the competing graph based tools.
Structure of the GrGen.NET system
Why to use GrGen
GrGen.NET offers processing of graph representations at their natural level of abstraction.
It is built on a rich and efficient metamodel implementing multi-graphs, with multiple inheritance on node and edge types.
The nodes and edges are wired in scalable ringlists, which give access to their incident elements in constant time, to all elements of a type in constant time, and allow to add and delete elements in constant time.
GrGen.NET features modular rules that don't smear functionality into traversal code as is the case in traditional pointer structure passes.
It offers declarative graph patterns of high expressiveness, saving you a lot of boilerplate code that would be needed for coding them manually.
And it implements efficient graph change rollback, thus allowing you to easily crawl search spaces without own bookkeeping (for undoing the changes).
GrGen.NET contains a C#-like programming language, so you don't run against walls in case of subtasks where the rules and patterns don't work well.
The general-purpose system is highly extensible and customizable, you can express solutions fitting well to your task at hand.
GrGen.NET offers the convenience of dedicated languages with well-readable syntax and static type checking, instead of clunky internal DSLs, limited annotations, or annoying XML.
Its languages are brought to life by an optimizing compiler that prunes not needed generality and generates pattern matchers adapted to the characteristics of the host graph at hand.
A runtime library is supplied that implements an easy-to-use API, and features built-in serialization / deserialization.
The system ships with a readily available shell application for file mapping tasks, which especially offers step-wise and visual debugging, saving you from chasing reference chains in the debugger of your programming language.
Further mature development support is offered with search plan explanation and profiling instrumentation.
Moreover, GrGen.NET is properly documented in an extensive user manual.
Traditional programming of graph representation processing is tedious, it requires careful orchestration of functionality attached to passes, boilerplate code for patterns, and low-level pointer fiddling.
You are more productive with GrGen.NET in one-shot-coding a solution, but esp. are you so for a continuous development process or when changes are needed afterwards, a GrGen-specification can be adapted at a much higher pace.
Altogether, GrGen.NET offers the highest combined speed of development and execution for graph representation processing you can find.
The following are toy examples showing the basics while preventing information overload.
Don't let their simplicity mislead you -- GrGen was developed based on real-world graph representations and tasks.
Koch snowflake generation debugging in GrGen.NET (GrShell, yComp); rule, match highlighted
Due to the large amount of regression tests using even the most current version is a pretty safe bet regarding old functionality.
GrGen.NET is free software in terms of the LGPL.
This means in a nutshell: You can freely use GrGen.NET without publishing your code (the generated code is yours, besides it you must only link against libGr.dll and lgspBackend.dll at runtime), but when you extend the supplied code you must share your changes.
The graph viewer yComp which is, for your convenience, part of the release is closed source and free for academic use (yComp is based on the commercially available package yFiles). You are not allowed to ship it with a release of your own commercial software, in contrast to the GrGen libraries.
Download GrGen Binary Distribution (Java/C) (release date 2006-10-04, outdated)
This download package contains the SearchPlan backend for the first time.
For users of previous releases it is necessary to update the GrShell scripts to use the new dynamic libraries.
Some fixes for a bug with NACs introduced with the previous release are included.
Please note that the contained graph engine is a stable version compiled without any optimizations (to enable efficient debugging).
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 everything from applying the rules (i.e.: matching, rewriting, cleanup), and the overhead of executing the rewrite sequences..
GrGen.NET easily copes with millions of graph elements.
It offers the indices you need to quickly find the elements of interest, and parallelized pattern matchers for tasks that are still search-intensive.
This is a small selection of papers on GrGen and GrGen.NET, a full list is available here: