Алгоритм Тарьяна поиска компонент двусвязности - История изменений

ASA в 12:38, 6 июля 2022

2022-07-06T12:38:42Z

← Предыдущая версия		Версия от 12:38, 6 июля 2022
Строка 59:		Строка 59:
	== Программная реализация алгоритма ==		== Программная реализация алгоритма ==
	=== Особенности реализации последовательного алгоритма ===		=== Особенности реализации последовательного алгоритма ===
	~~=== Локальность данных и вычислений ===~~
	~~==== Локальность реализации алгоритма ====~~
	~~===== Структура обращений в память и качественная оценка локальности =====~~
	~~===== Количественная оценка локальности =====~~
	=== Возможные способы и особенности параллельной реализации алгоритма ===		=== Возможные способы и особенности параллельной реализации алгоритма ===
	=== ~~Масштабируемость алгоритма и его реализации ===~~		=== Результаты прогонов ===
	~~==== Масштабируемость алгоритма ====~~
	~~==== Масштабируемость реализации алгоритма ====~~
	~~=== Динамические характеристики и эффективность реализации алгоритма~~ ===
	=== Выводы для классов архитектур ===		=== Выводы для классов архитектур ===
	~~=== Существующие реализации алгоритма ===~~

	* C++: [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph/doc/biconnected_components.html biconnected_components]</code>).
	* Python: [https://networkx.github.io NetworkX] (функция <code>[http://networkx.github.io/documentation/networkx-1.9.1/reference/generated/networkx.algorithms.components.biconnected.biconnected_components.html biconnected_components]</code>).
	* Java: [http://jgrapht.org JGraphT] (класс <code>[http://jgrapht.org/javadoc/org/jgrapht/alg/BiconnectivityInspector.html BiconnectivityInspector]</code>).

	== Литература ==		== Литература ==

ASA в 13:57, 14 марта 2018

2018-03-14T13:57:28Z

← Предыдущая версия		Версия от 13:57, 14 марта 2018
Строка 80:		Строка 80:

	[[Категория:Начатые статьи]]		[[Категория:Начатые статьи]]

			[[en:Tarjan's biconnected components algorithm]]

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

2018-03-06T14:15:26Z

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

	== Свойства и структура алгоритма ==		== Свойства и структура алгоритма ==
	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===

Teplov: /* Схема реализации последовательного алгоритма */

2016-11-18T15:39:03Z

Схема реализации последовательного алгоритма

@@ Строка 10: / Строка 10: @@
 === Макроструктура алгоритма ===
 === Схема реализации последовательного алгоритма ===
 === Последовательная сложность алгоритма ===

Teplov: /* Общее описание алгоритма */

2016-11-18T15:37:21Z

Общее описание алгоритма

← Предыдущая версия		Версия от 15:37, 18 ноября 2016
Строка 3:		Строка 3:

	'''Алгоритм Тарьяна'''<ref>Tarjan, Robert. “Depth-First Search and Linear Graph Algorithms.” SIAM Journal on Computing 1, no. 2 (1972): 146–60.</ref> находит [[Связность в графах\|компоненты двусвязности]] и шарниры неориентированного графа в процессе [[Поиск в глубину (DFS)\|поиска в глубину]] за время <math>O(m)</math>.		'''Алгоритм Тарьяна'''<ref>Tarjan, Robert. “Depth-First Search and Linear Graph Algorithms.” SIAM Journal on Computing 1, no. 2 (1972): 146–60.</ref> находит [[Связность в графах\|компоненты двусвязности]] и шарниры неориентированного графа в процессе [[Поиск в глубину (DFS)\|поиска в глубину]] за время <math>O(m)</math>.

			Процесс поиска в глубину является существенно последовательным (inherently sequential) и практически не параллелизуется. Вместе с тем, алгоритм Тарьяна по-видимому является максимально возможно эффективным последовательным алгоритмом (каждое ребро посещается ровно один раз). Как следствие этого, производительность этого последовательного алгоритма на практике часто не уступает производительности последовательных алгоритмов, вынужденных исполнять большее число операций, чем в алгоритме Тарьяна.

	=== Математическое описание алгоритма ===		=== Математическое описание алгоритма ===

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

2015-07-29T11:26:18Z

← Предыдущая версия		Версия от 11:26, 29 июля 2015
Строка 1:		Строка 1:
	== Свойства и структура ~~алгоритмов~~ ==		== Свойства и структура алгоритма ==
	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===

	'''Алгоритм Тарьяна'''<ref>Tarjan, Robert. “Depth-First Search and Linear Graph Algorithms.” SIAM Journal on Computing 1, no. 2 (1972): 146–60.</ref> находит [[Связность в графах\|компоненты двусвязности]] и шарниры неориентированного графа в процессе [[Поиск в глубину (DFS)\|поиска в глубину]] за время <math>O(m)</math>.		'''Алгоритм Тарьяна'''<ref>Tarjan, Robert. “Depth-First Search and Linear Graph Algorithms.” SIAM Journal on Computing 1, no. 2 (1972): 146–60.</ref> находит [[Связность в графах\|компоненты двусвязности]] и шарниры неориентированного графа в процессе [[Поиск в глубину (DFS)\|поиска в глубину]] за время <math>O(m)</math>.

	=== Математическое описание ===		=== Математическое описание алгоритма ===
	=== Вычислительное ядро алгоритма ===		=== Вычислительное ядро алгоритма ===
	=== Макроструктура алгоритма ===		=== Макроструктура алгоритма ===
	=== ~~Описание схемы~~ реализации последовательного алгоритма ===		=== Схема реализации последовательного алгоритма ===
	=== Последовательная сложность алгоритма ===		=== Последовательная сложность алгоритма ===

Строка 13:		Строка 13:

	=== Информационный граф ===		=== Информационный граф ===
	=== ~~Описание ресурса~~ параллелизма алгоритма ===		=== Ресурс параллелизма алгоритма ===

	Возможности параллелизации алгоритма Тарьяна сильно ограничены, поскольку он основан на [[Поиск в глубину (DFS)\|поиске в глубину]]. Параллельный [[Алгоритм Тарьяна-Вишкина поиска компонент двусвязности\|алгоритмом Тарьяна-Вишкина]]<ref>Tarjan, Robert Endre, and Uzi Vishkin. “An Efficient Parallel Biconnectivity Algorithm.” SIAM Journal on Computing 14, no. 4 (1985): 862–74.</ref> основан на тех же свойствах графа и может использовать любое остовное дерево.		Возможности параллелизации алгоритма Тарьяна сильно ограничены, поскольку он основан на [[Поиск в глубину (DFS)\|поиске в глубину]]. Параллельный [[Алгоритм Тарьяна-Вишкина поиска компонент двусвязности\|алгоритмом Тарьяна-Вишкина]]<ref>Tarjan, Robert Endre, and Uzi Vishkin. “An Efficient Parallel Biconnectivity Algorithm.” SIAM Journal on Computing 14, no. 4 (1985): 862–74.</ref> основан на тех же свойствах графа и может использовать любое остовное дерево.

	=== ~~Описание входных~~ и ~~выходных данных~~ ===		=== Входные и выходные данные алгоритма ===
	=== Свойства алгоритма===		=== Свойства алгоритма ===
	== Программная реализация ~~алгоритмов~~ ==
			== Программная реализация алгоритма ==
	=== Особенности реализации последовательного алгоритма ===		=== Особенности реализации последовательного алгоритма ===
	=== ~~Описание локальности~~ данных и вычислений ===		=== Локальность данных и вычислений ===
	=== Возможные способы и особенности реализации ~~параллельного~~ алгоритма ===		==== Локальность реализации алгоритма ====
			===== Структура обращений в память и качественная оценка локальности =====
			===== Количественная оценка локальности =====
			=== Возможные способы и особенности параллельной реализации алгоритма ===
	=== Масштабируемость алгоритма и его реализации ===		=== Масштабируемость алгоритма и его реализации ===
			==== Масштабируемость алгоритма ====
			==== Масштабируемость реализации алгоритма ====
	=== Динамические характеристики и эффективность реализации алгоритма ===		=== Динамические характеристики и эффективность реализации алгоритма ===
	=== Выводы для классов архитектур ===		=== Выводы для классов архитектур ===
Строка 35:		Строка 41:

	<references />		<references />

			[[Категория:Начатые статьи]]

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

2015-06-11T19:37:59Z

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

← Предыдущая версия		Версия от 19:37, 11 июня 2015
Строка 30:		Строка 30:
	* C++: [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph/doc/biconnected_components.html biconnected_components]</code>).		* C++: [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph/doc/biconnected_components.html biconnected_components]</code>).
	* Python: [https://networkx.github.io NetworkX] (функция <code>[http://networkx.github.io/documentation/networkx-1.9.1/reference/generated/networkx.algorithms.components.biconnected.biconnected_components.html biconnected_components]</code>).		* Python: [https://networkx.github.io NetworkX] (функция <code>[http://networkx.github.io/documentation/networkx-1.9.1/reference/generated/networkx.algorithms.components.biconnected.biconnected_components.html biconnected_components]</code>).
			* Java: [http://jgrapht.org JGraphT] (класс <code>[http://jgrapht.org/javadoc/org/jgrapht/alg/BiconnectivityInspector.html BiconnectivityInspector]</code>).

	== Литература ==		== Литература ==

	<references />		<references />

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

2015-06-11T18:19:45Z

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

← Предыдущая версия		Версия от 18:19, 11 июня 2015
Строка 28:		Строка 28:
	=== Существующие реализации алгоритма ===		=== Существующие реализации алгоритма ===

	* [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph/doc/biconnected_components.html biconnected_components]</code>).		* C++: [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph/doc/biconnected_components.html biconnected_components]</code>).
			* Python: [https://networkx.github.io NetworkX] (функция <code>[http://networkx.github.io/documentation/networkx-1.9.1/reference/generated/networkx.algorithms.components.biconnected.biconnected_components.html biconnected_components]</code>).

	== Литература ==		== Литература ==

	<references />		<references />

Daryin: /* Общее описание алгоритма */

2015-06-10T23:12:34Z

Общее описание алгоритма

← Предыдущая версия		Версия от 23:12, 10 июня 2015
Строка 2:		Строка 2:
	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===

	'''Алгоритм Тарьяна'''<ref>Tarjan, Robert. “Depth-First Search and Linear Graph Algorithms.” SIAM Journal on Computing 1, no. 2 (1972): 146–60.</ref> находит [[Связность в графах\|компоненты двусвязности]] неориентированного графа в процессе [[Поиск в глубину (DFS)\|поиска в глубину]]) за время <math>O(m)</math>.		'''Алгоритм Тарьяна'''<ref>Tarjan, Robert. “Depth-First Search and Linear Graph Algorithms.” SIAM Journal on Computing 1, no. 2 (1972): 146–60.</ref> находит [[Связность в графах\|компоненты двусвязности]] и шарниры неориентированного графа в процессе [[Поиск в глубину (DFS)\|поиска в глубину]] за время <math>O(m)</math>.

	=== Математическое описание ===		=== Математическое описание ===

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

2015-06-10T23:11:24Z

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

← Предыдущая версия		Версия от 23:11, 10 июня 2015
Строка 27:		Строка 27:
	=== Выводы для классов архитектур ===		=== Выводы для классов архитектур ===
	=== Существующие реализации алгоритма ===		=== Существующие реализации алгоритма ===

			* [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph/doc/biconnected_components.html biconnected_components]</code>).

	== Литература ==		== Литература ==

	<references />		<references />