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

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

9 голосов
/ 15 февраля 2011

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

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

Что касается правильности, то это кажется довольно очевидным: дляleafs (: = узлы, которые больше не зависят), максимальное расстояние до листа всегда равно 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;
  }

1 Ответ

13 голосов
/ 20 февраля 2011

Ваш алгоритм (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|) алгоритм. Это имеет ту же сложность, что и алгоритм в Википедии.

...