Graph Path Service Design


#1

So I am trying to apply Json API to my design and it seems to have a gaping hole…

My software maintains an ever-evolving non-directional graph between nodes.

If you query a node, I have it figured out that I can return the node’s attributes in its “attributes” section and even reference its first-degree neighbors in its “relationships” section and further “include” information on those neighbors in the “included” section.

This seemed to map up just fine.

{ 
  data: {
    type: "node",  id: "5",
    attributes: { name: "Foo" },
    relationships: {
      neighbors: {
         data: [ { type: 'node', id: 6 }, { type: 'node', id: 7 } ]
      }
    }
  },
  included: [
    {
      type: "node",  id: "6",
      attributes: { name: "Bar" },
      relationships: {
        neighbors: {
          data: [ { type: 'node', id: 5 }, { type: 'node', id: 4 } ]
        }
      }
    },
    {
      type: "node",  id: "7",
      attributes: { name: "Phoo" },
      relationships: {
        neighbors: {
          data: [ { type: 'node', id: 5 }, { type: 'node', id: 8 } ]
        }
      }
    }
  ]
}

However, I have a service that given 2 node ID’s attempts to find a path between them with various constraints that can be defined as query parameters (e.g.: “nodesToBeAvoided”, “maxDegreesOfSeparation”, etc…)

The result is NOT anything that has an ID, but rather a path between things that have an ID, but we include the list of nodes as well (as they existed at the time the path was found).

My best guess about how to return this one is to add a “path” attribute to the “meta” section at the top level and make my “data” section be an array of nodes in the path (i.e.: an array of what I have above for “data”).

Here is where it gets tricky… see above that my “node” return value typically identifies first-degree neighbors of each node as well and puts those in the “included” section. Now it seems since the nodes on the path are going to be first-degree neighbors that some of them will be enumerated in the “data” array and then repeated in the “included” array – which seems odd – unless I de-dupe. But if I de-dupe it means clients will have to know to look at both “data” and “included” when looking up the neighbors of the nodes on the path.

Does this seem like the appropriate way to handle this “find path” graph API?

{ 
  meta: {
     path: [ 5, 6, 4 ]
  },
  data: [
    {
      type: "node",  id: "5",
      attributes: { name: "Foo" },
      relationships: {
        neighbors: {
           data: [ { type: 'node', id: 6 }, { type: 'node', id: 7 } ]
        }
      }
    },
    {
      type: "node",  id: "6",
      attributes: { name: "Bar" },
      relationships: {
        neighbors: {
           data: [ { type: 'node', id: 5 }, { type: 'node', id: 4 } ]
        }
      }
    },
    {
      type: "node",  id: "4",
      attributes: { name: "Boo" },
      relationships: {
        neighbors: {
           data: [ { type: 'node', id: 6 } ]
        }
      }
    }
  ],
  included: [
    {
      type: "node",  id: "7",
      attributes: { name: "Phoo" },
      relationships: {
        neighbors: {
          data: [ { type: 'node', id: 5 }, { type: 'node', id: 8 } ]
        }
      }
    }
  ]
}

#2

Yes, the example response you showed at the end is exactly right.

At the moment, the deduping is required, on the theory that allowing duplication could result in the same resource (i.e. same type/id) being sent with two different sets of fields. (Also, deduping saves data over the wire.)

Frankly, neither of those rationale make much sense to me, but here’s the relevant part of the spec:

A compound document MUST NOT include more than one resource object for each type and id pair.

Note: This approach ensures that a single canonical resource object is returned with each response, even when the same resource is referenced multiple times.

Correct. I think the theory with included is that the client will immediately read its content, and those from data into a single object store, so that it has access to both.