在树结构中合并分支的模式或算法？

Question

我试图将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已完成,其输出是其输入.

编辑:好的,这是另一个十个节点的例子.我希望这能让您更好地了解我的节点何时合并.

要回答@blubb,在这个例子中我们可以看到"服务"8和9是如何合并的.否则他们需要工作的所有服务(1,2,3,4,5和6)将被呼叫两次而不需要.最后一个草图中的中间分支将执行两次:一次为8次,一次为9次.

Answer 1

最后，我找到了一种可以完成这项工作的算法。谨此献给所有试图帮助我的人：

首先，我从草图 1 中的 DAG 构建了一个倒置生成树。因此，我从模块 7 和 8 开始，向后构建树并复制模块。

之后，我创建名为 FLOW 和 SEQUENCE 的虚拟节点，并将它们引入树中，以便每个 MODULE 节点都是 SEQUENCE 节点的子节点。生成分支是 SEQUENCE 节点，它是 FLOW 节点的子节点。我认为这一步骤足够直观，但重要的想法是要了解我们需要虚拟节点，以便我们可以关闭 FLOW 节点，这些节点是从一个节点分裂为多个节点的节点。

之后，我首先检查树深度，对于每个模块（我们将其称为驱动程序），我将其子级与驱动程序兄弟姐妹的子级进行比较。如果它们不匹配，我会继续与驱动程序兄弟姐妹的孙子一起继续下去，这样，来自驱动程序兄弟姐妹的所有分支都必须通过与驱动程序相同的节点。从图形上看，这意味着在某些时候，两个节点都需要完全相同的模块。

如果它们匹配，我会从重合节点向下清理合并分支，这意味着我将它们与父级断开。从那里向上，它与驱动程序 SEQUENCE 节点一起进入新的 SEQUENCE 节点，进入同一个 FLOW 节点。

在遍历整棵树之后，只要进行了合并，我们就会再次遍历树，这一次具有更大的关系。这意味着我们不是比较驾驶员的孩子，而是比较驾驶员的曾孙。

最后一步显然是再次恢复树。

由于这些虚拟节点的编程意味着复杂性，我忽略了一些概念。主要是因为一旦引入虚拟节点，所有的父子兄弟关系就消失了。但我希望总体思路已被理解。