计算依赖图偏序的算法

Question

我正在尝试计算依赖图的部分“拓扑排序”，准确地说，它实际上是一个 DAG（有向无环图）；以便并行执行任务而不会产生依赖冲突。

我想出了这个简单的算法，因为我在谷歌上找到的东西并没有那么有用（我一直只找到本身并行运行以计算正常拓扑排序的算法）。

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，但是在一般的有向无环图中，路径的数量可以是指数的。

您可以通过记忆您的find_partial_ordering结果并返回而不递归来解决此问题您已经计算了特定节点的值。然而，这仍然给你留下了一个堆栈破坏递归解决方案。

维基百科上给出了一种有效的（线性）拓扑排序算法。这不符合您的需求吗？

编辑：啊，我明白了，您想知道深度边界在哪里，以便可以在给定深度上并行化所有内容。您仍然可以使用维基百科上的算法来实现此目的（从而避免递归）。

首先，用维基百科上的算法进行拓扑排序。 现在通过按拓扑顺序访问节点来计算深度：

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