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

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 服务，箭头代表输入和输出参数，例如，模块 1、2、3 和 4 完成后调用模块 5，它们的输出是其输入。

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

回答@blubb，在此示例中，我们可以看到“服务”8 和 9 是如何合并的。否则，他们需要工作的所有服务(1、2、3、4、5 和 6)将被调用两次而无需。最后一个草图中的中间分支将执行两次:一次用于 8，一次用于 9。

Answer 1

我不太了解树数据结构，我想这可能是结果的一个很好的外壳，而且我对转换为 XML 不太了解，但是如果我得到了映射了路由的数据例如，

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

那么合并节点的一种方法可能是:

Take increasingly larger chunks from the end of each line and examine the
first cell to the left of them. Nodes are merged if matching right-side 
chunks flow to the same aggregated first cells on the left. Remove duplicate 
paths.

解释/示例:

第一遍(获取末端细胞，与它们左侧的聚合第一细胞进行比较):

  4   <- 7
  5,6 <- 8
  5,6 <- 9
  2,5 <- 10

唯一可以合并的节点是 8 和 9，因为它们都流向相同的聚合单元 (5,6)。

第一遍结果:

1 4 7
1 2 5 (8,9) -- merged
1 3 5 (8,9)
1 4 5 (8,9)
1 3 6 (8,9)
1 2 5 (8,9)
1 3 5 (8,9)
1 4 5 (8,9)
1 3 6 (8,9)
1 2 10
1 2 5 10
1 3 5 10
1 4 5 10

第二遍(取末端细胞 + 1 个细胞，与左侧聚合的第一个细胞进行比较):

  1      <- 4 7
  2,3,4  <- 5 (8,9)
  3      <- 6 (8,9)
  1      <- 2 10
  2,3,4  <- 5 10

无法合并，因为没有匹配的右侧路径流向左侧相同的聚合第一个单元格。

第三遍(取末端细胞 + 2 个细胞，与左侧聚合的第一个细胞比较):

  N/A    <- 1 4 7
  1      <- 2 5 (8,9)
  1      <- 3 5 (8,9)
  1      <- 4 5 (8,9)
  1      <- 3 6 (8,9)
  N/A    <- 1 2 10
  1      <- 2 5 10
  1      <- 3 5 10
  1      <- 4 5 10

可以进行两次合并。首先:[2 5 (8,9)]、[3 5 (8,9)] 和 [4 5 (8,9)] 都流向 1。其次:[2 5 10]、[3 5 10] , 和 [4 5 10] 都流向 1.

第三遍结果:

1 4 7
1 (2,3,4) 5 (8,9)
1 3 6 (8,9)
1 2 10
1 (2,3,4) 5 10

在我看来很像请求的结果。 (末端的重复单元格可以合并为单个节点，即左侧为 1，右侧为 (8,9) 和 10，如 eskalera 的最终草图所示。)