Funktionale Graphen

Question

Ich habe versucht, eine funktionale Grafik zu erstellen. Das Diagramm, das ich mache, hat keine Schleifen, also ist es ein bisschen wie ein Baum, wo einige Knoten mehr als ein Elternteil haben können.

Das Problem ist beim Aktualisieren. Der übliche Weg mit einem Baum besteht darin, bis zu dem zu aktualisierenden Knoten zu gehen, wobei jeder Schritt des Weges einen neuen Knoten erzeugt, der so geändert wird, dass er auf einen neuen Kindknoten zeigt, bis der tatsächlich zu bearbeitende Knoten erreicht ist geändert.

Dieser Ansatz, wenn einige Knoten mehr als einen Elternteil haben, bricht, weil Sie im Grunde den Knoten "teilen". Der Knoten, der von zwei Eltern geteilt wird, wird zu zwei Knoten mit jeweils einem Elternteil, wobei einer (der Pfad, den Sie durchlaufen haben, um den Knoten zu erhalten) den neuen Wert und der andere Elternteil ein Kind mit dem alten Wert hat.

Also versuchte ich stattdessen die Elternknoten in jedem Knoten zu speichern, d. H. Knoten wissen, wer ihre Eltern sind.

Das funktioniert, aber es gibt ein Problem. Wenn ich einen Knoten aktualisiere, muss ich seine Eltern aktualisieren. Aber dann muss ich für jeden seiner Eltern nicht nur ihre Eltern aktualisieren, sondern auch ihre Kinder, weil ihre Kinder ihre Elternknoten speichern, und dieser Elternknoten sich nun geändert hat.

Um einen Knotenwert zu aktualisieren, muss ich jeden Knoten im Diagramm aktualisieren.

Die andere Idee, die ich hatte, war statt die Elternknoten in jedem Knoten zu speichern, nur die "Pfade" zu den Elternknoten in jedem Knoten speichern. Auf diese Weise sollte ich die Kinder des Elternteils nicht aktualisieren müssen, da sich der "Pfad" zum Elternteil nicht geändert hat (obwohl der Knoten selbst).

Aber vielleicht gibt es einen viel besseren Weg, eine funktionale Grafik zu erstellen? Irgendwelche Ideen? Es macht mir nichts aus, wenn Graphen mit Schleifen nicht behandelt werden. Ich schreibe in Haskell, aber eine Beschreibung ohne Programmiersprache wäre auch in Ordnung.

Answer 1

Um den Knotenwert zu aktualisieren, muss ich jeden Knoten im gesamten Diagramm aktualisieren.

Leider müssen Sie dies als Tatsache akzeptieren. Das ist im Grunde der Grund, warum Sie keinen effizienten Funktionsgraphen implementieren können. Alle Lösungen, die eine Aktualisierung ohne Durchlaufen des gesamten Graphen ermöglichen, basieren auf dem Modell der Tabellen und Indizes als Referenzen. Die Idee ist folgende: Sie speichern alle Knoten in einer indizierten Tabelle und in Kanten anstelle von direkten Verweisen auf Knoten, in denen Sie ihre Indizes speichern. Es gibt einige Variationen, die verschiedene Vorteile haben, aber im Grunde ist das die ganze Idee.

Aber nachdenken über das oben genannte, ist es nichts weiter als eine Emulation dessen, was Speicherzeiger tatsächlich tun. Im Grunde genommen enden Sie damit, ein Low-Level-Zeug neu zu implementieren, während Sie in der Leistung stark verlieren. Ehrlich gesagt, empfehle ich, einen veränderlichen Graphen zu integrieren, der keines dieser Probleme teilen wird.

Ich habe seit einiger Zeit an einem Graph-DB-Projekt gearbeitet, das noch nicht veröffentlicht wurde. Ich habe jedoch etwas Code veröffentlicht. Ich denke, this mutable graph implementation könnte für Sie als eine Quelle von Ideen von Nutzen sein.