Рисование многослойного графика - Layered graph drawing

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

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

Идеальной формой для многослойного рисунка будет направленный вверх плоский рисунок, в котором все ребра ориентированы в одинаковом направлении и никакие пары ребер не пересекаются. Однако графы часто содержат циклы, поэтому минимизация количества несовместно ориентированных ребер является 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 (мин) время на графиках с п вершины и м ребер из-за большого количества фиктивных вершин, которые могут быть созданы. Однако для некоторых вариантов алгоритма можно смоделировать влияние фиктивных вершин, не создавая их явно, что приводит к почтилинейное время выполнение.[18]

Инструмент "точка" в Graphviz производит послойные рисунки.[9] Алгоритм рисования многоуровневого графа также включен в Макет автоматического графика Microsoft[19] И в Тюльпан.[20]

Вариации

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

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

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

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

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

  1. ^ а б c d е ж грамм час я j Ди Баттиста, Джузеппе; Идс, Питер; Тамассия, Роберто; Толлис, Иоаннис Г. (1998), "Многослойные рисунки диграфов", Рисование графиков: алгоритмы визуализации графиков, Prentice Hall, стр. 265–302, ISBN  978-0-13-301615-4.
  2. ^ а б c d е ж грамм час я Бастерт, Оливер; Матушевский, Кристиан (2001), «Многослойные рисунки диграфов», у Кауфманна, Михаэля; Вагнер, Доротея (ред.), Графики рисования: методы и модели, Конспект лекций по информатике, 2025, Springer-Verlag, стр. 87–120, Дои:10.1007/3-540-44969-8_5, ISBN  978-3-540-42062-0.
  3. ^ а б c d е ж грамм час я j k л м п Хили, Патрик; Николов, Никола С. (2014), «Отрисовка иерархического графа», в Тамассия, Роберто (ред.), Справочник по рисованию и визуализации графиков, CRC Press, стр. 409–453..
  4. ^ Сугияма, Кодзо; Тагава, Сёдзиро; Тода, Мицухико (1981), "Методы визуального понимания структур иерархических систем", IEEE Transactions по системам, человеку и кибернетике, СМЦ-11 (2): 109–125, Дои:10.1109 / TSMC.1981.4308636, МИСТЕР  0611436.
  5. ^ Бергер, Б.; Шор, П. (1990), «Алгоритмы аппроксимации для задачи о максимальном ациклическом подграфе», Материалы 1-го симпозиума ACM-SIAM по дискретным алгоритмам (SODA'90), стр. 236–243, ISBN  9780898712513.
  6. ^ Идс, П.; Lin, X .; Смит, В. Ф. (1993), «Быстрая и эффективная эвристика для задачи набора дуг обратной связи», Письма об обработке информации, 47 (6): 319–323, Дои:10.1016 / 0020-0190 (93) 90079-О.
  7. ^ Идс, П.; Лин, X. (1995), "Новая эвристика для задачи набора дуг обратной связи", Австралийский журнал комбинаторики, 12: 15–26.
  8. ^ Чен, Цзианэр; Лю, Ян; Лу, Сунцзянь; О'Салливан, Барри; Разгон, Игорь (2008), "Алгоритм с фиксированными параметрами для задачи о множестве вершин с направленной обратной связью", Журнал ACM, 55 (5): 1, Дои:10.1145/1411509.1411511.
  9. ^ а б c d Gansner, E. R .; Koutsofios, E .; North, S.C .; Во, К.-П. (1993), «Техника рисования ориентированных графов», IEEE Transactions по разработке программного обеспечения, 19 (3): 214–230, Дои: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.
  12. ^ Эппштейн, Дэвид; Гудрич, Майкл Т.; Мэн, Джереми Ю (2004), «Сливающиеся слоистые рисунки», в Пах, Янош (ред.), Proc. 12-й Int. Symp. Графический рисунок (GD 2004), Конспект лекций по информатике, 47 (3383 ред.), Springer-Verlag, стр. 184–194, arXiv:cs.CG/0507051, Дои:10.1007 / s00453-006-0159-8.
  13. ^ Идс, Питер; Уайтсайдс, Сью (1994), «Рисование графиков в два слоя», Теоретическая информатика, 131 (2): 361–374, Дои:10.1016/0304-3975(94)90179-1.
  14. ^ а б Идс, Питер; Wormald, Николас С. (1994), "Пересечение ребер на чертежах двудольных графов", Алгоритмика, 11 (4): 379–403, Дои:10.1007 / BF01187020.
  15. ^ Мякинен, Э. (1990), "Эксперименты по рисованию двухуровневых иерархических графиков", Международный журнал компьютерной математики, 36 (3–4): 175–181, Дои:10.1080/00207169008803921.
  16. ^ Дуймович, Вида; Фернау, Хеннинг; Кауфманн, Майкл (2008), «Пересмотр алгоритмов с фиксированными параметрами для односторонней минимизации пересечения», Журнал дискретных алгоритмов, 6 (2): 313–323, Дои:10.1016 / j.jda.2006.12.008, МИСТЕР  2418986.
  17. ^ Брандес, Ульрик; Копф, Борис (2002), "Быстрое и простое задание горизонтальных координат", Отрисовка графика (Вена, 2001 г.), Конспект лекций по информатике, 2265, Берлин: Springer, стр. 31–44, Дои:10.1007/3-540-45848-4_3, ISBN  978-3-540-43309-5, МИСТЕР  1962417.
  18. ^ Эйглспергер, Маркус; Зибенхаллер, Мартин; Кауфманн, Майкл (2005), «Эффективная реализация алгоритма Сугиямы для рисования многоуровневого графа», Графический рисунок, 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-Verlag, стр. 366–367, Дои:10.1007/3-540-36151-0_36, ISBN  978-3-540-00158-4.
  22. ^ Бахмайер, Кристиан (2007), "Радиальная адаптация структуры Сугиямы для визуализации иерархической информации", IEEE Transactions по визуализации и компьютерной графике, 13 (3): 583–594, Дои:10.1109 / TVCG.2007.1000, PMID  17356223.
  23. ^ Хонг, Сок-Хи; Николов, Никола С. (2005), «Многослойные рисунки ориентированных графов в трех измерениях», Материалы Азиатско-Тихоокеанского симпозиума 2005 г. по визуализации информации (APVis '05), Конференции по исследованиям и практике в области информационных технологий, 45, стр. 69–74, ISBN  9781920682279.
  24. ^ Пупырев, Сергей; Нахмансон, Лев; Кауфманн, Майкл (2011), «Улучшение макетов слоистых графов с помощью объединения ребер», Графический рисунок, 18-й Международный симпозиум, GD 2010, Констанц, Германия, 21-24 сентября 2010 г., отредактированные избранные статьи, Конспект лекций по информатике, 6502, Springer-Verlag, стр. 329–340, Дои:10.1007/978-3-642-18469-7_30, ISBN  978-3-642-18468-0.
  25. ^ Эппштейн, Дэвид; Гудрич, Майкл Т.; Мэн, Джереми Ю (2007), «Сливающиеся слоистые рисунки», Алгоритмика, 47 (4): 439–452, arXiv:cs / 0507051, Дои:10.1007 / s00453-006-0159-8.
  26. ^ Dujmović, V .; Стипендиаты, M.R .; Китчинг, М .; Liotta, G .; McCartin, C .; Nishimura, N .; Ragde, P .; Розамонд, Ф .; Whitesides, S. (2008), "О параметризованной сложности построения многоуровневого графа", Алгоритмика, 52 (2): 267–292, Дои:10.1007 / s00453-007-9151-1.
  27. ^ Коул, Ричард (2001), «Автоматическая компоновка концептуальных решеток с использованием многоуровневых диаграмм и аддитивных диаграмм», Труды 24-й Австралазийской конференции по компьютерным наукам (ACSC '01), Австралийские коммуникации в области компьютерных наук, 23 (1): 47–53, Дои:10.1109 / ACSC.2001.906622, ISBN  0-7695-0963-0.
  28. ^ Бенно Швиковски; Питер Утц и Стэнли Филдс (2000). «Сеть белок-белковых взаимодействий в дрожжах». Природа Биотехнологии. 18 (12): 1257–1261. Дои:10.1038/82360. PMID  11101803.