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

问题描述

我正在尝试将DAG（定向非循环图）映射到下面显示的结构中。

这是DAG的一个例子，我从

其中弧总是从左到右。

然后，我将图形还原，并将其跨越一个树，重复的节点如下所示： p>

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

目标是生成一个这样的XML：

 <根> 
< 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完成，输出就是其输入。

编辑：好的，这里是另外10个节点的例子。我希望这可以让您更好地了解我的节点何时被合并。

要回答@blubb，在这个例子中我们可以看到服务8& 9也已经合并。否则，他们需要工作的所有服务（1,2,3,4,5和6）将无需两次通话。最后草图中的中间分支将执行两次：一次为8次，一次为9次。

解决方案

最后，我发现做了这个工作的算法。在这里，所有试图帮助我的人：

首先，我从草图1中的DAG中构建了一个反向生成树。所以我从模块开始之后，我创建了名为FLOW和SEQUENCE的虚拟节点，并将它们引入树中，以便每个MODULE节点是SEQUENCE节点的小孩。跨越分支是SEQUENCE节点，它们是FLOW节点的子节点。我认为这是一个直观的步骤，但重要的想法是理解我们需要虚拟节点，所以我们可以关闭FLOW节点，这些节点是从一个节点分成多个节点。

之后，我首先浏览树的深度，对于每个模块（我们称之为驱动程序），我将其孩子与司机的兄弟姐妹的孩子进行比较。如果他们不匹配，我会继续与司机的兄弟姐妹的孙子一起下去，所以从驾驶员兄弟姐妹出来的所有分支都必须通过与司机相同的节点。在图形上，这意味着在某些时候，两个节点都需要完全相同的模块。

如果匹配我将合并的分支从合并节点向下清理，这意味着我切割它们离开他们的父母从那里起，它与一个新的SEQUENCE节点一起进入同一个FLOW节点。

在整个树上，只要合并已经做好了，我们再次去树上，这个时候有了更大的关系。这意味着我们比较驾驶员的孩子，而不是比较驾驶员的大孩子。

最后一步显然是还原树。

由于这些虚拟节点的编程意味着错综复杂，我留下了一些概念。主要是由于所有的父 - 子兄弟关系在虚拟节点被引入后才会丢失。但我希望一般的想法已经被理解了。

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

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)

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>

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.

EDIT: 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.

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:

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.

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屋！