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

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

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

Вариации

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

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

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

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

Примечания

1. Di Battista, Eades и др., 1998, с. 265–302.
2. Bastert, Matuszewski, 2001, с. 87–120.
3. 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. 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. 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.

Литература

• Giuseppe Di Battista, Peter Eades, Roberto Tamassia, Ioannis G. Tollis. Layered Drawings of Digraphs // Graph Drawing: Algorithms for the Visualization of Graphs. — Prentice Hall, 1998. — ISBN 978-0-13-301615-4.
• Oliver Bastert, Christian Matuszewski. Layered drawings of digraphs // Drawing Graphs: Methods and Models. — Springer-Verlag, 2001. — Т. 2025. — (Lecture Notes in Computer Science). — ISBN 978-3-540-42062-0. — doi:10.1007/3-540-44969-8_5.
• Patrick Healy, Nikola S. Nikolov. Hierarchical Graph Drawing // Handbook of Graph Drawing and Visualization / Roberto Tamassia. — CRC Press, 2014.
• Kozo Sugiyama, Shôjirô Tagawa, Mitsuhiko Toda. Methods for visual understanding of hierarchical system structures // IEEE Transactions on Systems, Man, and Cybernetics. — 1981. — Т. SMC-11, вып. 2. — doi:10.1109/TSMC.1981.4308636.
• Berger B., Shor P. Approximation algorithms for the maximum acyclic subgraph problem // Proceedings of the 1st ACM-SIAM Symposium on Discrete Algorithms (SODA'90). — 1990. — ISBN 9780898712513.
• Eades P., Lin X., Smyth W. F. A fast and effective heuristic for the feedback arc set problem // Information Processing Letters. — 1993. — Т. 47, вып. 6. — doi:10.1016/0020-0190(93)90079-O.
• Eades P., Lin X. A new heuristic for the feedback arc set problem // Australian Journal of Combinatorics. — 1995. — Т. 12.
• Jianer Chen, Yang Liu, Songjian Lu, Barry O'Sullivan, Igor Razgon. A fixed-parameter algorithm for the directed feedback vertex set problem // Journal of the ACM. — 2008. — Т. 55, вып. 5. — doi:10.1145/1411509.1411511.
• Gansner E. R., Koutsofios E., North S. C., Vo K.-P. A technique for drawing directed graphs // IEEE Transactions on Software Engineering. — 1993. — Т. 19, вып. 3. — doi:10.1109/32.221135.
• Patrick Healy, Nikola S. Nikolov. How to layer a directed acyclic graph // Graph Drawing: 9th International Symposium, GD 2001 Vienna, Austria, September 23–26, 2001, Revised Papers. — Springer-Verlag, 2002. — Т. 2265. — (Lecture Notes in Computer Science). — ISBN 978-3-540-43309-5. — doi:10.1007/3-540-45848-4_2.
• Peter Eades, Sue Whitesides. Drawing graphs in two layers // Theoretical Computer Science. — 1994. — Т. 131, вып. 2. — doi:10.1016/0304-3975(94)90179-1.
• Peter Eades, Nicholas C. Wormald. Edge crossings in drawings of bipartite graphs // Algorithmica. — 1994. — Т. 11, вып. 4. — doi:10.1007/BF01187020.
• Newbery F. J. Edge concentration: a method for clustering directed graphs // Proceedings of the 2nd International Workshop on Software Configuration Management (SCM '89), Princeton, New Jersey, USA. — Association for Computing Machinery, 1989. — ISBN 0-89791-334-5. — doi:10.1145/72910.73350.
• David Eppstein, Michael T. Goodrich, Jeremy Yu Meng. Confluent layered drawings // Proc. 12th Int. Symp. Graph Drawing (GD 2004) / János Pach. — Springer-Verlag, 2004. — Т. 47. — (Lecture Notes in Computer Science). — doi:10.1007/s00453-006-0159-8.
• Mäkinen E. Experiments on drawing 2-level hierarchical graphs // International Journal of Computer Mathematics. — 1990. — Т. 36, вып. 3–4. — doi:10.1080/00207169008803921.
• Vida Dujmović, Henning Fernau, Michael Kaufmann. Fixed parameter algorithms for one-sided crossing minimization revisited // Journal of Discrete Algorithms. — 2008. — Т. 6, вып. 2. — doi:10.1016/j.jda.2006.12.008.
• Ulrik Brandes, Boris Köpf. Graph drawing (Vienna, 2001). — Berlin: Springer, 2002. — Т. 2265. — ISBN 978-3-540-43309-5. — doi:10.1007/3-540-45848-4_3.
• Markus Eiglsperger, Martin Siebenhaller, Michael Kaufmann. An efficient implementation of Sugiyama’s algorithm for layered graph drawing // Graph Drawing, 12th International Symposium, GD 2004, New York, NY, USA, September 29-October 2, 2004, Revised Selected Papers. — Springer-Verlag, 2005. — Т. 3383. — (Lecture Notes in Computer Science). — ISBN 978-3-540-24528-5. — doi:10.1007/978-3-540-31843-9_17.
• Christian Bachmaier. A radial adaptation of the Sugiyama framework for visualizing hierarchical information // IEEE Transactions on Visualization and Computer Graphics. — 2007. — Т. 13, вып. 3. — doi:10.1109/TVCG.2007.1000. — PMID 17356223.
• Lev Nachmanson, George Robertson, Bongshin Lee. Drawing Graphs with GLEE // Graph Drawing, 15th International Symposium, GD 2007, Sydney, Australia, September 24–26, 2007, Revised Papers. — Springer-Verlag, 2008. — Т. 4875. — (Lecture Notes in Computer Science). — ISBN 978-3-540-77536-2. — doi:10.1007/978-3-540-77537-9_38.
• David Auber. Tulip – A Huge Graph Visualization Framework // Graph Drawing Software / Michael Jünger, Petra Mutzel. — Springer-Verlag, 2004. — ISBN 978-3-540-00881-1.
• Danil E. Baburin. Some modifications of Sugiyama approach // Graph Drawing, 10th International Symposium, GD 2002, Irvine, CA, USA, August 26–28, 2002, Revised Papers. — Springer-Verlag, 2002. — Т. 2528. — (Lecture Notes in Computer Science). — ISBN 978-3-540-00158-4. — doi:10.1007/3-540-36151-0_36.
• Seok-Hee Hong, Nikola S. Nikolov. Layered drawings of directed graphs in three dimensions // Proceedings of the 2005 Asia-Pacific Symposium on Information Visualisation (APVis '05). — 2005. — Т. 45. — (Conferences in Research and Practice in Information Technology). — ISBN 9781920682279.
• Sergey Pupyrev, Lev Nachmanson, Michael Kaufmann. Improving layered graph layouts with edge bundling // Graph Drawing, 18th International Symposium, GD 2010, Konstanz, Germany, September 21-24, 2010, Revised Selected Papers. — Springer-Verlag, 2011. — Т. 6502. — (Lecture Notes in Computer Science). — ISBN 978-3-642-18468-0. — doi:10.1007/978-3-642-18469-7_30.
• David Eppstein, Michael T. Goodrich, Jeremy Yu Meng. Confluent layered drawings // Algorithmica. — 2007. — Т. 47, вып. 4. — doi:10.1007/s00453-006-0159-8. — arXiv:cs/0507051.
• Dujmović V., Fellows M.R., Kitching M., Liotta G., McCartin C., Nishimura N., Ragde P., Rosamond F., Whitesides S. On the parameterized complexity of layered graph drawing // Algorithmica. — 2008. — Т. 52, вып. 2. — doi:10.1007/s00453-007-9151-1.
• Richard Cole. Automated layout of concept lattices using layered diagrams and additive diagrams // Australian Computer Science Communications. — 2001. — Т. 23, вып. 1. — ISBN 0-7695-0963-0. — doi:10.1109/ACSC.2001.906622.
• Benno Schwikowski, Peter Uetz, Stanley Fields. A network of protein−protein interactions in yeast // Nature Biotechnology. — 2000. — Т. 18, вып. 12. — doi:10.1038/82360. — PMID 11101803.