Глава 19. Орграфы и ориентированные ациклические графы. 19.9. Еще раз о транзитивном замыкании

19.9. Еще раз о транзитивном замыкании

Объединяя результаты двух предыдущих разделов, мы можем разработать алгоритм решения задачи вычисления абстрактно-транзитивного замыкания для орграфов, который хотя и не вводит никаких усовершенствований в решение для худшего случая, основан­ное на поиске в глубину, но в то же время обеспечивает оптимальное решение во мно­гих других случаях.

В основе этого алгоритма лежит предварительная обработка орграфа, назначение ко­торой состоит в построении базового графа DAG рассматриваемого орграфа (см. свой­ство 19.2). Алгоритм эффективен в том случае, когда размер базового графа DAG мень­ше размеров исходного орграфа. Если исходный граф сам является графом DAG (и в силу этого обстоятельства идентичен базовому DAG), или если он содержит всего лишь несколько циклов, мы не можем рассчитывать на сколь либо заметную экономию затрат. В то же время, если орграф содержит большие циклы или крупные сильные компонен­ты (и поэтому содержит базовые DAG небольших размеров), мы можем построить оп­тимальные либо близкие к оптимальным алгоритмы. Для ясности предположим, что ба­зовый DAG достаточно мал, благодаря чему мы можем воспользоваться представлением графа в виде матрицы смежности, хотя основная идея сохраняет свою актуальность и для базовых DAG больших размеров.

Для реализации абстрактного транзитивного замыкания мы выполним предваритель­ную обработку графа в следующем объеме:

■ Найдем его сильные компоненты.

■ Построим его базовый DAG.

■ Вычислим транзитивное замыкание базового DAG.

Мы можем воспользоваться алгоритмом Косарайю, алгоритмом Тарьяна либо алгорит­мом Габова, чтобы найти сильные компоненты; выполнить один просмотр ребер с целью построения базового DAG (описание будет дано в следующем параграфе); и провести поиск в глубину (программа 19.9) с целью вычисления его транзитивного замыкания. По завершении этой предварительной обработки мы сразу можем обращаться к информации, необходимой для определения достижимости.

Если в нашем распоряжении имеется вектор, индексированный именами вершин с сильными компонентами орграфа, построение представления его базового DAG в виде матрицы смежности не представляет трудностей. Вершины графа DAG суть номера ком­понент орграфа. Для каждого ребра s-t исходного графа мы просто устанавливаем D-> adj[sc[s]][sc[t]] в 1. Нам пришлось бы решать проблему дубликатов ребер в базовом DAG, если бы мы воспользовались представлением графа в виде списков смежных вер­шин, в то же время в матрице смежности дубликаты ребер просто соответствуют установ­ке элемента матрицы в 1, который уже имел значение 1. Это небольшой нюанс приоб­ретает важное значение, поскольку потенциально в рассматриваемом приложении число дубликатов ребер огромно (по отношению к размеру базового DAG).

Свойство 19.17. Заданы две вершины s и t в орграфе D, пусть sc(s) и sc(t) — соответству­ющие им вершины в базовом DAG К орграфа D. Тогда t достижима из s в D тогда и только тогда, когда sc(t) достижима из sc(s) в К.

Часть 5. Алгоритмы на графах

Этот простой факт следует из определений. В частности, это свойство предполагает, что действует соглашение, согласно которому вершина достижима сама из себя (все вершины имеют петли). Если эти вершины находятся в одной и той же сильной ком­поненте (sc(s) = sc(t)), то они взаимно достижимы. ■

Мы определим, достижима ли вершина t из заданной вершины s тем же способом, ка­ким мы строили базовый DAG: воспользуемся вектором, индексированным именами вер­шин, вычисленным с помощью алгоритма сильных компонент, чтобы получить числа sc(s) и sc(t) (за постоянное время), которые мы будем рассматривать как индексы абстракт­ных вершин (abstract vertex) базового DAG. Их использование в качестве индексов для транзитивного замыкания базового DAG даст искомый результат.

Программа 19, 13. Транзитивное замыкание на основе сильных компонент________________

Данный класс реализует интерфейс (абстрактного) транзитивного замыкания орграфов путем вычисления сильных компонентов (с использованием, скажем, программы 19.11), базового DAG и транзитивного замыкания базового DAG (с использованием программы 19.9). Он предполагает, что класс SC обладает общедоступной функцией-элементом ID, которая возвращает индекс сильной компоненты (из массива id) для любой заданной вершины. Эти числа суть индексы вершин в базовом DAG. Вершина t орграфа достижима из вершины s тогда и только тогда, когда ID(t) достижима из ID(s) в базовом DAG.

template < class 6raph> class TC { const Graph & G; DenseGRAPH *K; dagTOCDenseGRAPH, Graph> *Ktc; SC< Graph> *Gsc; public:

TC (const Graph & G): G(G) {

Gsc = new SC< Graph> (G);

К = new DenseGRAPH(Gsc-> count(), true); for (int v = 0; v < G.V(); v++) { typename Graph:: adjIterator A(G, v);

for (int t = A.beg();! A.end(); t = A.nxt())

K-> insert(Edge(Gsc-> ID(v), Gsc-> ID(t))); } Ktc = new dagTC< CDenseGRAPH, Graph> (*K);

}

~TC() { delete K; delete Ktc; delete Gsc; } bool reachable (int v, int w)

{ return Ktc-> reachable(Gsc-> ID(v), Gsc-> ID(w)); } };

Программа 19.13 представляет собой реализацию АТД абстрактно-транзитивного замы­кания, которое воплощает эти идеи. Мы используем интерфейс абстрактно-транзитивного замыкания также и в базовом DAG. Время прогона этой реализации зависит не только от числа вершин и ребер орграфа, но и от свойств базового DAG. В целях анализа пред­положим, что мы используем матрицу смежности для представления базового DAG, по­скольку мы ожидаем, что базовый DAG имеет небольшие размеры, если только он еще и не насыщен.

Свойство 19.18. Мы можем поддерживать постоянное время запроса АТД абстрактно­го транзитивного замыкания орграфа при затратах пространства памяти, пропорциональ­ных V + v², и времени, пропорциональных Е + v² + vx, на предварительную обработку (на вычисление транзитивного замыкания); здесь v есть число вершин в базовом DAG, ах — число поперечных ребер в его лесе DFS. Доказательство: Непосредственно следует из свойства 19.13. ■