计算依赖图偏序的算法

Question

我正在尝试计算依赖图的部分“拓扑排序”，准确地说，它实际上是一个 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;
  }

Answer 1

您的算法 (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|) 算法。这与维基百科上的算法具有相同的复杂性。