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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 этап (транзитивное замыкание [math]\displaystyle{ \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]\displaystyle{ G }[/math]) либо выполняется следующим алгоритмом:

Входные данные
    граф G с вершинами V;
    компоненты сильной связности SCC(v) графа G;
    граф [math]\displaystyle{ \tilde G }[/math] с вершинами [math]\displaystyle{ \tilde V }[/math];
    транзитивное замыкание [math]\displaystyle{ \tilde T }[/math] графа [math]\displaystyle{ \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]\displaystyle{ \tilde V }[/math]:
    for each w ∈ [math]\displaystyle{ \tilde T(v) }[/math]:
        T(v) := T(v) ∪ SCC(w)
    for each x ∈ SCC(v):
        T(x) := T(v)    /* присваивание по ссылке */

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

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

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

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

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

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

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

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

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

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