Использование физических аналогий

Методы, основанные на использовании физических аналогий (force-directed methods), интерпретируют граф при построении его изображения как физическую систему с силами между вершинами и пытаются минимизировать энергию системы для получения хорошего рисунка.

Такого типа алгоритмы используются для рисования произвольных (разреженных) сетей, таких как блок-схемы, графы программного планирования, графы телефонных вызовов и т. п. Они также применяются для построения кластерных изображений.

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

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

Большое разнообразие алгоритмов можно использовать для нахождения такого расположения графа на плоскости, при котором достигается равновесие всех сил, действующих на вершины графа. Простейший из них — это алгоритм, который работает в два следующих этапа. На первом этапе вершины размещаются на плоскости случайным образом. Второй этап — это последовательность итераций до стабилизации, на каждой из которых вычисляются для всех вершин p силы F(p), и для тех из них, для которых F(p)≠Ō, происходит перемещение вершины в направлении этой силы на расстояние, пропорциональное модулю силы. Пропорция сдвига одна для всех вершин и является еще одним параметром алгоритма. Алгоритм достаточно прост, но не всегда дает наиболее быстрый способ достижения равновесия. Вместе с тем он позволяет осуществить интуитивно понятный плавный переход от случайных размещений к конфигурациям равновесия сил.

В общем случае методы, основанные на использовании физических аналогий, успешно дают хорошие результаты для относительно небольших графов, но не являются хорошо масштабируемыми. Большие графы часто приводят к тому, что функция энергии становится весьма трудной для достижения минимума. Более того, типичный алгоритм, реализующий данные методы, является итерационным. Во время каждой итерации позиции всех вершин переопределяются на основе предыдущей итерации, которая, вероятно, требует O(n² + m) времени, где n и m — количество вершин и ребер соответственно. Хорошая раскладка обычно требует O(n) итераций. Следовательно, общая временная сложность алгоритма составляет O(n³) или даже O(n⁴). Кроме того, основанные на физических аналогиях алгоритмы раскладки не обладают предсказуемостью, и это означает, что один и тот же алгоритм, обрабатывая один и тот же граф, может получать совсем не похожие результаты. Непредсказуемость данных алгоритмов может вызывать в некоторых случаях серьезные проблемы, поскольку навигация пользователя сильно зависит от визуального представления графов.

Литература

• Касьянов В. Н., Евстигнеев В. А. Графы в программировании: обработка, визуализация и применение. – СПб.: БХВ-Петербург, 2003. – 1104 c.
• Касьянов В.Н., Касьянова Е.В. Визуализация информации на основе графовых моделей // Научная визуализация. – 2014. – Том. 6, N 1. – С. 31 – 50.
• Касьянов В.Н., Касьянова Е.В. Визуализация информации на основе графовых моделей. – Новосибирск: НГУ, 2014. – 149 с.