Силовые алгоритмы: различия между версиями

Перейти к навигации Перейти к поиску
нет описания правки
Нет описания правки
Строка 1: Строка 1:
Силовые алгоритмы размещения графов на плоскости относятся к алгоритмам, основанных на физических аналогиях. В качестве основного инструмента используется физическая модель, в которой возникает система определенных сил. В основе алгоритма может лежать один тип силы, либо же комбинация нескольких. Например: сила притяжения, отталкивания, гравитации, магнитного поля.  
Силовые алгоритмы ('''force-directed algorithms''') размещения графов на плоскости или в пространстве относятся к алгоритмам [[изображение графа|изображения графа]], основанным на физических аналогиях. В качестве основного инструмента используется физическая модель, в которой возникает система определенных сил. В основе алгоритма может лежать один тип силы, либо же комбинация нескольких. Например: сила притяжения, отталкивания, гравитации, магнитного поля.  


= Постановка задачи =
= Постановка задачи =
Предполагается, что входные графы являются [[Простой граф|простыми]], [[Связный граф|связными]], [[Неориентированный_граф | неориентированными]] графами.
При нахождении [[прямолинейное изображение|прямолинейного изображения]] такого графа он может рассматриваться как система тел с силами, взаимодействующими между телами, например, считая вершины графа телами, а ребра пружинами. В этом случае алгоритм должен находить конфигурацию тел с локально минимальной энергией — так называемую конфигурацию равновесия сил, в которой каждое тело занимает такую позицию, что сумма всех сил, приложенных к телу, равна нулю.


Графы, нарисованные с использованием силовых алгоритмов получаются эстетически привлекательными, проявляют симметрию, а также в них возникают варианты размещения без пересечения для плоских графов.  
Графы, нарисованные с использованием силовых алгоритмов получаются эстетически привлекательными, проявляют симметрию, а также в них возникают варианты размещения без пересечения для плоских графов.  
Строка 9: Строка 12:
# Связанные [[Вершина|вершины]] должны находится рядом с друг другом, не связанные в отдалении.
# Связанные [[Вершина|вершины]] должны находится рядом с друг другом, не связанные в отдалении.


Мы предполагаем, что входные графы являются [[Простой граф|простыми]], [[Связный граф|связными]], [[Неориентированный_граф | неориентированными]] графами.


Результатом [[алгоритм|алгоритма]] будет [[Layout|размещение графа (layout)]].


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


Алгоритмы определяют целевую функцию, которая отображает каждое размещение графа в R+, представляющее энергию системы. Эта функция определена таким образом, что малые энергии соответствуют размещениям, в которых соседние узлы находятся вблизи на заранее заданном расстоянии друг от друга, и на котором несмежные узлы хорошо разнесены.
Алгоритмы определяют целевую функцию, которая отображает каждое размещение графа в R+, представляющее энергию системы. Эта функция определена таким образом, что малые энергии соответствуют размещениям, в которых соседние узлы находятся вблизи на заранее заданном расстоянии друг от друга, и на котором несмежные узлы хорошо разнесены.
Строка 24: Строка 33:
= Применение и реализации =
= Применение и реализации =


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


D3.js — это библиотека JavaScript для управления документами, в основе которых лежат данные. Позволяет размещать граф по алгоритму Фрюхтермана-Рейнгольда, а также имеет несколько особенных методов, например размещение с помощью аппроксимации движения N тел Барнса-Хата.
D3.js — это библиотека JavaScript для управления документами, в основе которых лежат данные. Позволяет размещать граф по алгоритму Фрюхтермана-Рейнгольда, а также имеет несколько особенных методов, например размещение с помощью аппроксимации движения N тел Барнса-Хата.

Навигация