Graphersetzungssystem

Beispiel für Graphersetzungsregel (Optimierung aus dem Compilerbau: Multiplikation mit 2 durch Addition ersetzt)

Graphersetzungssysteme dienen der formalen Beschreibung der Veränderung von Graphen. Sie werden häufig mit Computerprogrammen implementiert und damit ausführ- und anwendbar gemacht.

Ein Graphersetzungssystem ist eine Menge $M$ von Graphersetzungsregeln $p\colon L\rightarrow R$. Eine Graphersetzungsregel $p$ besteht aus dem Mustergraphen $L$ der linken Seite sowie dem Ersetzungsgraphen $R$ der rechten Seite.

Eine Regel $p$ wird in einer direkten Ableitung $G{\xrightarrow {p}}H$ angewandt, $G$ ist der Arbeitsgraph vor der Regelanwendung, $H$ der modifizierte Arbeitsgraph danach. Eine Regelanwendung besteht aus dem Finden einer Instanz von $L$ in $G$ (Pattern Matching, hier: Teilgraphen-Isomorphie) und dem Ersetzen der gefundenen Instanz durch eine Instanz der rechten Seite $R$. Eine Ableitung ist eine Folge von Regelanwendungen, die einen Ausgangsgraph in einen resultierenden Graphen überführt.

Verschiebt sich der Fokus vom Verändern eines gegebenen Graphen hin zum Erzeugen aller, aus einem Startgraphen ableitbarer Graphen, wird von einer Graphgrammatik anstelle eines Graphersetzungssystems und von Produktionen anstelle von Regeln gesprochen. Die Vereinigung der beim systematischen Aufzählen entstehenden Graphen ist die Sprache der Graphgrammatik. Meist werden zudem die Graphelemente in Nichtterminale und Terminale unterschieden, und nur die Nichtterminale ersetzt; unter der Sprache werden dann nur die ableitbaren terminalen Graphen verstanden.

Wohlgeformtheit von Graphen wird häufig über das Enthaltensein in der Sprache einer kontextfreien Graphgrammatik definiert. Ein gegebener Graph kann dann mit einem Graphparser, der berechnet, ob er in der Sprache der Graphgrammatik enthalten ist, auf Wohlgeformtheit geprüft werden, im Erfolgsfall erhält man zudem seine Ableitung(en).

Graphersetzungssysteme können (auch) als eine Verallgemeinerung der Termersetzungssysteme von (Grund-)Termen / deren Bäumen auf Graphen angesehen werden.

Algebraischer Ansatz

Die größte Bedeutung bei der Spezifikation von Graphersetzungssystemen hat der algebraische Ansatz erlangt, der mit dem Ziel entwickelt wurde, Chomsky-Grammatiken von Wörtern auf Graphen zu verallgemeinern. Das Finden einer Instanz wird durch das Bestimmen eines Passungs-Graphhomomorphismus $m$ von $L$ in $G$ definiert, die Ersetzung durch die Konstruktion eines einfachen oder doppelten Pushouts.

Graphen

Graphen im Sinne des algebraischen Ansatzes werden formal wie folgt modelliert: ein Graph $G=(E,K,b,e)$ besteht aus zwei Trägermengen $E$ und $K$, den Ecken und Kanten des Graphen, sowie aus zwei Abbildungen $b,e\colon K\rightarrow E$, die festlegen, an welchen Ecken die Kanten beginnen und enden. Oft werden die Ecken und Kanten beschriftet, wobei die Definition des Graphen dann um zwei Funktionen ergänzt wird, die Ecken und Kanten auf geeignete Symbole abbilden.

Es handelt sich also um sog. gerichtete Multigraphen mit Schleifen, als Diagramme zeichnerisch darstellbare Gebilde aus Knoten (Ecken) und gerichteten Kanten (Pfeilen). Sie können so o. ä. in der Informatik zur Formalisierungen von Datenstrukturen, Prozessen etc. eingesetzt werden. Diese spezielle Variation von Graphen stimmt insbesondere mit der graphischen Darstellung von Kategorien überein. In der Literatur zu Graphgrammatiken werden bevorzugt kategoriale Begriffe eingesetzt.

Graph-Homomorphismen

Die Semantik der Ersetzungsregeln wird mit Hilfe von Graph-Homomorphismen erklärt, dies sind strukturhaltende Abbildungen zwischen Graphen. Ein Graph-Homomorphismus $\phi \colon G\rightarrow H$ bildet einen Graphen $G$ derart auf einen Graphen $H$ ab, dass eine Zusammenfassung von Knoten nur dann möglich ist, wenn auch die Kanten passend zusammengefasst werden. Formal besteht damit $\phi$ aus zwei Funktionen $\phi _{E}\colon E_{G}\rightarrow E_{H}$ und $\phi _{K}\colon K_{G}\rightarrow K_{H}$, derart, dass gilt:

1. $b_{H}\circ \phi _{K}=\phi _{E}\circ b_{G}$
2. $e_{H}\circ \phi _{K}=\phi _{E}\circ e_{G}$

Ersetzung

Bei der Definition des Ersetzens wird die Konstruktion eines einfachen Pushouts (Single Pushout, SPO) von der Konstruktion eines doppelten Pushouts (Double Pushout, DPO) unterschieden.

Double Pushout Diagramm

Der Zusammenhang zwischen $L$ und $R$ im DPO wird durch einen Klebegraphen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle K} und zwei Graphhomomorphismen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle l\colon K \rightarrow L} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r\colon K \rightarrow R} hergestellt. Im Ersetzungsschritt bleiben die Elemente aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle K} erhalten, die aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L \setminus K} werden gelöscht, die aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R \setminus K} hinzugefügt.

Single Pushout Diagramm

Im SPO hingegen wird der Zusammenhang zwischen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R} durch einen partiellen Graphhomomorphismus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r\colon L \rightarrow R} hergestellt. Im Ersetzungsschritt bleiben durch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r} in Beziehung gesetzte Elemente erhalten, die nicht in Beziehung stehenden aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L} werden gelöscht, die nicht in Beziehung stehenden aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R} werden hinzufügt.

Beim Ersetzen können zwei Konfliktfälle auftreten:

1. Ein zu löschender und ein zu erhaltender Musterknoten werden auf den gleichen Arbeitsgraphknoten abgebildet, es ist nicht klar, ob gelöscht oder erhalten werden soll. (Ein Graphhomomorphismus ist nicht zwangsläufig injektiv.)
2. Ein zu löschender Knoten ist mit nicht im Mustergraphen angegebenen Kanten mit dem restlichen Arbeitsgraphen verbunden, nach alleinigem Löschen des Knotens würden Arbeitsgraphkanten in der Luft hängen.

Die Regelanwendung im DPO wird durch die Konstruktion von zwei Pushouts beschrieben, was in den beiden Konfliktfällen nicht möglich ist, womit die Regel in diesen Fällen nicht angewendet werden kann.

Die Regelanwendung im SPO wird durch die Konstruktion eines Pushouts beschrieben, was bewirkt, dass im 1. Fall Löschen Vorrang vor Erhalten hat, und im 2. Fall in der Luft hängende Kanten gelöscht werden.

Alternative Definitionen

Weitere Vorgehensweisen innerhalb des algebraischen Ansatzes stellen der Sesqui-Pushout- sowie der Pullback-Ansatz dar.

Weniger mächtige, kontextfreie Formulierungen von Graphersetzung (außerhalb des algebraischen Ansatzes) sind die Knotenersetzung und die Hyperkantenersetzung. Bei der Knotenersetzung besteht das Muster jeweils nur aus einem Knoten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} , der Ersetzungsgraph wird anhand von Verbindungsinstruktionen mit den, vor der Regelanwendung zu der Instanz von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} benachbarten (adjazenten) Knoten verbunden. Bei der Hyperkantenersetzung besteht das Muster jeweils nur aus einer Hyperkante Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle e} , der Ersetzungsgraph wird mit den, vor der Regelanwendung an der Instanz von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle e} anliegenden (inzidenten) Knoten verklebt.

Anwendung der Graphersetzung

Während die Graphentheorie in der Mathematik Graphen und deren Eigenschaften (wie zum Beispiel Färbbarkeit) betrachtet, und die Graphentheorie in der Theoretischen Informatik ihre Aufmerksamkeit auf Graphersetzungssysteme und deren Eigenschaften (zum Beispiel Konfluenz) richtet, steht für die Praktische Informatik die Bereitstellung von effizienten Graphersetzungssystemen im Vordergrund, die im Rahmen der Angewandten Informatik zum Modellieren von Daten in Form von Graphen und der Spezifikation von Berechnungen auf den Graphen durch Graphersetzungsregeln benutzt werden.

Graphen bieten sich als anschaulicher, mathematisch präziser und ausdrucksstarker Formalismus zur Modellierung von in Beziehung stehender Objekte (Entitäten) an, die Objekte werden dabei in Knoten codiert und die Beziehungen durch Kanten dargestellt. Unterschiedliche Objekte und Beziehungen werden durch unterschiedliche Knoten- und Kantentypen ausgedrückt, in Abhängigkeit von den Typen können die Graphelemente darüber hinaus noch mit Attributen versehen werden. Berechnungen werden in diesem Modell durch Veränderung der Beziehungen zwischen den Objekten dargestellt, aber auch der Veränderung der Attribute. Sie werden durch Graphersetzungsregeln beschrieben.

In der Praxis erfolgt eine, gegenüber dem indeterministischen Konzept des reinen Graphersetzungssystems stärkere, algorithmischere Kontrolle der Regelanwendung, die den Indeterminismus der Regel (welche Regel aus der Regelmenge wird angewendet?) und den Indeterminismus des Ortes (an welcher Stelle im Arbeitsgraphen wird die Regel angewendet?) einschränkt. Dabei kann über Steuerkonstrukte wie Abfolge, Alternative oder Iteration die nächste anzuwendende Regel bestimmt werden (in Abhängigkeit von Erfolg oder Fehlschlag der vorherigen Regelanwendung), oder durch Parameterübergabe zwischen den Regeln das Bearbeiten eines gemeinsamen Ansatzes sichergestellt werden. Es wird dann von "Programmierter Graphersetzung" gesprochen.

Graphen sind in Form von verzeigerten Strukturen (Objekte = Knoten, Referenzen/Zeiger = gerichtete Kanten) in jedem größeren Programm implizit anzutreffen. Sind Objekte, insbesondere Muster von miteinander verbundenen Objekten zu suchen und zu ersetzen, ist ein explizit machen durch die Nutzung eines Graphersetzungssystems lohnend; es kann dann mit kurzen, deklarativen Graphersetzungsregeln gearbeitet werden, anstelle von umfangreichen, handprogrammierten Such- und Ersetzungsunterprogrammen.

Graphersetzungssysteme setzen den Fokus auf die musterbasierte Verarbeitung von Graphen im Hauptspeicher, im Gegensatz zu Graphdatenbanken, die mit dem Ziel der persistenten Speicherung im transaktionssicheren Mehrbenutzerbetrieb entwickelt werden.

Anwendungsbeispiele

• Softwaretechnik: Modellgetriebene Softwareentwicklung mit UML-Graphen
• Übersetzerbau: Optimierungen auf graphbasiertem Zwischencode
• Biologie, Grafik
• Produktentwicklung, Produktkonfiguration, Systems Engineering

Allgemeine Graphersetzungssysteme

• GrGen.NET
• PROGRES

Auf Graphersetzung aufbauende Systeme

• Tripel-Graph-Grammatik (Modelltransformation)
• Fujaba (Visuelle Programmierung, Modelltransformation)

Literatur

• G. Rozenberg (Hrsg.): Handbook of Graph Grammars and Computing by Graph Transformation. 3 Bände. World Scientific Publishing, Singapore u. a. 1997–1999.

Weblinks

• Graph Transformation in a Nutshell (PDF; 235 kB)
• Algebraic Approaches to Graph Transformation, Part I: Basic Concepts and Double Pushout Approach
• Computing with Graphs and Graph Rewriting
• Graph Transformation for Specification and Programming
• Model Transformation by Graph Transformation: A Comparative Study (PDF; 2,5 MB)
• Vorlesung Graphersetzungssysteme