Поиск транзитивного замыкания орграфа
Содержание
1 Постановка задачи
Пусть задан ориентированный граф [math]G = (V, E)[/math]. Последовательность [math]P(u, v)[/math] рёбер [math]e_1 = (u, w_1)[/math], [math]e_2 = (w_1, w_2)[/math], …, [math]e_k = (w_{k-1}, v)[/math] называется путём, идущим от вершины [math]u[/math] к вершине [math]v[/math]. Вершина [math]v[/math] называется достижимой из вершины [math]u[/math], если существует хотя бы один путь [math]P(u, v)[/math]. Каждая вершина достижима сама из себя.
Требуется построить транзитивное замыкание [math]G^+ = (V, E^+)[/math] графа [math]G[/math]: ребро [math](v, w) \in E^+[/math] тогда и только тогда, когда в графе [math]G[/math] вершина [math]w[/math] достижима из вершины [math]v[/math].
Эквивалентная формулировка: для данного рефлексивного бинарного отношения [math]R[/math] требуется построить наименьшее по включению отношение [math]R^+[/math], содержащее [math]R[/math] и облагающее свойством транзитивности: если [math]aR^+b[/math] и [math]bR^+c[/math], то [math]aR^+c[/math]. Если исходное отношение [math]R[/math] было симметричным, то [math]R^+[/math] будет отношением эквивалентности и тогда достаточно найти его классы эквивалентности.
2 Свойства задачи
Если вершины [math]v[/math] и [math]w[/math] принадлежат одной компоненте сильной связности графа [math]G[/math], то транзитивное замыкание содержит рёбра [math](v, w)[/math] и [math](w, v)[/math]. В неориентированном графе ребро [math](v, w)[/math] принадлежит транзитивному замыканию в том и только в том случае, когда вершины [math]v[/math] и [math]w[/math] принадлежат одной и той же компоненте связности. Следовательно, для неориентированного графа поиск транзитивного замыкания эквивалентен поиску компонент связности.
Если вершины [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]G[/math] схлопыванием каждой компоненты сильной связности в одну вершину; на этом принципе основан алгоритм Пурдома.
Граф [math]G[/math] и его транзитивное замыкание [math]G^+[/math] имеют одни и те же компоненты сильной связности (в терминах вершин).
3 Алгоритмы решения задачи
В неориентированном графе вершина [math]w[/math] достижима из вершины [math]v[/math] тогда и только тогда, когда они обе принадлежат одной и той же компоненте связности. Транзитивное замыкание сводится к поиску компонент связности графа и может быть найдено следующими алгоритмами:
- последовательным применением алгоритма поиска в ширину за время [math]O(m)[/math];
- с помощью системы непересекающихся множеств[1] за время [math]O(m \alpha(m, n))[/math], с возможностью эффективной многопоточной реализации[2];
- параллельным алгоритмом Шилоаха-Вишкина[3] за время [math]O(\ln n)[/math] на [math]n + 2m[/math] процессорах.
В ориентированном графе транзитивное замыкание может быть сведено к поиску кратчайших путей в графе с единичными весами и найдено следующими алгоритмами:
- алгоритм Флойда-Уоршелла[4][5], сложность [math]O(n^3)[/math] (первый опубликованный алгоритм поиска транзитивного замыкания[6] как раз представляет собой алгоритм Флойда-Уоршелла для графов с единичными весами);
- многократное применение поиска в ширину, сложность [math]O(mn)[/math];
- алгоритм Пурдома[7], сложность [math]O(m + \mu n)[/math].
Обозначения: [math]m[/math] – число рёбер, [math]n[/math] – число вершин, [math]\mu \le m[/math] – число рёбер, соединяющих компоненты сильной связности.
4 Ресурс параллелизма
Задача может быть решена путём алгоритма поиска в ширину для всех вершин графа, при этом вычисления для различных вершин независимы и могут выполняться параллельно.
В связи с квадратичной сложностью выходных данных и вычислений, имеет смысл проводить предварительную обработку данных и использовать различные декомпозиции графа, сводя задачу к параллельному нахождению кратчайших путей на подграфах меньших размеров[8]:
- выделение компонент связности;
- выделение подграфов, связанных только «мостами» (рёбрами, удаление которых нарушает связность графа);
- выделение компонент двусвязности, связанных только «шарнирами» (другие названия – «точки сочленения» и «разделяющие вершины»; вершины, удаление которых нарушает связность графа);
- удаление «висящих» вершин (вершины, имеющие не более одной соседней вершины в графе).
Набор декомпозиций, который целесообразно использовать в конкретном случае, зависит от структуры графа и может быть определён только после её анализа.
5 Ссылки
- ↑ Tarjan, Robert Endre. “Efficiency of a Good but Not Linear Set Union Algorithm.” Journal of the ACM 22, no. 2 (April 1975): 215–25. doi:10.1145/321879.321884.
- ↑ Anderson, Richard J, and Heather Woll. “Wait-Free Parallel Algorithms for the Union-Find Problem,” 370–80, New York, New York, USA: ACM Press, 1991. doi:10.1145/103418.103458.
- ↑ Shiloach, Yossi, and Uzi Vishkin. “An [math]O(\log n)[/math] Parallel Connectivity Algorithm.” Journal of Algorithms 3, no. 1 (March 1982): 57–67. doi:10.1016/0196-6774(82)90008-6.
- ↑ Floyd, Robert W. “Algorithm 97: Shortest Path.” Communications of the ACM 5, no. 6 (June 1, 1962): 345. doi:10.1145/367766.368168.
- ↑ Warshall, Stephen. “A Theorem on Boolean Matrices.” Journal of the ACM 9, no. 1 (January 1, 1962): 11–12. doi:10.1145/321105.321107.
- ↑ Roy, Bernard. “Transitivité Et Connexité.” Comptes Rendus De l'Académie Des Sciences 249 (1959): 216–218.
- ↑ Purdom, Paul, Jr. “A Transitive Closure Algorithm.” Bit 10, no. 1 (March 1970): 76–94. doi:10.1007/BF01940892.
- ↑ Banerjee, Dip Sankar, Ashutosh Kumar, Meher Chaitanya, Shashank Sharma, and Kishore Kothapalli. “Work Efficient Parallel Algorithms for Large Graph Exploration on Emerging Heterogeneous Architectures.” Journal of Parallel and Distributed Computing, December 2014. doi:10.1016/j.jpdc.2014.11.006.
