Силовые алгоритмы
Силовые алгоритмы (force-directed algorithms) размещения графов на плоскости или в пространстве относятся к алгоритмам изображения графа, основанным на физических аналогиях. В качестве основного инструмента используется физическая модель, в которой возникает система определенных сил. В основе алгоритма может лежать один тип силы, либо же комбинация нескольких. Например: сила притяжения, отталкивания, гравитации, магнитного поля.
Постановка задачи
Предполагается, что входные графы являются простыми, связными, неориентированными графами. При нахождении прямолинейного изображения такого графа он может рассматриваться как система тел с силами, взаимодействующими между телами, например, считая вершины графа телами, а ребра пружинами. В этом случае алгоритм должен находить конфигурацию тел с локально минимальной энергией — так называемую конфигурацию равновесия сил, в которой каждое тело занимает такую позицию, что сумма всех сил, приложенных к телу, равна нулю.
Графы, нарисованные с использованием силовых алгоритмов получаются эстетически привлекательными, проявляют симметрию, а также в них возникают варианты размещения без пересечения для планарных графов.
Определение эстетической привлекательности графа достаточно субъективно, однако все же имеет некоторые свойства:
Алгоритмы
Большое разнообразие алгоритмов можно использовать для нахождения такого расположения графа на плоскости или в пространстве, при котором достигается равновесие всех сил, действующих на вершины графа.
Простейший из них — это алгоритм, который работает в два следующих этапа. На первом этапе вершины размещаются на плоскости случайным образом. Второй этап — это последовательность итераций до стабилизации, на каждой из которых вычисляются для всех вершин силы и для тех из них, для которых , происходит перемещение вершины в направлении этой силы на расстояние, пропорциональное модулю силы. Пропорция сдвига одна для всех вершин и является еще одним параметром алгоритма. Алгоритм достаточно прост, но не всегда дает наиболее быстрый способ достижения равновесия. Вместе с тем он позволяет осуществить интуитивно понятный плавный переход от случайных размещений к конфигурациям равновесия сил.
Алгоритмы определяют целевую функцию, которая отображает каждое размещение графа в R+, представляющее энергию системы. Эта функция определена таким образом, что малые энергии соответствуют размещениям, в которых соседние вершины находятся вблизи на заранее заданном расстоянии друг от друга, и на котором несмежные вершины хорошо разнесены.
- Алгоритм Идеса (P.Eades)
- Алгоритм Фрюхтермана-Рейнгольда (T.Fruchterman, S.Reingold)
- Алгоритм Камады-Каваи (T.Kamada, S.Kawai)
- Метод барицентров Тутте (W.Tutte)
Применение и реализации
Силовые алгоритмы рисования графов достаточно популярны, поскольку физические аналоги, с одной стороны, делают алгоритмы рисования достаточно прозрачными для понимания и простыми для реализации, а с другой, приводят к алгоритмам, дающим весьма хорошие расположения графов.
Ниже приведены библиотеки и программное обеспечение для визуализации графов, которые в качестве основного метода размещения используют силовые алгоритмы или имеют возможность разместить граф по данному алгоритму.
D3.js — это библиотека JavaScript для управления документами, в основе которых лежат данные. Позволяет размещать граф по алгоритму Фрюхтермана-Рейнгольда, а также имеет несколько особенных методов, например размещение с помощью аппроксимации движения N тел Барнса-Хата.
VivaGraphJS предназначен для расширения и поддержки различных механизмов рендеринга и алгоритмов размещения графов. Позволяет размещать граф с помощью силового алгоритма, позволяя задавать параметры.
Gephi - ведущее программное обеспечение для визуализации и исследования всех видов графов и сетей. Имеется несколько реализованных алгоритмов укладки графов, в том числе и Фрюхтермана-Рейнгольда.
Открытые проблемы
Полезность базового силового подхода ограничена небольшими графами, и результаты плохи для графов с более чем несколькими сотнями вершин. Есть несколько причин, почему силовые алгоритмы не работают хорошо для больших графов. Одно из основных препятствий для масштабируемости этих подходов состоит в том, что физическая модель обычно имеет много локальных минимумов. Даже с помощью сложных механизмов для избегания локальных минимумов силовые алгоритмы не способны постоянно производить хорошие размещения для больших графов из-за проблем с разрешением, поскольку для больших графов минимальное расстояние между вершинами становится весьма небольшим. Вместе с тем возникают различные расширения классических силовых алгоритмов, например, связанные с использованием многоуровневого подхода к изображению графа или с переходом при его изображении к геометрии, отличной от геометрии Евклида, позволяющие расширять применимость силовых алгоритмов на графы с десятками тысяч и даже с сотнями тысяч вершин.
Литература
- Handbook of graph drawing and visualization / ed. by R. Tamassia [et al.]. – Boca Raton: CRC Press, 2013. – 862 p.
- Касьянов В. Н., Евстигнеев В. А. Графы в программировании: обработка, визуализация и применение. – СПб.: БХВ-Петербург, 2003. – 1104 c.
- Касьянов В.Н., Касьянова Е.В. Визуализация информации на основе графовых моделей. – Новосибирск: НГУ, 2014. – 149 с.
