Traversal Algorithm for Recursive JSON Data Structure

1
votes

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):

  1. Start -> node1 -> node2 -> node4 -> failure
  2. 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.

2
javascripttreetraversal
your json is invalid.. just checked it at jsonlint.com - wirey00
jQuery will be of no help for data manipulation, I removed the tag - Bergi
So your JSON represents a binary tree or what? - Bergi
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
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 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

2 Answers

1
votes

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);
1
votes

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.