20
правок
Алгоритм Фрюхтермана-Рейнгольда: различия между версиями
Материал из WEGA
Алгоритм Фрюхтермана-Рейнгольда (посмотреть исходный код)
Версия от 14:19, 17 октября 2019
, 17 октября 2019→Демонстрация
Omeln (обсуждение | вклад) мНет описания правки |
Omeln (обсуждение | вклад) |
||
| (не показаны 3 промежуточные версии 2 участников) | |||
| Строка 2: | Строка 2: | ||
= Постановка задачи = | = Постановка задачи = | ||
Имеется простой неориентированный граф <math>G = (V, E)</math>. У каждой [[Вершина|вершины]] из множества <math>V</math> в качестве переменных используются координаты ее размещения <math>V_x</math> и <math>V_y</math>, а также <math>V_f</math> - вектор силы, направленный на приведение физической системы в равновесие. Необходимо применить физическую модель и минимизировать энергию системы. Результатом [[алгоритм|алгоритма]] будет [[ | Имеется простой неориентированный граф <math>G = (V, E)</math>. У каждой [[Вершина|вершины]] из множества <math>V</math> в качестве переменных используются координаты ее размещения <math>V_x</math> и <math>V_y</math>, а также <math>V_f</math> - вектор силы, направленный на приведение физической системы в равновесие. Необходимо применить физическую модель и минимизировать энергию системы, меняя расположение вершин. Результатом [[алгоритм|алгоритма]] будет наглядное [[изображение графа]] на плоскости. | ||
= Описание алгоритма = | = Описание алгоритма = | ||
| Строка 31: | Строка 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 | ||
# Алгоритм не останавливается, в графе циклически повторяется размещение наименее [[Связные_вершины|связных вершин]], что можно видеть на демонстрации (проблема решается с помощью добавления модификации температуры) | |||
= Модификации = | = Модификации = | ||
| Строка 43: | Строка 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. | ||
[[Категория:Визуализация графов]] | |||
