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

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

Показов 14443 Комментарии 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

Комментарии

Новые блоги и статьи Все статьи Все блоги /
Из невошедшего на форум (диалог с ИИ-гугла) zorxor 29.07.2026 А вот, что интересно, сказал мне ИИ-гугла: Этот текст — эмоциональный пост пользователя под ником zorxor на интернет-форуме (вероятно, посвященном мистике, непознанному или альтернативной науке). . . .	Был праздник вчера, а я и не знал. kumehtar 28.07.2026 27. 07. 2026г. Intel Core 2 Duo исполнилось 20 лет Новости компьютерного мира и их обсуждение (4) Салют, шампанское, овации! :drink:	Нейтральные знания, чистый код - бла-бла-бла-бла, на самом деле кликбейт и самореклама, плагиат, и вот почему Hrethgir 27.07.2026 То-есть отклонение такой публикации говорит само за себя, и пусть только возьмут на вооружение после отклонения публикации - это будет чистейшим актом плагиата. Отклонял Хабр. Дословно, отклонённая. . .	тв 16 бой ии anaschu 27.07.2026 Великий Перелом ИИ: Как уравнения ОДУ Radau дожали цензурные фильтры Алисы Фиксируем в мемофонде Теории Всего беспрецедентный факт в истории ИИ-зондирования. В затяжном многораундовом. . .
мв 15. непроверенное, возможно, глюк anaschu 27.07.2026 НАУЧНО-АНАЛИТИЧЕСКИЙ ОТЧЕТ. РАЗДЕЛ 1. 1: «НАУКА» (РАСШИРЕННАЯ СТЕХИОМЕТРИЧЕСКАЯ И ГЕНЕТИЧЕСКАЯ ВЕРСИЯ)Тема: Теоретическое обоснование инвариантности 19-мерного тензорного ядра непрерывных ОДУ и. . .	Очистка реквизитов и табличных частей документа при копировании (вариант 2) Maks 26.07.2026 Алгоритм из решения ниже разработан на примере нетипового документа "ЗаявкаНаРаботу", разработанного в КА2. Задача: Заменить алгоритм запрета копирования документов для сотрудников с ролью "Стажер",. . .	Доктрина интенционального знания - Доктрина для портала "Срез". Hrethgir 25.07.2026 Может найдётся кто захочет оценить доктрину. . . Написания правил участия для меня роскошь, требующая лимита времени, поэтому все сообщения не прошедшие модерацию будут видны только участникам портала,. . .	сукцессия 44. Решил подать на припринт в межународные сервисы препринтов. Но нужно одобрение от ученых anaschu 25.07.2026 Английский вариант. Пока кто то не одобрит мою личность, мне не получиться это опубликовать на препринте. Но заявку на публикацию статьи я сегодня подам.

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

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