Алгоритм Фрюхтермана-Рейнгольда: различия между версиями

Алгоритм Фрюхтермана-Рейнгольда относится к семейству силовых (forced-directed) алгоритмов укладки графов на плоскости, в котором используятся пружинная физическая модель, где вершины графа определяются как тела системы, а ребра как пружины. Силы могут действовать только на вершины, вес пружин при этом не учитывается. Имеется простой неориентированный граф G = (V, E). У каждой вершины из множества V в качестве переменных используются координаты ее размещения Vx и Vy, а также Vf - вектор силы, направленный на приведение физической системы в равновесие.

<math display="block"> l = \sqrt{area/|V|} \text{ - Идеальная длина пружины для ребра e} </math>

<math display="block">p_v = (x_v, y_v) \text{ - Вектор положения вершины v}</math>

<math display="block">||p_v - p_u || \text{ - Евклидовое расстояние между вершинами u и v}</math>

<math display="block">\Vec{p_up_v}  \text{ - Направленный вектор из вершины  u в v}</math>

<math display="block">f_{spring} = \frac{{||p_u-p_v||}^2}{l}\Vec{p_vp_u}</math>

<math display="block">f_{rep} = \frac{l^2}{||p_u-p_v||}\Vec{p_up_v}</math>