Implementierung und Einsatz von GrGen.NET

Abstract

Die Anwendung einer Graphersetzungsregel besteht aus zwei Teilen: Erstens dem Finden des zu ersetzenden Teilgraphen und zweitens dem eigentlichen Ersetzen. Leider ist die Graphmustersuche ein NP-vollständiges Problem (vgl. Garey and Johnson, Problem GT48). Mithin ist das effiziente Beherrschen der Mustersuche - für einen praktisch relevanten Teil aller Graphen - ausschlaggebend für den Erfolg der Graphersetzung (auch Graphtransformation).

Um trotz der NP-Vollständigkeit der Mustersuche für viele praktisch relevante Fälle Passungen in polynomieller Zeit zu finden, definieren wir eine virtuelle Maschine, deren Programme verschiedenen Suchstrategien entsprechen. Aus der Menge dieser Programme werden bezüglich verschiedener Kostenmodelle gute Programme selektiert, wobei die Kosten aus Domänenwissen oder aus der Analyse des vorliegenden Arbeitsgraphen stammen können. Fernerhin kann die virtuelle Maschine die Programme zur Laufzeit neu optimieren und mit Techniken der dynamischen Programmierung den Suchraum heuristisch weiter beschneiden. Damit gelingt es, für Graphen, bei denen alle starken V-Strukturen, die zur exponentiellen Ausweitung des Suchraums führen, bei der Mustersuche umgehbar sind, linearen Suchaufwand zu garantieren [4]. Für bezüglich dieses Kriteriums "komplexere" Graphen gelingt es immer noch, den Suchaufwand im Erwartungswert heuristisch zu minimieren. Weitere Heuristiken, die spezielle Eigenschaften der Muster- und Arbeitsgraphen ausnutzen, sind integriert.

Die Leistungsfähigkeit unserer Heuristiken wird durch GrGen.NET, dem weltweit schnellsten automatischen Graphersetzungssystem, dokumentiert. Bei mindestens gleicher Ausdrucksstärke und z.T. sogar identischem, also SPO-basiertem, Ersetzungsansatz ist GrGen bezüglich des von Varró entwickelten Benchmarks mindestens 40-mal schneller als das nächstschnellste System (meist um Komplexitätsklassen schneller).

Die Entwicklung von Graphersetzungsanwendungen wird durch eine interaktive Umgebung unterstützt, die, vergleichbar mit einem Debugger für konventionelle Programmiersprachen, das schrittweise Ausführen, Visualisieren und Komponieren von Regel-Sequenzen ermöglicht. Die erweiterten regulären Graphersetzungssequenzen (XGRS) erweisen sich dabei als einfache, aber für viele Bereiche ausreichende Spezifikationstechnik zur Regelauswahl.

Referenzen

1. Blomer,Geiß;GrGen.NET User Manual Universität Karlsruhe, 2008
2. Edgar Jakumeit Mit GrGen.NET zu den Sternen - Erweiterung der Regelsprache eines Graphersetzungswerkzeugs um rekursive Regeln mittels Sterngraphgrammatiken und Paargraphgrammatiken. Diplomarbeit, Universität Karlsruhe, 2008
3. Berthold Hoffmann, Edgar Jakumeit, Rubino Geiß: Graph Rewrite Rules with Structural Recursion. International Workshop on Graph Computation Models, Leicester, September 2008.
4. Gernot Veit Batz, Moritz Kroll, Rubino Geiß, A First Experimental Evaluation of Search-Plan-Driven Graph Pattern Matching, A. Schürr and M. Nagl and A. Zündorf (Ed.), Proc. 3rd Intl. Workshop on Applications of Graph Transformation with Industrial Relevance (AGTIVE '07), Springer, 2008.