How do you store a Directed Acyclic Graph (DAG) as

Question

I want to represent a DAG as JSON text and wondering if anyone has tried this and any issues they dealt with in regards to validating if the JSON is actually a DAG.

Answer 1

Label each node and make an edge list. That is, for each node store the nodes that it has edges to, for example:

{
  "a": [ "b", "c", "d" ],
  "b": [ "d" ],
  "c": [ "d" ],
  "d": [ ]
}

You can store many kinds of graphs this way, not just DAGs, so you will need to post-process it to make sure that it has no loops. Just pick a node, DFS, if you see any node more than once it is not a DAG. Then remove all of the nodes you just saw and repeat with any remaining nodes. Do this until you find a loop or you've removed all of the nodes, in the latter case the graph is a DAG.

Note that this does not store parent nodes, since that is redundant information. You can generate those after loading the graph if you need that data.

Answer 2

Strictly speaking you cannot do it with JSON directly. You'd have to come up with your own way of representing objects that can be identified by reference elsewhere in the data structure, and then you'd have to post-process the result of deserializing the JSON string.

You can't do it with JSON for the simple reason that the JSON expression is the object graph, and there's simply no provisions for expressing the notion that the value of a property should be the value of another property elsewhere in the data structure. To put it another way, no object in the graph can have more than one parent, which implies that every object is the value of exactly one property of one other object.

Answer 3

JSON has no native facility to represent DAGs unless you make your own convention to represent linked data. JSON-LD (a W3C proposal) is a JSON extension that is trying to do exactly that. The proposal can be found here: http://json-ld.org/spec/latest/json-ld/.