0

我无法在我的 DAG 中找到两个节点之间的所有路径。我确信这已经被覆盖过，但是我在代码和算法方面遇到了问题。

我有一个 DAG，其数据结构为：

{
    "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"
        }
    ]
}

该position对象用于保存节点在页面上的位置（此问题不需要），并且type是边缘的类型（success或failure）。

我需要从这些信息中得出的是“开始”（在数据中表示为'source': 'node-root'）和失败（node-endpointfailure）之间的所有路径。我希望通过 和 之间的边缘类型返回多维node-root路径node-endpointfailure。像这样的输出将是：

[
    ['failure', 'failure', 'failure'],
    ['failure', 'failure', 'success', 'failure'],
    ['failure', 'success', 'failure'],
    ['success', 'success', 'failure', 'failure'],
    ...etc
]

我已经尝试了一些 DFS 算法，但是一旦我找到了我的端点，我就会陷入将路径拉出函数的困境。这是我到目前为止所得到的：

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, []);

我试过在这里使用算法。看起来不错，但我不确定我错过了什么：https ://stackoverflow.com/a/13852674/881011

4

0 回答 0