Traversal Algorithm for Recursive JSON Data Structure

Question

I'm building a graph editor in Javascript and I need an algorithm to identify all possible routes between two 'node' objects.

Given the following JSON object:

{
    "failureNode": {
        "failureNode": {
            "failureNode": {
                "failureNode": {
                    "failureNode": null,
                    "successNode": null,
                    "id": "node-endpointfailure",}
                },
                "successNode": {
                    "failureNode": null,
                    "successNode": null,
                    "id": "node-endpointsuccess",
                },
                "id": "node-1",
            },
            "successNode": {
                "failureNode": null,
                "successNode": null,
                "id": "node-endpointsuccess",
            },
            "id": "node-2",
        },
        "successNode": {
            "failureNode": {
                "failureNode": {
                    "failureNode": null,
                    "successNode": null,
                    "id": "node-endpointfailure",
                },
                "successNode": {
                    "failureNode": null,
                    "successNode": null,
                    "id": "node-endpointsuccess",
                },
                "id": "node-1",
            },
            "successNode": {
                "failureNode": null,
                "successNode": null,
                "id": "node-endpointsuccess",
            },
            "id": "node-3",
        },
        "id": "node-4",
    },
    "successNode": {
        "failureNode": null,
        "successNode": null,
        "id": "node-endpointsuccess",
    },
    "id": "node-root",
}

I need all possible routes between nodes with ID = 'node-root' &'node-endpointfailure'. In this example, there are two possible ways to start at 'Start' (which is node-root in the data structure) and end and 'Failure' (node-endpointfailure):

Start -> node1 -> node2 -> node4 -> failure
Start -> node1 -> node3 -> node4 -> failure

For this example, the output would be an array of JSON paths. Something like this...

[
    failureNode.failureNode.failureNode.failureNode,
    failureNode.successNode.failureNode.failureNode
]

Most of the application is using jQuery, so either a pure Javascript or jQuery solution will work.

jQuery will be of no help for data manipulation, I removed the tag — Bergi, Jan 30 '13 at 18:59
what have you tried? I think you'll find you are more likely to receive help when you post something that you have tried. As of right now your question is suggesting that the community write your code for you — dm03514, Jan 30 '13 at 19:02
Just to add to what wirey said, you never are supposed to have a comma before an end bracket, it's not valid JSON (see http://www.json.org/) It seems like you are requesting some algorithm to do what you desire. As often needs to be repeated here, "What have you tried?". — JayC, Jan 30 '13 at 19:06
I stripped irrelevant data from the data structure for simplicity, and probably accidentally missed the comma. My data structure is valid according to JSONLint. — jungos, Jan 31 '13 at 05:02
I've tried rewriting this algorithm without success: http://stackoverflow.com/questions/58306/graph-algorithm-to-find-all-connections-between-two-arbitrary-vertices. Not sure if I failed because the data structure was dissimilar or if I translated the code incorrectly. — jungos, Jan 31 '13 at 05:29

score 1 · Accepted Answer · answered Jan 30 '13 at 19:13

This should do the task:

function recurse(from, to, node) {
    var result = [],
        choices = ["sucessNode", "failureNode"];
    if (!from && to == node.id)
        return [[]];
    if (from == node.id)
        return recurse(null, to, node);
    for (var i=0; i<choices.length; i++) {
        var choice = choices[i];
        if (node[choice] != null) {
            var res = recurse(from, to, node[choice]);
            for (var j=0; j<res.length; j++) {
                res[j].unshift(choice);
                result.push(res[j]);
            }
        }
    }
    return result;
}
recurse('node-root', 'node-endpointfailure', data);

score 1 · Answer 2 · answered Jan 30 '13 at 19:42

1

I find your choice of representation a little bizarre and confusing. A tree is not an optimal way to represent this. What you are describing is essentially a DAG (Directed Acyclic Graph). A recursive representation would end up duplicating objects. While I'm sure there are other ways to represent this, a simple representation would be just to list each node with it's success and failure nodes as identified by id. The stop nodes would have nulls (or zero length strings, whichever) for their success and failure nodes. Or you could have a single dictionary of them all.

For instance, your graph could then be described (listwise) as:

[
  {
    id: "Start",
    successNode: "success",
    failureNode: "node-1"
  },
  {
    id: "node-1",
    successNode: "node-3",
    failureNode: "node-2"
  },
  {
    id: "node-2",
    successNode: "success",
    failureNode: "node-4"
  },
  {
    id: "node-3",
    successNode: "success",
    failureNode: "node-4"
  },
  {
    id: "node-4",
    successNode: "success",
    failureNode: "failure"
  },
  {
    id: "success",
    successNode: "",
    failureNode: ""
  },
  {
    id: "failure",
    successNode: "",
    failureNode: ""
  }
]

making it quite easy to edit your graph. Just add or remove nodes and their values as appropriate. I might use another object as a dictionary to make it faster/easier to find each node. Supposing I did have such a dictionary dict, it would not be hard to navigate from node to node to see where you end up.

answered Jan 30 '13 at 19:42

JayC

7,053
2
25
41

1

+1 for "bizarre and confusing representation". But why would you use an array of nodes and not an object (nodes by id) in the first place? – Bergi Jan 30 '13 at 23:40
1

There are some advantages to using an array. It allows for easy representation via a grid and fits in really well with some javascript MVC frameworks (Backbone.js in particular) deal with collections of models, and, of course, you can always order the nodes in any way you prefer. I also remember some (older) browsers you have to be really careful with object key names, at least this way, if you have to uglify the keys to make it work, it can be done behind the scenes. – JayC Jan 31 '13 at 00:34
2

Of course, if you use the object notation, and get rid of the id field, it'd be shorter, and one representation is trivially derived from the other. I suppose I showed the array representation to emphasize the set-like nature of the things OP should be dealing with and not to over-complicate things. – JayC Jan 31 '13 at 00:36
Yeah, the struct is pretty odd -- it doesn't make sense at all when you have loops like this. This used to be a strict binary tree graph, and turned into a DAG like JayC called. I was hoping this data structure could be salvaged, but it doesn't look like it's going to work out. – jungos Jan 31 '13 at 05:10
1

I wanted to circle back around to note that I did end up changing the data structure to what JayC suggested in this answer. I'm keeping Bergi marked as the solution since it solves the question, even though the question was bad. – jungos Feb 10 '13 at 21:41

Traversal Algorithm for Recursive JSON Data Structure

2 Answers2