|
|
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. |
|---|
|
Contents:
» Description
» Why to use GrGen
» Look'n'Feel
» Download
» Documentation
» Benchmark
» Papers
» Known uses
» History
» Contact
Description
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 github repository).
Debugging and graph visualisation are realized in cooperation with the graph viewer 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.
Look'n'Feel
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
|
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-case posed at Grabats 08
An excerpt from the rule file of the GrGen.NET specification solving the Antworld-case posed at Grabats 08
Download
You can download a binary package of GrGen.NET and the outdated GrGen C:
Documentation
Benchmark
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.
Papers
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
Known Uses
This is a list of some projects using GrGen.NET or papers describing GrGen employments (somewhat outdated, GrGen is also used in industry, and there are more current research projects existing):
History
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.
- 2022-04-01
- Release of GrGen.NET V6.6
- 2022-01-06
- Release of GrGen.NET V6.5
- 2021-07-29
- Release of GrGen.NET V6.1
- 2021-03-28
- Release of GrGen.NET V6.0
- 2020-11-22
- Release of GrGen.NET V5.2
- 2020-07-29
- Release of GrGen.NET V5.1
- 2020-04-27
- Release of GrGen.NET V5.0
- 2017-04-09
- Release of GrGen.NET V4.5
- 2014-07-29
- Release of GrGen.NET V4.4
- 2014-01-12
- Release of GrGen.NET V4.2
- 2013-09-07
- Release of GrGen.NET V4.1
- 2013-07-29
- Release of GrGen.NET V4.0
- 2012-07-29
- Release of GrGen.NET V3.5
- 2011-07-29
- Release of GrGen.NET V3.0
- 2010-09-05
- Release of GrGen.NET V2.6
- 2009-06-28
- Release of GrGen.NET V2.5
- 2008-12-19
- Release of GrGen.NET V2.1
- 2008-07-29
- Release of GrGen.NET V2.0
- 2008-03-20
- Release of GrGen.NET V1.4
- 2008-03-06
- Release of the MOF Suite for GrGen.NET V1.0
- 2007-11-06
- Release of GrGen.NET V1.3
- 2007-07-19
- Release of GrGen.NET V1.2
- 2007-04-19
- First public beta of GrGen.NET
- 2007-04-14
- GrGen has its own domain www.grgen.net
- 2006-10-04
- Last release of C based GrGen
- 2006-09-17
- ICGT 2006: An article stating that GrGen is the world's fastest automatic graph transformation system
- 2003-12-20
- First release of C based GrGen
- 2003-02-01
- Sebastian Hack and Rubino Geiss initiate the development of GrGen
Questions, suggestions, bugs? Feel free to contact the GrGen.NET developers at
| |
