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