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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Входные данные:
    ациклический граф '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 этап (транзитивное замыкание $G$) либо выполняется следующим алгоритмом:

Входные данные
    граф 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)    /* присваивание по ссылке */

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

Входные данные
    граф 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 Последовательная сложность алгоритма

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

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

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

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

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

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

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