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

Question

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

algorithmdesign-patterns

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>

我认为这与问题无关，但我正在使用JAVA 7解析JSON并编写XML。方框代表web服务，箭头表示输入和输出参数，例如，模块5在模块1、2、3和4完成并且它们的输出是其输入后才被调用。

编辑：好的，这里有另一个包含十个节点的示例。我希望这能让您更好地了解何时需要合并节点。

请参考以下图片：https://istack.dev59.com/2YTmM.webp 回答@blubb，我们可以看到在此示例中，“服务”8和9也已合并。否则，所有它们需要工作的服务（1,2,3,4,5和6）都将不必要地被调用两次。最后一个草图中的中间分支将执行两次：一次为8，一次为9。

- eskalera

你能否扩展一下最后一段？我认为这会很有帮助，更清楚地理解问题。 - blubb

另外，您能解释一下为什么要同时合并2、3、4的三个1节点，而不是与3和4的两个1节点合并吗？ - blubb

1

在你的最后一个例子中，我不明白为什么你有2,3,4和4,3,2，而不只是其中一个。看起来你可以只使用其中一个，然后在5之后进行分叉，一支与6合并（以加入8,9），另一支去10。 - naitoon

你可以从拓扑排序开始，按照逆拓扑顺序处理DAG。如果它们是“并行”的话，也就是说它们根据顺序无法比较，那么你可以按照这个顺序对顶点进行分组。然后你可以尝试匹配这些组。至少这是我会开始的地方。 - G. Bach

谢谢@G.Bach，这基本上就是我现在的情况。我已经解决了第二个草图。现在我需要一种递归方法来像草图3中那样合并节点。 - eskalera

显示剩余5条评论

2个回答

1

最终，我找到了一个能胜任的算法。以下是给所有曾经帮助过我的人：

首先，我从图1中的DAG构建了一个反向生成树。所以我从模块7和8开始，向后构建树形结构，并在重复模块处进行合并。

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

之后，我按深度优先的顺序遍历整棵树，并针对每个模块（我们称之为驱动程序），将其子节点与驱动程序兄弟节点的子节点进行比较。如果它们不匹配，我将继续向下遍历驱动程序兄弟节点的孙子节点，以便所有从驱动程序兄弟节点出来的分支必须通过与驱动程序完全相同的节点。从图形上看，这意味着在某个时刻，两个节点需要具有完全相同的模块。

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

在遍历整个树之后，只要进行了合并，我们就再次遍历树，这次使用更大的关系。这意味着我们不再比较驱动程序的子代，而是比较驱动程序的子代的后代。

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

由于引入虚拟节点后所有父子兄弟关系都丢失，因此我已经忽略了一些概念，因为这些虚拟节点的编程非常复杂。但我希望您已经理解了基本思想。

- eskalera

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- גלעד ברקן · Accepted Answer

我对树形数据结构并不是很了解，但我想它可能是一个存储结果的好地方。我对转换为XML也不是很熟悉，但如果我有路线映射的数据，例如：

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

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 的最终草图一样。)