合併兩個圖結構的部分的算法或理論？

Question

我有向無環圖，其中的一個例子可能看起來像：

     | 
        (1) 
       /| \ 
       /| \ 
       (3) (2) (4) 
       // | \ \ 
      // | \ \ 
      // | \ \ 
      (6)(7) (5) (8)(9) 
      | | | | | 
      (10)(11) (12)(13)(14) 
      \ \ | // 
       \ \ (15)_//
       \ \ | /
       \___(16)__/ 
        | 
        | 

• 每個節點的執行發生向下。
• 如果一個節點有多個傳出分支，則會創建一個圖的副本，並且所選分支在不同的進程中執行。
• 其中節點具有一個以上的傳入分支的曲線的副本被路由回到主過程，以便它們可以被合併，因此主副本具有所有的分支製成（在單獨的進程）的變化。
• 流程是長時間運行的和短暫的，所以我不能/不會已經執行後要路由每個節點回主 - 我只是想在主合併時，一大塊的工作（一分支）已經遠程完成。

因此，例如，在節點(1)有三個分支必須在節點(16)同步。就其本身而言，這是比較簡單 - 爲​​節點(1)馬克節點(16)和節點(1)合併(16)下來分支時執行命中(16)被同步。

然而，節點(2)有還必須在節點(16)同步兩個分支（它也有兩個必須在節點(15)同步）。

問題在於，在此示例中，當執行命中節點(16)時，它不知道備份樹開始同步的距離（即節點(1)或(2)）。

我需要類似於圖着色方案的東西，由此不同的執行路徑提供它們自己的指向它們起源的節點的指針，所以當路徑(11) -> (16)被激活時，執行知道要合併的圖的部分開始在節點(2)。

有一些理論或算法可以幫助嗎？或者我以錯誤的方式處理問題？

Answer 1

Topological sorting是你在找什麼。您可以使用該算法將圖的節點劃分爲每個固定節點X的三類節點 - X的前驅節點，X的後繼節點和獨立於X的節點。

請注意，您的圖必須是非循環的對於算法，雖然你說你的圖是循環的（但在我的例子中我看不到循環）。

算法

1. 採取一系列直接前輩的節點的節點X的DP。
2. 對於每個直接前驅節點Ni在DP中查找前驅節點集合Pi。
3. 找到一組常見的前身由相交的所有節點PiCP。
4. 找到CP中的唯一後繼節點（如果CP非空）。

例

讓我們來看看節點15. arew兩次直接前輩12和13.現在發現的這兩個節點的所有前任 - 12它們是5,2和1。13它們是8,2和1.這兩個集合的交集是2和1，因此這兩個節點是公共前輩，節點2是沒有後繼者的公共前輩（而節點1是公共前輩，但是具有節點2作爲後繼者） 。因此在節點15兩個分支源自節點2加入。