1294
правки
Силовые алгоритмы: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
Omeln (обсуждение | вклад) |
KVN (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
Силовые алгоритмы размещения графов на плоскости относятся к алгоритмам, | Силовые алгоритмы ('''force-directed algorithms''') размещения графов на плоскости или в пространстве относятся к алгоритмам [[изображение графа|изображения графа]], основанным на физических аналогиях. В качестве основного инструмента используется физическая модель, в которой возникает система определенных сил. В основе алгоритма может лежать один тип силы, либо же комбинация нескольких. Например: сила притяжения, отталкивания, гравитации, магнитного поля. | ||
= Постановка задачи = | = Постановка задачи = | ||
Предполагается, что входные графы являются [[Простой граф|простыми]], [[Связный граф|связными]], [[Неориентированный_граф | неориентированными]] графами. | |||
При нахождении [[прямолинейное изображение|прямолинейного изображения]] такого графа он может рассматриваться как система тел с силами, взаимодействующими между телами, например, считая вершины графа телами, а ребра пружинами. В этом случае алгоритм должен находить конфигурацию тел с локально минимальной энергией — так называемую конфигурацию равновесия сил, в которой каждое тело занимает такую позицию, что сумма всех сил, приложенных к телу, равна нулю. | |||
Графы, нарисованные с использованием силовых алгоритмов получаются эстетически привлекательными, проявляют симметрию, а также в них возникают варианты размещения без пересечения для плоских графов. | Графы, нарисованные с использованием силовых алгоритмов получаются эстетически привлекательными, проявляют симметрию, а также в них возникают варианты размещения без пересечения для плоских графов. | ||
| Строка 9: | Строка 12: | ||
# Связанные [[Вершина|вершины]] должны находится рядом с друг другом, не связанные в отдалении. | # Связанные [[Вершина|вершины]] должны находится рядом с друг другом, не связанные в отдалении. | ||
= Алгоритмы = | = Алгоритмы = | ||
Большое разнообразие алгоритмов можно использовать для нахождения такого расположения графа на плоскости или в пространстве, при котором достигается равновесие всех сил, действующих на вершины графа. Простейший из них — это алгоритм, который работает в два следующих этапа. | |||
На первом этапе вершины размещаются на плоскости случайным образом. | |||
Второй этап — это последовательность итераций до стабилизации, на каждой из которых вычисляются для всех вершин силы и для тех из них, для которых , происходит перемещение вершины в направлении этой силы на расстояние, пропорциональное модулю силы. Пропорция сдвига одна для всех вершин и является еще одним параметром алгоритма. | |||
Алгоритм достаточно прост, но не всегда дает наиболее быстрый способ достижения равновесия. Вместе с тем он позволяет осуществить интуитивно понятный плавный переход от случайных размещений к конфигурациям равновесия сил. | |||
Алгоритмы определяют целевую функцию, которая отображает каждое размещение графа в R+, представляющее энергию системы. Эта функция определена таким образом, что малые энергии соответствуют размещениям, в которых соседние узлы находятся вблизи на заранее заданном расстоянии друг от друга, и на котором несмежные узлы хорошо разнесены. | Алгоритмы определяют целевую функцию, которая отображает каждое размещение графа в R+, представляющее энергию системы. Эта функция определена таким образом, что малые энергии соответствуют размещениям, в которых соседние узлы находятся вблизи на заранее заданном расстоянии друг от друга, и на котором несмежные узлы хорошо разнесены. | ||
| Строка 24: | Строка 33: | ||
= Применение и реализации = | = Применение и реализации = | ||
Силовые алгоритмы | Силовые алгоритмы рисования графов достаточно популярны, поскольку физические аналоги, с одной стороны, делают алгоритмы рисования достаточно прозрачными для понимания и простыми для реализации, а с другой, приводят к алгоритмам, дающим весьма хорошие расположения графов. | ||
Ниже приведены библиотеки и программное обеспечение для визуализации графов, которые в качестве основного метода размещения используют силовые алгоритмы или имеют возможность разместить граф по данному алгоритму. | |||
D3.js — это библиотека JavaScript для управления документами, в основе которых лежат данные. Позволяет размещать граф по алгоритму Фрюхтермана-Рейнгольда, а также имеет несколько особенных методов, например размещение с помощью аппроксимации движения N тел Барнса-Хата. | D3.js — это библиотека JavaScript для управления документами, в основе которых лежат данные. Позволяет размещать граф по алгоритму Фрюхтермана-Рейнгольда, а также имеет несколько особенных методов, например размещение с помощью аппроксимации движения N тел Барнса-Хата. | ||