Алгоритм Фрюхтермана-Рейнгольда

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

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

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

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

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

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

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

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

[math]\displaystyle{ p_v = (x_v, y_v) }[/math] - Вектор положения вершины [math]\displaystyle{ v }[/math]

[math]\displaystyle{ ||p_v - p_u || }[/math] - Евклидовое расстояние между вершинами [math]\displaystyle{ u }[/math] и [math]\displaystyle{ v }[/math]

[math]\displaystyle{ (p_u, p_v) }[/math] - Направленный вектор из вершины [math]\displaystyle{ u }[/math] в [math]\displaystyle{ v }[/math]

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

[math]\displaystyle{ f_{spring} = \frac{{||p_u-p_v||}^2}{l} \overrightarrow{p_v p_u} }[/math]

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

[math]\displaystyle{ f_{rep} = \frac{l^2}{||p_u-p_v||} \overrightarrow{p_u p_v} }[/math]

Свойства

1. Алгоритм применяется для размещения простых неориентированных графов и хорошо работает для графов с количеством вершин не превышающих 100
2. Алгоритм не останавливается, в графе циклически повторяется размещение наименее связных вершин, что можно видеть на демонстрации (проблема решается с помощью добавления модификации температуры)

Модификации

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

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

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

Литература

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