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

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.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 этап (топологическая сортировка) может быть реализован алгоритмом Кана либо последовательным применением поиска в глубину для нумерации вершин в предпорядке.

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

Входные данные:
    ациклический граф 'G с вершинами 'V, пронумерованными в топологическом порядке, и рёбрами E.
Выходные данные:
    для каждой вершины v ∈ V – набор вершин T(v),
        так что транзитивное замыкание G состоит из рёбер (v, w), v ∈ V, w ∈ T(v).
    
for each v ∈ V do T(v) := { v }
for v ∈ V 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].
Выходные данные:
    для каждой вершины v ∈ V – набор вершин T(v),
        так что транзитивное замыкание G состоит из рёбер (v, w), v ∈ V, w ∈ T(v).
        
for each v ∈ V 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 x ∈ SCC(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 := T ∪ SCC(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] в противном случае.

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

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

• Boost Graph Library (функция transitive_closure).