Силовые алгоритмы: различия между версиями
KVN (обсуждение | вклад) Нет описания правки |
KVN (обсуждение | вклад) |
||
(не показаны 3 промежуточные версии этого же участника) | |||
Строка 6: | Строка 6: | ||
При нахождении [[прямолинейное изображение|прямолинейного изображения]] такого графа он может рассматриваться как система тел с силами, взаимодействующими между телами, например, считая вершины графа телами, а ребра пружинами. В этом случае алгоритм должен находить конфигурацию тел с локально минимальной энергией — так называемую конфигурацию равновесия сил, в которой каждое тело занимает такую позицию, что сумма всех сил, приложенных к телу, равна нулю. | При нахождении [[прямолинейное изображение|прямолинейного изображения]] такого графа он может рассматриваться как система тел с силами, взаимодействующими между телами, например, считая вершины графа телами, а ребра пружинами. В этом случае алгоритм должен находить конфигурацию тел с локально минимальной энергией — так называемую конфигурацию равновесия сил, в которой каждое тело занимает такую позицию, что сумма всех сил, приложенных к телу, равна нулю. | ||
Графы, нарисованные с использованием силовых алгоритмов получаются эстетически привлекательными, проявляют симметрию, а также в них возникают варианты размещения без пересечения для | Графы, нарисованные с использованием силовых алгоритмов получаются эстетически привлекательными, проявляют симметрию, а также в них возникают варианты размещения без пересечения для [[планарный граф|планарных графов]]. | ||
Определение эстетической привлекательности графа достаточно субъективно, однако все же имеет некоторые свойства: | Определение эстетической привлекательности графа достаточно субъективно, однако все же имеет некоторые свойства: | ||
# Между [[Вершина|вершинами]] графа должно быть достаточно расстояния. | # Между [[Вершина|вершинами]] графа должно быть достаточно расстояния. | ||
# Связанные [[Вершина|вершины]] должны находится рядом с друг другом, не связанные в отдалении. | # Связанные [[Вершина|вершины]] должны находится рядом с друг другом, не связанные в отдалении. | ||
= Алгоритмы = | = Алгоритмы = | ||
Большое разнообразие алгоритмов можно использовать для нахождения такого расположения графа на плоскости или в пространстве, при котором достигается равновесие всех сил, действующих на вершины графа | Большое разнообразие алгоритмов можно использовать для нахождения такого расположения графа на плоскости или в пространстве, при котором достигается равновесие всех сил, действующих на вершины графа. | ||
Простейший из них — это алгоритм, который работает в два следующих этапа. | |||
На первом этапе вершины размещаются на плоскости случайным образом. | На первом этапе вершины размещаются на плоскости случайным образом. | ||
Второй этап — это последовательность итераций до стабилизации, на каждой из которых вычисляются для всех вершин силы и для тех из них, для которых , происходит перемещение вершины в направлении этой силы на расстояние, пропорциональное модулю силы. Пропорция сдвига одна для всех вершин и является еще одним параметром алгоритма. | Второй этап — это последовательность итераций до стабилизации, на каждой из которых вычисляются для всех вершин силы и для тех из них, для которых , происходит перемещение вершины в направлении этой силы на расстояние, пропорциональное модулю силы. Пропорция сдвига одна для всех вершин и является еще одним параметром алгоритма. | ||
Алгоритм достаточно прост, но не всегда дает наиболее быстрый способ достижения равновесия. Вместе с тем он позволяет осуществить интуитивно понятный плавный переход от случайных размещений к конфигурациям равновесия сил. | Алгоритм достаточно прост, но не всегда дает наиболее быстрый способ достижения равновесия. Вместе с тем он позволяет осуществить интуитивно понятный плавный переход от случайных размещений к конфигурациям равновесия сил. | ||
Алгоритмы определяют целевую функцию, которая отображает каждое размещение графа в R+, представляющее энергию системы. Эта функция определена таким образом, что малые энергии соответствуют размещениям, в которых соседние | Алгоритмы определяют целевую функцию, которая отображает каждое размещение графа в R+, представляющее энергию системы. Эта функция определена таким образом, что малые энергии соответствуют размещениям, в которых соседние вершины находятся вблизи на заранее заданном расстоянии друг от друга, и на котором несмежные вершины хорошо разнесены. | ||
* [[Алгоритм | * [[Алгоритм Идеса]] (P.Eades) | ||
* [[Алгоритм Фрюхтермана-Рейнгольда]] (Fruchterman | * [[Алгоритм Фрюхтермана-Рейнгольда]] (T.Fruchterman, S.Reingold) | ||
* [[Алгоритм Камада-Кавай]] (Kamada | * [[Алгоритм Камада-Кавай]] (T.Kamada, S.Kawai) | ||
* [[Метод | * [[Метод барицентров Тутте]] (W.Tutte) | ||
= Применение и реализации = | = Применение и реализации = | ||
Строка 45: | Строка 42: | ||
= Открытые проблемы = | = Открытые проблемы = | ||
Полезность базового силового подхода ограничена небольшими графами, и результаты плохи для графов с более чем несколькими сотнями [[Вершина|вершин]]. Есть несколько причин, почему силовые алгоритмы не работают хорошо для больших графов. | Полезность базового силового подхода ограничена небольшими графами, и результаты плохи для графов с более чем несколькими сотнями [[Вершина|вершин]]. Есть несколько причин, почему силовые алгоритмы не работают хорошо для больших графов. Одно из основных препятствий для масштабируемости этих подходов состоит в том, что физическая модель обычно имеет много локальных минимумов. Даже с помощью сложных механизмов для избегания локальных минимумов силовые алгоритмы не способны постоянно производить хорошие размещения для больших графов из-за проблем с разрешением, поскольку для больших графов минимальное расстояние между вершинами становится весьма небольшим. Вместе с тем возникают различные расширения классических силовых алгоритмов, например, связанные с использованием многоуровневого подхода к изображению графа или с переходом при его изображении к геометрии, отличной от геометрии Евклида, позволяющие расширять применимость силовых алгоритмов на графы с десятками тысяч и даже с сотнями тысяч вершин. | ||
= Литература = | = Литература = | ||
* Handbook of graph drawing and visualization / ed. by R. Tamassia [et al.]. – Boca Raton: CRC Press, 2013. – 862 p. | |||
* Касьянов В. Н., Евстигнеев В. А. Графы в программировании: обработка, визуализация и применение. – СПб.: БХВ-Петербург, 2003. – 1104 c. | |||
* Касьянов В.Н., Касьянова Е.В. Визуализация информации на основе графовых моделей. – Новосибирск: НГУ, 2014. – 149 с. | |||
[[Категория:Визуализация графов]] | [[Категория:Визуализация графов]] |
Текущая версия от 12:03, 2 февраля 2020
Силовые алгоритмы (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 с.