🗊Презентация Cиловые алгоритмы. (Лекция 6)

Cиловые алгоритмы (Л. 6) Апанович З.В. apanovich@iis.nsk.su Тел:3309344 К. 217

Методы размещения, основанные на физических аналогиях Методы, основанные на физических аналогиях очень популярны по следующим причинам: 1) они очень интуитивны; 2) их легко понять и запрограммировать; 3) для графов размером порядка 150 вершин дают вполне удовлетворительные результаты; 4) размещения, получаемые при помощи этих алгоритмов, являются эстетически приятными, показывают симметрию и порождают (если это возможно) размещения без пересечений ребер 5) Их легко настраивать на новые приложения

Методы размещения, основанные на физических аналогиях Основу любого силового алгоритма составляют две компоненты: модель, описывающая физические объекты (соответствующие вершинам и ребрам графа) и взаимодействие между этими объектами алгоритм, который (приблизительно) вычисляет состояние равновесия для этой системы Описание модели основывается на том, какое изображение можно считать хорошим в каждом конкретном случае. С моделью связывается целевая функция, описывающая конкретное понятие «хорошести» Алгоритм служит для оптимизации целевой функции.

Методы размещения, основанные на физических аналогиях (общие рассуждения) Рассмотрим, к примеру, связный неориентированный граф G(V,E) и попробуем получить прямолинейное изображение этого графа, обладающее следующими свойствами: 1) Вершины равномерно распределены на поверхности изображения. 2) Смежные вершины (соединенные ребром) должны быть расположены примерно на одинаковом расстоянии друг от друга.

Методы размещения, основанные на физических аналогиях (общие рассуждения) Эти пожелания можно обосновать только интуитивно. Равномерное распределение вершин уменьшает беспорядок, а одинаковая длина ребер дает впечатление неискаженного изображения. Поскольку понятия «искажение» и «беспорядок» уже имеются в физике, можно пообсуждать физические аналогии, где встречаются такие понятия. Равномерное распределение можно искать для движущихся объектов. Достаточно естественно представить вершины как заряженные шары, которые отталкиваются друг от друга для удовлетворения первого критерия. А чтобы смежные вершины не разбегались слишком далеко, их можно соединить чем-то, например, пружинами, соответствующими ребрам.

Методы размещения, основанные на физических аналогиях (общие рассуждения) Пружины подходят больше, чем жесткие палки или веревки, так как они могут и удлиняться и сжиматься. Чем сильнее отклонение от «естественной длины» тем больше будет сила, действующая на них, чтобы вернуть пружины к заданной длине. При этом небольшое искажение естественной длины неизбежно, так как чаще всего невозможно изобразить весь граф с прямыми ребрами одинаковой длины. Доказано, что проблема выяснения имеет ли произвольный граф прямолинейное размещение с ребрами равной длины в любом количестве измерений является NP-полной (1982, Джонсон).

Методы размещения, основанные на физических аналогиях (общие рассуждения) Если система описана, и объектам разрешено двигаться под влиянием действующих на них сил, то она постепенно придет в состояние равновесия , в котором все силы уравновешивают друг друга и взяв изображение, соответствующее этому положению равновесия, мы получим изображение, приблизительно удовлетворяющее указанным выше критериям.

Силовые алгоритмы (Spring embedder, Eades 1984) Дан связный неориентированный граф G = (V, E) Пусть P = (pv), vV – это вектор позиций вершин. Каждая вершина v имеет координату pv = (xv,yv). Расстояние между вершинами ||pv-pu|| - это Евклидово расстояние. Будем обозначать Единичный вектор, направленный от pu к pv. Эстетичность размещения описывалось словами: «все ребра должны быть одинаковой длины, а размещение должно быть как можно более симметричным.

Силовые алгоритмы (Eades 1984) 1) Сила отталкивания действует между каждой парой не-смежных вершин: u, v V

Силовые алгоритмы (Eades 1984) Алгоритм Spring embedder (Eades 1984) Вход: связный неориентированный граф G = (V, E) и начальное размещение его вершин p = (pv) vV Выход: Размещение с низким внутренним напряжением for t :=1 to Количество_итераций do for v V do{ } for v V do pv :=pv+ Fv(t) } У Идеса: Cspring = 2, Crep =1, l =1,  =0.1, кол-во итераций =100.

Пример изображения, порождаемого алгоритмом Eades

Силовые алгоритмы (Fruchterman &Reingold, 1991) Алгоритм Фрюхтермана и Рейнгольда 1991 года ввел критерий равномерного распределения и попробовал его формализовать. Также ввел несколько модификаций, направленных, в основном, на ускорение работы алгоритма, так как результаты, получаемые этим алгоритмом, весьма похожи на результаты работы алгоритма Идеса.

Fruchterman&Reingold(1991). Модификация сил, действующих на вершины Силы отталкивания действуют между каждой парой вершин для всех (u, v)V Силы притяжения действуют только между смежными вершинами. Сила пружины вычисляется как сумма этих сил Fspring(pu,pv) = fattr(pu,pv)+frep(pu,pv)

Fruchterman&Reingold(1991). Сила притяжения вычисляется быстрее, потому что не надо вычислять корень. Процесс быстрее сходится к решению, за счет того, что увеличено влияние компоненты расстояния (квадратный показатель степени).

Силовые алгоритмы (Fruchterman &Reingold, 1991) area:= W * L; {W и L – это ширина и длина фрейма} G := (V, E); вершинам присваиваются случайные начальные позиции l := area/|V|;/* идеальная длина зависит от площади и количества вершин*/ function frep (x) := begin return l2/x end; function fatr(x) := begin return x2/l end; for i := 1 to iterations do begin

Силовые алгоритмы (Fruchterman &Reingold, 1991) /* вычислить силы отталкивания, действующие на каждую вершину со стороны всех остальных вершин и смещение вершины под влиянием силы отталкивания: */ for v in V do begin { /* каждая вершина имеет два вектора: .pos и .disp */ v.disp := 0; for u in V do { if (u v) then begin /* -это вектор разностей между позициями двух вершин*/ := v.pos – u.pos; v.disp := v.disp +(/||) * frep (||) } }

Силовые алгоритмы (Fruchterman &Reingold, 1991) /*вычислить силы притяжения между двумя смежными вершинами смещения обеих вершин под влиянием силы притяжения:*/ for e in E do { /*каждое ребро это упорядоченная пара вершин .v и .u*/  := e.v.pos – e.u.pos; e.v.disp := e.v.disp - (/||) . fatr(||); e.u.disp := e.u.disp +(/||) . fatr(||); }

Силовые алгоритмы (Fruchterman &Reingold, 1991) /*ограничить max_смещение температурой t и предотвратить перемещения за границу фрейма*/ for v in V do { v.pos := v.pos +(v.disp/[v.disp|) * min(v.disp, t); v.pos.x := min(W/2, max(-W/2, v.pos.x)); v.pos.y := min(L/2, max(-L/2, v.pos.y)) } /*уменьшить температуру по мере приближения размещения к лучшей конфигурации*/ t := cool(t) }

Модификации, связанные с вектором смещения

Fruchterman&Reingold(1991) На каждой итерации базовый алгоритм вычисляет O(|E|) сил притяжения и O(|V|2) сил отталкивания. Для уменьшения квадратичной сложности сил отталкивания Фр&Ре предложили использовать сеточный вариант их базового алгоритма, где силы отталкивания между отдаленными вершинами игнорируются. Поскольку отталкивание отдаленных вершин не сильно влияет на вектор смещения, то эти несущественные вершины отбрасываются из суммы сил отталкивания. Рассматриваются только вершины, расположенные в узлах сетки, близких к узлу v и, если их расстояние меньше заданного порога, только тогда вычисляется сила отталкивания. Это позволяет оценку по времени O(n) для вычисления сил отталкивания.

Пример изображения, получаемого алгоритмом Fruchterman- Reingolda

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

Силовые алгоритмы (Frick et al,1995) Поэтому в работе (Frick et al 1995) была введена еще дополнительная сила: сила гравитации, которая зависит от количества ребер, инцидентных вершине v, то есть, от степени вершины v. Другое заметное улучшение касается ускорения сходимости алгоритма. Силы отталкивания и притяжения были изменены так, чтобы не надо было вычислять квадратный корень:

Силовые алгоритмы (Frick et al,1995) То есть, вершины с высокой степенью двигаются медленнее, они ведь «тяжелые»

Силовые алгоритмы (Frick et al,1995) Кроме того, была введена сила гравитации, которая толкает каждую вершину к общему центру тяжести.

Силовые алгоритмы (Frick et al,1995) Чтобы уменьшить количество итераций, вектор Fv(t-1) запоминался и сравнивался с Fv(t) То есть вычислялся угол  =  (Fv(t-1), F (t). Если угол небольшой, то есть движение происходит в том же самом направлении, то v(t) выбирался побольше, а если угол большой, то есть направление движения вершины менялось, то v(t) выбирался поменьше. Также подсчитывалась мера поворота, если угол  = (Fv(t-1), Fv(t) близок к 90, то v(t) тоже понижалось.

Силовые алгоритмы (Frick et al,1995)

Силовые алгоритмы (Frick et al,1995)

Силовые алгоритмы (Frick et al,1995)

Силовые алгоритмы (Frick et al,1995)

Силовые алгоритмы, сила гравитации

Силовые алгоритмы, сила гравитации

Силовые алгоритмы

Магнитное поле.

Магнитное поле. cm, ,  > 0 параметры настройки системы

Магнитные поля [SM95] Разные типы магнитных полей: Параллельное: все силы действуют в одном направлении, может быть полезно для получения изображений, направленных сверху вниз Концентрическое: сила действует по концентрическим окружностям, выделяет циклы Радиальное: сила действует радиально из некоторой точки

Магнитные силы комбинируются с электрической силой и силой пружины Магнитные силы комбинируются с электрической силой и силой пружины Алгоритм поиска равновесия Случайное начальное размещение и на каждой итерации смещать вершину в позицию с более низкой энергией Эта стратегия: Может размещать ориентированные графы (однонаправленные пружины с одним из трех полей) Может размещать ортогональные изображения, если применять комбинацию горизонтального и вертикального поля, а вершинам позволить принимать два направления Может размещать изображения с линиями под углом 45°(карты железных дорог, метро, путей) Успешно применяется к смешанным графам (графы, которые имеют одновременно и ориентированные и неориентированные ребра)

Влияние магнитного поля

Влияние магнитного поля

Влияние магнитного поля

S.Hong, D.Merrick H.Nascimento Automatic Visualization of Metro Maps, 2006

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

[Kamada, Kawai 89] В 1989 году Камада и Кавай ввели другой взгляд на то, что считать хорошим размещением. В то время как алгоритмы Идеса и Фрюхтермана-Рейнгольда стараются держать смежные вершины (связанные ребром), на одинаковом идеальном расстоянии, Камада и Кавай предложили рассматривать в качестве идеального расстояния между любыми вершинами соответствующее расстояние между ними по графу, вычисляемое как кратчайший путь между всеми парами вершин. Поскольку эта цель не всегда может быть достигнута для произвольных двумерных и трехмерных графов евклидова пространства, подход пытается привести систему пружин в такое состояние, что минимизация энергии системы соответствует минимизации разницы между Евклидовым расстоянием и расстоянием по графу.

[Kamada, Kawai 89] Была взята за основу потенциальная энергия пружины, имеющей естественную длину l, растянутой до длины d: EKK= kspring·(d - l)2 В этой модели нет раздельных сил притяжения и отталкивания. Вместо этого, вершины притягиваются или отталкиваются в зависимости от того, больше или меньше евклидово расстояние между ними, чем расстояние по графу. Разница расстояний подсчитывается по полному графу.

[Kamada, Kawai 89] Пусть dij означает длину кратчайшего пути между вершинами i и j в графе G(V, E). L - это длина единичного ребра на дисплее. Тогда lij= L*dij - это идеальная длина пружины, соединяющей вершины  i и j. Камада и Кавай предложили использовать в качестве L = L0/max i<j dij , где L0 - это длина стороны дисплея, а maxi<j dij - это диаметр графа, то есть расстояние между двумя наиболее удаленными вершинами. Сила пружины между вершинами i и j определяется как где K- это константа.

[Kamada, Kawai 89] Таким образом, получаем следующую функцию энергии:

[Kamada, Kawai 89] Требуется найти такие значения переменных, которые минимизируют функцию энергии EКК(x1,x2,...xn,y1,y2, , yn). Поскольку известно, что в локальном минимуме все частные производные равны 0, это соответствует решению системы из 2n нелинейных уравнений.

[Kamada Kawai 89] Уравнение можно решить при помощи итеративного подхода На каждом шаге перемещается одна вершина, которая минимизирует энергию, в то время как остальные вершины остаются зафиксированными Выбирается вершина, на которую действует наибольшая сила, то есть на каждом шаге этого алгоритма выбирается частица pm с наибольшим значением градиента m, где

[Kamada, Kawai 89] Вычислить di,j for 1 ≤ i j ≤ n; Вычислить li,j for 1 ≤ i j ≤ n; Вычислить ki,j for 1 ≤ i j ≤ n; initialize p1,p2,..., p; while (maxii >){ Пусть pm - это частица, удовлетворяющая m = maxii; while (m >){ /*вычислить x и xy решением следующей системы уравнений: */ xm := xm + x; ym := ym + y; } }

Пример размещения полученного методом Фрюхтерман-Рейнгольда

Пример результата размещения методом Камада-Кавая графа связей Автор_публикации с предварительным выделением несвязных компонент

[Kamada, Kawai 89] Алгоритм Камада-Кавая является вычислительно затратным, поскольку требует вычисления кратчайших путей между всеми парами вершин, что может быть сделано за время O(|V|3). Кроме этого он требует O(|V|2) памяти для хранения попарных расстояний между вершинами. Несмотря на свою затратность, его достоинством является простое и понятное определение того, что является хорошим размещением.

Метод барицентров(алгоритм Tutte,63) Исторически, метод барицентровТатта 1963 года был первым силовым алгоритмом для получения изображения без пересечений ребер 3-связного планарного графа. В отличие от большинства силовых алгоритмов, Татт гарантировал, что результирующее изображение не будет иметь пересечений ребер и более того, все грани изображения будут выпуклыми. Идея состоит в том, что если некоторую грань планарного графа зафиксировать на плоскости, то можно найти подходящие позиции для оставшихся вершин решением системы линейных уравнений, где каждая вершина представляется в виде выпуклой комбинации позиций ее соседей.

Метод барицентров(алгоритм Tutte,63) Вместо пружин переменной длины, как у Камада –Кавая, Татт считает, что идеальная длина всех пружин равна 0.

Метод барицентров(алгоритм Tutte,63) Разбить V на 2 подмножества: фиксированные вершины (не меньше 3) и свободные вершины Для достижения равновесия, выбрать такое размещение pv, что Fx(v) = 0 для всех свободных вершин; Аналогично, выбрать такое размещение pv, что Fy(v) = 0 для всех свободных вершин. Поэтому,

Метод барицентров(алгоритм Tutte,63) Все уравнения линейные. Количество уравнений и количество неизвестных равны количеству свободных вершин. Решается размещением каждой свободной вершины в барицентр ее соседей. Отсюда и название «метод барицентров»

Пример

Пример (2) V(J) = {v1, v2, v3} N(4) = {v1, v2, v3, v5} N(5) = {v2, v3, v4} L(G) =

Пример: Алгоритм Tutte Пусть координаты вершин имеют следующие значения: v1= (3,6), v2= (0, 3), v3 = (4, 1).   Соответствующая система линейных уравнений для вычисления x-координат вершин v4 и v5 через известные x-координаты вершин v1 v2 и v3 имеет вид: L41 v1x + L42 v2x + L43 v3x + L44 v4x + L45 v5x = 0 (2) L51 v1x + L52 v2x + L53 v3x + L54 v4x + L55 v5x = 0 (3)

Пример: Алгоритм Tutte В соответствии с нашим выбором v1x= 3, v2x= 0, v3x= 4. L44 равно степени вершины 4, то есть четырем, все остальные L4i равны минус единице. L55 равно степени вершины 5, то есть трем, L51 равно нулю, поскольку v5 и v1 не связаны ребром, все остальные L5i равны минус единице. Подставив эти значения, получим два выражения:  -1 *3 + (-1)*0 + (-1) * 4 + 4 v4x+ (-1)* v5x = 0 0*3+ (-1)*0 +(-1)*4+(-1)* v4x + 3* v5x = 0   В результате имеем систему уравнений: 4v4x -7 = v5x -v4x+3 v5x= 4  Решением этой системы будут v4x = 25/11, v5x = 23/11.

Пример: Алгоритм Tutte Точно так же y-координаты вершин v4 и v5 вычисляются через известные y-координаты вершин v1 , v2 и v3:   L 41 v1y + L 42 v2y + L 43 v3y + L 44 v4y + L 45 v5y = 0 L 51 v1y + L 52 v2y + L 53 v3y + L 54 v4y + L 55 v5y = 0   Стало быть, система уравнений имеет вид:  4v4y - v5y = 10 -v4y+3 v5y= 4, Решением системы будут v4y = 34/11 и v5y = 26/11.

Пример: Алгоритм Tutte

Algorithm Barycenter-Draw Algorithm Barycenter-Draw Вход: разбиение множества вершин V, V0: не менее 3 фиксированных вершин V1: множество свободных вершин Строго выпуклый многоугольник P с V0 вершинами Выход: размещение pv 1. Поместить вершины u V0 в вершины многоугольника P, а каждую свободную вершину в начало координат 2. repeat foreach свободной вершины v V1 do xv = 1/deg(v)(u,v)E xu yv = 1/deg(v)(u,v)E yu until xv and yv сходятся для всех свободных вершин v.

Метод барицентров(алгоритм Tutte,63) Основная теорема, доказанная Tutte (1963) утверждает, что барицентрическое размещение 3-связных планарных графов является планарным, все грани являются выпуклыми, если вершины одной грани в единственной планарной укладке зафиксированы на границе выпуклого многоугольника в соответствующем порядке. Такое размещение может быть получено за время O(nlogn).

Пример размещения, полученного методом барицентров

Ускорение силовых алгоритмов Экспериментальное сравнение базового алгоритма Fruchterman-Reingold, алгоритма GEM (Frick et al.,), метода the Kamada and Kawai, simulated annealing метода Davidson and Harel , осуществлялось Brandenburg et al. в 1995 году. Эксперименты показали, что все алгоритмы генерировали сравнительно хорошие размещения для небольших графов размера (|V | + |E|) < 180 менее чем за 2 минуты. Для больших графов они не очень подходят. Например, GEM требовал в тот момент 71 секунду для построения изображения графа, содержащего 256 вершин и представлявшего собой регулярную квадратную сетку. Оценка времени работы для графа, содержащего 25600 вершин, на таком же компьютере потребовало бы более двух лет. Понятно, что исследователи стали искать новые идеи позволявшие применять силовые алгоритмы для построения изображений больших графов.