Поиск транзитивного замыкания орграфа
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]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], сложность [math]O(n^3)[/math] (первый опубликованный алгоритм поиска транзитивного замыкания[5][6] как раз представляет собой алгоритм Флойда-Уоршелла для графов с единичными весами);
- многократное применение 'Поиск в ширину (BFS), сложность [math]O(mn)[/math].
Обозначения: [math]m[/math] – число рёбер, [math]n[/math] – число вершин.
3 Ресурс параллелизма
Задача может быть решена путём алгоритма поиска в ширину для всех вершин графа, при этом вычисления для различных вершин независимы и могут выполняться параллельно.
В связи с квадратичной сложностью выходных данных и вычислений, имеет смысл проводить предварительную обработку данных и использовать различные декомпозиции графа, сводя задачу к параллельному нахождению кратчайших путей на подграфах меньших размеров[7]:
- выделение компонент связности;
- выделение подграфов, связанных только «мостами» (рёбрами, удаление которых нарушает связность графа);
- выделение компонент двусвязности, связанных только «шарнирами» (другие названия – «точки сочленения» и «разделяющие вершины»; вершины, удаление которых нарушает связность графа);
- удаление «висящих» вершин (вершины, имеющие не более одной соседней вершины в графе).
Набор декомпозиций, который целесообразно использовать в конкретном случае, зависит от структуры графа и может быть определён только после её анализа.
4 Ссылки
- ↑ 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.
- ↑ Roy, Bernard. “Transitivité Et Connexité.” Comptes Rendus De l'Académie Des Sciences 249 (1959): 216–218.
- ↑ Warshall, Stephen. “A Theorem on Boolean Matrices.” Journal of the ACM 9, no. 1 (January 1, 1962): 11–12. doi:10.1145/321105.321107.
- ↑ 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.
