|
|
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 (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 (including multiple edges of the same type)
- Undirected and arbitrarily directed edges
- Node and edge types can be equipped with typed attributes (like structs) including powerful set and map 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 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 (e.g. arithmetic-,boolean-,string- or set-expressions on the attributes)
- Type conditions (including powerful instanceof-like type expressions)
- 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 arbitraty depth (e.g. iterated paths) and breadth (e.g multinodes)
- Parameter passing to rules
- 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
- Attribute re-/calculation (assigning the result of e.g. arithmetic expressions to the attributes)
- 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
- Two modes of specification: A rule can either express changes to be made to the match or replace the whole match
- 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
- A rewrite part for the nested patterns and subpatterns, so that complex structures can not only get matched, but also get rewritten
- Visited flags (which can be written here, in addition to reading them in the pattern language)
- Parameter passing out of rules
- The rule application language (xgrs: extended graph rewrite sequences) supports:
- Composing several rules with sequential, logical, and iterative control
- Variables to store graph elements handed into rules and returned from rules
- Visited flags management
- Storages, i.e. sets and maps capable of storing graph elements and allowing element-wise iteration
- These were the features of the core of 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:
- graph management,
- graph validation,
- graph input and output,
- graph manipulation,
- graph and model queries,
- graph visualisation,
- action execution,
- debugging,
- backend selection and usage.
The debugging and graph visualisation commands are implemented in cooperation with the graph viewer yComp.
Alternatively to GrShell, you can access the match and rewrite facility through LibGr.
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
| |
