用于计算依赖图的部分排序的算法

我试图计算一个依赖图的部分“拓扑排序”，它实际上是一个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

用于计算依赖图的部分排序的算法

回答

相关问题