Алгоритм Пурдома

Материал из Алговики
Перейти к навигации Перейти к поиску

Содержание

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

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

Алгоритм Пурдома[1] находит транзитивное замыкание ориентированного графа за время [math]O(m + \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 этап (вычисление компонент сильной связности) может быть реализован алгоритмом Тарьяна[2], находящим компоненты сильной связности в ходе поиска в глубину.

2 этап (топологическая сортировка) может быть реализован алгоритмом Кана[3] либо последовательным применением поиска в глубину[2] для нумерации вершин в предпорядке.

3 этап (транзитивное замыкание [math]\tilde G[/math]) выполняется следующим алгоритмом:

Входные данные:
    ациклический граф 'G с вершинами 'V, пронумерованными в топологическом порядке, и рёбрами E.
Выходные данные:
    для каждой вершины vV – набор вершин T(v),
        так что транзитивное замыкание G состоит из рёбер (v, w), vV, wT(v).
    
for each vV do T(v) := { v }
for vV in reverse order:
    for each (v, w) ∈ E do T(v) := T(v) ∪ T(w)

4 этап (транзитивное замыкание [math]G[/math]) либо выполняется следующим алгоритмом:

Входные данные
    граф G с вершинами V;
    компоненты сильной связности SCC(v) графа G;
    граф [math]\tilde G[/math] с вершинами [math]\tilde V[/math];
    транзитивное замыкание [math]\tilde T[/math] графа [math]\tilde G[/math].
Выходные данные:
    для каждой вершины vV – набор вершин T(v),
        так что транзитивное замыкание G состоит из рёбер (v, w), vV, wT(v).
        
for each vV do T(v) := { v }
for each v[math]\tilde V[/math]:
    for each w[math]\tilde T(v)[/math]:
        T(v) := T(v) ∪ SCC(w)
    for each xSCC(v):
        T(x) := T(v)    /* присваивание по ссылке */

либо транзитивное замыкание может строиться по упакованным данным [math]\tilde T(v)[/math] одной из следующих функций:

Входные данные
    граф G с вершинами V;
    компоненты сильной связности SCC(v) графа G;
    отображение R(v) вершин графа G на вершины графа [math]\tilde G[/math];
    граф [math]\tilde G[/math] с вершинами [math]\tilde V[/math];
    транзитивное замыкание [math]\tilde T[/math] графа [math]\tilde G[/math].
    
function transitive_closure(v):
    T := { v }
    for each w[math]\tilde T(R(v))[/math]:
        T := TSCC(w)
    return T
    
function is_in_transitive_closure(v, w):
    return R(w) ∈ [math]\tilde T(R(v))[/math]

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

Первый и второй этап выполняются с помощью поиска в глубину со сложностью [math]O(m)[/math].

На третьем этапе основой операцией является объединение списков вершин. В случае хранения списков в отсортированном виде объединение выполняется за линейное время. Количество списков не превосходит [math]n[/math], а в каждом списке не более [math]\mu[/math] вершин, где [math]\mu[/math] – количество компонент сильной связности. Общая сложность тогда составляет [math]O(\mu^2)[/math]. Альтернативным форматов хранения списка вершин является битовая маска с такой же общей сложностью.

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

Таким образом, общая сложность составляет [math]O(m + \mu^2)[/math], если не требуется явное построение транзитивного замыкания, или [math]O(m + \mu n)[/math] в противном случае.

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

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

1.9 Входные и выходные данные алгоритма

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

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

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

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

2.2.1 Локальность реализации алгоритма

2.2.1.1 Структура обращений в память и качественная оценка локальности
2.2.1.2 Количественная оценка локальности

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

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

2.4.1 Масштабируемость алгоритма

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

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.
  2. 2,0 2,1 Tarjan, Robert. “Depth-First Search and Linear Graph Algorithms.” SIAM Journal on Computing 1, no. 2 (1972): 146–60.
  3. Kahn, A B. “Topological Sorting of Large Networks.” Communications of the ACM 5, no. 11 (November 1962): 558–62. doi:10.1145/368996.369025.