|
|
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
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 databases which ease the task of persistent data storage and querying.
Graph rewriting is the high-level way of processing pointer structures;
GrGen.NET offers declarative pattern matching and rewriting in meshes of massively linked objects,
releaving the programmer from directly dealing with pointer structures and pointer structure navigation-, search-, and replacement routines
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 generated program code 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 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 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.
We have recently 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 (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
- 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:
- 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;
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.
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.
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
| |
