20
правок
Алгоритм Фрюхтермана-Рейнгольда: различия между версиями
Материал из WEGA
Алгоритм Фрюхтермана-Рейнгольда (посмотреть исходный код)
Версия от 14:19, 17 октября 2019
, 17 октября 2019→Демонстрация
Omeln (обсуждение | вклад) |
Omeln (обсуждение | вклад) |
||
| (не показаны 4 промежуточные версии 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 | # Алгоритм применяется для размещения простых [[Неориентированный_граф | неориентированных графов]] и хорошо работает для [[граф|графов]] с количеством вершин не превышающих 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. | ||
[[Категория:Визуализация графов]] | |||
