GrGen

Debugging der Sequenz zum Erzeugen einer Koch-Schneeflocke (links die Regeln, unten die GrShell mit hervorgehobener aktueller Regel, rechts yComp mit hervorgehobener Passung im Arbeitsgraph)

Ausführung des Ersetzungsschrittes

GrGen.NET (Graph Rewrite GENerator, .NET-Version) ist ein Graphersetzungssystem, das aus deklarativen Graphersetzungsregeln effizienten C#-Code (bzw. .NET-Assemblies) generiert. Graphen und Graphersetzungsregeln werden durch intuitive Fachsprachen (DSL) mit einer auf dem SPO-Ansatz beruhenden Semantik (DPO ist ebenfalls verfügbar) spezifiziert. Sie können über Graphersetzungssequenzen genutzt werden, einer einfachen, aber für viele Graphersetzungsaufgaben hinreichenden Steuerungssprache, oder über eine Programmierschnittstelle durch jede .NET-Sprache. GrGen ist dafür vorgesehen, den algorithmischen Kern von Anwendungen zu generieren, die graphartige Daten (Programmgraphen, soziale Netze, chemische Strukturen, ...) verarbeiten. Zum Rapid Prototyping und Debugging enthält das Programmpaket eine interaktive Kommandozeile und einen (VCG-)Graphvisualisierer; es kann unter Windows und Linux (Mono benötigt) ausgeführt werden und ist als Open Source unter der GPL v3 verfügbar.

Beispielspezifikation

Es folgt ein Auszug aus der Graphmodell- und Ersetzungsregelspezifikation der GrGen.NET-Lösung für die AntWorld-Aufgabe, die auf der Grabats 08 gestellt wurde.

Graphmodell:

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;

Ersetzungsregeln:

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);
}

Weblinks

• Hauptseite des GrGen.NET-Projektes
• GrGen.NET User Manual (engl.)
• Kurze Einführung in GrGen.NET (engl.)
• Wissenschaftliche Veröffentlichungen zu GrGen