c# - グラフが再収束するタイミングを検出するアルゴリズム（一般的なサブツリーと同様ですか？）

Question

私はこの問題に一日中取り組んでおり、レガシー製品の1つを書き直しており、フローチャートで特定のノードを見つける方法を決定するのに苦労しています。問題は私に大学を思い出させます、しかし私の一生の間、私はこれを解決するためのアルゴリズムを思い付くことができません。

これを説明するために3つのスクリーンショットを添付しましたが、基本的な問題は、YES / NOですか？決定ノードで、ブランチを終了する最も近い子ノードを見つけます。

私はC＃.NETとJSONで作業しています。JSONには、各ノードに一意の識別子を与え、あるノードから次のノードへの各「リンク」を識別するオブジェクトがあります。C＃で分岐ノードが与えられた場合に、最初の「エンドノード」を決定する関数（またはいくつか）を作成したいと思います。現在、C＃でjSONをXMLに組み込んでいます。

ありとあらゆるアイデアが奨励され、実際にはコードを探すのではなく、アプローチ/アルゴリズムを探しています。

添付されているのは、図からのjSONの出力です。

{ "class": "go.GraphLinksModel",
  "linkFromPortIdProperty": "fromPort",
  "linkToPortIdProperty": "toPort",
  "nodeDataArray": [ 
{"key":-1, "category":"Start", "loc":"169 288", "text":"Start"},
{"key":-2, "category":"End", "loc":"855 394", "text":"End"},
{"category":"Branch", "text":"Yes or No", "key":-4, "loc":"284.8837209302326 285.7848837209302"},
{"category":"DelayNode", "text":"Delay", "key":-3, "loc":"365.8837209302326 215.52345997177622"},
{"category":"Branch", "text":"Yes or No", "key":-5, "loc":"478.8837209302326 214.52345997177622"},
{"category":"DelayNode", "text":"Delay", "key":-6, "loc":"568.8837209302326 151.52345997177622"},
{"category":"DelayNode", "text":"Delay", "key":-7, "loc":"573.8837209302326 268.5234599717762"},
{"category":"DelayNode", "text":"Delay", "key":-8, "loc":"653.8837209302326 215.52345997177622"},
{"category":"Branch", "text":"Yes or No", "key":-9, "loc":"392.8837209302326 392.5234599717762"},
{"category":"DelayNode", "text":"Delay", "key":-10, "loc":"454.8837209302326 317.5234599717762"},
{"category":"DelayNode", "text":"Delay", "key":-11, "loc":"550.8837209302326 473.5234599717762"},
{"category":"DelayNode", "text":"Delay", "key":-12, "loc":"549.8837209302326 317.5234599717762"},
{"category":"DelayNode", "text":"Delay", "key":-13, "loc":"711.8837209302326 343.5234599717762"},
{"category":"Branch", "text":"Yes or No", "key":-14, "loc":"434.8837209302326 487.5234599717762"}
 ],
  "linkDataArray": [ 
{"from":-4, "to":-3, "fromPort":"T", "toPort":"L", "visible":true},
{"from":-1, "to":-4, "fromPort":"R", "toPort":"L"},
{"from":-3, "to":-5, "fromPort":"R", "toPort":"L"},
{"from":-5, "to":-6, "fromPort":"T", "toPort":"L", "visible":true},
{"from":-5, "to":-7, "fromPort":"B", "toPort":"L", "visible":true, "text":"NO"},
{"from":-6, "to":-8, "fromPort":"R", "toPort":"L"},
{"from":-7, "to":-8, "fromPort":"R", "toPort":"L"},
{"from":-4, "to":-9, "fromPort":"B", "toPort":"L", "visible":true, "text":"NO"},
{"from":-9, "to":-10, "fromPort":"T", "toPort":"L", "visible":true},
{"from":-10, "to":-12, "fromPort":"R", "toPort":"L"},
{"from":-11, "to":-13, "fromPort":"R", "toPort":"L"},
{"from":-12, "to":-13, "fromPort":"R", "toPort":"L"},
{"from":-8, "to":-13, "fromPort":"R", "toPort":"L"},
{"from":-13, "to":-2, "fromPort":"R", "toPort":"L"},
{"from":-9, "to":-14, "fromPort":"B", "toPort":"L", "visible":true, "text":"NO"},
{"from":-14, "to":-11, "fromPort":"T", "toPort":"L", "visible":true},
{"from":-14, "to":-11, "fromPort":"B", "toPort":"L", "visible":true, "text":"NO"}
 ]}

Answer 1

私はアレックスの答えが好きで、それは非常に効率的だと思われます。これが問題を解決する別の方法です。これは、実際には最も低い共通祖先の問題です。これはグラフ理論で非常によく研究されている問題です。すべての矢印を逆にする必要があるため、最初は表示されませんでした。

このソリューションを使用すると、費用のかかる前処理を1回実行するだけで、答えを読み取ることができるデータ構造が得られます。

グラフのノードにラベルを付けました。最初にすべての矢印を逆にしてから、結果のDAGのオイラートラバーサルを作成します。各ステップで、「ルート」（終了）からの距離を記憶します。

オイラートラバーサルは、「自分自身を訪問し、隣人を繰り返し、自分自身を訪問し、隣人を繰り返し、...自分自身を訪問する」というものです。つまり、C＃で記述している場合は、次のようになります。

void Eulerian(Node n, int i, List<Tuple<Node, int>> traversal)
{
    traversal.Add(Tuple.Create(node, i));
    foreach(Node neighbour in node.Neighbours)
    {
        Eulerian(neighbour, i + 1, traversal);
        traversal.Add(Tuple.Create(node, i));
    }
}

オイラートラバーサルは、グラフを歩いている場合に実際に取るトラバーサルです。

例として示したグラフには、すべての矢印を逆にしてENDから開始すると、次のオイラートラバーサルがあります。

A0 B1 C2 D3 E4 F5 G6 H7 G6 F5 E4 D3 C2 I3 E4 F5 G6 H7 G6 F5 E4 I3 C2 
B1 J2 K3 L4 G5 H6 G5 L4 K3 J2 B1 M2 N3 L4 G5 H6 G5 L4 N3 M2 N3 L4 G5 
H6 G5 L4 N3 M2 B1 A0

これで、質問に対する答えをトラバーサルから読み取ることができます。あなたの例では、決定ノードE、L、Gがあります。

Eの場合：トラバーサルでEの最初と最後の出現を見つけます。次に、トラバーサル内のこれら2つの間のノードで、番号が最も小さいノードを検索します。スコアが2のCです。

Lの場合：トラバーサルでLの最初と最後の出現を見つけます。それらの間の番号が最も小さいノードはBであり、スコアは1です。

Gの場合：Gの最初の出現と最後の出現の間でスコアが最も低いノードはBです。

グラフが大きい場合、トラバーサルの計算にはコストがかかる可能性がありますが、1回だけ実行する必要があるのは良いことです。その後、それは単なる線形探索の問題です。（本当に必要な場合は、劣線形探索問題にすることもできますが、それは多くの余分な作業のようです。）

Answer 2

私が問題を理解している場合は、「はい」と「いいえ」のサブツリーの間で最初の共通ノードを見つけようとしています。その場合、それを行う簡単な方法は、yes サブツリーの幅優先走査で、各要素をリストに追加することです。次に、幅優先のトラバーサルまたは no サブツリーを実行し、そのサブツリーの要素が「yes」リストに表示されると停止します。

Answer 3

これは、2 つの幅/深さ優先検索を使用して O(V + E) 時間で実行できます。

まず、問題を特徴付けましょう。グラフ、開始ノード A、および終了ノード END が与えられます。@EricLippert で定義されているように (B と C の代わりに A を同等に使用できるため、私が少し調整しました)、次の 2 つのプロパティを持つノード G を探しています。

• A から END までの可能なパスはすべて G を通過します。
• G は、最初のプロパティを持つ A に最も近いノードです。

まず、X-first 検索を使用して、A から END へのパスを見つけます。P = (p1, p2, p3, ..., pk) で p1 = A および pk = END をこのパスとし、それらに 1、2、...、k の番号を付けます (つまり、pi の番号は i です)。これらの数値をノードとともにグラフに保存します。P が使用するエッジをグラフから削除します。A から別の X-first 検索を実行し、A から到達可能な最大番号のノード pi を見つけます。この検索をわずかに変更します。以前の最高到達可能ノード pk よりも高い到達可能ノード pj を見つけるたびに、すべてのサブパス (pk、pk+1、...、pj) のエッジをグラフに戻し、その間にあるこれらすべてのノードを到達可能としてマークし、以前に到達できなかったすべてのノードを使用したキュー/スタックに追加します処理の X ファースト検索で。この方法で見つかった pi を返します。

ここで、pi が G の条件を満たすことを示します。(矛盾に到達する目的で) パス S=(s1, s2, s3, ..., sj) があり、s1 = A および sj = END であるとします。円周率を通りません。このパスの一部のプレフィックス (s1、s2、s3、... sm) はパス P と一致するため、s1=p1、s2=p2、...、sm=pm ですが、sm+1 != pm+1 です。S は pi を通過せず、2 回目の X-first 検索で pi に到達したため、(s1, s2, s3, ..., sm) で使用されるエッジを追加すると、2 回目の X-first 検索で sm に到達可能になります。 . したがって、2 番目の X-first 検索は、END に到達するか、S で使用されるエッジ (pr, pr+1) がパス P にあるが r > i であるため、このエッジが削除されました。ただし、その場合、pr (または END) が到達可能であり、r > i であることがわかり、矛盾する pi を返さなかったでしょう。したがって、

ここで、上記のプロパティを持つが、pi よりも A に「近い」ノード G' があるとします。すべてのパスが G' を通過するとき、P も G' を通過するため、pv=G' および v < i の v がいくつか存在します。すべてのパスが G' を通過し、(pv, pv+1) が削除されたため、最初は pv を超えるノードに到達できず、したがって (pv, pv+1) が追加されることはなく、pi も到達可能になることはありません。アルゴリズムによって返されましたが、これは矛盾しています。したがって、pi はそのような最も近いノードであり、G の条件を満たし、アルゴリズムは正しいです。

最初の X-first 検索には O(V+E) 時間かかります。2 番目も O(V+E) 時間かかります。すべてのノードがキュー/スタックに最大 1 回追加されるため、エッジをグラフに追加し直しても実行時間は維持されます。最終的なエッジ数も元のグラフのエッジ数を超えません。パスのインデックスとこれまでに見つかった最高のインデックスを維持するには O(V+E) 時間もかかるため、アルゴリズムは O(V+E) 時間で機能すると結論付けます。

Answer 4

したがって、ここで提供されているいくつかの回答を考慮して、これについてさらに考えました。コードの作成はまだ開始していませんが、回答の1つを考慮して、疑似コードに少し変更しました。

より効率的なアプローチは、共通の辞書変数 (キー、値) ペアで任意の分岐ノードのすべての結果を追跡することだと思います。このアプローチに対する考えはありますか？1 つ言及しておくべきことは、グラフが 25 を超えるノードに成長してはならないということです。

//call this function for all nodes with 2 children
int getFirstCommonAllpathEndNode(currentNodeId, xml, endNodeId){

    Array[] possibleNodeIds;
    //traverse child nodes
    foreach(childnode of CurrentNode.TopPortChildNode){
        if(childNode has 2 ports)
        {
            possibleNodeIds.add( getFirstCommonAllPathEndNode(childNode.id, xml, endnodeId));
        }
        else{
            possibleNodeIds.add(childNode.Id);
        }
    }

    foreach(childnode of CurrentNode.BottomPortChildNode){
        if(childNode has 2 ports)
        {
            //recursive call for this branch to get it's first common all path end node
            var someNodeId = getFirstCommonAllPathEndNode(childNode.id, xml, endnodeId) 
            if(possibleNodeIds contains someNodeId) 
                return someNodeId;
            //otherwise skip forward to someNodeId as next node to process in for loop
        }
        else{
            if (possibleNodeIds contains childNode.Id)
                return childNode.id
        }
    }
    //return the endNode if nothing else is satisfied. although this code should never be hit
    return endNodeId;
}