Data Structure to represent a DAG in Javascript

问题:

I have a string that I need to parse into a graph (DAG) data structure using javascript. Included in the data structure are a few attributes I should store, such as the node's id, name, and a label that is given to the link if one exists to another node. So, an example would be

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

and so forth. Once the data structure is created I do not need to do any more operations on it other than read it (I will later use it to render a visualization with d3). The amount of nodes will not be very many, as several of them are shared.

I am imagining an adjacency list but am not sure how I would encode that in javascript. For instance, I know a json object can have a "field" : "value" structure but can I do that with Object : [list of adjacent Objects]?

回答1:

you can use lists (arrays) in json. E.g. I could represent a simple directed graph as

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

This would be the graph:

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

The name field really isn't needed, but you can associate any attributes you want with a node that way.

回答2:

JavaScript objects must have string keys, but can store any type of value. Of course, the entire point in an id is to allow you to represent a complex type wirh a simple one.

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