计算依赖图的部分排序的算法

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结果,并没有递归时你已经计算出特定节点的值返回.但是,这仍然会给你一个堆栈破坏的递归解决方案.

维基百科上给出了一种用于拓扑排序的有效(线性)算法.这不符合您的需求吗？

编辑:啊,我明白了,你想知道深度边界的位置,这样你就可以在给定的深度上并行化所有东西.您仍然可以在维基百科上使用该算法(以避免递归).

首先,使用维基百科上的算法进行拓扑排序.现在通过以拓扑顺序访问节点来计算深度:

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|)算法.这与Wikipedia上的算法具有相同的复杂性.