19

Inspired by this question, I'm trying to represent a DAG in JSON. My case includes edges and nodes that contain some data (rather than just strings as in this example). I was thinking of a spec like this:

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

    "nodes": {
        "a": {
            "name": "Adam"
        },
        "b": {
            "name": "Bob"
        },
        "c": {
            "name": "Caillou"
        }
    },

    "edges": {
        // how to do the same for edges?
        // ie: how to query edges ?
    }
}

One idea I had was to make the keys of the edges be the concatenation of the two vertex ids that it connects. For example, ab, ac, and bc are the three edges in this graph. I want to know if there's a more standard way of doing this.

EDIT: This is what I'm thinking of now

{
    "graph": {
        "a": {
            "data": {
                // a's vertex data
            },
            "neighbors": {
                "b": {
                    "data": {
                        // data in edge ab
                    }
                },
                "c": {
                    "data": {
                        // data in edge ac
                    }
                }
            }
        },
        "b": {
            "data": {
                // b's vertex data
            },
            "neighbors": {
                "c": {
                    "data": {
                        // data in edge bc
                    }
                }
            }
        },
        "c": {
            "data": {
                // c's vertex data
            }
        }
    }
}
Community
  • 1
  • 1
Carpetfizz
  • 8,707
  • 22
  • 85
  • 146

3 Answers3

18

Since the DAG's edges hold data, they better have their own identifiers, just like the nodes. That is, the json representation should be composed of three components:

  1. Node records: mapping each node identifier to the node's data.
  2. Edge records: mapping each edge identifier to the edge's data.

  3. Adjacency lists: mapping each node identifier to an array of edge identifiers, each corresponds to an edge going out of the node.

    DAG = {
  "adjacency": {
    "a": ["1", "2"],
    "b": ["3"]
  },
  "nodes": {
    "a": {
      // data
    },
    "b": {
      // data
    },
    "c": {
      // data
    }
  },
  "edges": {
    "1": {
      "from": "a", "to": "b",
      "data": {
        // data
      }
    },
    "2": {
      "from": "a", "to": "b",
      "data": {
        // data
      }
    },
    "3": {
      "from": "b", "to": "c",
      "data": {
        // data
      }
    }
  }
}
snakile
  • 52,936
  • 62
  • 169
  • 241
  • Thanks for the reply, I will consider doing this, but that means I will have to somehow generate edge ids, which would be kinda annoying if I manually want to create this graph. What do you think of my edit ? – Carpetfizz Mar 27 '17 at 20:19
  • 1
    @Carpetfizz, combining the two vertex ids into an edge id is definitely legit. Go for it. – snakile Mar 27 '17 at 20:24
  • Great, thanks! Will still accept you since you gave a valid answer. I wanted to model mine like networkx which is a python library – Carpetfizz Mar 27 '17 at 20:25
  • 1
    What is the purpose of the adjacency list? Can't the same information be gathered from the node list plus the edge "from" property? – TomDane Feb 13 '21 at 05:40
14

Turns out there are standards that are trying to emerge for this sort of thing. I recently had to look these up for a project of my own. You might be interested in http://jsongraphformat.info/ for example, or one of the peer projects it references on its website. Goals include trying to represent in JSON anything you can represent in the DOT language (https://en.wikipedia.org/wiki/DOT_(graph_description_language)).

Nathan
  • 1,451
  • 1
  • 15
  • 28
4

json-ld was made for this. It has a semi-steep learning curve, but it is a robust way to represent graph data in json.

jshen
  • 11,507
  • 7
  • 37
  • 59