Силовые алгоритмы
Силовые алгоритмы размещения графов на плоскости относятся к алгоритмам, основанных на физических аналогиях. В качестве основного инструмента используется физическая модель, в которой возникает система определенных сил. В основе алгоритма может лежать один тип силы, либо же комбинация нескольких. Например: сила притяжения, отталкивания, гравитации, магнитного поля.
Постановка задачи
Графы, нарисованные с использованием силовых алгоритмов получаются эстетически привлекательными, проявляют симметрию, а также в них возникают варианты размещения без пересечения для плоских графов.
Определение эстетической привлекательности графа достаточно субъективно, однако все же имеет некоторые свойства:
- Между вершинами графа должно быть достаточно расстояния.
- Связанные вершины должны находится рядом с друг другом, не связанные в отдалении.
Мы предполагаем, что входные графы являются простыми, связными, неориентированными графами.
Результатом алгоритма будет размещение графа (layout).
Алгоритмы
Алгоритмы определяют целевую функцию, которая отображает каждое размещение графа в R+, представляющее энергию системы. Эта функция определена таким образом, что малые энергии соответствуют размещениям, в которых соседние узлы находятся вблизи на заранее заданном расстоянии друг от друга, и на котором несмежные узлы хорошо разнесены.
- Алгоритм Eades
- Алгоритм Фрюхтермана-Рейнгольда (Fruchterman-Reingold)
- Алгоритм Камада-Кавай (Kamada and Kawai)
- Метод Барицентров Тутте (Tutte’s 1963 barycentric method)
Применение и реализации
Силовые алгоритмы используют для размещения графов на плоскости. Ниже приведены библиотеки и программное обеспечение для визуализации графов, которые в качестве основного метода размещения используют силовые алгоритмы или имеют возможность разместить граф по данному алгоритму.
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.