用於計算依賴圖的部分排序的算法

我試圖計算一個依賴圖的部分「拓撲排序」，它實際上是一個DAG（直接非循環圖）以並行地執行沒有衝突依賴關係的任務。用於計算依賴圖的部分排序的算法

我想出了這個簡單的算法，因爲我在Google上找到的東西並不是那麼有用（我一直只找到自己並行運算來計算正常拓撲排序的算法）。

visit(node) 
{ 
    maxdist = 0; 
    foreach (e : in_edge(node)) 
    { 
     maxdist = max(maxdist, 1 + visit(source(e))) 
    } 
    distance[node] = maxdist; 
    return distance[node]; 
} 

make_partial_ordering(node) 
{ 
    set all node distances to +infinite; 
    num_levels = visit(node, 0); 
    return sort(nodes, by increasing distance) where distances < +infinite; 
}

（請注意，這僅僅是僞代碼，並一定會有幾個可能的小優化）

至於正確性，它似乎很明顯：對於葉子（：這還沒有進一步=節點依賴性），最大距離到葉子總是0（正確，因爲循環由於0邊緣而被跳過）。對於連接到節點n1，...，nk的任何節點，最大距離與葉子的距離爲1 + max {distance [n1]，..，distance [nk]}。

我在寫下算法之後，確實找到了這篇文章：http://msdn.microsoft.com/en-us/magazine/dd569760.aspx 但是說實話，他們爲什麼要做所有的列表複製等等，它看起來真的很低效。

無論如何，我想知道我的算法是否正確，如果是的話，它是什麼叫我可以讀一些關於它的東西。

更新：我在我的程序中實現了算法，它似乎對我測試過的所有東西都很好。代碼明智它看起來像這樣：

typedef boost::graph_traits<my_graph> my_graph_traits; 
    typedef my_graph_traits::vertices_size_type vertices_size_type; 
    typedef my_graph_traits::vertex_descriptor vertex; 
    typedef my_graph_traits::edge_descriptor edge; 

    vertices_size_type find_partial_ordering(vertex v, 
     std::map<vertices_size_type, std::set<vertex> >& distance_map) 
    { 
     vertices_size_type d = 0; 

     BOOST_FOREACH(edge e, in_edges(v)) 
     { 
      d = std::max(d, 1 + find_partial_ordering(source(e), distance_map)); 
     } 

     distance_map[d].insert(v); 

     return d; 
    }

來源

2011-02-15 d3ddev

您可能希望通過記憶find_partial_ordering的返回值來將最壞情況從二次方減少到線性...... – 2011-02-16 14:56:30

您是否需要預先爲圖找到一組圖層，或者您是否可以增量方式任務執行？如果您的任務執行時間不盡相同，那麼創建一個算法來挑選其依賴關係已滿足的元素很簡單，然後在線程空閒時運行該算法。 – 2011-02-19 03:26:34

你的算法（C++）的作品，但它有非常糟糕的最壞情況下的時間複雜度。它在一個節點上計算find_partial_ordering以獲取與該節點相同數量的路徑。在樹的情況下，路徑的數量是1，但是在一般的有向無環圖中，路徑的數量可以是指數的。

您可以通過memoizing您的find_partial_ordering結果修復此問題，並在您已經計算出特定節點的值時不返回而返回。但是，這仍然會給你帶來一個堆棧式的遞歸解決方案。

An efficient (linear) algorithm for topological sorting is given on Wikipedia。這不符合你的需求嗎？

編輯：啊，我明白了，你想知道深度邊界在哪裏，以便你可以在給定的深度平行化所有的東西。您仍然可以在維基百科上使用該算法（因此避免遞歸）。

首先，用維基百科上的算法進行拓撲排序。現在計算的深度訪問拓撲序節點：

depths : array 1..n 
for i in 1..n 
    depths[i] = 0 
    for j in children of i 
     depths[i] = max(depths[i], depths[j] + 1) 
return depths

請注意，有沒有以上遞歸，只是一個普通的O(|V| + |E|)算法。這與維基百科上的算法具有相同的複雜性。

來源

2011-02-20 12:42:03 rlibby

用於計算依賴圖的部分排序的算法

回答

相關問題