Próbuję zmapować DAG (skierowany wykres acykliczny) do struktury, którą pokazuję poniżej.

Oto przykład DAG, od którego zaczynam

gdzie łuki zawsze idą od lewej do prawej.

Następnie odwracam wykres i rozciągam go na drzewo z powtarzającymi się węzłami w ten sposób:

To, czego szukam, to jakiś algorytm lub wzorzec do osiągnięcia następującej struktury scalonej. (Zauważ, że jest ponownie przywrócony)

Celem jest wygenerowanie kodu XML w następujący sposób:

<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>

Nie sądzę, że jest to istotne, ale parsuję JSON, aby napisać XML za pomocą JAVA 7. Skrzynki są usługami sieciowymi, a strzałki reprezentują parametry wejściowe i wyjściowe, więc na przykład Moduł 5 nazywa się kiedyś Moduły 1,2,3 i 4 skończyłem, a ich wyniki są jego wejściami.

EDYTOWAĆ: Ok, oto kolejny przykład z dziesięcioma węzłami. Mam nadzieję, że daje to lepsze zrozumienie, kiedy węzły mają zostać połączone.

Aby odpowiedzieć @blubb, w tym przykładzie możemy zobaczyć, jak scalono również usługi „8” i „9”. W przeciwnym razie wszystkie usługi, których potrzebują do pracy (1,2,3,4,5 i 6), będą wywoływane dwukrotnie bez potrzeby. Środkowa gałąź ostatniego szkicu byłaby wykonywana dwukrotnie: raz na 8 i raz na 9.