Diff für gerichtete azyklische Graphen
Ich suche nach einem Algorithmus, der diff zwei gerichtete azyklische Graphen (DAGs) haben kann. Das heißt, ich möchte einen Algorithmus, der eine Sequenz von Deletionen und Insertionen auf der ersten DAG erzeugt, um die zweite DAG zu erzeugen.
Ich bin mir nicht hundertprozentig sicher, aber ich denke, dass eine längste gemeinsame Subsequenz auf die DAGs angewendet werden kann. Ich bin weniger besorgt über die Länge der resultierenden Editiersequenz (solange sie kurz genug ist) und mehr um die Laufzeit des Algorithmus besorgt.
Eine Komplikation ist, dass keiner meiner Vertices mit Ausnahme eines einzelnen Wurzelknotens beschriftet ist. Der Wurzelknoten ist auch der einzige Knoten mit Null-In-Kanten. Die Kanten des Diagramms sind beschriftet, und die "Daten" im Diagramm werden durch die Pfade von der Wurzel bis zu den Blättern dargestellt. Dies ist ähnlich einem trie , aber mit einem gerichteten Graphen anstelle eines Baumes. Tatsächlich sind meine Graphen der directed acyclic word graph -Datenstruktur sehr ähnlich.
Hier ist ein Beispiel.
DAG1
DAG2
Um DAG 2 zu erhalten, fügen Sie einfach einen Scheitelpunkt von der Wurzel zu einem anderen Scheitelpunkt mit dem Label 'b' hinzu. Von diesem Eckpunkt gibt es eine Kante zum letzten "ac" Vertex in DAG 1 und eine Kante zu einem neuen Eckpunkt, dessen Label "d" ist. Von diesem letzten Scheitelpunkt gibt es eine weitere Kante zum Scheitelpunkt 'ac' in DAG 1. Ich würde einen Link zum Diff im DAG-Formular veröffentlichen, aber ich kann nicht mehr als zwei Links posten.
Danke und hoffe, das ist lesbar genug.
1 Antwort
Das könnte ein bisschen zu spät sein, aber nur zum Spaß: Beide DAGs können als Matrizen ausgedrückt werden, wobei der Zeilenindex den "von" -Scheitelpunkt und der Spaltenindex den "to" -Scheitelpunkt angibt, und die entsprechende Zelle mit der Kanten-ID. Sie können Vertex eindeutige und zufällige IDs geben.
Der nächste Teil ist etwas knifflig, weil nur Ihre Kanten aussagekräftige Bezeichnungen haben, die von DAG1 zu DAG2 passen. Angenommen, Sie haben eine Menge von Kanten E *, die die Schnittmenge von markierten Kanten von DAG1 und DAG2 sind, müssen Sie eine Reihe von Zeilenverschiebung (nach oben oder nach unten) oder Spaltenverschiebung (nach links oder rechts) ausführen, um die Position aller zu erreichen Kanten in E * in DAG1 und DAG2 bilden einander ab. Beachten Sie, dass für eine DAG, die in Matrix dargestellt wird, die Verschiebung der gesamten Zeile oder der gesamten Spalte die Darstellung immer noch äquivalent macht.
Die verbleibende Operation wäre, den Scheitelpunkt entsprechend den abgebildeten Matrizen umzubenennen, die zwei Matrizen zu vergleichen und die neuen Kanten und den neuen Scheitelpunkt (und Kanten und Scheitelpunkte, die entfernt werden können) zu identifizieren.
Tags und Links algorithm diff directed-acyclic-graphs