1

グラフ構造を以下に示す構造にマッピングしようとしています。

これが私がマップする必要があるグラフのタイプの例です

ここに画像の説明を入力してください

ここで、矢印は常に左から右への方向を持っています。

これが私が探している結果です。

ここに画像の説明を入力してください

目標は、次のようなXMLを生成することです。

<root>
    <seq>
        <mod1/>
        <flow>
            <seq>
                <mod4/>
                <mod7/>
            </seq>
            <seq>
                <flow>
                    <seq>
                        <flow>
                            <mod4/>
                            <mod3/>
                        </flow>
                        <mod6/>
                    </seq>
                    <seq>
                        <flow>
                            <mod4/>
                            <mod3/>
                            <mod2/>
                        </flow>
                        <mod5/>
                    </seq>
                </flow>
                <mod8/>
            </seq>
        </flow>
    </seq>
</root>

使用できるアルゴリズムはありますか？

関連性はないと思いますが、JSONを解析してJAVA 7でXMLを記述しています。ボックスはWebサービスであり、矢印は入力パラメーターと出力パラメーターを表します。たとえば、モジュール5はモジュール1、2、3、4と呼ばれます。終了し、それらの出力はその入力です。

4

6 に答える 6

5

上に示したグラフにはサイクルがあるため、ツリーとして表すことはできません。一般に、ツリーは、サイクルのない連結グラフとして定義されます。したがって、一般的なグラフをツリーに変換する唯一の方法があります。サイクルを削除し、必要に応じて接続します。

編集：編集に従ってグラフが指示されるため、DAGが作成されます。これもツリーではありませんが、いくつかの興味深いプロパティがあります。

于 2013-03-26T15:28:14.660 に答える
3

（答えではありませんが、私の提案した編集は偽の理由で拒否されました。）

この質問と他の質問へのコメントに基づいた、正式な問題の言い換え

入力は、頂点Xを持つ非巡回有向グラフによって指定された有限集合Xの半順序≤Xです。出力は、有限集合Yの直並列半順序≤Yであり、1の直並列合成によって指定されます。要素の半順序、およびマップf：Y→Xは、すべての最大チェーンに対してx1<X…<Xxn（=入力グラフの遷移縮小におけるソースからシンクへのパス）となるように明示的に指定されます。 、 f（yjでy1 < Y … < Yynの最大チェーンが1つだけ存在します。）=すべてのj∈ {1、…、n}に対してxj。|Y|をお願いします できるだけ小さくする。

于 2013-04-15T21:13:55.513 に答える
2

パスが指示された場合、複数のパスに対応するようにリーフノードを複製することによって形成された同等のツリー構造が存在します。構造に有向パスがない場合、一般的なケースでは対応するツリー構造はないと思います。

編集

これが有向グラフであるという新しい情報に照らして、同等のツリー構造は次のとおりです。

1
  2
    5
      8
  3
    5
      8
    6
      8
  4
    6
      8
    7

これを導出するためのアルゴリズムは、グラフのインフィックストラバーサルであり、出力パスがない場合は各リムで停止します。

于 2013-03-26T15:19:24.540 に答える
1

問題はまだ少し不明ですが、グラフのシリアル化、またはグラフのトポロジカルソートを実行する必要があると感じています。サイクルの存在は依存サイクルとして解釈される可能性があるため、これはDAGにのみ適用できます。

于 2013-03-26T21:10:44.003 に答える
0

あなたが示している写真は、アプローチが最後から後ろに向かって働くべきであることを示唆しています。まず、子を持たないノード（この場合は8と7）を探します。ツリーの「デュアルトランク」を形成します。次に、8と7のすべての親を探します。また、親を持たないモジュール（この場合は1）を探します。これを祖先と呼びます。それが「終点」です。最後に、共通ノードのセットごとに「ファミリ」を宣言します。同じノードが複数のファミリに属する​​ことができる場合でも、共通の子を持つノードはファミリです。親が1つしかないノードは、その親のファミリの一部です。

8の場合、5と6が見つかります。ファミリA。

7の場合、4が見つかります。ファミリーB。7には親が1つしかないため、ファミリーBの4つの部分と呼びます。

これらを「第2世代」と呼びます。

第2世代については、親を探します。

ファミリーA：5->2,3,4。ファミリーC6->3,4。ファミリーD

家族B：4->1-拡大家族が祖先に到達します。これで、このパスは完了です。1つのパスを1-4-7-end（すべて「ファミリB」）としてキャプチャできます。

次に、Gen3の親を探します。

of 5（ファミリーC）：2-> 1 3-> 1 4-> 1同じ親を持つ同じファミリーのメンバーは「親しい兄弟」であり、<flow>上下を取得します。

of 6（ファミリーD）：3-> 14->1別の親しい家族

そして、これらの家族はす​​べて祖先を指していることになったので、そこに別の家族が必要になります。

したがって、説明されているすべてのプロセスの完全な祖先があります。次に、上記の「ファミリ」を使用して、フローマップに変換します。

Your desired XML - annotated with the families. You can see how this works

<root>
    <seq>
        <mod1/> // the ancestor
        <flow>
            <seq> // family B - straight through.
                <mod4/>
                <mod7/>
            </seq>
            <seq> 
                <flow>
                    <seq>
                        <flow> // close family D
                            <mod4/>
                            <mod3/>
                        </flow>
                        <mod6/> // child of D
                    </seq>
                    <seq>
                        <flow> // close family C
                            <mod4/>
                            <mod3/>
                            <mod2/>
                        </flow>
                        <mod5/> // child of C
                    </seq>
                </flow>
                <mod8/>
            </seq>
        </flow>
    </seq>
</root>

これは役に立ちますか、それとも私は完全にマークから外れていますか？

編集：「途中で流れを閉じる」というテーマで、次の考え：

家族が別の家族と同じ（孫）子を持ち、同じ（祖父母）親を持っている場合、それらのフローはそのレベルで組み合わせることができます。これを発見するには、各家族の「直接の血統」のリストを保持する必要があります。また、すべての家族についてこのリストを繰り返し検索して、共通の（祖父母）親と共通の（孫）子の両方が存在するケースを見つける必要があります。これを一般的な方法で処理するには、今夜私ができるよりも少し手間がかかります。あなたが解決策に近づいていることを示したので、ここに残しておきます...

于 2013-04-17T02:50:11.920 に答える
0

最後に、私はその仕事をするアルゴリズムを見つけました。これは私を助けようとしたすべての人のためのものです：

まず、スケッチ1のDAGから逆スパニングツリーを構築しました。そこで、モジュール7と8から開始し、ツリーを逆方向に構築し、モジュールが複製されます。

その後、FLOWおよびSEQUENCEという仮想ノードを作成し、それらをツリーに導入して、すべてのMODULEノードがSEQUENCEノードの子になるようにします。スパニングブランチは、FLOWノードの子であるSEQUENCEノードです。これは直感的な手順だと思いますが、重要なのは、1つのノードから複数のノードに分割されているFLOWノードを閉じることができるように仮想ノードが必要であることを理解することです。

その後、最初にツリーの深さを調べ、すべてのモジュール（これをドライバーと呼びます）について、その子をドライバーの兄弟の子と比較します。それらが一致しない場合、私はドライバーの兄弟の孫と一緒に降り続けます。そのため、ドライバーの兄弟から出てくるすべてのブランチは、ドライバーと同じノードを通過する必要があります。グラフィカルにこれは、ある時点で、両方のノードがまったく同じモジュールを必要とすることを意味します。

それらが一致する場合、私は一致するノードから下向きにマージするブランチをクリーンアップします。つまり、それらを親から切り離します。そこから上に向かって、ドライバーのSEQUENCEノードと一緒に新しいSEQUENCEノードに入り、同じFLOWノードに入ります。

ツリー全体を調べた後、マージが行われている限り、今度はより大きな関係でツリーをもう一度調べます。これは、ドライバーの子供を比較する代わりに、ドライバーの偉大な子供を比較することを意味します。

最後のステップは、明らかにツリーを元に戻すことです。

これらの仮想ノードのプログラミングが暗示する複雑さのために、私が残したいくつかの概念があります。主に、仮想ノードが導入されると、すべての親子兄弟関係が失われるためです。しかし、一般的な考え方が理解されていることを願っています。

于 2013-04-29T15:05:18.137 に答える