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

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


= Постановка задачи =
= Постановка задачи =


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


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


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


Результатом [[алгоритм|алгоритма]] будет [[Layout|размещение графа (layout)]].
Большое разнообразие алгоритмов можно использовать для нахождения такого расположения графа на плоскости или в пространстве, при котором достигается равновесие всех сил, действующих на вершины графа.  


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


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


* [[Алгоритм Eades]]
* [[Алгоритм Идеса]] (P.Eades)
* [[Алгоритм Фрюхтермана-Рейнгольда]] (Fruchterman-Reingold)
* [[Алгоритм Фрюхтермана-Рейнгольда]] (T.Fruchterman, S.Reingold)
* [[Алгоритм Камада-Кавай]] (Kamada and Kawai)
* [[Алгоритм Камада-Кавай]] (T.Kamada, S.Kawai)
* [[Метод Барицентров Тутте]] (Tutte’s 1963 barycentric method)
* [[Метод барицентров Тутте]] (W.Tutte)


= Применение и реализации =
= Применение и реализации =


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


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


Полезность базового силового подхода ограничена небольшими графами, и результаты плохи для графов с более чем несколькими сотнями [[Вершина|вершин]]. Есть несколько причин, почему силовые алгоритмы не работают хорошо для больших графов. Один из основных препятствий для масштабируемости этих подходов является тот факт, что физическая модель обычно имеет много локальных минимумов. Даже с помощью сложных механизмов для избегания локального минимума, силовые алгоритмы не способны постоянно производить хорошие размещения для больших графов.
Полезность базового силового подхода ограничена небольшими графами, и результаты плохи для графов с более чем несколькими сотнями [[Вершина|вершин]]. Есть несколько причин, почему силовые алгоритмы не работают хорошо для больших графов. Одно из основных препятствий для масштабируемости этих подходов состоит в том, что физическая модель обычно имеет много локальных минимумов. Даже с помощью сложных механизмов для избегания локальных минимумов силовые алгоритмы не способны постоянно производить хорошие размещения для больших графов из-за проблем с разрешением, поскольку для больших графов минимальное расстояние между вершинами становится весьма небольшим. Вместе с тем возникают различные расширения классических силовых алгоритмов, например, связанные с использованием многоуровневого подхода к изображению графа или с переходом при его изображении к геометрии, отличной от геометрии Евклида, позволяющие расширять применимость силовых алгоритмов на графы с десятками тысяч и даже с сотнями тысяч вершин.
 
 


= Литература =
= Литература =


# Handbook of graph drawing and visualization / ed. by R. Tamassia [et al.]. – Boca Raton: CRC Press, 2013. – 862 p.
* 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) размещения графов на плоскости или в пространстве относятся к алгоритмам изображения графа, основанным на физических аналогиях. В качестве основного инструмента используется физическая модель, в которой возникает система определенных сил. В основе алгоритма может лежать один тип силы, либо же комбинация нескольких. Например: сила притяжения, отталкивания, гравитации, магнитного поля.

Постановка задачи

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

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

Определение эстетической привлекательности графа достаточно субъективно, однако все же имеет некоторые свойства:

  1. Между вершинами графа должно быть достаточно расстояния.
  2. Связанные вершины должны находится рядом с друг другом, не связанные в отдалении.

Алгоритмы

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

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

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

Применение и реализации

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

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

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 с.