计算依赖图偏序的算法 [英] Algorithm for computing partial orderings of dependency graphs
问题描述
我正在尝试计算依赖图的部分拓扑排序",准确地说,它实际上是一个 DAG(有向无环图);从而并行执行任务而不会产生依赖冲突.
I'm trying to compute a partial "topological sort" of a dependency graph, which is actually a DAG (Directed Acyclic Graph) to be precise; so as to execute tasks without conflicting dependencies in parallel.
我想出了这个简单的算法,因为我在 Google 上找到的算法并没有那么有用(我一直只找到自己并行运行以计算正常拓扑排序的算法).
I came up with this simple algorithm because what I found on Google wasn't all that helpful (I keep finding only algorithms that themselves run in parallel to compute a normal topological sort).
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;
}
(注意这只是伪代码,肯定会有一些可能的小优化)
(Note that this is only pseudocode and there would certainly be a few possible small optimizations)
至于正确性,这似乎很明显:对于叶子(:= 没有进一步依赖关系的节点),到叶子的最大距离始终为 0(正确,因为循环由于 0 边而被跳过).对于连接到节点 n1,..,nk 的任何节点,到叶子的最大距离为 1 + max{distance[n1],..,distance[nk]}.
As for the correctness, it seems pretty obvious: For the leafs (:= nodes which have no further dependency) the maximum distance-to-leaf is always 0 (correct because the loop gets skipped due to 0 edges). For any node connected to nodes n1,..,nk the maximum distance-to-leaf is 1 + max{distance[n1],..,distance[nk]}.
我写下算法后确实找到了这篇文章:http://msdn.microsoft.com/en-us/magazine/dd569760.aspx但老实说,他们为什么要进行所有列表复制等操作,这似乎效率很低..?
I did find this article after I had written down the algorithm: http://msdn.microsoft.com/en-us/magazine/dd569760.aspx But honestly, why are they doing all that list copying and so on, it just seems so really inefficient..?
无论如何,我想知道我的算法是否正确,如果正确,它叫什么,以便我可以阅读一些关于它的内容.
Anyway I was wondering whether my algorithm is correct, and if so what it is called so that I can read up some stuff about it.
更新:我在我的程序中实现了这个算法,它似乎对我测试的所有东西都很有效.代码方面它看起来像这样:
Update: I implemented the algorithm in my program and it seems to be working great for everything I tested. Code-wise it looks like this:
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;
}
推荐答案
你的算法 (C++) 可以工作,但它的最坏情况时间复杂度非常糟糕.它在一个节点上计算 find_partial_ordering
的路径与该节点的路径一样多.在树的情况下,路径的数量是 1,但在一般的有向无环图中,路径的数量可以是指数的.
Your algorithm (C++) works, but it has very bad worst-case time complexity. It computes find_partial_ordering
on a node for as many paths as there are to that node. In the case of a tree, the number of paths is 1, but in a general directed acyclic graph the number of paths can be exponential.
您可以通过记忆您的find_partial_ordering
结果并返回来解决这个问题当您已经计算了特定节点的值时,无需递归.但是,这仍然给您留下了一个堆栈破坏递归解决方案.
You can fix this by memoizing your find_partial_ordering
results and returning without recursing when you have already computed the value for a particular node. However, this still leaves you with a stack-busting recursive solution.
维基百科提供了一种高效的(线性)拓扑排序算法.这不符合您的需求吗?
An efficient (linear) algorithm for topological sorting is given on Wikipedia. Doesn't this fit your needs?
啊,我明白了,您想知道深度边界在哪里,以便您可以在给定深度并行化所有内容.您仍然可以为此使用维基百科上的算法(从而避免递归).
ah, I see, you want to know where the depth boundaries are so that you can parallelize everything at a given depth. You can still use the algorithm on Wikipedia for this (and so avoid recursion).
首先,使用维基百科上的算法进行拓扑排序.现在通过按拓扑顺序访问节点来计算深度:
First, Do a topological sort with the algorithm on Wikipedia. Now compute depths by visiting nodes in topological order:
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|)
算法.这与维基百科上的算法具有相同的复杂性.
Notice that there's no recursion above, just a plain O(|V| + |E|)
algorithm. This has the same complexity as the algorithm on Wikipedia.
这篇关于计算依赖图偏序的算法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!