Алгоритм Тарьяна-Вишкина поиска компонент двусвязности: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
Строка 30: Строка 30:
 
=== Входные и выходные данные алгоритма ===
 
=== Входные и выходные данные алгоритма ===
 
=== Свойства алгоритма ===
 
=== Свойства алгоритма ===
 +
1. Компонента сильной связности – подграф, любые две вершины которого принадлежат какому-либо циклу, и содержащий все такие циклы для своих вершин.
 +
 +
2. Компонента сильной связности является объединением всех циклом, проходящих через её вершины.
  
 
== Программная реализация алгоритма ==
 
== Программная реализация алгоритма ==

Версия 16:59, 18 ноября 2016

Содержание

1 Свойства и структура алгоритма

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

Параллельный алгоритм Тарьяна-Вишкина [1] находит компоненты двухсвязности неориентированного графа за время [math]O(\ln n)[/math] на [math]O(m + n)[/math] процессорах. Алгоритм может быть адаптирован для поиска мостов. Эффективность алгоритма Тарьяна-Вишкина подтверждена в последнее время[2][3] как на системах архитектуры SMP, так и при вычислениях на GPU.

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

В задаче поиска компонент сильной связности требуется разбить вершины ориентированного графа на непересекающиеся группы (компоненты), так что в каждой компоненты все вершины достижимы друг из друга по рёбрам графа (с учётом направления).

Пусть задан ориентированный граф [math]G=(V,E)[/math] с вершинами [math]V= (v_1,v_2,...,v_n)[/math] и рёбрами [math]E=(e_1,e_2,...,e_m)[/math].

Путём между вершинами [math]u[/math] и [math]v[/math] называется последовательность рёбер [math]\pi_{uv}=(e_1,...,e_k)[/math], начинающаяся в вершине [math]u[/math] и заканчивающаяся в вершине [math]v[/math], так что началом каждого следующего ребра служит конец предыдущего.

Если существует такой путь [math]\pi_{uv}[/math], то вершина [math]v[/math] достижима из вершины [math]u[/math]. Считается, что от вершины [math]u[/math] к самой себе ведёт пустой путь [math]\pi_{uu}[/math], то есть каждая вершина достижима из самой себя. Непустой путь [math]\pi_{uu}[/math] называется циклом (замкнутым обходом).

Ориентированный граф называется сильно связным, если всякая его вершина [math]v[/math] достижима из любой другой его вершины [math]u[/math]. Компонентой сильной связности ориентированного графа называется любой максимальный по включению сильно связный подграф.

1.3 Вычислительное ядро алгоритма

1.4 Макроструктура алгоритма

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

1.6 Последовательная сложность алгоритма

Последовательный вариант алгоритма аналогичен алгоритму Тарьяна[4] и имеет линейную сложность [math]O(m + n)[/math].

1.7 Информационный граф

1.8 Ресурс параллелизма алгоритма

Алгоритм изначально параллельный, время работы [math]O(\ln n)[/math] на [math]O(m + n)[/math] процессорах.

1.9 Входные и выходные данные алгоритма

1.10 Свойства алгоритма

1. Компонента сильной связности – подграф, любые две вершины которого принадлежат какому-либо циклу, и содержащий все такие циклы для своих вершин.

2. Компонента сильной связности является объединением всех циклом, проходящих через её вершины.

2 Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

2.2 Локальность данных и вычислений

2.2.1 Локальность реализации алгоритма

2.2.1.1 Структура обращений в память и качественная оценка локальности
2.2.1.2 Количественная оценка локальности

2.3 Возможные способы и особенности параллельной реализации алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.4.1 Масштабируемость алгоритма

2.4.2 Масштабируемость реализации алгоритма

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

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

3 Литература

  1. ↑ Tarjan, Robert Endre, and Uzi Vishkin. “An Efficient Parallel Biconnectivity Algorithm.” SIAM Journal on Computing 14, no. 4 (1985): 862–74.
  2. ↑ Edwards, James A, and Uzi Vishkin. “Better Speedups Using Simpler Parallel Programming for Graph Connectivity and Biconnectivity,” PMAM’12, 103–114, New York, USA: ACM Press, 2012. doi:10.1145/2141702.2141714
  3. ↑ Guojing Cong, and David A Bader. “An Experimental Study of Parallel Biconnected Components Algorithms on Symmetric Multiprocessors (SMPs),” 45b, IEEE, 2005. doi:10.1109/IPDPS.2005.100.
  4. ↑ Tarjan, Robert. “Depth-First Search and Linear Graph Algorithms.” SIAM Journal on Computing 1, no. 2 (1972): 146–60.
Источник — https://algowiki-project.org/w/ru/index.php?title=Алгоритм_Тарьяна-Вишкина_поиска_компонент_двусвязности&oldid=18157