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

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$.

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

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

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