合併兩個DAG的高效算法

我有兩個加權的DAG（有向無環圖），需要將它們合併爲一個，因此我可以得到一個拓撲排序（在某些情況下它可能超過兩個）。問題是這些圖是非循環的，但可以一起形成一個循環。此外，圖形很大（100k +節點，500k +邊緣）。有沒有一種巧妙的方法來合併圖表？「同時」遍歷所有圖的算法同樣好。合併兩個DAG的高效算法

編輯：

通過「合併」我的意思是這兩個圖的所有邊緣和頂點組合在一起（當然保留的權重），如果他們不創造週期。如果邊緣已經存在，我想用更大的重量。

這個想法是，從兩個非循環圖開始應該比簡單地「修復」結果後有優勢（這意味着要找到反饋弧集合，這是NP難以避免的）。

謝謝您的建議。

來源

2010-12-19 Thomas

你是什麼意思合併？請更具體地說明 – 2010-12-19 12:10:06

感謝您的回答。我修改了問題以澄清。 – Thomas 2010-12-19 14:32:32

當創建一個循環時，仍然不清楚該怎麼做。 – wnoise 2011-02-06 08:51:39

假設頂點是相同的兩個圖表如果沒有，只考慮

V = V1 U V1

讓我們假設你有一個鄰接表。現在，對於V1和V2中的每個頂點v，可以通過邊緣導向的頂點對鄰接列表進行排序（如果它是（頂點，權重）對，按頂點排序）。由於圖表很小，所以它不應該太昂貴，它應該是summation degree(v)*log(degree(v))，它不應該那麼糟糕。

之後，您可以迭代V1和V2中的所有頂點v，並在V1和V2中對v的鄰接列表進行合併排序。這類似於使用合併排序找到2個排序數組的聯合，只是在那裏你會發現一個元素出現在你可以選擇更大的邊緣。

來源

2010-12-31 20:05:48 user513590

一個問題是可能有多個解決方案。考慮例如DAG {（a，b），（a，c）}和{（b，a），（b，c）}。你可以「合併」這兩種不同的方式：

{（A，B），（A，C），（B，C）}
{（A，C），（B，A ），（b，c）}

解決方案的數量與兩個圖的並集中的週期數成比例地增長，所以對於大圖，可能有很多方法可以「合併「他們。

您是否有一個標準可以幫助您確定哪個DAG比另一個「更好」？

來源

2011-04-28 15:20:35 mitchus

我有一個類似的問題，我解決了，像這樣：

我改變了我的DAG與地圖節點的地圖（按節點ID鍵，值節點的集合，大概一個開始）和邊緣圖（由源，目標對鍵值，值是邊的集合，可能是一個開始）。我稱之爲正常化。原圖是「根」的集合，每個節點有孩子

的集合，然後我可以一起通過鍵合併通過鍵邊緣節點和合並兩個。即：如果節點確實存在，則將新節點引用到現有節點值，如果節點不存在，則添加它。與邊緣相同。

這工作很乾淨，但它沒有避免週期。

下面是一些代碼，我用（Clojure的）：

(def empty-graph 
    {:nodes {} 
    :edges {}}) 

(defn merge-graphs 
    [a b] 
    {:nodes (merge-with concat (get a :nodes) (get b :nodes)) 
    :edges (merge-with concat (get a :edges) (get b :edges))}) 

(defn normalize-graph 
    [graph] 
    {:nodes (->> 
      graph 
      (mapcat 
       (fn [root] 
       (->> 
        root 
        (tree-seq (fn [_] true) (fn [node] (get node :children))) 
        (mapcat 
        (fn [edge] 
         (concat 
         (if-let [source (get edge "source")] 
          [[source [source]]] 
          []) 
         (if-let [target (get edge "target")] 
          [[target [target]]] 
          []))))))) 
      (into {})) 
    :edges (->> 
      graph 
      (mapcat 
       (fn [root] 
       (->> 
        root 
        (tree-seq (fn [_] true) (fn [node] (get node :children))) 
        (filter (fn [edge] (and (not (nil? (get edge "source"))) (not (nil? (get edge "target")))))) ;this sucks but is necessary 
        (map 
        (fn [edge] 
         (let [compact (dissoc edge :children)] 
         [[(get edge "source") (get edge "target")] [compact]])))))) 
      (into {}))})

來源

2017-04-04 20:30:50 Brad

合併兩個DAG的高​​效算法

回答

相關問題

合併兩個DAG的高效算法