Diff für gerichtete azyklische Graphen

Question

Ich bin auf der Suche nach einem Algorithmus, der diff zwei Directed Azyklische Graphen (DAGs) 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 nicht hundertprozentig sicher, aber ich denke, eine längste gemeinsame Subsequenz kann auf die DAGs angewendet werden. 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 zu 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

DAG 2 zu erhalten, fügen Sie einfach eine Ecke von der Wurzel mit dem Label 'b' zu einem anderen Eckpunkt. 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 Eckpunkt aus gibt es eine weitere Kante zum 'ac'-Eckpunkt in DAG 1. Ich würde einen Link zum diff im DAG-Formular posten, aber ich kann nicht mehr als zwei Links posten.

Danke und hoffe, das ist lesbar genug.

Answer 1

Dies ist vielleicht ein bisschen zu spät, aber nur zum Spaß: Beide DAGs können als Matrizen ausgedrückt werden, wobei der Zeilenindex den "from" - Vertex und der Spaltenindex den "to" - Vertex angibt entsprechende Zelle mit Kanten-ID markiert. Sie können Vertex eindeutige und zufällige IDs geben.

Der nächste Teil ist ein bisschen knifflig, weil nur Ihre Kanten aussagekräftige Label haben, die von DAG1 zu DAG2 mappen. 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. entsprechend die kartiert Matrizen

würde der verbleibende Betrieb sein, den Scheitelpunkt zu benennen, vergleichen, um die zwei Matrizen, und identifizieren, um die neuen Kanten und neue Ecke erforderlich (und Kanten und Scheitelpunkte, die entfernt werden können.