1

Javascript でグラフ エディターを作成しています。2 つの「ノード」オブジェクト間のすべての可能なルートを識別するアルゴリズムが必要です。

次の JSON オブジェクトがあるとします。

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

ID = 'node-root' &'node-endpointfailure' のノード間のすべての可能なルートが必要です。この例では、「開始」(データ構造のノード ルート) から開始し、終了して「失敗」(ノード エンドポイントの失敗) する 2 つの方法があります。

  1. 開始 -> ノード 1 -> ノード 2 -> ノード 4 -> 失敗
  2. 開始 -> ノード 1 -> ノード 3 -> ノード 4 -> 失敗

この例では、出力は JSON パスの配列になります。このようなもの...

[
    failureNode.failureNode.failureNode.failureNode,
    failureNode.successNode.failureNode.failureNode
]

ほとんどのアプリケーションは jQuery を使用しているため、純粋な Javascript または jQuery ソリューションのいずれかが機能します。

4

2 に答える 2

1

私はあなたの表現の選択が少し奇妙で紛らわしいと思います。ツリーはこれを表すのに最適な方法ではありません。あなたが説明しているのは本質的にDAG（有向非巡回グラフ）です。再帰的な表現は、オブジェクトを複製することになります。これを表現する方法は他にもあると思いますが、単純な表現は、idで識別される成功ノードと失敗ノードを含む各ノードをリストすることです。停止ノードには、成功ノードと失敗ノードのnull（または長さゼロの文字列のいずれか）があります。または、それらすべての単一の辞書を持つこともできます。

たとえば、グラフは次のように（リストごとに）記述できます。

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

グラフの編集が非常に簡単になります。必要に応じて、ノードとその値を追加または削除するだけです。別のオブジェクトを辞書として使用して、各ノードをすばやく簡単に見つけることができます。私がそのような辞書を持っていたとdictしたら、ノードからノードへとナビゲートして、最終的にどこに到達するかを確認するのは難しくありません。

于 2013-01-30T19:42:50.033 に答える
1

これで次のタスクが実行されます。

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);
于 2013-01-30T19:13:25.250 に答える