Размещение ориентированных графов (минимизация пересечений ребер ) Апанович З.В. apanovich@iis.nsk.su Тел:3309344 К. 217. - презентация

1 Размещение ориентированных графов (минимизация пересечений ребер ) Апанович З.В. Тел: К. 217

2 Минимизация количества пересечений ребер После фазы разбиения на слои имеется собственный поуровневый граф (L 1 L 2 …. …L h, E) возможно, с большим количеством пересечений ребер. Пересечения ребер нам не дают никакой полезной информации о структуре графа, а понимание затрудняют. Поэтому желательно их минимизировать.

3 Минимизация количества пересечений ребер пересечение шаг пересечений

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

5 Просмотр графа слой за слоем (Layer-by- layer sweep) Просмотр графа слой за слоем осуществляется следующим образом: Фиксируются относительные позиции вершин в первом слое (на первом шаге можно выбрать либо случайные позиции либо каким-то образом оптимизированные. ) Затем во втором слое меняется порядок вершин, с тем чтобы минимизировать количество пересечений между ребрами, концы которых расположены в первом и втором слое. Затем порядок вершин во втором слое фиксируется и начинаются перестановки в третьем слое и т.д. Когда все слои обработаны, можно пойти в обратном порядке: от последнего слоя к первому.

6 Просмотр графа слой за слоем (Layer-by- layer sweep) Как вариант, можно зафиксировать порядки вершин в слоях L i-1, L i+1 и начать менять порядок вершин в слое L i, чтобы уменьшить количество пересечений ребер, концами которых являются слои L i-1, L i, L i+1.

7 Проблема двухслойной минимизации количества пересечений фиксированный свободный L2L2 L3L ? L2L2 L3L3 Таким образом, чаще всего требуется решить множество проблем двухслойной минимизации количества пересечений: Минимизировать количество пересечений между двумя смежными слоями, L i и L i+1. При этом в слое L i порядок вершин фиксирован, а в слое L i+1 – меняется.

8 Проблема двухслойной минимизации количества пересечений Итак, G = (V 1,V 2, E) - это 2-слойный, двудольный граф, чьи вершины присвоены слоям L 1 и L 2, E V 1 V 2. Упорядочение вершин определяется перестановкой i для множества V i. Упорядочение вершин во множестве V 1 задается перестановкой 1, а во множестве V 2 - перестановкой 2. Будем обозначать cross(G, 1, 2 ) – количество пересечений в прямолинейном изображении графа G, заданном перестановками 1 и 2.

9 Проблема двухслойной минимизации количества пересечений Зафиксируем перестановку 1 множества V 1, и обозначим минимальное количество пересечений, которого можно достичь, меняя порядок вершин во множестве V 2, через opt(G, 1 ) : opt(G, 1 ) = min cross(G, 1, 2 ) 2 Тогда проблема односторонней минимизации пересечений формулируется следующим образом: Дан двудольный граф G = (V 1,V 2, E) и перестановка 1 множества вершин V 1 Найти перестановку 2 множества V 2, которая минимизирует количество пересечений в изображении графа G, то есть cross(G, 1, 2 ) = opt(G, 1 ).

10 Значение пересечений (crossing number) Для рассмотрения этой проблемы существенным является понятие значение пересений (crossing number) Предположим, что 1 множества V 1 зафиксирована. Определим для каждой пары вершин u,v V 2 значение пересечений c uv – количество пересечений ребер, инцидентных вершине u, и ребер, инцидентных вершине v, при условии что 2 (u) < 2 (v). c uu = 0 для всех u V. С uv = 3 C vu = 5

11 Значение пересечений (crossing number) матрица пересечений Очевидно, что значение пересечений зависит только от относительных позиций вершин и не зависит от позиций остальных вершин. Поэтому можно построить матрицу пересечений, вычислив попарно значения пересечений для всех вершин V 2. Существует алгоритм, вычисляющий все числа пересечений за время O(|V 1 | +(|V 2 |+ |E| + c), где с- это количество пересечений ребер. с e,f = 2; с e,g = 1; с f,g = 2

12 Значение пересечений (crossing number) матрица пересечений с f,е = 1

13 Значение пересечений (crossing number) матрица пересечений с g,e = 0

14 Значение пересечений (crossing number) матрица пересечений с g,f = 3

15 Значение пересечений (crossing number) Значение пересечений можно использовать для вычисления суммарного количества пересечений cross(G, 1, 2 ):

16 Значение пересечений (crossing number) Используя значения пересечений, можно оценить нижнюю границу количества пересечений: Нижняя оценка верна, потому что для двух вершин u и v либо 2 (u)< 2 (v) либо 2 (v)< 2 (u)

17 Эвристики для минимизации количества пересечений Наиболее простыми и очевидными являются метод барицентров и метод медиан для минимизации количества пересечений. Для упорядочения вершин во множестве V 2, вычисляется среднее значение (или барицентр или медиану) позиций соседей каждой вершины u V 2, расположенных в слое V 1 и упорядочивают вершины во множестве V 2 в соответствии с найденными значениями.

18 Метод барицентров Метод барицентров (Sugiyama et al, 1981) основан на предположении, что для того, чтобы пересечений было немного, желательно расположить каждую вершину поближе к ее соседям Если значения барицентров у двух вершин равны, то одному из них прибавить небольшую величину, а потом отсортировать все вершины по значению этих барицентров. Время вычислений, необходимое для вычисления барицентра одной вершины, пропорционально степени вершины, поэтому барицентры можно вычислить за линейное время. После этого вершины еще надо упорядочить в соответствии со значением барицентра. Это требует O(|V 2 |log |V 2 |)

19 Метод медиан(Eades, Wormald,1994) В медианной эвристике координата каждой вершины определяется медианой координат соседей вершины. Медиана определяется следующим образом: Предположим, соседями вершины u являются вершины v 1,v 2,…v j. При этом они упорядочены так, что 1 (v 1 )< 1 (v 2 )<… < 1 (v j ) med(u)= 1 (v j/2

20 Метод медиан(Eades, Wormald,1994) Это определение отличается от классического понятия медианы, потому что в случае четного j медиан будет две. В этом случае предлагается всегда выбирать левую медиану. Если у вершины соседей нет, ее медиана устанавливается в ноль. Затем вершины сортируются по значению их медиан. Сложность вычисления медиан тоже линейна и зависит от степени вершины u. Другие эвристики: 2. Выбирать среднее арифметическое двух медиан (average median) 3. Если количество соседей вершины четно, брать барицентр ее соседей (semi median)

21 Метод медиан(Gansner et al, 1993) Существует вариант метода медиан (weighted median), когда в случае четной степени вершины, такой что deg(u)>2, медиана вычисляется по формуле: med el (u) – левая из двух медиан = 1 (v j/2 ) med er (u)- правая из двух медиан= 1 (v j/2+1 ) (3*(100-60) + 60*(3-1))/((3-1)+( ))=(3*40+60*2)/42 6

22 Свойства методов барицентров и медиан Известно, что если существует изображение без пересечений ребер, то и метод барицентров и метод медиан его найдет: Утверждение Дан двудольный граф G = (V 1,V 2,E). Если opt(G, 1 )= 0, то bary(G, 1 )= med(G, 1 )= 0 С другой стороны, Ни один из этих методов не может гарантировать оптимальное решение в случае наличия пересечений ребер.

23 Нижняя граница метода барицентров Утверждение Для любого n существует 2-слойный ориентированный граф G = (V 1,V 2,E), |V 1 |=n, |V 2 |=2 и упорядочением 1 таким, что количество пересечений ребер, полученных методом барицентров, превышает минимальное количество пересечений в ( n) раз: bary(G, 1 )/ opt(G, 1 ) ( n)

24 Наихудший случай для метода барицентров V 2 = {u,v}; V 1 = {v 1,v 2,...v n }, где n = k 2 + k-1 N(v)={v k 2 } N(u) ={v 1,v k 2 +1, …, v k 2 +k-1 } - всего k элементов

25 Нижняя граница метода барицентров 1) bary(v) = k 2 Поскольку bary(u) < bary(v) то и вершина u будет размещена левее вершины v, и при этом возникнет k-1 пересечений. Но если бы вершина v была расположена левее вершины u, то пересечений было бы всего одно! То есть, Поскольку было выбрано n = k 2 + k-1, к имеет порядок O( n) Значит, утверждение доказано. 2)

26 Наихудший случай для медианной эвристики Множество V 1 имеет n = 4k+2 вершин Множество V 2 имеет 2 вершины v и u Соседи вершин v и u следуют вперемешку. N(v) = {v 1,…,v k, v 2k+2,…,v 3k+2 } Медианой для v будет элемент с номером v 2k+2 N(u) ={v k+1,…,v 2k+1, v 3k+3,…v 4k+2 } Медианой для u будет элемент с номером v 2k+1

27 Наихудший случай для медианной эвристики Теперь подсчитаем количество пересечений при таком расположении вершин. med(G, 1 ) = N 1 (v) N 1 (u) + N 1 (v) ) N 2 (u)+ N 2 (v) N 2 (u) = k*(k+1) + k*k + (k+1)*k= 2k(k+1)+k 2 В то время как при размещении v левее u opt(G, 1 ) = (k+1) 2

28 Наихудший случай для медианной эвристики Значит, med(G, 1 )/ opt(G, 1 )= Таким образом, мы доказали утверждение: Для любого n существует 2-слойный ориентированный граф G=(V 1,V 2,E) такой что |V 1 |=n, |V 2 |=2 и упорядочением 1 при котором med(G, 1 )/ opt(G, 1 ) 3-O(1/n)

29 Сравнение методов барицентров и медиан Теперь сравним две полученные оценки. Нижняя граница количества пересечений, которые можно получить методом барицентров, оценивается как n opt((G, 1 ). То есть его отношение к оптимальному количеству пересечений возрастает с возрастанием n. А метод медиан пропорционален opt((G, 1 ) постоянное количество раз. Поэтому, с теоретической точки зрения, метод медиан лучше, чем метод барицентров. Еще одно теоретическое преимущество состоит в том, что у метода медиан есть еще и верхняя граница, в соответствии со следующей теоремой.

30 Сравнение методов барицентров и медиан Теорема: Для всех двухслойных графов G=(V 1,V 2,E) и всех упорядочений вершин 1 на множестве V 1 med(G, 1 ) 3 opt((G, 1 ) Теорема: Для всех двухслойных графов G=(V 1,V 2,E), степени всех вершин которых < 3 и всех упорядочений вершин 1 на множестве V 1 med(G, 1 ) 2opt((G, 1 )

31 Минимизация количества пересечений при помощи сортировки В зависимости от значений с uv и c vu можно попробовать определить относительный порядок вершин u и v. Но такое позиционирование не может быть ни частичным, ни линейным порядком, иначе можно было бы решить NP- полную проблему простой сортировкой. Значение пересечений не задает отношение порядка!

32 Минимизация количества пересечений при помощи сортировки Отношение, индуцируемое значением пересечений, не обладает свойством транзитивности Пример c bc = c cb =1 (B = C) c ca = 3,c ac = 4 (C < A) c ab = 1, c ba = 2 (A < B) То есть, если бы отношение было транзитивным, мы бы Имели А A

33 Минимизация количества пересечений при помощи сортировки С другой стороны, выполняется закон трихотомии: То есть, для любой пары вершин верно одно из соотношений: Либо A B

34 Минимизация количества пересечений при помощи сортировки Несколько простых эвристических методов требуют предварительного вычисления значений пересечений, этот процесс требует времени O(|V 2 | 2 ). Эвристика Greedy switch работает подобно методу пузырьков, она переставляет соседние пары вершин, если при этом значение пересечений уменьшается. Greedy switch (Adjacent exchange) repeat for u:=1 to |V 2 |-1 do If c u,u+1 >c u+1,u then Переставить вершины в позициях u и u+1 until количество пересечений перестает уменьшаться

35 Наихудший пример для метода Greedy switch (AdjacentExchange) Makinen, 1990,Gansner, 1993

36 Algorithm split(1,|V 2 |) Eades&Kelly,1986 Algorithm split(i,j:1,…,|V 2 |) if j>i then pivot:=low:=i; high:=j; for k:=i+1 to j do if c k,pivot < c pivot,k then (k):=low; low:=low + 1; else (k):=high; high:=high-1; } /*low==high*/ (pivot):=low; Copy (i,…,j) в 2 (i,…,j); split(i, low-1); split(high+1,j); } Аналог быстрой сортировки, Дает результаты лучше, чем метод барицентров или метод медиан ценой более долгого времени работы O(|V 2 | 2 )

37 Sifting (Ruddel,1993), Matuszewski,1999 foreach u V 2 do Сдвинуть u в самую левую позицию; crossings:= 2(u)< 2(v) c uv ; min_crossings:=crossings; for p:=1 to |V 2 |-1 do –crossings:=crossings - c p(p+1) + c (p+1)p ; –Переставить вершины в позициях p и p+1; –if crossings < min_crossings then min_crossings:=crossings; best_position:=p; } Переместить u в позицию best_position; }

38 Оптимальная минимизация пересечений Junger, Mutzel «2-layer straight line crossing minimization :performance of exact and heuristic algorithms»,1997) Можно вычислить оптимальное количество пересечений методом branch and cut. Очень быстро работает для небольших графов (наилучший порядок 60 вершин в перестанавливаемом слое находится быстрее, чем любой эвристикой за исключением методов барицентров и метода медиан)

39 Оптимальная минимизация пересечений Задача односторонней минимизации пересечений формулируется как задача линейного программирования. Для этого вводятся если i (k) < i (l) в противном случае Верхний индекс – номер слоя, Нижние индексы – позиции вершин

40 Оптимальная минимизация пересечений Предположим, что имеется два ребра с концами (вершинами) (i, k) и (j, l) Если k, l L 1, а i, j L 2 k N(i), l N(j) то их пересечение возможно в двух случаях:

41 Оптимальная минимизация пересечений Тогда мы можем выразить общее число пересечений в терминах : Cross( 2 ) = cross( 2 ) = Эта запись означает в точности все возможные конфигурации индексов i, j, k, l, дающие пересечения соответствующих ребер. Вершины i, j расположены во втором слое, k, l - в первом.

42 Оптимальная минимизация пересечений С другой стороны, количество пересечений можно выразить через значения пересечений с ij В то же время, каждое с ij можно выразить через. Если i находится слева от j то, чтобы было пересечение между ребрами (i,k) и (j, i) необходимо, чтобы i было расположено левее (раньше) k с ij =

43 Оптимальная минимизация пересечений Тогда выражение 1 можно переписать следующим образом:

44 Оптимальная минимизация пересечений Переобозначив n 2 через n, через x ij, c ij - c ji через a ij Получили проблему линейного упорядочения: Минимизировать При ограничениях : 0 x ij + x jk - x ik 1 для 1 i < j < k n /*это действительно перестановка */ 0 x ij 1 для 1 i < j n x ij Z для 1 i < j n После того, как эта проблема будет решена, останется добавить к найденному значению константную величину:

45 Обозначения на схемах Lowerbound -Тривиальная нижняя граница: Minimum – минимальное значение, вычисленное методом branch and cut Gre-swi = greedy switch

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

47 Оптимальная минимизация пересечений Время вычислений для 100 примеров графов вершин с возрастающей плотностью

48 Оптимальная минимизация пересечений Если перестановки разрешены в обоих слоях, можно существенно улучшить результат. Минимизация количества пересечений при фиксированном нижним слое, 48 пересечений Минимизация пересечений, с возможностью изменения позиций в обоих слоях, 19 пересечений

49 Примеры работы алгоритмов при двусторонней минимизации Применение оптимального однослойного алгоритма(branch- and-cut), 30 пересечений ( просто итерировали оптимальный алгоритм от слоя к слою, пока улучшения не прекратились)

50 Примеры работы алгоритмов при двусторонней минимизации Применения метода барицентров, 10 пересечений

51 Примеры работы алгоритмов при двусторонней минимизации Оптимальное решение, 4 пересечения. Выводы: 1. В случае, когда свободный слой содержит не более 60 вершин – вполне можно найти точное решение за разумное время 2. В двуслойном случае – метод барицентров наилучший.

52 Проблема к-слойной минимизации пересечений ребер Алгоритм Tutte Фиксируются позиции вершин в первом и последнем слое. А во всех остальных слоях x- координата вершины u вычисляется как барицентр смежных с ней вершин: X(u) = После чего требуется решить разреженную систему линейных уравнений для того, чтобы вычислить x(u) для каждой вершины u. После этого вершины упорядочиваются по x- координате

53 Планаризация(Mutzel,1997) Отрисовка графа при помощи планаризации, 34 пересечения Отрисовка графа с минимальным количеством пересечений, 24 пересечения

54 Плотные графы и концентрация ребер Доказано ( Di Battista et al, 1999), что для плотных графов количество пересечений близко к оптимальному для любого упорядочения вершин Если две вершины имеют много соседей, то оба значения пересечений велики, как не переставляй. 1)Все эвристики работают «лучше» при возрастании плотности 2)Все изображения нечитаемы, потому что пересечений много.

55 Плотные графы и концентрация ребер Проблема концентрации ребер : Дан двудольный граф G=(V 1,V 2, E). Найти множество полных двудольных графов G 1, G 2, …, G s (возможно, с наложением), которое включает все ребра исходного графа G и минимизирует количество ребер в эквивалентном трехдольном представлении. Про эту проблему неизвестно, является ли она NP-трудной. Есть похожая проблема, про которую известно, что она является NP-трудной. Дан двудольный граф G=(V 1,V 2, E). Найти минимальное множество полных двудольных графов G 1, G 2, …, G s (возможно, с наложением), которое покрывает все ребра исходного графа.