在有向无环图的拆分和合并处插入节点

Question

我有以下有向无环图，其中边方向是从上到下

                A
                |  
                B
               / \  
              C   D
             / \  |    
            E   F | 
             \ /  | 
              G   |
               \ /
                H 

我想在节点分裂的地方插入特殊的分裂节点，在它们再次合并的地方插入合并节点，即我想将上面的图结构转换成下面的图

                A
                |
                B  
                | 
               B-S
               / \  
              C   D
              |   |  
             C-S  |  
             / \  |    
            E   F | 
             \ /  | 
             C-M  |
              |   | 
              G   |
               \ /
               B-M 
                |
                H 

如何进行上述转换？

Answer 1

我把图重写成这样，所以M和S有关系就一目了然了。我也在考虑这棵树最多有两个 children，但它可以很容易地在合并部分更新到更多 children。

            A
            |
            B  
            | 
           B-S1
           / \  
          C   D
          |   |  
         C-S2 |  
         / \  |    
        E   F | 
         \ /  | 
         C-M2 |
          |   | 
          G   |
           \ /
           B-M1
            |
            H 

主要原则是当你进行拆分时，你必须通过所有其他节点传递相关信息，直到你再次合并它们。

算法如下：

开始：创建stack变量并将A与空tokenStack一起推送到它（它就像一个object{node: A, tokenStack: {}}

1. 从stack
取item
2. 检查 parents 和 item.parents.length 的数量
   • 如果是2，检查item.token是否存在
     • 如果没有，从 tokenStack 中取出最后一项并将其保存在 item.token 中
       • 跳过下面的所有内容并从 1.
       继续
     • 如果存在值，它应该与您在 tokenStack 中的最后一个值相同。从您的 tokenStack 中取出该值，您可以继续 3.
3. 用 item.childrens.length 检查 children 的数量
   • 如果等于 1，将 children 推到 stack 并保持不变 tokenStack
   • 如果有两个 children，进行拆分，创建令牌（即唯一字符串），将此令牌添加到 tokenStack，将其保存到当前 item.token 并推送两个 children 到 stack 连同 tokenStack

现在您完成了所有操作，Split 和 Merge 节点具有相同的 item.token

注意：您还可以在流程中保存有关 tokenStack 中所有现有令牌的信息，如果您想稍后调查哪些节点在 left/right 部分分支中。