|
|
|---|
Contents:
» Description
» Why to use GrGen
» Look'n'Feel
» Download
» Documentation
» Benchmark
» Papers
» Some uses
» Contact
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 (a .NET-API, so only a thin layer of interop is needed to employ it in a native application, in contrast to JAVA based solutions). 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 yComp; combined with the expressive rules they allowed us to win both of the GraBaTs live contests held, which were measuring the rapid prototyping abilities of the competing graph based tools (GraBaTs 2008 and GraBaTs 2009, which became the origin of the current Transformation Tool Contest series; the GraBaTs workshop series ended with GraBaTs 2014).
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 |
Koch snowflake generation debugging in GrGen.NET (GrShell, yComp); rule, rewrite highlighted |
|---|
You can download a binary package of GrGen.NET:
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ó.
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 (back then, speed mattered even more ;). 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 (similar to a database), and parallelized pattern matchers for tasks that are still search-intensive.
In the following, we give an annotated selection of papers on GrGen and GrGen.NET, a full list is available here, together with an overview of the project history (including links to copies of the old homepage supplied by the Wayback Machine).
This is a list of some usages of GrGen.NET you find online, roughly ordered by their domains (some external, some from IPD ; some papers from behind the paywall, others not), enriched by some overviews:
In engineering, in the emerging field of computational design synthesis, do you find several employments. A first one was in the booggie project as described in Helms: Object-Oriented Graph Grammars for Computational Design Synthesis, or in Münzer, Helms, Shea: Automatically Transforming Object-Oriented Graph-Based Representations Into Boolean Satisfiability Problems for Computational Design Synthesis (esp. aimed at mechanical and electrical engineering), booggie was succeeded by the commercially available products from soley. The Engineering Design and Computing Laboratory is using GrGen to synthesize designs, as described in e.g. Königseder: A Methodology for Supporting Design Grammar Development and Application in Computational Design Synthesis or in Stöckli, Shea: Automated Synthesis of Passive Dynamic Brachiating Robots Using a Simulation-Driven Graph Grammar Method. The Chair of Computational Modeling and Simulation is utilizing GrGen.NET for civil engineering, esp. the detailing of parametric building graphs as described in Abualdenien, Borrmann: PBG: A parametric building graph capturing and transferring detailing patterns of building models and in Vilgertshofer: Unterstützung parametrischer Modellierung durch Graphersetzung: Automatisierte Erstellung von graphbasierten Modellrepräsentationen. In architecture, you find employments with GRAPE and GRAPE For Web, implementing SHAPE and Palladian grammars. Some recent overview papers over that field are available with Kolbeck, Vilgertshofer, Abualdenien, Borrmann: Graph Rewriting Techniques in Engineering Design and Voss, Petzold, Rudolph: Graph transformation in engineering design: an overview of the last decade.
GrGen.NET was used in natural language processing, the SENSE / Sale Project was concerned with Model Extraction from Natural Language Texts, some results are described in Tichy, Körner: Text to software: developing tools to close the gaps in software engineering and Gelhausen: Modellextraktion aus natürlichen Sprachen: eine Methode zur systematischen Erstellung von Domänenmodellen. A usage in computer linguistics is described in Bedaride, Gardent: Semantic Normalisation: a Framework and an Experiment. In that realm, feature structures are popular, you find direct support for them with the grew tool, which the general-pupose tool GrGen.NET is lacking, but the mentioned tool on the other hand is lacking the context-free grammar like pattern und rule building GrGen is offering with its recursive and iterated patterns (allowing you to capture and rewrite entire subtrees or limited graphs within one rule application or query).
GrGen was originally produced for compiler construction, so of course do you find some uses in formal language processing with Schösser, Geiß: Graph Rewriting for Hardware Dependent Program Optimizations and Buchwald, Zwinkau: Instruction Selection by Graph Transformation; as well as e.g. Skalch - Sketching for scala, a compiler for programs with holes (available on github). (As a personal note: in case you're not a major in the subject, you may find this tutorial to be of interest.)
Somewhat related to formal languages and their processing are models and their transformation, often naturally leading to graphs (a reason why graph based and model transformation tools are competing in a joint Transformation Tool Contest), in Gelhausen, Derre, Geiß: Customizing GrGen.NET for Model Transformation do you find how to cope with the respective standards from the domain of model transformation, the MOF/UML technical space defined by OMG, in Van Gorp, Eshuis: Transforming Process Models: executable rewrite rules versus a formalized Java program (Preprint do you find a use from Business Process Management and Transformation Engineering. The Ontology-Driven Management of Change research project and the the locutor project were concerned with the management of change on collections of documents, modelled as graphs. A survey and comparison of graph and model transformation tools, with a focus on the expressiveness in their ability to capture graph structures is given in Jakumeit, Buchwald, Wagelaar, Dan, Hegedüs, Herrmannsdörfer, Horn, Kalnina, Krause, Lano, Lepper, Rensink, Rose, Wätzoldt, Mazanek: A survey and comparison of transformation tools based on the transformation tool contest.
Below do you find a video (originally available on screenr.com) from a series of screencasts recorded by Pieter van Gorp related to the paper A visual token-based formalization of BPMN 2.0 based on in-place transformations - watch it to see GrGen in action (an older version, but it should still give a good impression of the software and its merits when employed for model transformation tasks).
The Schimmel, Gelhausen, Schaefer: Gene Expression with General Purpose Graph Rewriting Systems paper describes a potential use in bio informatics/biology.
Questions, suggestions, bugs? Feel free to contact the GrGen.NET developers at
