Ich möchte eine DAG als JSON-Text darstellen und mich fragen, ob jemand diese und alle Probleme, die sie in Bezug auf die Validierung behandelt haben, versucht hat, wenn die JSON tatsächlich eine DAG ist.Wie speichern Sie eine gerichtete azyklische Grafik (DAG) als JSON?
Beschriften Sie jeden Knoten und erstellen Sie eine Kantenliste. Das heißt, für jeden Knoten speichern die Knoten, die es Kanten, zum Beispiel hat:
{
"a": [ "b", "c", "d" ],
"b": [ "d" ],
"c": [ "d" ],
"d": [ ]
}
Sie viele Arten von Graphen auf diese Weise speichern kann, nicht nur DAGs, so dass Sie nachbearbeiten müssen, um es zu machen, sicher, dass es keine Schleifen hat. Wählen Sie einfach einen Knoten, DFS, wenn Sie einen Knoten mehr als einmal sehen, es ist keine DAG. Entfernen Sie dann alle Knoten, die Sie gerade gesehen haben, und wiederholen Sie sie mit den verbleibenden Knoten. Tun Sie dies, bis Sie eine Schleife finden oder alle Knoten entfernt haben. Im letzteren Fall ist der Graph eine DAG.
Beachten Sie, dass dies keine übergeordneten Knoten speichert, da das redundante Informationen sind. Sie können diese nach dem Laden des Diagramms generieren, wenn Sie diese Daten benötigen.
Gibt es einen Nachteil, es invers zu speichern (mit den Array-Werten die "von" Knoten anstelle von "nach")? Ich würde denken, das wäre besser, wenn Sie versuchen, eine topologische Art zu tun. –
Genau genommen können Sie es nicht direkt mit JSON tun. Sie müssten Ihre eigene Art der Darstellung von Objekten erstellen, die durch Verweis an anderer Stelle in der Datenstruktur identifiziert werden können, und dann müssten Sie das Ergebnis der Deserialisierung der JSON-Zeichenfolge nachbearbeiten.
Sie können es nicht mit JSON aus dem einfachen Grund, dass der JSON-Ausdruck das Objektdiagramm ist, und es gibt einfach keine Bestimmungen für den Ausdruck, dass der Wert einer Eigenschaft den Wert einer anderen Eigenschaft an anderer Stelle sein sollte in der Datenstruktur. Um es anders auszudrücken, kein Objekt im Graph kann mehr als ein Elternteil haben, was impliziert, dass jedes Objekt der Wert genau einer Eigenschaft eines anderen Objekts ist.
In einer DAG kann ein Knoten zwei Eltern haben. Stellen Sie sich die Darstellung eines Ausdrucks in einer Programmiersprache vor (z. B. JavaScript :-) mit zwei Referenzen auf eine einzelne Variable. Üblicherweise beziehen sich diese beiden Punkte im Ausdruck auf denselben Knoten. Es gibt keine Zyklen in einem DAG (per Definition), weil (normalerweise; nicht unbedingt ich denke) alle Links "zeigen" den Graphen, so dass Sie nie "zurückgehen". Es ist wie ein Baum, außer wenn ähnliche Knoten zusammengeführt werden. – Pointy
Ha ha gut dieser Kommentar war eine Antwort auf eine Frage zu diesem Thema mit Zyklen, also werde ich es dort lassen. – Pointy
Ja, grundlegender CS Verständnisfehler von mir ;-) Danke für die Erklärung. –
JSON verfügt über keine native Funktion zur Darstellung von DAGs, es sei denn, Sie erstellen eine eigene Konvention zur Darstellung verknüpfter Daten. JSON-LD (ein W3C-Vorschlag) ist eine JSON-Erweiterung, die genau das versucht. Der Vorschlag kann hier gefunden werden: http://json-ld.org/spec/latest/json-ld/.
DAGs dürfen keine einzige Wurzel haben, wenn ich DAG richtig verstehe. Wie trocknen Sie das Modell aus, wenn Sie nicht sicher sind, ob Sie es sehen? –
Jedes JSON-Objekt wird definitiv eine DAG sein. – Pointy