算法计算的依赖关系图的偏序 [英] Algorithm for computing partial orderings of dependency graphs
问题描述
我试图计算依赖关系图,这实际上是一个DAG(有向无环图)的部分拓扑排序是precise;从而不平行依赖性冲突而执行任务。
我想出了这个简单的算法,因为我发现在谷歌是不是所有的有用的(我一直发现只有自己在并行运行的算法来计算一个正常的拓扑排序)。
访问(节点)
{
maxdist = 0;
的foreach(E:in_edge(节点))
{
maxdist = MAX(maxdist,1 +访问(源(E)))
}
距离[节点] = maxdist;
返回距离[节点]
}
make_partial_ordering(节点)
{
将所有节点的距离到+无穷大;
num_levels =访问(节点,0);
返回排序(节点,通过增加距离),其中距离< +无限的;
}
(注意,这是唯一的伪code和有一定会是一些可能的小优化)
至于正确性,似乎pretty的明显的:对于叶子(:它们没有进一步依赖=节点)的最大距离 - 薄片始终为0(正确的,因为环被跳过由于0边缘)。 对于连接到节点n1的任何节点,...,nk的最大距离 - 薄片是1 +最大距离{[N1],..,距离[NK]}
我没有找到这篇文章后,我写下来的算法:<一href="http://msdn.microsoft.com/en-us/magazine/dd569760.aspx">http://msdn.microsoft.com/en-us/magazine/dd569760.aspx 但说实话,他们为什么这样做所有的列表复制等特点,它只是似乎真的如此低效..?
无论如何,我不知道我的算法是否正确,如果是的话它叫什么,这样我可以读了一些东西吧。
更新:我实现的算法在我的计划,这似乎是伟大的工作,一切我测试。 code-明智的,它看起来是这样的:
的typedef的boost :: graph_traits&LT; my_graph&GT; my_graph_traits;
的typedef my_graph_traits :: vertices_size_type vertices_size_type;
的typedef my_graph_traits ::顶点描述的顶点;
的typedef my_graph_traits :: edge_descriptor边缘;
vertices_size_type find_partial_ordering(顶点v,
的std ::地图&LT; vertices_size_type,性病::集&LT;点&GT; &GT;&安培; distance_map)
{
vertices_size_type D = 0;
BOOST_FOREACH(边e,in_edges(V))
{
D =的std ::最大(D,1 + find_partial_ordering(源(E),distance_map));
}
distance_map并[d] .insert(ⅴ);
返回D组;
}
您算法(C ++)的作品,但它有非常坏的最坏情况下的时间复杂度。它计算 find_partial_ordering
尽可能多路径的节点上,因为有该节点。在树的情况下,路径的数目是1,但在一般的向无环图的路径的数量可以是指数的。
您可以通过修复此 memoizing 你的 find_partial_ordering
结果没有返回时,已经计算了一个特定节点的值递归。然而,这仍然给你留下一堆克星递归解决方案。
一个有效的(线性)算法的拓扑排序,给出维基百科。这是否符合你的需要?
编辑:啊,我明白了,你想知道的深度界限,让您可以并行的一切在给定的深度。您仍然可以使用该算法在维基百科上的这个(从而避免递归)。
首先,做一个拓扑排序与维基百科的算法。的现在的访问拓扑节点顺序计算深度:
深度:数组1..N
因为我在1..N
深度[I] = 0
对于j的i的子女
深度[I] =最大值(深度[I]中,深度[j]的+1)
回报深处
请注意,上面没有递归,只是一个普通的 0的(| V | + | E |)
算法。这有相同的复杂性,在维基百科上的算法。
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.
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)
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]}.
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;
}
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.
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?
Edit: 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
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屋!