1

我正在尝试将图形结构映射到下面显示的结构中。

这是我需要映射的图表类型的示例

在此处输入图像描述

其中箭头始终具有从左到右的方向。

这是我正在寻找的结果。

在此处输入图像描述

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

4

6 回答 6

5

您在上面显示的图表具有循环，因此它永远不能表示为树。一般来说，树被定义为没有环的连通图。所以只有一种方法可以将一般图转换为树 - 删除循环并在需要时连接它。

编辑：根据您的编辑，该图是定向的，因此您将拥有一个DAG，它再次不是树，但具有几个有趣的属性。

于 2013-03-26T15:28:14.660 回答
3

（不是答案，但我建议的编辑因虚假原因被拒绝。）

正式的问题重述，基于对这个问题和另一个问题的评论

输入是有限集 X 上的偏序≤ X，由具有顶点 X 的无环有向图指定。输出是有限集 Y 上的串并联偏序≤ Y，由一的串联和并行组合指定元素偏序和映射 f : Y → X，明确指定，使得对于每个最大链 x 1 < X ... < X x n （=输入图的传递缩减中的源到汇路径） , 恰好存在一个最大链 y 1 < Y ... < Y y n且 f(y j) = x j对于所有 j ∈ {1, ..., n}。我们想要 |Y| 尽可能小。

于 2013-04-15T21:13:55.513 回答
2

如果路径是有向的，那么通过复制多个叶节点形成一个等效的树结构来对应多条路径。如果结构没有有向路径，那么我相信一般情况下没有对应的树结构。

编辑

鉴于这是一个有向图的新信息，等效的树结构为：

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

并且推导它的算法是图的中缀遍历，当没有传出路径时在每个肢体上停止。

于 2013-03-26T15:19:24.540 回答
1

问题仍然有点不清楚，但是我感觉您需要执行图形序列化或图形的拓扑排序。这只能应用于 DAG，因为循环的存在可以解释为依赖循环。

于 2013-03-26T21:10:44.003 回答
0

您展示的图片表明该方法应该是从头向后工作。您首先查找没有子节点的节点 - 在本例中为 8 和 7。形成树的“双主干”。然后查找 8 和 7 的所有父级。同时查找没有父级的模块 - 在本例中为 1。称其为祖先。它是“终点”。最后，对于每组公共节点，我们声明一个“族”。具有共同孩子的节点是家庭——即使同一个节点可以属于多个家庭。只有一个父节点的节点是该父节点家族的一部分。

对于 8，您会找到 5 和 6。家庭 A。

对于 7，你会找到 4。家庭 B。7 只有一个父母，所以我们称 4 是家庭 B 的一部分。

将这些称为“第 2 代”。

对于第 2 代，寻找父母。

家庭 A： 5 -> 2,3,4 。家庭 C 6 -> 3,4 。家庭 D

家庭 B：4 -> 1 - 大家庭到达祖先。这条路径现在已经完成。我们可以将一条路径捕获为 1-4-7-end（所有“家庭 B”）

现在寻找第 3 代的父母：

5 人（家庭 C）： 2 -> 1 3 -> 1 4 -> 1 具有相同父母的同一家庭的成员是“近亲”，并得到一个<flow>以上和以下。

6 人（家庭 D）：3 -> 1 4 -> 1 另一个亲密的家庭

既然这些家族最终都指向了祖先，我们就需要另一个家族。

因此，我们拥有所描述的每个过程的完整祖先。现在我们使用上面的“家庭”转换为您的流程图。

Your desired XML - annotated with the families. You can see how this works

<root>
    <seq>
        <mod1/> // the ancestor
        <flow>
            <seq> // family B - straight through.
                <mod4/>
                <mod7/>
            </seq>
            <seq> 
                <flow>
                    <seq>
                        <flow> // close family D
                            <mod4/>
                            <mod3/>
                        </flow>
                        <mod6/> // child of D
                    </seq>
                    <seq>
                        <flow> // close family C
                            <mod4/>
                            <mod3/>
                            <mod2/>
                        </flow>
                        <mod5/> // child of C
                    </seq>
                </flow>
                <mod8/>
            </seq>
        </flow>
    </seq>
</root>

这有帮助吗，还是我完全不合时宜？

编辑：关于“中间关闭流程”的主题，以下想法：

如果一个家庭与另一个家庭有相同的（孙）子女，并且他们有相同的（祖）父母，那么他们的流量可以在该级别合并。要发现这一点，您需要为每个家庭保留一份“直系血统”列表，并且您需要为每个家庭反复搜索此列表，以查找同时存在普通（祖）父母和普通（孙）子女的情况。以一般方式解决这个问题需要比我今晚投入更多的精力，既然你已经表示你已经接近解决方案，我将把它留在这里......

于 2013-04-17T02:50:11.920 回答
0

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

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

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

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

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

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

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

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

于 2013-04-29T15:05:18.137 回答