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已经完成，它们的输出是它的输入。

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

在此处输入图像描述

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

4

2 回答 2

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 的最终草图。）

于 2013-04-10T21:27:31.090 回答
1

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

首先，我在草图 1 中从 DAG 构建了一个反向生成树。所以我从模块 7 和 8 开始，反向构建树，并在其中复制模块。

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

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

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

在遍历整个树之后，只要进行了合并，我们就会再次遍历树，这一次关系更大。这意味着我们不是比较司机的孩子，而是比较司机的好孩子。

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

由于这些虚拟节点的编程隐含的复杂性，我忽略了一些概念。主要是因为一旦引入虚拟节点，所有的父子兄弟关系都会丢失。但我希望大体的想法已经被理解。

于 2013-04-29T15:07:34.350 回答