I'm having trouble finding all the paths between two nodes in my DAG. I'm sure this has been covered before, but I'm having trouble with the code and less of the algorithm.
I have a DAG with a data structure of:
{
"graph": [
{
"source": "node-6",
"target": "node-endpointsuccess",
"type": "success"
},
{
"source": "node-7",
"target": "node-endpointsuccess",
"type": "success"
},
{
"source": "node-7",
"target": "node-endpointfailure",
"type": "failure"
},
{
"source": "node-6",
"target": "node-7",
"type": "failure"
},
{
"source": "node-2",
"target": "node-6",
"type": "success" },
{
"source": "node-7",
"target": "node-endpointsuccess",
"type": "success"
},
{
"source": "node-7",
"target": "node-endpointfailure",
"type": "failure"
},
{
"source": "node-5",
"target": "node-7",
"type": "success"
},
{
"source": "node-4",
"target": "node-endpointsuccess",
"type": "success"
},
{
"source": "node-4",
"target": "node-endpointfailure",
"type": "failure"
},
{
"source": "node-5",
"target": "node-4",
"type": "failure"
},
{
"source": "node-2",
"target": "node-5",
"type": "failure"
},
{
"source": "node-root",
"target": "node-2",
"type": "success"
},
{
"source": "node-4",
"target": "node-endpointsuccess",
"type": "success"
},
{
"source": "node-4",
"target": "node-endpointfailure",
"type": "failure"
},
{
"source": "node-1",
"target": "node-4",
"type": "success"
},
{
"source": "node-3",
"target": "node-endpointfailure",
"type": "failure"
},
{
"source": "node-1",
"target": "node-3",
"type": "failure"
},
{
"source": "node-root",
"target": "node-1",
"type": "failure"
},
{
"source": "node-3",
"target": "node-8",
"type": "success"
},
{
"source": "node-8",
"target": "node-endpointfailure",
"type": "failure"
},
{
"source": "node-8",
"target": "node-endpointsuccess",
"type": "success"
},
{
"source": "node-endpointsuccess"
},
{
"source": "node-endpointfailure"
}
]
}
The position
object is used for saving the position the node on the page (unneeded for this problem), and type
is the type of edge (either success
or failure
).
What I need to derive from this information are all the paths between 'Start' (represented in the data as 'source': 'node-root'
) and failure (node-endpointfailure
). I'm looking to return an multidimensional of paths by edge type between node-root
and node-endpointfailure
. Something like this would be the output:
[
['failure', 'failure', 'failure'],
['failure', 'failure', 'success', 'failure'],
['failure', 'success', 'failure'],
['success', 'success', 'failure', 'failure'],
...etc
]
I've tried a few DFS algorithms, but where I'm getting stuck on pulling the paths out of the function once I've found my endpoints. Here's what I've got so far:
function getPaths(from, to, nodes, visited) {
results = [];
// for all nodes
for (var n in nodes) {
// get the nodes that are connected to this one
if (nodes[n].source == from) {
// check if we have found an endpoint
if (nodes[n].target == to) {
// found an endpoint, return the edge type
console.info('paydirt');
results.push(nodes[n].type);
return results;
}
// follow that path
results = getPaths(nodes[n].source, to, nodes, visited);
// add to visited list
for (var r in results)
visited.push(results[r].type);
}
}
return visited;
}
getPaths('node-root', 'node-endpointfailure', data, []);
I've tried using the algorithm here. Looks to be a good but I'm not sure what I'm missing: https://stackoverflow.com/a/13852674/881011