计算依赖图的偏序算法

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;
  }

- d3ddev

---

你可能想通过记忆化find_partial_ordering的返回值来将最坏情况从二次降至线性。 - a dabbler

你需要提前找到一组图层，还是可以在任务执行时逐步完成？如果您有不同的任务执行时间，那么很容易创建一个算法来选择一个其依赖关系已满足的元素，然后在线程空闲时运行它。 - Jeremiah Willcock

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

- rlibby