模式或算法合并树状结构的分支？ [英] Pattern or algorithm to merge branches in tree structure?

问题描述

我想一个DAG（有向无环图）映射到我出现如下图所示的结构。

I am trying to map a DAG (Directed Acyclic Graph) into the structure I show below.

下面是DAG的从我做起的例子

Here is an example of the DAG I start from

在这里弧线总是从左至右。

where arcs always go from left to right.

我再恢复图形和跨越到一个树这样的重复节点：

I then revert the graph and span it into a tree with repeated nodes like this:

我在找的是一些算法或模式来实现以下合并后的结构。 （请注意它再次恢复）

What I am looking for is some algorithm or pattern to achieve the following merged structure. (Note it is reverted again)

的目标是生成这样的XML：

The goal is to generate an XML like this:

<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服务和箭头重新present输入和输出parameteres，因此，例如，模块5被调用一次技术模块1,2,3和4已经完成，其产出的投入。

I don't think it's relevant but I am parsing JSON to write an XML with JAVA 7. Boxes are web services and the arrows represent input and output parameteres, so for instance, Module 5 is called once Modules 1,2,3 and 4 have finished and their outputs are its inputs.

编辑：确定，这里是另外一个例子与十个节点。我希望这给你当我的节点是为了合并更好的AP preciation。

Ok, here is another example with ten nodes. I hope this gives you a better appreciation of when I nodes are meant to be merged.

要回答@blubb，在这个例子中，我们可以看到服务8安培; 9也被合并。否则，他们需要的所有服务工作（1,2,3,4,5和6）将无需调用两次。在过去的草图中间的分支将被执行两次：一次为8，一次是9

To answer @blubb, in this example we can see how "services" 8 & 9 have also been merged. Otherwise all the services they need to work (1,2,3,4,5 and 6) would be call twice with no need. The middle branch in the last sketch would be executed twice: once for 8 and once for 9.

推荐答案

最后，我发现了一个算法做了工作。在这里，它是为大家谁试图帮助我了：

Finally, I found an algorithm that did the job. Here it is for all of you who tried to help me out:

首先我的素描1.建一个倒生成树从DAG所以我从模块7和8日开始，建设树向后并在模块是重复的。

First of all I built an inverted spanning tree from the DAG in sketch 1. So I started from modules 7 and 8, building the tree backwards and where modules are duplicated.

在我创建一个名为流量和SEQUENCE虚拟节点，并介绍他们在树中，使每个模块节点是一个序列的子节点。跨越分支节点序列这是流节点的孩子的。我认为这是一步是不够直观，但重要的想法是要明白，我们需要虚拟节点，所以我们可以关闭该流节点，这是那些分裂从一个节点到多个。

After that I create virtual nodes called FLOW and SEQUENCE and introduce them in the tree so that every MODULE node is a child of a SEQUENCE node. Spanning branches are SEQUENCE nodes which are childs of FLOW nodes. I think this is step is intuitive enough but the important idea is to understand that we need virtual nodes so we can close the FLOW nodes, which are the ones splitting from one node to more than one.

之后，我去了树的深度优先，并为每个模块（我们称之为驾驶员）我比较与司机的兄弟姐妹的孩子的孩子。如果它们不匹配我继续走下去的司机的兄弟姐妹的孙子，这样一来，所有分支出来驾驶员的兄弟姐妹都必须经过相同的节点作为司机一样。图形，这意味着，在某些时候，这两个节点需要完全相同的模块

After that I go over the tree depth first, and for every module(we'll call it the driver) I compare its children with the children of the driver's siblings. If they don't match I keep going down with the grandchildren of the driver's siblings, so that, all branches coming out of the driver's siblings must pass through the same nodes as the driver does. Graphically this means that at some point, both nodes need the exact same modules.

如果他们符合我的重合节点清理合并分支向下，这意味着我将它们赶走他们的父母。从这里向上就进入到一个新的序列节点连同司机序列节点，进入同一个流的节点。

If they match I clean the merging branches from the coinciding nodes downwards, which means I cut them off their parents. From there upwards it goes into a new SEQUENCE node together with the drivers SEQUENCE node, into the same FLOW node.

在去在整棵树，只要合并已经取得了，我们去了树，这一次有较大的关系。这意味着不是比较司机的孩子，我们比较了驾驶者的巨大儿。

After going over the whole tree, as long as a merge has been made, we go over the tree again, this time with a greater relationship. This means that instead of comparing the driver's children, we compare the driver's great children.

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

The last step is obviously to revert the tree again.

有一些概念，我已经离开了，因为这些错综复杂的虚拟节点的编程暗示的一边。主要是由于被失去了所有的父子，兄弟关系，一旦虚拟节点相继出台。但我希望的总体思路已经明白。

There are some concepts I have left aside because of the intricacies the programming of these virtual nodes imply. Mainly due to all the parent-children-sibling relationship being lost once virtual nodes have been introduced. But I hope the general idea has been understood.

这篇关于模式或算法合并树状结构的分支？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！