Силовые методы рисования графов. Демонстрация.

Запись от Mysterious Light размещена 30.01.2014 в 16:17

Показов 14500 Комментарии 0

Краткое содержание:
Ниже рассказывается про силовой алгоритм рисования графов, физику моделируемого процесса и прикладывается программа (под браузер), в которой можно этот метод посмотреть пошагово.

Часто возникает такое желание: изобразить граф по-красивее. Конечно, существует бесчисленное множество инструментов, и отдельные программы, и библиотеки под каждый язык программирования, под каждую среду.
Но ведь что лучше может быть, чем пощупать ручками!

Одним из способов является так называемый Force-Directed Graph Drawing — силовой алгоритм рисования графов. Он красив хотя бы потому, что основывается на простом физическом наблюдении: всякая физическая система стремится к минимуму своей энергии, в котором минимум дефектов и наибольшая симметрия.

Суть проста: в вершины графа помещаются заряды q, которые отталкиваются, будучи одноимёнными, а ребра заменяются на пружины одниковой равновесной длины l0 и жесткости k; система случайным образом размещается на плоскости, приводится в движение и дальше отпускается, эволюционируя по простым и естественным законам физики, пока не придёт в равновесие.

Вполне естественно, что для прихода в равновесия система должна иметь механизм релаксации. Обычно, это трение — сила, зависящая от скорости и противонаправленная ей, индивидуальная для каждой частицы.

Теоретик сразу скажет, что как только сделалась такая физическая аналогия, то задача сразу становится эквивалентной поиску минимума на потенциальном ландшафте — минимизация функции . Замечу, речь идёт о потенциальной энергии.

Один из алгоритмов минимизации мы знаем — это градиентный спуск. Физическая аналогия его такова: это движение тела с бесконечно большим трением. Дествительно, тело перестаёт быть инертным, ибо скорость всегда очень мала, а значит сонаправлена силе, и поэтому система будет двигаться строго по градиенту энергии. Однако, такой метод для больших графов даёт плохой результат из-за большого числа локальных минимумов.

Оставим систему инертной: спускаясь на санках с горки, нужно преодолеть небольшой выступ, чтобы спуститься ещё ниже. Кроме этого, оставимся на физичной системе, а потому и на физичных уравнениях:

$https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac d{dt}\vec{r_i} = \vec{v_i} \quad\quad\quad\quad \frac d{dt}\vec{v_i} = \vec{f_i}$

здесь f — это приведённая сила (на ед. массы), а индекс указывает номер вершины,
r — положение, v — скорость. Перед нами обычное уравнение Ньютона.

Физика процесса

На вершину i действует электростатическая сила отталкивания со стороны всех других вершин:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\vec{f^{\rm{coulomb}}_i} \;=\; \sum_{j\neq i} \,\frac{q^2}{\| \vec{r_i}-\vec{r_j} \|} \, \rm{ort} (\vec{r_i}-\vec{r_j})$
А также со стороны всех смежных вершин действует сила растяжения/сжатия пружины по закону Гука:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\vec{f^{\rm{hooke}}_i} \;=\; \sum_{\rm{\small neighbours}} \; k \left( \| \vec{r_i}-\vec{r_j} \| - l_0 \right) \, \rm{ort} (\vec{r_i}-\vec{r_j})$
Здесь ort определяет единичный вектор направления от вершины j к вершине i.

Кроме этого, имеется сила трения
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\vec{f^{\rm{fric}}_i} \;=\; - \| f_{\rm{fric}} \| \, \rm{ort}\vec{v_i}$
сила трения противонаправлена скорости. Модуль силы трения обычно полагается пропорциональным некоторой степени скорости, например, — линейная зависимость, — квадратичная.

Таким образом, на каждую вершину действиет сила
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\vec{f_i} = f^{\rm{coulomb}}_i + f^{\rm{hooke}}_i + f^{\rm{fric}}_i$

Обратим внимание на то, что первые две силы потенциальны и зависят только от положения всех вершин, но не от из скоростей, а последняя сила определяется только скоростью, притом только той частицы, на которую она действиет.

Представление данных

Положение всей системы задаётся набором векторов , где каждый вектор имеет x и y компоненты. Если "развернуть" и выписать всё в ряд, то получится массив из 2n чисел , на нечетных позициях стоят абсциссы, на четных — ординаты вершин. Таким образом, состояние системы (положение) задается вектором 2n-мерного пространства.
Оказывается, и скорость, и сила представляются как массив из 2n-чисел.
Такое представление ценно ещё и тем, что сохраняются основные соотношения:

$https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac d{dt}r = v \quad\quad\quad\quad \frac d{dt}v = f$

Алгоритм

Алгоритм выглядит таким образом:

1. Генерируем случайное начальное положение r и случайную скорость v, как 2n-мерный массив.

2. Повторяем одну и ту же процедуру много раз, пока систему не придёт в условно равновесное состояние (то есть практически остановится)

2.1. Определяем вектор силы (как 2n-мерный массив) по формулам из физических соображений

$https://www.cyberforum.ru/cgi-bin/latex.cgi?f = f(r,v)$

2.2. Вычисляем новую скорость и положение (используется самая простенькая конечно-разностное приближение)

$https://www.cyberforum.ru/cgi-bin/latex.cgi?v \leftarrow v + f\Delta t$
$https://www.cyberforum.ru/cgi-bin/latex.cgi?r \leftarrow r + v\Delta t$

$https://www.cyberforum.ru/cgi-bin/latex.cgi?\Delta t$ — шаг по времени.

2.3. Проверяем, не остановилась ли система. Проверка может осуществляться по кинетической энергии

$https://www.cyberforum.ru/cgi-bin/latex.cgi?K = \sum_i \frac{\|\vec{v_i}\|^2}2$

в первых обозначениях, или в новых (2n-мерный массив) обозначениях

$https://www.cyberforum.ru/cgi-bin/latex.cgi?2K = \sum_i v_i^2$

Ниже можно увидеть реализацию этого алгоритма. Основной файл Graph/Visual.html, браузер должен поддерживать canvas.

Поддерживаются два варианта силы трения: линейная и квадратичная.
Также сделано два варианта силы пружины: линейная зависимость (закон Гука) и логарифмическая , где — расстояние между смежными вершинами. При малом отклонении этого расстояния от равновесного эти две зависимости эквивалентны, однако при большом отклонении логарифмическая зависимость ведёт себя более мягко (эластично) по сравнению с Гуком.

В многих статьях по визуализации графов рекомендуется использовать именно логарифмическую. Вы можете сами убедиться в правомерности этого совета.

Справа также показывается изменение потенциальной энергии от времени.

Все основные параметры могут быть изменены в начале файла Visual.js

Матрица смежности нетривиального графа для тех, кто не хочет придумывать сам

можете взять такую

Code
1
2
3
4
5
6
7
8
[
  [0,1,1,0,0,0],
  [1,0,1,1,0,0],
  [1,1,0,1,1,0],
  [0,1,1,0,1,1],
  [0,0,1,1,0,1],
  [0,0,0,1,1,0]
]

Метки граф, графика

Размещено в Без категории

« Сжатие данных по алгоритму Лемпеля — Зива — Велча (используется в GIF и PNG) Главная страница Счётность типов »

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.

Всего комментариев 0

Комментарии

Новые блоги и статьи Все статьи Все блоги /
Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .	Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .	Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .
Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .	Программа опроса у.з. расходомера SLS-720F Argus19 02.09.2026 Программа опроса у. з. расходомера SLS-720F Программа опрашивает один раз в минуту три ультразвуковых расходомера SLS-720F через интерфейс RS-485 по протоколу Modbus RTU. Опрашиваются регистры. . .	Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0. Maks 31.08.2026 При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка: Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .	Архитектура биовида Стива в Майнкрафте: Зачем бонобо кубический каннибализм anaschu 30.08.2026 Кубический Вагинокапитализм в Minecraft: Математический инвариант ОДУ и рок Стивов-бонобо Главная задача разработанной «Модели Всего» — наглядно продемонстрировать наличие системной «судьбы». . .

Сообщение форума

Отменить изменения