Алгоритм Пурдома: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
Строка 19: Строка 19:
 
# Найти [[Связность в графах|компоненты сильной связности]] исходного графа, заменить каждую компоненту на одну вершину и удалить образовавшиеся рёбра-петли.
 
# Найти [[Связность в графах|компоненты сильной связности]] исходного графа, заменить каждую компоненту на одну вершину и удалить образовавшиеся рёбра-петли.
 
# Выполнить топологическую сортировку полученного ациклического графа <math>\tilde G</math>.
 
# Выполнить топологическую сортировку полученного ациклического графа <math>\tilde G</math>.
# Вычислить транзитивное замыкание графа <math>\tilde G</math>, двигаясь от вершин с бо́льшиминомерами к меньшим.
+
# Вычислить транзитивное замыкание графа <math>\tilde G</math>, двигаясь от вершин с бо́льшими номерами к меньшим.
 
# По найденному транзитивному замыканию <math>\tilde G</math> восстановить транзитивное замыкание исходного графа.
 
# По найденному транзитивному замыканию <math>\tilde G</math> восстановить транзитивное замыкание исходного графа.
  

Версия 11:52, 14 июня 2015

1 Свойства и структура алгоритмов

1.1 Общее описание алгоритма

Алгоритм Пурдома[1] находит транзитивное замыкание ориентированного графа за время [math]O(\mu n)[/math], где [math]\mu \le m[/math] – число рёбер, соединяющих компоненты сильной связности этого графа.

1.2 Математическое описание

Алгоритм основан на следующих свойствах:

  1. Если вершины [math]v[/math] и [math]w[/math] принадлежат одной компоненте сильной связности графа [math]G[/math], то его транзитивное замыкание [math]G^+[/math] содержит рёбра [math](v, w)[/math] и [math](w, v)[/math].
  2. Если вершины [math]x[/math] и [math]y[/math] принадлежат одной компоненте сильной связности графа [math]G[/math], а вершины [math]z[/math] и [math]t[/math] – другой, то рёбра [math](x, z)[/math], [math](x, t)[/math], [math](y, z)[/math], [math](y, t)[/math] принадлежат или не принадлежат транзитивному замыканию [math]G^+[/math] одновременно.

Таким образом, поиск транзитивного замыкания графа [math]G[/math] сводится к поиску транзитивного замыкания ациклического графа [math]\tilde G[/math], полученного из [math]G[/math] схлопыванием каждой компоненты сильной связности в одну вершину. Транзитивное замыкание ациклического графа вычисляется с использованием топологической сортировки вершин графа.

1.3 Вычислительное ядро алгоритма

1.4 Макроструктура алгоритма

Вычисления производятся в четыре этапа:

  1. Найти компоненты сильной связности исходного графа, заменить каждую компоненту на одну вершину и удалить образовавшиеся рёбра-петли.
  2. Выполнить топологическую сортировку полученного ациклического графа [math]\tilde G[/math].
  3. Вычислить транзитивное замыкание графа [math]\tilde G[/math], двигаясь от вершин с бо́льшими номерами к меньшим.
  4. По найденному транзитивному замыканию [math]\tilde G[/math] восстановить транзитивное замыкание исходного графа.

Последний этап не является обязательным, если рассматривать транзитивное замыкание [math]\tilde G[/math] как «упакованное» транзитивное замыкание [math]G[/math].

1.5 Описание схемы реализации последовательного алгоритма

1.6 Последовательная сложность алгоритма

1.7 Информационный граф

1.8 Описание ресурса параллелизма алгоритма

1.9 Описание входных и выходных данных

1.10 Свойства алгоритма

2 Программная реализация алгоритмов

2.1 Особенности реализации последовательного алгоритма

2.2 Описание локальности данных и вычислений

2.3 Возможные способы и особенности реализации параллельного алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

2.7 Существующие реализации алгоритма

3 Литература

  1. Purdom, Paul, Jr. “A Transitive Closure Algorithm.” Bit 10, no. 1 (March 1970): 76–94. doi:10.1007/BF01940892.