9

DAG (有向非巡回グラフ) を以下に示す構造にマップしようとしています。

これは、私が開始するDAGの例です

ここに画像の説明を入力

円弧は常に左から右に進みます。

次に、グラフを元に戻し、次のようにノードが繰り返されるツリーにスパンします。

ここに画像の説明を入力

私が探しているのは、次のマージされた構造を実現するためのアルゴリズムまたはパターンです。(また元に戻すことに注意してください)

ここに画像の説明を入力

目標は、次のような 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 で 1 回呼び出されます。終了し、それらの出力はその入力です。

編集:わかりました、ここに 10 個のノードを持つ別の例があります。これにより、I ノードがいつマージされる予定であるかをよりよく理解できることを願っています。

ここに画像の説明を入力

@blubb に答えるために、この例では、「サービス」8 と 9 もどのようにマージされているかを確認できます。そうしないと、動作に必要なすべてのサービス (1、2、3、4、5、および 6) が必要なく 2 回呼び出されます。最後のスケッチの中央の分岐は、8 に対して 1 回、9 に対して 1 回の 2 回実行されます。

4

2 に答える 2