0

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

Community
  • 1
  • 1
jungos
  • 476
  • 5
  • 21
  • DAG means directed **acyclic** graph. You say you have a DAG, but then you say eventually you want to detect cycles? a DAG cannot have cycles. ALso, type and position should be removed entirely from your post if they're just some irrelevant implementation detail. – goat Feb 11 '13 at 01:10
  • Corrected question per @rambocoder's comments – jungos Feb 11 '13 at 01:16

0 Answers0