|
|
GrGen.NET is a generative programming system for graph rewriting,
consisting of a compiler transforming declarative graph rewrite rule specifications into highly efficient .NET-assemblies
and a rapid prototyping environment offering graphical and stepwise debugging of programmed rule applications. |
|---|
|
Contents:
» Description
» Look'n'Feel
» Download
» Documentation
» Benchmark
» Papers
» History
» Contact
Description
The GrGen.NET graph transformation tool (Graph Rewrite Generator, see Wikipedia for an explanation of graph rewriting, deutsch: Graphersetzung)
features an intuitive and expressive specification language (a domain specific language for graph rewriting) and implements a modification of the theoretically well-founded SPO approach to graph rewriting (DPO available as well).
The generated program code executes very fast and is easy to invoke through a comfortable interface.
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 sytems 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 optimization can be done at runtime depending on 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.
We have recently re-implemented the original GrGen system (written in Java/C).
The result of this effort is the new GrGen.NET system for graph rewriting (written in Java/C#).
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, 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 (source distribution/public svn).
Structure of the GrGen.NET system
The process of graph rewriting can be divided into four steps:
Representing a graph according to a model, searching a pattern aka finding a match, performing changes to the matched spot in the host graph, and, finally, selecting the next rule(s) for application.
We have organized 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 (including multiple edges of the same type)
- Undirected and arbitrarily directed edges
- Node and edge types can be equipped with typed attributes (like structs)
- 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 nodes/edges, so that the matching is not injective
- Besides SPO, three additional modes for the semantics of a rule application can be choosen: matching of exact patterns only, matching of induced subgraphs only, and DPO semantics
- Attribute conditions (including arithmetic operations on the attributes)
- Type conditions (including powerful instanceof-like type expressions)
- Parameter passing to rules
- Dynamic patterns with iterative or recursive paths and graphs
- The rewrite language supports:
- Attribute re-calculation (using arithmetic operations on the attributes)
- Retyping of nodes/edges (a more general version of casts known from common programming languages)
- Creation of new nodes/edges of statically as well as dynamically computed types (some kind of generic templates)
- Two modes of specification: A rule can either express changes to be made to the match or replace the whole match (the semantics is always mapped to SPO)
- Returning certain edges/nodes for further computations
- Copying (duplicating) of elements from the match - comparable with sesqui-pushout rewriting (yet to be implemented)
- Composing several rules with logical and iterative sequence control (called extended graph rewrite sequences, XGRS), including support for nested transactions
- Emitting user-defined text to stdout during the rewrite steps
- The rule application language (GrShell) supports:
- XGRS support
- Various methods for creation/deletion/input/output of graphs/nodes/edges
- Stepwise and graphic debugging of rule application
- Graph rewrite sequences that can contain nested transactions
- Alternatively to GrShell, you can access the match and rewrite facility through LibGr.
In this way you can build your own algorithmic rule applications in a .NET language of your choice.
Look'n'Feel
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
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 the whole rule applications i.e.: matching, rewriting, cleanup, and the overhead executing the rewrite sequences.
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
- Schösser, Geiß: Graph Rewriting for Hardware Dependent Program Optimizations
- Gelhausen, Derre, Geiß: Customizing GrGen.NET for Model Transformation
- Hoffmann, Jakumeit, Geiß: Graph Rewrite Rules with Structural Recursion
- Geiß: Graphersetzung mit Anwendungen im Übersetzerbau (Diss., dt.)
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.
- 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-12-06
- Release of GrGen.NET V1.3.1
- 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
| |
