Алгоритм для вычисления частичного упорядочения графов зависимостей

Я пытаюсь вычислить частичную «топологическую сортировку» графа зависимостей, который на самом деле является 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;
}

(Обратите внимание, что это всего лишь псевдокод и определенно будет несколько возможных небольших оптимизаций)

Что касается правильности, это кажется довольно очевидным: для листов (: = узлов, которые больше не зависят) максимальное расстояние -to-leaf всегда 0 (правильно, потому что цикл пропускается из-за 0 ребер). Для любого узла, подключенного к узлам n1, .., nk, максимальное расстояние до листа равно 1 + max {distance [n1], .., расстояние [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;
  }