Это не официальный сайт wikipedia.org 01.01.2023

Послойное рисование графа — Википедия
Википедия

Послойное рисование графа

Послойное рисование графа или иерархическое рисование графа — это способ визуализации графов, в котором вершины ориентированного графа рисуются горизонтальными рядами или слоями с рёбрами, преимущественно направленными вниз[1][2][3]. Такой способ известен как стиль Сугиямы визуализации графов, по имени Козо Сугиямы, который первым разрабатывал этот стиль[4].

Послойное представление ориентированного ациклического графа, созданное пакетом Graphviz

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

Алгоритм компоновкиПравить

Построение послойной визуализации графов происходит в несколько этапов:

  • Если входной граф ещё не является ориентированным ациклическим графом, определяется множество рёбер, обращение которых делает граф ациклическим. Нахождение наименьшего возможного такого множества рёбер является NP-полной задачей нахождения разрезающего циклы набора рёбер, так что здесь часто используется эвристический жадный алгоритм вместо точных оптимизационных алгоритмов[1][2][3][5][6][7]. Точное решение этой задачи можно сформулировать с помощью целочисленного программирования[3]. Альтернативно, если число обратных рёбер очень мало, эти рёбра можно найти с помощью фиксированно-параметрически разрешимого алгоритма[en][8].
  • Вершины ориентированного ациклического графа, полученного на первом этапе назначаются слоям, так что каждая дуга идёт сверху вниз. Целью этого этапа является создание малого количества уровней, достижения малого количества рёбер, которые проходят через большое количество слоёв, и сбалансированное назначение вершин по слоям[1][2][3]. Например, по теореме Мирского[en], распределение вершин по слоям согласно самого длинного пути, начиная с самой верхней вершины даёт распределение с минимальным числом слоёв[1][3]. Можно использовать алгоритм Коффмана — Грэма[en], чтобы найти распределение по слоям с предопределённым ограничением числа вершин на слой и приблизительно минимизирует число слоёв[1][2][3]. Задача минимизации ширины самого широкого слоя NP-трудна, но может быть решена методом ветвей и границ или эвристическими приблизительными алгоритмами[3]. Альтернативно, задача минимизации общего числа слоёв, охватываемых рёбрами (без ограничений на число вершин в слое) можно решить с помощью линейного программирования[9]. Процедуры целочисленного программирования, хотя они более затратны в смысле времени вычисления, могут быть использованы с целью комбинации минимизации рёбер с ограничением на число вершин на уровень[10].
  • Рёбра, которые охватывают несколько слоёв, заменяются на пути с дополнительными вершинами, так что после этого шага каждая дуга в расширенном графе соединяет две вершины соседних слоёв рисунка[1][2].
  • В качестве дополнительного (необязательного) шага может быть использован уровень концентрации рёбер (или слияния пересечений) между двумя существующими уровнями вершин, чтобы сократить плотность дуг путём замены полных двудольных подграфов на звёзды через эти концентраторы[3][11][12].
  • Вершины внутри каждого слоя переставляются в попытке сократить число пересечений дуг, соединяющих их с предыдущим слоем[1][2][3]. Задачи нахождения минимального числа пересечений или максимального множества дуг без пересечений NP-полна, если даже пытаемся упорядочить один слой за раз[13][14], так что снова обычно прибегают к эвристическим методам, таким как размещение каждой вершины в позиции, определённой средним или медианой позиций соседей на предыдущем уровне, и перестановкой затем смежных пар, пока такие перестановки уменьшают число пересечений[1][2][9][14][15]. Альтернативно, упорядочение вершин в слое за один раз может быть выбрано с помощью алгоритма, который фиксированно-параметрически разрешимы[en] по числу пересечений между слоем и предыдущим уровнем[3][16].
  • Каждой вершине назначается координата внутри слоя, которая согласуется с предыдущим шагом[1][2]. На этом шаге подразумевается вставка дополнительных вершин в линию между двумя соседями (чтобы избежать излишние изломы) и размещение каждой вершины в центральное положение по отношению к соседям[3]. Оригинальная работа Сугиямы предполагала формулировку данного шага в виде задачи квадратичного программирования. Более поздний метод Брандеса и Кёпфа работает за линейное время и гарантирует максимум два излома на дугу[3][17].
  • Дуги, обращённые на первом этапе алгоритма, возвращаются к их начальному направлению, добавленные вершины удаляются из графа, после чего рисуются вершины и рёбра. Чтобы избежать пересечения между вершинами и дугами, дуги, которые охватывают несколько слоёв, могут быть нарисованы как ломаные линии или в виде кусочно-полиниомиальных кривых через добавочные вершины на внутренних слоях, через которые проходит дуга[1][2][9].

РеализацииПравить

В своей простейшей форме алгоритмы послойной визуализации графов могут требовать время O(mn) на графах с n вершинами и m рёбрами, поскольку может быть создано большое количество добавочных вершин. Однако, для некоторых вариантов алгоритма, можно смоделировать эффект дополнительных вершин без фактического их добавления, что приводит к реализации алгоритма с почти линейному времени выполнения[18].

Язык описания «DOT» в пакете Graphviz создаёт поуровневые представления[9]. Алгоритм послойной визуализации графов включён также в библиотеку Microsoft автоматической компоновки графов[en][19] и во фреймворк Tulip[en][20].

ВариацииПравить

Хотя обычно рисование осуществляется с вершинами по строкам и с рёбрами, идущими сверху вниз, алгоритмы послойной визуализации графов могут вместо это вершины располагать вертикально по столбцам, а рёбра рисовать слева направо[21]. Тот же самый фреймворк может использовать радиальное расположение, при котором вершины располагаются на концентричных окружностях (с центром в некотором начальном узле)[3][22], а также трёхмерное послойное рисование графов[3][23].

При послойной визуализации графов с большим числом длинных дуг, хаос можно уменьшить путём группировки множеств рёбер в пучки и направление их через то же самое множество добавочных вершин[24]. Аналогично, для рисования многих пересекающихся рёбер между парами последовательных слоёв рёбра в максимальных двудольных подграфах могут быть сгруппированы в сливающиеся пакеты[25].

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

Для послойного рисования решёток понятий может быть использован гибридный подход, комбинирующий подход Сугиямы с аддитивными методами (в которых каждая вершина представляет множество и позиция вершины является суммой векторов, представляющих элементы в множестве). В этом гибридном подходе фазы перестановки вершин и назначения координат алгоритма заменяются одним шагом, в котором каждая горизонтальная позиция каждой вершины выбирается как сумма скалярных представлений элементов для этой вершины[27]. Методы послойной визуализации графов использовались для обеспечения начального расположения для в силовых алгоритмах визуализации графов[28].

ПримечанияПравить

  1. ↑ 1 2 3 4 5 6 7 8 9 10 Di Battista, Eades и др., 1998, с. 265–302.
  2. ↑ 1 2 3 4 5 6 7 8 9 Bastert, Matuszewski, 2001, с. 87–120.
  3. ↑ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Healy, Nikolov, 2014, с. 409–453.
  4. ↑ Sugiyama, Tagawa, Toda, 1981, с. 109–125.
  5. ↑ Berger, Shor, 1990, с. 236–243.
  6. ↑ Eades, Lin, Smyth, 1993, с. 319–323.
  7. ↑ Eades, Lin, 1995, с. 15–26.
  8. ↑ Chen, Liu, Lu и др., 2008, с. 1.
  9. ↑ 1 2 3 4 Gansner, Koutsofios, North, Vo, 1993, с. 214–230.
  10. ↑ Healy, Nikolov, 2002, с. 16–30.
  11. ↑ Newbery, 1989, с. 76–85.
  12. ↑ Eppstein, Goodrich, Meng, 2004, с. 184–194.
  13. ↑ Eades, Whitesides, 1994, с. 361–374.
  14. ↑ 1 2 Eades, Wormald, 1994, с. 379–403.
  15. ↑ Mäkinen, 1990, с. 175–181.
  16. ↑ Dujmović, Fernau, Kaufmann, 2008, с. 313–323.
  17. ↑ Brandes, Köpf, 2002, с. 31–44.
  18. ↑ Eiglsperger, Siebenhaller, Kaufmann, 2005, с. 155–166.
  19. ↑ Nachmanson, Robertson, Lee, 2008, с. 389–394.
  20. ↑ Auber, 2004.
  21. ↑ Baburin, 2002, с. 366–367.
  22. ↑ Bachmaier, 2007, с. 583–594.
  23. ↑ Hong, Nikolov, 2005, с. 69–74.
  24. ↑ Pupyrev, Nachmanson, Kaufmann, 2011, с. 329–340.
  25. ↑ Eppstein, Goodrich, Meng, 2007, с. 439–452.
  26. ↑ Dujmović, Fellows, Kitching и др., 2008, с. 267–292.
  27. ↑ Cole, 2001, с. 47–53.
  28. ↑ Schwikowski, Uetz, Fields, 2000, с. 1257–126.

ЛитератураПравить

Источник — https://ru.wikipedia.org/w/index.php?title=Послойное_рисование_графа&oldid=117243725