Datenstruktur zur Darstellung eines DAG in Javascript

Question

Ich habe eine Zeichenfolge, die ich brauche, um in einen Graphen (DAG) Datenstruktur mit Javascript zu parsen. In der Datenstruktur enthalten sind ein paar Attribute, die ich speichern sollte, wie die Knoten-ID, Name und eine Beschriftung, die den Link gegeben wird, wenn eine zu einem anderen Knoten existiert. Also, ein Beispiel wäre

Node1 (id: 1, name: 'first') --('link name')--> Node2 (id:....)

und so weiter. Sobald die Datenstruktur erstellt ist, muss ich keine weiteren Operationen mehr durchführen, außer sie zu lesen (ich werde sie später zum Rendern einer Visualisierung mit d3 verwenden). Die Anzahl der Knoten wird nicht sehr groß sein, da mehrere von ihnen gemeinsam genutzt werden.

Ich stelle mir eine Adjazenzliste vor, bin mir aber nicht sicher, wie ich das in Javascript kodieren würde. Zum Beispiel weiß ich, dass ein Json-Objekt eine "Feld" : "Wert" Struktur haben kann, aber kann ich das mit Object : [Liste der benachbarten Objekte] tun?

Answer 1

Sie können Listen (Arrays) in json verwenden. Ich könnte z.B. einen einfachen gerichteten Graphen darstellen als

{
  "NodeA": {"name": "NodeA", "adjacentTo": ["NodeB", "NodeC"]},
  "NodeB": {"name": "NodeB", "adjacentTo": ["NodeC", "NodeD"]},
  "NodeC": {"name": "NodeC", "adjacentTo": ["NodeA"]},
  "NodeD": {"name": "NodeD", "adjacentTo": []}
}

Dies wäre das Diagramm:

C
^^
| \
|  \
A -> B -> D

Das Namensfeld wird eigentlich nicht benötigt, aber Sie können auf diese Weise beliebige Attribute mit einem Knoten verknüpfen.

Answer 2

JavaScript-Objekte müssen String-Schlüssel haben, können aber jede Art von Wert speichern. Natürlich besteht der Sinn einer id darin, dass man einen komplexen Typ mit einem einfachen Typ darstellen kann.

var adjacentTo = {};
adjacentTo[node1.id] = [node2, node3]