我正在尝试计算依赖图的部分“拓扑排序”,准确地说,它实际上是一个 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;
}
最佳答案
您的算法 (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|)
算法。这与维基百科上的算法具有相同的复杂性。
关于计算依赖图偏序的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5004973/