Search code examples
jsondata-structuresdirected-acyclic-graphs

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

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.

Solution

  • Label each node and make an edge list. That is, each node stores 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 ensure that it has no loops.

    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.