Определение диаметра графа: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
Daryin (обсуждение | вклад) |
ASA (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
== Свойства и структура | == Свойства и структура алгоритма == | ||
=== Общее описание алгоритма === | === Общее описание алгоритма === | ||
| Строка 6: | Строка 6: | ||
'''Алгоритм ''i''FUB'''<ref>Crescenzi, Pilu, Roberto Grossi, Michel Habib, Leonardo Lanzi, and Andrea Marino. “On Computing the Diameter of Real-World Undirected Graphs.” Theoretical Computer Science 514 (November 2013): 84–95. doi:10.1016/j.tcs.2012.09.018.</ref> (англ. ''iterative'' Fringe Upper Bound) позволяет уменьшить количество вызовов алгоритма поиска в ширину. Для многих реальных графов будет достаточно всего нескольких вызовов и общая сложность будет близка к линейной <math>O(m)</math>. | '''Алгоритм ''i''FUB'''<ref>Crescenzi, Pilu, Roberto Grossi, Michel Habib, Leonardo Lanzi, and Andrea Marino. “On Computing the Diameter of Real-World Undirected Graphs.” Theoretical Computer Science 514 (November 2013): 84–95. doi:10.1016/j.tcs.2012.09.018.</ref> (англ. ''iterative'' Fringe Upper Bound) позволяет уменьшить количество вызовов алгоритма поиска в ширину. Для многих реальных графов будет достаточно всего нескольких вызовов и общая сложность будет близка к линейной <math>O(m)</math>. | ||
=== Математическое описание === | === Математическое описание алгоритма === | ||
=== Вычислительное ядро алгоритма === | === Вычислительное ядро алгоритма === | ||
=== Макроструктура алгоритма === | === Макроструктура алгоритма === | ||
=== | === Схема реализации последовательного алгоритма === | ||
=== Последовательная сложность алгоритма === | === Последовательная сложность алгоритма === | ||
| Строка 15: | Строка 15: | ||
=== Информационный граф === | === Информационный граф === | ||
=== | === Ресурс параллелизма алгоритма === | ||
=== | === Входные и выходные данные алгоритма === | ||
'''Входные данные''': неориентированный граф <math>(V, E)</math> (<math>n</math> вершин <math>v_i</math> и <math>m</math> рёбер). | '''Входные данные''': неориентированный граф <math>(V, E)</math> (<math>n</math> вершин <math>v_i</math> и <math>m</math> рёбер). | ||
| Строка 26: | Строка 26: | ||
'''Объём выходных данных''': <math>O(1)</math>. | '''Объём выходных данных''': <math>O(1)</math>. | ||
=== Свойства алгоритма=== | === Свойства алгоритма === | ||
== Программная реализация | |||
== Программная реализация алгоритма == | |||
=== Особенности реализации последовательного алгоритма === | === Особенности реализации последовательного алгоритма === | ||
=== | === Локальность данных и вычислений === | ||
=== Возможные способы и особенности реализации | ==== Локальность реализации алгоритма ==== | ||
===== Структура обращений в память и качественная оценка локальности ===== | |||
===== Количественная оценка локальности ===== | |||
=== Возможные способы и особенности параллельной реализации алгоритма === | |||
=== Масштабируемость алгоритма и его реализации === | === Масштабируемость алгоритма и его реализации === | ||
==== Масштабируемость алгоритма ==== | |||
==== Масштабируемость реализации алгоритма ==== | |||
=== Динамические характеристики и эффективность реализации алгоритма === | === Динамические характеристики и эффективность реализации алгоритма === | ||
=== Выводы для классов архитектур === | === Выводы для классов архитектур === | ||
| Строка 42: | Строка 48: | ||
<references /> | <references /> | ||
[[Категория:Начатые статьи]] | |||
Версия от 11:12, 29 июля 2015
Свойства и структура алгоритма
Общее описание алгоритма
Диаметром неориентированного графа называется максимальная длина кратчайшего пути между двумя вершинами. Классический способ определения диаметра – выполнить поиск в ширину от всех вершин, тогда диаметр равен максимальному из найденных расстояний. Сложность такого подхода составляет [math]\displaystyle{ O(mn) }[/math], и в худшем случае (например, когда граф является циклом) эту оценку, по-видимому, улучшить нельзя.
Алгоритм iFUB[1] (англ. iterative Fringe Upper Bound) позволяет уменьшить количество вызовов алгоритма поиска в ширину. Для многих реальных графов будет достаточно всего нескольких вызовов и общая сложность будет близка к линейной [math]\displaystyle{ O(m) }[/math].
Математическое описание алгоритма
Вычислительное ядро алгоритма
Макроструктура алгоритма
Схема реализации последовательного алгоритма
Последовательная сложность алгоритма
Последовательная сложность алгоритма iFUB равна [math]\displaystyle{ O(Bm) }[/math], где [math]\displaystyle{ B }[/math] – число вызовов алгоритма поиска в ширину, сложность каждого вызова [math]\displaystyle{ O(m) }[/math]. В худшем случае (граф является циклом) [math]\displaystyle{ B = n }[/math] и общая сложность равна [math]\displaystyle{ O(mn) }[/math], однако для многих реальных графов [math]\displaystyle{ B = O(1) }[/math] и общая сложность составляет [math]\displaystyle{ O(m) }[/math].
Информационный граф
Ресурс параллелизма алгоритма
Входные и выходные данные алгоритма
Входные данные: неориентированный граф [math]\displaystyle{ (V, E) }[/math] ([math]\displaystyle{ n }[/math] вершин [math]\displaystyle{ v_i }[/math] и [math]\displaystyle{ m }[/math] рёбер).
Объём входных данных: [math]\displaystyle{ O(m + n) }[/math].
Выходные данные: диаметр графа [math]\displaystyle{ (V, E) }[/math].
Объём выходных данных: [math]\displaystyle{ O(1) }[/math].
Свойства алгоритма
Программная реализация алгоритма
Особенности реализации последовательного алгоритма
Локальность данных и вычислений
Локальность реализации алгоритма
Структура обращений в память и качественная оценка локальности
Количественная оценка локальности
Возможные способы и особенности параллельной реализации алгоритма
Масштабируемость алгоритма и его реализации
Масштабируемость алгоритма
Масштабируемость реализации алгоритма
Динамические характеристики и эффективность реализации алгоритма
Выводы для классов архитектур
Существующие реализации алгоритма
- Java: WebGraph (класс
FourSweepIterativeFringeDiameter), многопоточная реализация. Алгоритм был использован для вычисления диаметра подграфа социальной сети Facebook (149 миллионов вершин, 16 миллиардов рёбер), время работы составило 20 минут[2]. - Python/C++: NetworKit (класс
networkit.properties.Diameter).
Литература
- ↑ Crescenzi, Pilu, Roberto Grossi, Michel Habib, Leonardo Lanzi, and Andrea Marino. “On Computing the Diameter of Real-World Undirected Graphs.” Theoretical Computer Science 514 (November 2013): 84–95. doi:10.1016/j.tcs.2012.09.018.
- ↑ Backstrom, Lars, Paolo Boldi, Marco Rosa, Johan Ugander, and Sebastiano Vigna. “Four Degrees of Separation,” WebSci'12, 33–42, New York, New York, USA: ACM Press, 2012. doi:10.1145/2380718.2380723.