javascript - Javascript の有向非巡回グラフの 2 つのノード間のパスのトラバース

Question

DAG 内の 2 つのノード間のすべてのパスを見つけるのに問題があります。これは以前に取り上げられたと思いますが、コードとアルゴリズムに問題があります。

次のデータ構造を持つ 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