Поиск транзитивного замыкания орграфа - История изменений

ASA в 14:01, 6 марта 2018

2018-03-06T14:01:57Z

← Предыдущая версия		Версия от 14:01, 6 марта 2018
Строка 1:		Строка 1:
			{{level-p}}

	== Постановка задачи ==		== Постановка задачи ==

ASA в 11:09, 29 июля 2015

2015-07-29T11:09:25Z

← Предыдущая версия		Версия от 11:09, 29 июля 2015
Строка 44:		Строка 44:

	<references />		<references />

			[[Категория:Статьи в работе]]

Daryin: /* Алгоритмы решения задачи */

2015-06-14T10:35:25Z

Алгоритмы решения задачи

← Предыдущая версия		Версия от 10:35, 14 июня 2015
Строка 25:		Строка 25:
	* '''[[Алгоритм Флойда-Уоршелла\|алгоритм Флойда-Уоршелла]]'''<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> как раз представляет собой алгоритм Флойда-Уоршелла для графов с единичными весами);		* '''[[Алгоритм Флойда-Уоршелла\|алгоритм Флойда-Уоршелла]]'''<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(\mu n)</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(m + \mu n)</math>.

	Обозначения: <math>m</math> – число рёбер, <math>n</math> – число вершин, <math>\mu \le m</math> – число рёбер, соединяющих [[Связность в графах\|компоненты сильной связности]].		Обозначения: <math>m</math> – число рёбер, <math>n</math> – число вершин, <math>\mu \le m</math> – число рёбер, соединяющих [[Связность в графах\|компоненты сильной связности]].

Daryin в 14:33, 11 июня 2015

2015-06-11T14:33:27Z

← Предыдущая версия		Версия от 14:33, 11 июня 2015
Строка 40:		Строка 40:

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

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

	* [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph/doc/transitive_closure.html transitive_closure]</code>): алгоритм Пурдома<ref name=Purdom />, сложность <math>O(mn)</math>.

	== Ссылки ==		== Ссылки ==

	<references />		<references />

Daryin: Свойства задачи

2015-06-11T14:24:48Z

Свойства задачи

← Предыдущая версия		Версия от 14:24, 11 июня 2015
Строка 6:		Строка 6:

	Эквивалентная формулировка: для данного рефлексивного бинарного отношения <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> будет отношением эквивалентности и тогда достаточно найти его классы эквивалентности.		Эквивалентная формулировка: для данного рефлексивного бинарного отношения <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> будет отношением эквивалентности и тогда достаточно найти его классы эквивалентности.

			== Свойства задачи ==

			Если вершины <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> имеют одни и те же компоненты сильной связности (в терминах вершин).

	== Алгоритмы решения задачи ==		== Алгоритмы решения задачи ==

Daryin: /* Алгоритмы решения задачи */

2015-06-11T13:10:55Z

Алгоритмы решения задачи

← Предыдущая версия		Версия от 13:10, 11 июня 2015
Строка 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> – число рёбер, соединяющих [[Связность в графах\|компоненты сильной связности]].

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

Daryin: /* Алгоритмы решения задачи */

2015-06-10T21:45:14Z

Алгоритмы решения задачи

← Предыдущая версия		Версия от 21:45, 10 июня 2015
Строка 16:		Строка 16:
	В '''ориентированном''' графе транзитивное замыкание может быть сведено к поиску кратчайших путей в графе с единичными весами и найдено следующими алгоритмами:		В '''ориентированном''' графе транзитивное замыкание может быть сведено к поиску кратчайших путей в графе с единичными весами и найдено следующими алгоритмами:
	* '''[[Алгоритм Флойда-Уоршелла\|алгоритм Флойда-Уоршелла]]'''<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>, сложность <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> как раз представляет собой алгоритм Флойда-Уоршелла для графов с единичными весами);
	* многократное применение ''''[[Поиск в ширину (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(mn)</math>.

Daryin: /* Существующие реализации */

2015-06-10T21:44:03Z

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

← Предыдущая версия		Версия от 21:44, 10 июня 2015
Строка 32:		Строка 32:

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

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

			* [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph/doc/transitive_closure.html transitive_closure]</code>): алгоритм Пурдома<ref name=Purdom />, сложность <math>O(mn)</math>.

	== Ссылки ==		== Ссылки ==

	<references />		<references />

Daryin: /* Алгоритмы решения задачи */

2015-06-10T21:43:19Z

Алгоритмы решения задачи

← Предыдущая версия		Версия от 21:43, 10 июня 2015
Строка 16:		Строка 16:
	В '''ориентированном''' графе транзитивное замыкание может быть сведено к поиску кратчайших путей в графе с единичными весами и найдено следующими алгоритмами:		В '''ориентированном''' графе транзитивное замыкание может быть сведено к поиску кратчайших путей в графе с единичными весами и найдено следующими алгоритмами:
	* '''[[Алгоритм Флойда-Уоршелла\|алгоритм Флойда-Уоршелла]]'''<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>, сложность <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> как раз представляет собой алгоритм Флойда-Уоршелла для графов с единичными весами);
	* многократное применение ''''[[Поиск в ширину (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>.

	Обозначения: <math>m</math> – число рёбер, <math>n</math> – число вершин.		Обозначения: <math>m</math> – число рёбер, <math>n</math> – число вершин.

Daryin: Описание задачи

2015-06-09T20:35:09Z

Описание задачи

Новая страница

== Постановка задачи ==

Пусть задан ориентированный граф <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> будет отношением эквивалентности и тогда достаточно найти его классы эквивалентности.

== Алгоритмы решения задачи ==

В '''неориентированном''' графе вершина <math>w</math> достижима из вершины <math>v</math> тогда и только тогда, когда они обе принадлежат одной и той же компоненте связности. Транзитивное замыкание сводится к поиску [[Связность в графах|компонент связности]] графа и может быть найдено следующими алгоритмами:
* последовательным применением алгоритма [[Поиск в ширину (BFS)|поиска в ширину]] за время <math>O(m)</math>;
* с помощью [[Система непересекающихся множеств|системы непересекающихся множеств]]<ref>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.</ref> за время <math>O(m \alpha(m, n))</math>, с возможностью эффективной многопоточной реализации<ref>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.</ref>;
* параллельным алгоритмом [[Алгоритм Шилоаха-Вишкина поиска компонент связности|Шилоаха-Вишкина]]<ref>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.</ref> за время <math>O(\ln n)</math> на <math>n + 2m</math> процессорах.

В '''ориентированном''' графе транзитивное замыкание может быть сведено к поиску кратчайших путей в графе с единичными весами и найдено следующими алгоритмами:
* '''[[Алгоритм Флойда-Уоршелла|алгоритм Флойда-Уоршелла]]'''<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> как раз представляет собой алгоритм Флойда-Уоршелла для графов с единичными весами);
* многократное применение ''''[[Поиск в ширину (BFS)]]''', сложность <math>O(mn)</math>.

Обозначения: <math>m</math> – число рёбер, <math>n</math> – число вершин.

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

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

В связи с квадратичной сложностью выходных данных и вычислений, имеет смысл проводить предварительную обработку данных и использовать различные декомпозиции графа, сводя задачу к параллельному нахождению кратчайших путей на подграфах меньших размеров<ref>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.</ref>:
* [[Алгоритм Шилоаха-Вишкина поиска компонент связности|выделение компонент связности]];
* [[Алгоритм Тарьяна поиска «мостов» в графе|выделение подграфов, связанных только «мостами»]] (рёбрами, удаление которых нарушает связность графа);
* [[Алгоритм Тарьяна поиска компонент двусвязности|выделение компонент двусвязности]], связанных только «шарнирами» (другие названия – «точки сочленения» и «разделяющие вершины»; вершины, удаление которых нарушает связность графа);
* удаление «висящих» вершин (вершины, имеющие не более одной соседней вершины в графе).

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

== Ссылки ==

<references />