Алгоритм Фрюхтермана-Рейнгольда: различия между версиями
Omeln (обсуждение | вклад) |
Omeln (обсуждение | вклад) мНет описания правки |
||
| Строка 1: | Строка 1: | ||
Алгоритм Фрюхтермана-Рейнгольда ([[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> - вектор силы, направленный на приведение физической системы в равновесие. Необходимо применить физическую модель и минимизировать энергию системы. Результатом [[алгоритм|алгоритма]] будет [[Layout|размещение графа (layout)]]. | |||
= Описание алгоритма = | = Описание алгоритма = | ||
| Строка 12: | Строка 11: | ||
# Повторяются шаги 2-3 | # Повторяются шаги 2-3 | ||
Алгоритм не имеет механизма остановки, а значит пользователь сам решает, когда закончить работу алгоритма. Обычно при реализации ограничивают количество итераций. Для достижения хорошего результата 100 итераций достаточно. | [[Алгоритм]] не имеет механизма остановки, а значит пользователь сам решает, когда закончить работу алгоритма. Обычно при реализации ограничивают количество итераций. Для достижения хорошего результата 100 итераций достаточно. | ||
= Описание модели = | = Описание модели = | ||
| Строка 34: | Строка 33: | ||
= Применение = | = Применение = | ||
Алгоритм применяется для размещения простых неориентированных графов и хорошо работает для графов с количеством вершин не превышающих 100. | Алгоритм применяется для размещения простых [[Неориентированный_граф | неориентированных графов]] и хорошо работает для [[граф|графов]] с количеством вершин не превышающих 100. | ||
= Модификации = | |||
Количество итераций алгоритма не ограничено, и в определенный момент система начинает колебаться. Этот процесс циклически повторяет несколько размещений и для приведение системы в состояние покоя было введено понятие температуры. | Количество итераций алгоритма не ограничено, и в определенный момент система начинает колебаться. Этот процесс циклически повторяет несколько размещений и для приведение системы в состояние покоя было введено понятие температуры. | ||
Версия от 12:21, 10 октября 2019
Алгоритм Фрюхтермана-Рейнгольда (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] - вектор силы, направленный на приведение физической системы в равновесие. Необходимо применить физическую модель и минимизировать энергию системы. Результатом алгоритма будет размещение графа (layout).
Описание алгоритма
- Вершины графа помещаются в случайные координаты
- Рассчитываются силы, действующие на вершины
- Происходит перемещение вершин, проверяется выход за границу экрана
- Повторяются шаги 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]
Применение
Алгоритм применяется для размещения простых неориентированных графов и хорошо работает для графов с количеством вершин не превышающих 100.
Модификации
Количество итераций алгоритма не ограничено, и в определенный момент система начинает колебаться. Этот процесс циклически повторяет несколько размещений и для приведение системы в состояние покоя было введено понятие температуры.
Начиная с некоторого начального значения, температура убывает до нуля. Значение температуры влияет на скорость движения вершин и останавливает выполнения алгоритма при достижении нулевого значения. По мере того, как улучшается размещение, изменения позиций вершин уменьшаются. Если вектор смещения выталкивает вершину за эту границу, соответствующая координата вектора смещений обрезается (вершина просто прилипает к границе).
Демонстрация
Литература
- Fruchterman T. M. J., Reingold E. M., Graph Drawing by Force-Directed Placement. Software -Practice and Experience, 1991, 21(11), 1129-1164.