Поиск транзитивного замыкания орграфа: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
Строка 15: Строка 15:
  
 
В '''ориентированном''' графе транзитивное замыкание может быть сведено к поиску кратчайших путей в графе с единичными весами и найдено следующими алгоритмами:
 
В '''ориентированном''' графе транзитивное замыкание может быть сведено к поиску кратчайших путей в графе с единичными весами и найдено следующими алгоритмами:
* '''[[Алгоритм Флойда-Уоршелла|алгоритм Флойда-Уоршелла]]'''<ref>Floyd, Robert W. “Algorithm 97: Shortest Path.” Communications of the ACM 5, no. 6 (June 1, 1962): 345. doi:10.1145/367766.368168.</ref>, сложность <math>O(n^3)</math> (первый опубликованный алгоритм поиска транзитивного замыкания<ref>Roy, Bernard. “Transitivité Et Connexité.” Comptes Rendus De l'Académie Des Sciences 249 (1959): 216–218.</ref><ref>Warshall, Stephen. “A Theorem on Boolean Matrices.” Journal of the ACM 9, no. 1 (January 1, 1962): 11–12. doi:10.1145/321105.321107.</ref> как раз представляет собой алгоритм Флойда-Уоршелла для графов с единичными весами);
+
* '''[[Алгоритм Флойда-Уоршелла|алгоритм Флойда-Уоршелла]]'''<ref>Floyd, Robert W. “Algorithm 97: Shortest Path.” Communications of the ACM 5, no. 6 (June 1, 1962): 345. doi:10.1145/367766.368168.</ref><ref>Warshall, Stephen. “A Theorem on Boolean Matrices.” Journal of the ACM 9, no. 1 (January 1, 1962): 11–12. doi:10.1145/321105.321107.</ref>, сложность <math>O(n^3)</math> (первый опубликованный алгоритм поиска транзитивного замыкания<ref>Roy, Bernard. “Transitivité Et Connexité.” Comptes Rendus De l'Académie Des Sciences 249 (1959): 216–218.</ref> как раз представляет собой алгоритм Флойда-Уоршелла для графов с единичными весами);
 
* многократное применение '''[[Поиск в ширину (BFS)|поиска в ширину]]''', сложность <math>O(mn)</math>;
 
* многократное применение '''[[Поиск в ширину (BFS)|поиска в ширину]]''', сложность <math>O(mn)</math>;
* '''алгоритм Пурдома'''<ref name=Purdom>Purdom, Paul, Jr. “A Transitive Closure Algorithm.” Bit 10, no. 1 (March 1970): 76–94. doi:10.1007/BF01940892.</ref>, сложность <math>O(mn)</math>.
+
* '''[[алгоритм Пурдома]]'''<ref name=Purdom>Purdom, Paul, Jr. “A Transitive Closure Algorithm.” Bit 10, no. 1 (March 1970): 76–94. doi:10.1007/BF01940892.</ref>, сложность <math>O(\mu n)</math>.
  
Обозначения: <math>m</math> – число рёбер, <math>n</math> – число вершин.
+
Обозначения: <math>m</math> – число рёбер, <math>n</math> – число вершин, <math>\mu \le m</math> – число рёбер, соединяющих [[Связность в графах|компоненты сильной связности]].
  
 
== Ресурс параллелизма ==
 
== Ресурс параллелизма ==

Версия 16:10, 11 июня 2015

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]m[/math] – число рёбер, [math]n[/math] – число вершин, [math]\mu \le m[/math] – число рёбер, соединяющих компоненты сильной связности.

3 Ресурс параллелизма

Задача может быть решена путём алгоритма поиска в ширину для всех вершин графа, при этом вычисления для различных вершин независимы и могут выполняться параллельно.

В связи с квадратичной сложностью выходных данных и вычислений, имеет смысл проводить предварительную обработку данных и использовать различные декомпозиции графа, сводя задачу к параллельному нахождению кратчайших путей на подграфах меньших размеров[8]:

Набор декомпозиций, который целесообразно использовать в конкретном случае, зависит от структуры графа и может быть определён только после её анализа.

4 Существующие реализации

5 Ссылки

  1. 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.
  2. 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.
  3. 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.
  4. Floyd, Robert W. “Algorithm 97: Shortest Path.” Communications of the ACM 5, no. 6 (June 1, 1962): 345. doi:10.1145/367766.368168.
  5. Warshall, Stephen. “A Theorem on Boolean Matrices.” Journal of the ACM 9, no. 1 (January 1, 1962): 11–12. doi:10.1145/321105.321107.
  6. Roy, Bernard. “Transitivité Et Connexité.” Comptes Rendus De l'Académie Des Sciences 249 (1959): 216–218.
  7. 7,0 7,1 Purdom, Paul, Jr. “A Transitive Closure Algorithm.” Bit 10, no. 1 (March 1970): 76–94. doi:10.1007/BF01940892.
  8. 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.