GrGen - AbsoluteAstronomy.com

GrGen.NET is a graph transformation tool which generates efficient C#-code (or .NET-assemblies

.NET assembly

In the .NET framework, an assembly is a compiled code library used for deployment, versioning, and security. There are two types: process assemblies and library assemblies . A process assembly represents a process that will use classes defined in library assemblies...

) out of declarative graph rewrite

Graph rewriting

Graph transformation, or Graph rewriting, concerns the technique of creating a new graph out of an original graph using some automatic machine. It has numerous applications, ranging from software verification to layout algorithms....

rule specifications.
Graphs

Graph (mathematics)

In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...

and graph rewrite rules are specified by intuitive domain specific languages (semantics based on the SPO-approach, DPO available as well); they may get used from graph rewrite sequences, a simple, yet for most graph transformation tasks sufficient, special purpose programming language, or via an API by any .NET language.
GrGen is meant to be used for generating the algorithmic

Algorithm

In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

kernel of applications processing graph structured data

Graph (data structure)

In computer science, a graph is an abstract data structure that is meant to implement the graph and hypergraph concepts from mathematics.A graph data structure consists of a finite set of ordered pairs, called edges or arcs, of certain entities called nodes or vertices...

(program graphs, social nets

Social network

A social network is a social structure made up of individuals called "nodes", which are tied by one or more specific types of interdependency, such as friendship, kinship, common interest, financial exchange, dislike, sexual relationships, or relationships of beliefs, knowledge or prestige.Social...

, chemical structures, ...).
For rapid prototyping and debugging, an interactive shell and a (VCG-)graph viewer are included in the package, which executes under Windows

Microsoft Windows

Microsoft Windows is a series of operating systems produced by Microsoft.Microsoft introduced an operating environment named Windows on November 20, 1985 as an add-on to MS-DOS in response to the growing interest in graphical user interfaces . Microsoft Windows came to dominate the world's personal...

and Linux

Linux

Linux is a Unix-like computer operating system assembled under the model of free and open source software development and distribution. The defining component of any Linux system is the Linux kernel, an operating system kernel first released October 5, 1991 by Linus Torvalds...

(Mono

Mono (software)

Mono, pronounced , is a free and open source project led by Xamarin to create an Ecma standard compliant .NET-compatible set of tools including, among others, a C# compiler and a Common Language Runtime....

required) and is open source

Open source

The term open source describes practices in production and development that promote access to the end product's source materials. Some consider open source a philosophy, others consider it a pragmatic methodology...

available under LGPL v3.

Specification sample

An example containing some graph model and rule specifications from the GrGen.NET-solution to the AntWorld-challenge posed at Grabats 08.

Graph model:

node class GridNode {
food:int;
pheromones:int;
}
node class GridCornerNode extends GridNode;
node class AntHill extends GridNode {
foodCountdown:int = 10;
}
node class Ant {
hasFood:boolean;
}

edge class GridEdge connect GridNode[1] -> GridNode[1];
edge class PathToHill extends GridEdge;
edge class AntPosition;

Rewrite Rules:

rule TakeFood(curAnt:Ant)
{
curAnt -:AntPosition-> n:GridNode\AntHill;
if { !curAnt.hasFood && n.food > 0; }

modify {
eval {
curAnt.hasFood = true;
n.food = n.food - 1;
}
}
}

rule SearchAlongPheromones(curAnt:Ant)
{
curAnt -oldPos:AntPosition-> old:GridNode <-:PathToHill- new:GridNode;
if { new.pheromones > 9; }

modify {
delete(oldPos);
curAnt -:AntPosition-> new;
}
}

test ReachedEndOfWorld(curAnt:Ant) : (GridNode)
{
curAnt -:AntPosition-> n:GridNode\AntHill;
negative {
n <-:PathToHill-;
}
return (n);
}

External links

Conference papers

GrGen: A Fast SPO-Based Graph Rewriting Tool/http://www.info.uni-karlsruhe.de/papers/grgen_icgt2006.pdf - ICGT 06
Generation of Sierpinski Triangles: A Case Study for Graph Transformation Tools - AGTIVE 07
Graph Rewriting for Hardware Dependent Program Optimizations - AGTIVE 07
A First Experimental Evaluation of Search Plan Driven Graph Pattern Matching - AGTIVE 07
Customizing GrGen.NET for Model Transformation - GraMoT 08
Graph Rewrite Rules with Structural Recursion - ICGT/GCM 08

Specification sample

External links

Conference papers

See also