Просмотр кода страницы Алгоритм Фрюхтермана-Рейнгольда

Алгоритм Фрюхтермана-Рейнгольда ([[Fruchterman T. M. J.|Fruchterman T. M. J.]]-[[Reingold E. M.|Reingold E. M.]])) относится к семейству [[силовые алгоритмы | силовых алгоритмов (forced-directed)]] [[Укладка графа|укладки графов]] на плоскости, в котором используется пружинная физическая модель, где [[Вершина|вершины]] определяются как тела системы, а [[Ребро|ребра]] как пружины. Силы могут действовать только на [[Вершина|вершины]], вес пружин при этом не учитывается.
= Постановка задачи =

Имеется простой неориентированный граф <math>G = (V, E)</math>. У каждой [[Вершина|вершины]] из множества <math>V</math> в качестве переменных используются координаты ее размещения <math>V_x</math> и <math>V_y</math>, а также <math>V_f</math> - вектор силы, направленный на приведение физической системы в равновесие. Необходимо применить физическую модель и минимизировать энергию системы, меняя расположение вершин. Результатом [[алгоритм|алгоритма]] будет наглядное [[изображение графа]] на плоскости.

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

# Вершины графа помещаются в случайные координаты
# Рассчитываются силы, действующие на вершины
# Происходит перемещение вершин, проверяется выход за границу экрана
# Повторяются шаги 2-3

[[Алгоритм]] не имеет механизма остановки, а значит пользователь сам решает, когда закончить работу алгоритма. Обычно при реализации ограничивают количество итераций. Для достижения хорошего результата 100 итераций достаточно.

= Описание модели =

<math> l = \sqrt{area/|V|} </math> - Идеальная длина пружины для ребра <math>e</math>

<math>p_v = (x_v, y_v)</math> - Вектор положения вершины <math>v</math>

<math> ||p_v - p_u || </math> - Евклидовое расстояние между вершинами <math>u</math> и <math>v</math>

<math> (p_u, p_v) </math> - Направленный вектор из вершины <math>u</math> в <math>v</math>

Для всех вершин действует сила отталкивания

<math> f_{spring} = \frac{{||p_u-p_v||}^2}{l} \overrightarrow{p_v p_u} </math>

Для всех смежных вершин действует сила притяжения

<math> f_{rep} = \frac{l^2}{||p_u-p_v||} \overrightarrow{p_u p_v} </math>

= Свойства =

# Алгоритм применяется для размещения простых [[Неориентированный_граф | неориентированных графов]] и хорошо работает для [[граф|графов]] с количеством вершин не превышающих 100
# Алгоритм не останавливается, в графе циклически повторяется размещение наименее [[Связные_вершины|связных вершин]], что можно видеть на демонстрации (проблема решается с помощью добавления модификации температуры) 

= Модификации =

Количество итераций алгоритма не ограничено, и в определенный момент система начинает колебаться. Этот процесс циклически повторяет несколько размещений и для приведение системы в состояние покоя было введено понятие температуры.

Начиная с некоторого начального значения, температура убывает до нуля. Значение температуры влияет на скорость движения вершин и останавливает выполнения алгоритма при достижении нулевого значения. По мере того, как улучшается размещение, изменения позиций вершин уменьшаются. Если вектор смещения выталкивает вершину за эту границу, соответствующая координата вектора смещений обрезается (вершина просто прилипает к границе).

= Демонстрация =

[[Файл:7 tree FR.mp4]]
[[Файл:15 tree FR.mp4]]

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

# Fruchterman T. M. J., Reingold E. M., Graph Drawing by Force-Directed Placement. Software -Practice and Experience, 1991, 21(11), 1129-1164.

[[Категория:Визуализация графов]]