Алгоритм Фрюхтермана-Рейнгольда: различия между версиями
Omeln (обсуждение | вклад) мНет описания правки |
Omeln (обсуждение | вклад) |
||
| (не показано 5 промежуточных версий 2 участников) | |||
| Строка 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> - вектор силы, направленный на приведение физической системы в равновесие. Необходимо применить физическую модель и минимизировать энергию системы, меняя расположение вершин. Результатом [[алгоритм|алгоритма]] будет наглядное [[изображение графа]] на плоскости. | |||
= Описание алгоритма = | = Описание алгоритма = | ||
| Строка 12: | Строка 11: | ||
# Повторяются шаги 2-3 | # Повторяются шаги 2-3 | ||
Алгоритм не имеет механизма остановки, а значит пользователь сам решает, когда закончить работу алгоритма. Обычно при реализации ограничивают количество итераций. Для достижения хорошего результата 100 итераций достаточно. | [[Алгоритм]] не имеет механизма остановки, а значит пользователь сам решает, когда закончить работу алгоритма. Обычно при реализации ограничивают количество итераций. Для достижения хорошего результата 100 итераций достаточно. | ||
= Описание модели = | = Описание модели = | ||
| Строка 32: | Строка 31: | ||
<math> f_{rep} = \frac{l^2}{||p_u-p_v||} \overrightarrow{p_u p_v} </math> | <math> f_{rep} = \frac{l^2}{||p_u-p_v||} \overrightarrow{p_u p_v} </math> | ||
= | = Свойства = | ||
# Алгоритм применяется для размещения простых [[Неориентированный_граф | неориентированных графов]] и хорошо работает для [[граф|графов]] с количеством вершин не превышающих 100 | |||
# Алгоритм не останавливается, в графе циклически повторяется размещение наименее [[Связные_вершины|связных вершин]], что можно видеть на демонстрации (проблема решается с помощью добавления модификации температуры) | |||
= Модификации = | |||
Количество итераций алгоритма не ограничено, и в определенный момент система начинает колебаться. Этот процесс циклически повторяет несколько размещений и для приведение системы в состояние покоя было введено понятие температуры. | Количество итераций алгоритма не ограничено, и в определенный момент система начинает колебаться. Этот процесс циклически повторяет несколько размещений и для приведение системы в состояние покоя было введено понятие температуры. | ||
| Строка 46: | Строка 44: | ||
= Демонстрация = | = Демонстрация = | ||
[[Файл: | [[Файл: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. | # Fruchterman T. M. J., Reingold E. M., Graph Drawing by Force-Directed Placement. Software -Practice and Experience, 1991, 21(11), 1129-1164. | ||
[[Категория:Визуализация графов]] | |||
Текущая версия от 14:19, 17 октября 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] - вектор силы, направленный на приведение физической системы в равновесие. Необходимо применить физическую модель и минимизировать энергию системы, меняя расположение вершин. Результатом алгоритма будет наглядное изображение графа на плоскости.
Описание алгоритма
- Вершины графа помещаются в случайные координаты
- Рассчитываются силы, действующие на вершины
- Происходит перемещение вершин, проверяется выход за границу экрана
- Повторяются шаги 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.