Рисование многослойного графика

Рисование графа с вершинами в горизонтальных слоях

Многослойный рисунок ориентированного ациклического графа , созданный Graphviz.

Рисование многослойного графа или изображение иерархического графа — это тип изображения графа , в котором вершины ориентированного графа рисуются в горизонтальных строках или слоях с краями, обычно направленными вниз. ^{[1] [2] [3]} Он также известен как графическое рисование в стиле Сугияма в честь Кодзо Сугиямы , который первым разработал этот стиль рисования. ^[4]

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

Алгоритм раскладки

Построение чертежа слоистого графа происходит в последовательность шагов:

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

Реализации

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

Инструмент «Точка» в Graphviz создает многослойные рисунки. ^[9] Алгоритм рисования многоуровневых графов также включен в Microsoft Auto Graph Layout ^[19] и Tulip . ^[20]

Вариации

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

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

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

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

Рекомендации

1. Ди Баттиста, Джузеппе; Идс, Питер ; Тамассия, Роберто ; Толлис, Иоаннис Г. (1998), «Многослойные рисунки орграфов», Рисование графиков: алгоритмы визуализации графов , Прентис Холл , стр. 265–302, ISBN 978-0-13-301615-4.
2. Бастерт, Оливер; Матушевский, Кристиан (2001), «Многослойные рисунки орграфов», Кауфманн, Майкл; Вагнер, Доротея (ред.), Рисование графиков: методы и модели , Конспекты лекций по информатике , том. 2025, Springer-Verlag, стр. 87–120, номер документа : 10.1007/3-540-44969-8_5, ISBN. 978-3-540-42062-0.
3. Хили, Патрик; Николов, Никола С. (2014), «Рисование иерархических графов», в Тамассии, Роберто (ред.), Справочник по рисованию и визуализации графиков, CRC Press, стр. 409–453..
4. Сугияма, Кодзо; Тагава, Сёдзиро; Тода, Мицухико (1981), «Методы визуального понимания иерархических системных структур», Транзакции IEEE по системам, человеку и кибернетике , SMC-11 (2): 109–125, doi : 10.1109/TSMC.1981.4308636, MR  0611436, S2CID  8367756.
5. Бергер, Б .; Шор, П. (1990), «Алгоритмы аппроксимации для проблемы максимального ациклического подграфа», Труды 1-го симпозиума ACM-SIAM по дискретным алгоритмам (SODA'90), стр. 236–243, ISBN 9780898712513.
6. Идс, П .; Лин, X.; Смит, В.Ф. (1993), «Быстрая и эффективная эвристика для решения задачи множества дуг обратной связи», Information Processing Letters , 47 (6): 319–323, doi :10.1016/0020-0190(93)90079-O.
7. Идс, П .; Лин, X. (1995), «Новая эвристика для проблемы множества дуг обратной связи», Австралийский журнал комбинаторики , 12 : 15–26..
8. Чен, Цзянер; Лю, Ян; Лу, Сунцзянь; О'Салливан, Барри; Разгон, Игорь (2008), «Алгоритм с фиксированными параметрами для задачи множества вершин с направленной обратной связью», Журнал ACM , 55 (5): 1, doi : 10.1145/1411509.1411511, S2CID  1547510.
9. Ганснер, скорая помощь; Куцофиос, Э.; Норт, Южная Каролина; Во, К.-П. (1993), «Техника рисования ориентированных графов», IEEE Transactions on Software Engineering , 19 (3): 214–230, doi : 10.1109/32.221135.
10. Хили, Патрик; Николов, Никола С. (2002), «Как расслоить ориентированный ациклический граф», Рисование графа: 9-й Международный симпозиум, GD 2001, Вена, Австрия, 23–26 сентября 2001 г., Переработанные статьи , Конспекты лекций по информатике, том. 2265, Springer-Verlag, стр. 16–30, номер документа : 10.1007/3-540-45848-4_2 , ISBN. 978-3-540-43309-5, МР:  1962416.
11. Ньюбери, Ф.Дж. (1989), «Концентрация краев: метод кластеризации ориентированных графов», Труды 2-го международного семинара по управлению конфигурацией программного обеспечения (SCM '89), Принстон, Нью-Джерси, США , Ассоциация вычислительной техники, стр. 76–85, номер домена : 10.1145/72910.73350 , ISBN. 0-89791-334-5, S2CID  195722969.
12. Эппштейн, Дэвид ; Гудрич, Майкл Т .; Мэн, Джереми Ю (2007), «Рисунки слитных слоев», в Пач, Янош (ред.), Рисунки слитных слоев , Конспекты лекций по информатике, том. 47 (изд. 3383), Springer-Verlag, стр. 184–194, arXiv : cs.CG/0507051 , doi : 10.1007/s00453-006-0159-8, S2CID  1169.
13. Идс, Питер ; Уайтсайдс, Сью (1994), «Рисование графиков в двух слоях», Theoretical Computer Science , 131 (2): 361–374, doi : 10.1016/0304-3975(94)90179-1.
14. Идс, Питер ; Вормальд, Николас К. (1994), «Пересечения ребер на рисунках двудольных графов», Algorithmica , 11 (4): 379–403, doi : 10.1007/BF01187020, S2CID  22476033.
15. Мякинен, Э. (1990), «Эксперименты по построению двухуровневых иерархических графов», Международный журнал компьютерной математики , 36 (3–4): 175–181, doi : 10.1080/00207169008803921.
16. Дуймович, Вида ; Фернау, Хеннинг; Кауфманн, Майкл (2008), «Пересмотр алгоритмов с фиксированными параметрами для минимизации одностороннего пересечения», Журнал дискретных алгоритмов , 6 (2): 313–323, doi : 10.1016/j.jda.2006.12.008 , MR  2418986.
17. Брандес, Ульрик ; Кёпф, Борис (2002), «Быстрое и простое присвоение горизонтальных координат», Рисование графика (Вена, 2001) , Конспекты лекций по информатике, том. 2265, Берлин: Springer, стр. 31–44, номер документа : 10.1007/3-540-45848-4_3 , ISBN. 978-3-540-43309-5, МР  1962417.
18. Эйгльспергер, Маркус; Зибенхаллер, Мартин; Кауфманн, Майкл (2005), «Эффективная реализация алгоритма Сугиямы для рисования многослойных графов», Graph Drawing, 12-й Международный симпозиум, GD 2004, Нью-Йорк, штат Нью-Йорк, США, 29 сентября – 2 октября 2004 г., Пересмотренные избранные статьи , лекция Заметки по информатике, том. 3383, Springer-Verlag, стр. 155–166, номер документа : 10.1007/978-3-540-31843-9_17 , ISBN. 978-3-540-24528-5.
19. Нахмансон, Лев; Робертсон, Джордж; Ли, Бонгшин (2008), «Рисование графиков с помощью GLEE» (PDF) , в Хонг, Сок-Хи ; Нисидзеки, Такао ; Цюань, Ву (ред.), Рисование графиков, 15-й Международный симпозиум, GD 2007, Сидней, Австралия, 24–26 сентября 2007 г., Пересмотренные статьи , Конспекты лекций по информатике, том. 4875, Springer-Verlag, стр. 389–394, номер документа : 10.1007/978-3-540-77537-9_38 , ISBN. 978-3-540-77536-2.
20. Обер, Дэвид (2004), «Тюльпан - огромная структура визуализации графов», Юнгер, Майкл; Мутцель, Петра (ред.), Программное обеспечение для рисования графиков , Springer-Verlag, ISBN 978-3-540-00881-1.
21. Бабурин, Данил Э. (2002), «Некоторые модификации подхода Сугиямы», Рисунок графика, 10-й Международный симпозиум, GD 2002, Ирвин, Калифорния, США, 26–28 августа 2002 г., Переработанные статьи , Конспекты лекций по информатике, том. 2528, Springer, стр. 366–7, номер документа : 10.1007/3-540-36151-0_36 , ISBN. 978-3-540-00158-4.
22. Бахмайер, Кристиан (2007), «Радиальная адаптация структуры Сугиямы для визуализации иерархической информации», IEEE Transactions on Visualization and Computer Graphics , 13 (3): 583–594, doi : 10.1109/TVCG.2007.1000, PMID  17356223, S2CID  9852297.
23. Хон, Сок Хи ; Николов, Никола С. (2005), «Многослойные рисунки ориентированных графов в трех измерениях», Труды Азиатско-Тихоокеанского симпозиума по визуализации информации 2005 г. (APVis '05), Конференции по исследованиям и практике в области информационных технологий, том. 45, стр. 69–74, ISBN. 9781920682279.
24. Пупырев, Сергей; Нахмансон, Лев; Кауфманн, Майкл (2011), «Улучшение макетов многоуровневых графов с помощью объединения ребер», Graph Drawing, 18-й Международный симпозиум, GD 2010, Констанц, Германия, 21–24 сентября 2010 г., Пересмотренные избранные статьи , Конспекты лекций по информатике, том. 6502, Springer, стр. 329–340, номер doi : 10.1007/978-3-642-18469-7_30 , ISBN. 978-3-642-18468-0.
25. Эппштейн, Дэвид ; Гудрич, Майкл Т .; Мэн, Джереми Ю (2007), «Слитные многослойные рисунки», Algorithmica , 47 (4): 439–452, arXiv : cs/0507051 , doi : 10.1007/s00453-006-0159-8, S2CID  1169.
26. Дуймович, В .; Товарищи, MR; Китчинг, М.; Лиотта, Г.; Маккартин, К.; Нисимура, Н.; Рагде, П.; Розамонд, Ф.; Уайтсайдс, С. (2008), «О параметризованной сложности построения многослойных графов», Algorithmica , 52 (2): 267–292, doi : 10.1007/s00453-007-9151-1, S2CID  2298634.
27. Коул, Ричард (2001). «Автоматическая компоновка решеток понятий с использованием слоистых диаграмм и аддитивных диаграмм». Материалы 24-й Австралийской конференции по информатике. АКСК 2001 . Том. 23. С. 47–53. дои : 10.1109/ACSC.2001.906622. ISBN 0-7695-0963-0. S2CID  7143873.
28. Бенно Швиковски; Питер Утц и Стэнли Филдс (2000). «Сеть белок-белковых взаимодействий у дрожжей». Природная биотехнология . 18 (12): 1257–61. дои : 10.1038/82360. PMID  11101803. S2CID  3009359.