将图形映射到另一个结构的算法

Question

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

下面是曲线图的类型的一个例子，我需要映射

其中箭头总是有一个方向从左至右。

这是我正在寻找的结果。

的目标是产生一个这样的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来编写一个XML与JAVA 7. 框是Web服务和箭头表示输入和输出参数，所以例如，模块5被调用一次模块1， 2,3和4已完成，其输出是其输入。

Answer 1

最后，我找到了一个算法那做了这个工作。这里是所有人试图帮助我的：

首先，我在草图1中从DAG构建了一棵倒转的树。所以我从模块7和8开始，向后建树，模块是重复的。

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

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

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

在遍历整棵树后，只要合并完成，我们再次翻过树，这次的关系更大。这意味着我们不是比较驾驶员的孩子，而是比较驾驶者的优秀孩子。

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

由于这些虚拟节点的编程意味着错综复杂，所以我留下了一些概念。主要是因为一旦引入了虚拟节点，所有的父母 - 孩子 - 兄弟姐妹关系都会丢失。但我希望大家的想法能够被理解。

Answer 2

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

EDIT

在新的信息的光，这是一个有向图，等效树结构是：

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

和算法来推导，这是的一个中缀遍历图中，当没有外出路径时停止在每个肢体上。

Answer 3

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

编辑：根据您的编辑图是指示，所以你将有DAG这再次不是一棵树，但有几个有趣的属性。

Answer 4

的问题仍然是一个有点不清楚，但是我得到你需要执行图形序列，或拓扑排序图的的感觉。这只能应用于DAG，因为周期的存在可以被解释为依赖周期。

Answer 5

（不是一个答案，但我的建议编辑得到了拒绝虚假的理由。）

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

输入是一个 ≤ _X在有限集X上，由具有顶点X的无环有向图指定。输出是一个有限集合Y上的series-parallel partial order ≤ _Y，该有限集合Y由单元素部分顺序的串联和并联组合指定，并且映射f：Y → X，明确指定，使得对于每个最大链x < _X＆hellip; < _X X _Ñ（=在输入图的transitive reduction一个源到宿的路径），存在恰好一个最大链ÿ < _ý＆hellip; < _ÿý_Ñ以f（Y _Ĵ）= X _Ĵ对于所有的j ∈ {1，＆hellip;，N}。我们想要| Y |尽可能小。

Answer 6

您正在显示的图片表明该方法应该从结尾向后工作。您首先查找没有孩子的节点 - 在本例中为8和7.树的形式为“双树干”。然后查找8和7的所有父母。还要查找没有父母的模块 - 在这种情况下，1.称这为祖先。这是“终点”。最后，对于每一组共同节点，我们声明一个“家庭”。与一个共同孩子的节点是家庭 - 即使同一节点可以属于多个家庭。只有一个父母的节点是该父母家庭的一部分。

对于8，你会发现5和6系列A.

对于7，你会发现4.家庭B. 7只有一个父，所以我们称之为家庭B.

召唤4部分这些“第二代”。

对于第二代，寻找父母。

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

家庭B： 4 - > 1 - 扩展家庭达到祖先。此路径现已完成。我们可以捕获一条路径为1-4-7端（所有 “家庭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> 

这是否有帮助，还是我完全不符合标准？

编辑：在“中间闭合流动”的主题，如下思考：

如果一个家庭有相同的（大）的孩子作为另一个家庭，和他们有相同的（大）的父母，那么他们的流量可以在这个水平上合并。为了发现这一点，您需要为每个家庭保留一份“直系亲属”的清单，并且您需要为每个家庭反复搜索这个清单，以查找既有普通（大）父母又有普通（大）孩子的情况。通过一般的方式工作将花费比我今晚可以投入更多的努力，并且既然你已经表明你已经接近解决方案，我将把它留在这里...