Рисунок графа или сетевой диаграммы — это графическое представление вершин и ребер графа . Этот рисунок не следует путать с самим графом: очень разные макеты могут соответствовать одному и тому же графу. [2] В абстракции все, что имеет значение, — это то, какие пары вершин соединены ребрами. Однако в конкретном случае расположение этих вершин и ребер на рисунке влияет на его понятность, удобство использования, стоимость изготовления и эстетику . [3] Проблема усугубляется, если граф со временем изменяется путем добавления и удаления ребер (динамическое рисование графа), а цель состоит в том, чтобы сохранить ментальную карту пользователя. [4]
Графы часто рисуются как диаграммы узлов-связей, в которых вершины представлены в виде дисков, ящиков или текстовых меток, а ребра представлены в виде отрезков прямых , полилиний или кривых на евклидовой плоскости . [3] Диаграммы узлов-связей можно проследить до работ Псевдо-Луллля XIV-XVI веков, которые были опубликованы под именем Рамона Луллия , полимата XIII века. Псевдо-Луллль рисовал диаграммы этого типа для полных графов , чтобы проанализировать все попарные комбинации среди наборов метафизических концепций. [5]
В случае направленных графов наконечники стрелок образуют обычно используемое графическое соглашение для отображения их ориентации ; [2] однако, исследования пользователей показали, что другие соглашения, такие как сужение, предоставляют эту информацию более эффективно. [6] Восходящее плоскостное рисование использует соглашение, что каждое ребро ориентировано от нижней вершины к верхней вершине, что делает наконечники стрелок ненужными. [7]
Альтернативные соглашения для диаграмм узлов и связей включают представления смежности, такие как упаковки кругов , в которых вершины представлены непересекающимися областями на плоскости, а ребра представлены смежностями между областями; представления пересечений , в которых вершины представлены непересекающимися геометрическими объектами, а ребра представлены их пересечениями; представления видимости, в которых вершины представлены областями на плоскости, а ребра представлены областями, которые имеют беспрепятственную линию видимости друг с другом; конфлюэнтные рисунки, в которых ребра представлены в виде плавных кривых внутри математических железнодорожных путей ; ткани, в которых узлы представлены в виде горизонтальных линий, а ребра - в виде вертикальных линий; [8] и визуализации матрицы смежности графа.
Меры качества
Для графических изображений было определено множество различных мер качества в попытке найти объективные средства оценки их эстетики и удобства использования. [9] Помимо руководства выбором между различными методами компоновки для одного и того же графика, некоторые методы компоновки пытаются напрямую оптимизировать эти меры.
Плоский граф, нарисованный без перекрывающихся ребер
Число пересечений рисунка — это число пар рёбер, которые пересекают друг друга. Если граф плоский , то часто удобно рисовать его без пересечений рёбер; то есть в этом случае рисунок графа представляет собой вложение графа . Однако в приложениях часто возникают неплоские графы, поэтому алгоритмы рисования графов должны, как правило, учитывать пересечения рёбер. [10]
Площадь рисунка — это размер его наименьшего ограничивающего прямоугольника относительно ближайшего расстояния между любыми двумя вершинами. Рисунки с меньшей площадью, как правило, предпочтительнее, чем с большей площадью, поскольку они позволяют отображать элементы рисунка в большем размере и, следовательно, более разборчиво. Соотношение сторон ограничивающего прямоугольника также может быть важным.
Отображение симметрии — это проблема поиска групп симметрии в заданном графе и поиска рисунка, который отображает как можно больше симметрии. Некоторые методы компоновки автоматически приводят к симметричным рисункам; в качестве альтернативы, некоторые методы рисования начинаются с поиска симметрий во входном графе и использования их для построения рисунка. [11]
Важно, чтобы ребра имели максимально простую форму, чтобы глазу было легче их отслеживать. В полилинейных рисунках сложность ребра может быть измерена количеством изгибов , и многие методы направлены на то, чтобы предоставить рисунки с небольшим количеством изгибов или небольшим количеством изгибов на ребро. Аналогично для сплайновых кривых сложность ребра может быть измерена количеством контрольных точек на ребре.
Несколько часто используемых мер качества касаются длин ребер: обычно желательно минимизировать общую длину ребер, а также максимальную длину любого ребра. Кроме того, может быть предпочтительнее, чтобы длины ребер были однородными, а не сильно различались.
Угловое разрешение — это мера самых острых углов в графическом рисунке. Если граф имеет вершины с высокой степенью , то он обязательно будет иметь малое угловое разрешение, но угловое разрешение может быть ограничено снизу функцией степени. [12]
Число наклонов графа — это минимальное число различных наклонов ребер, необходимых для чертежа с ребрами сегмента прямой линии (допускающими пересечения). Кубические графы имеют число наклонов не более четырех, но графы степени пять могут иметь неограниченное число наклонов; остается открытым вопрос, ограничено ли число наклонов графов степени 4. [12]
Методы компоновки
Визуализация сети на основе силы. [13]Визуализация макета спектрального графика.
Существует множество различных стратегий компоновки графиков:
В системах компоновки на основе сил программное обеспечение для рисования графов изменяет начальное размещение вершин, непрерывно перемещая вершины в соответствии с системой сил, основанной на физических метафорах, связанных с системами пружин или молекулярной механикой . Обычно эти системы объединяют силы притяжения между соседними вершинами с силами отталкивания между всеми парами вершин, чтобы найти компоновку, в которой длины ребер малы, а вершины хорошо разделены. Эти системы могут выполнять минимизацию энергетической функции на основе градиентного спуска или могут напрямую переводить силы в скорости или ускорения для движущихся вершин. [14]
Методы ортогональной компоновки, которые позволяют ребрам графа проходить горизонтально или вертикально, параллельно осям координат компоновки. Эти методы изначально были разработаны для задач компоновки СБИС и печатных плат , но они также были адаптированы для рисования графов. Они обычно включают многофазный подход, в котором входной граф планируется путем замены точек пересечения вершинами, находится топологическое вложение планированного графа, выбирается ориентация ребер для минимизации изгибов, вершины размещаются в соответствии с этими ориентациями, и, наконец, этап уплотнения компоновки уменьшает область рисунка. [16]
Алгоритмы компоновки дерева, эти показывают корневую древовидную структуру, подходящую для деревьев . Часто, в технике, называемой «компоновка шара», потомки каждого узла в дереве рисуются на окружности, окружающей узел, причем радиусы этих окружностей уменьшаются на более низких уровнях в дереве, так что эти окружности не перекрываются. [17]
Методы рисования многослойных графов (часто называемые рисованием в стиле Сугиямы) лучше всего подходят для направленных ациклических графов или графов, которые почти ацикличны, таких как графы зависимостей между модулями или функциями в программной системе. В этих методах узлы графа располагаются в горизонтальные слои с использованием таких методов, как алгоритм Коффмана–Грэма , таким образом, что большинство ребер идут вниз от одного слоя к другому; после этого шага узлы внутри каждого слоя располагаются так, чтобы минимизировать пересечения. [18]
Дуговая диаграмма
Дуговые диаграммы , стиль компоновки, появившийся в 1960-х годах [19], размещают вершины на линии; ребра могут быть нарисованы в виде полукругов выше или ниже линии или в виде плавных кривых, соединенных вместе из нескольких полукругов.
Круговые методы компоновки размещают вершины графа на окружности, тщательно выбирая порядок вершин по окружности, чтобы уменьшить пересечения и разместить смежные вершины близко друг к другу. Ребра могут быть нарисованы либо как хорды окружности, либо как дуги внутри или снаружи окружности. В некоторых случаях могут использоваться несколько окружностей. [20]
Рисунок доминирования размещает вершины таким образом, что одна вершина находится вверху, справа или и там, и там, если и только если она достижима из другой вершины. Таким образом, стиль макета делает отношение достижимости графа визуально очевидным. [21]
Графические чертежи для конкретных приложений
Графики и графические рисунки, возникающие в других областях применения, включают:
Кроме того, этапы размещения и маршрутизации автоматизации электронного проектирования (EDA) во многом похожи на рисование графа, как и проблема жадного встраивания в распределенных вычислениях , а литература по рисованию графа включает несколько результатов, заимствованных из литературы EDA. Однако эти проблемы также различаются в нескольких важных отношениях: например, в EDA минимизация площади и длина сигнала важнее эстетики, а проблема маршрутизации в EDA может иметь более двух терминалов на сеть, в то время как аналогичная проблема в рисовании графа обычно включает только пары вершин для каждого ребра.
^ Ди Баттиста и др. (1998), стр. vii–viii; Герман, Мелансон и Маршалл (2000), раздел 1.1, «Типичные области применения».
^ аб Ди Баттиста и др. (1998), с. 6.
^ аб Ди Баттиста и др. (1998), с. viii.
^ Мисью и др. (1995).
^ Кнут (2013).
^ Холтен и ван Вейк (2009); Холтен и др. (2011).
^ Гарг и Тамассиа (1995).
^ Лонгабо (2012).
^ Ди Баттиста и др. (1998), Раздел 2.1.2, Эстетика, стр. 14–16; Покупка, Коэн и Джеймс (1997).
^ Ди Баттиста и др. (1998), стр. 14.
^ Ди Баттиста и др. (1998), с. 16.
^ ab Pach & Sharir (2009).
^ Гранджин (2014).
^ Ди Баттиста и др. (1998), Раздел 2.7, «Подход, направленный на силу», стр. 29–30, и Глава 10, «Методы, направленные на силу», стр. 303–326.
^ Бекман (1994); Корен (2005).
^ Ди Баттиста и др. (1998), глава 5, «Поток и ортогональные рисунки», стр. 137–170; Эйгльспергер, Фекете и Клау (2001).
^ Герман, Мелансон и Маршалл (2000), Раздел 2.2, «Традиционная компоновка – Обзор».
^ Сугияма, Тагава и Тода (1981); Бастерт и Матушевский (2001); Ди Баттиста и др. (1998), Глава 9, «Многослойные рисунки орграфов», стр. 265–302.
^ Саати (1964).
^ Догрусоз, Мэдден и Мэдден (1997).
^ Ди Баттиста и др. (1998), раздел 4.7, «Рисунки доминирования», стр. 112–127.
^ Скотт (2000); Брандес, Фримен и Вагнер (2014).
^ Ди Баттиста и др. (1998), стр. 15–16 и Глава 6, «Поток и восходящая планарность», стр. 171–214; Фриз (2004).
^ Дзаппони (2003).
^ Андерсон и Хед (2006).
^ Ди Баттиста и Римондини (2014).
^ Бахмайер, Брандес и Шрайбер (2014).
^ «Graphviz и Dynagraph – статические и динамические инструменты рисования графов», Джон Эллсон, Эмден Р. Ганснер, Элефтериос Куцофиос, Стивен К. Норт и Гордон Вудхалл, в Jünger & Mutzel (2004).
^ "Введение в рисование графов", Wolfram Language & System Documentation Center , получено 21.03.2024
^ Нахмансон, Робертсон и Ли (2008).
^ «Tulip – огромная структура визуализации графов», Дэвид Обер, в Jünger & Mutzel (2004).
^ «yFiles – Визуализация и автоматическая компоновка графиков», Роланд Визе, Маркус Эйгльшпергер и Михаэль Кауфманн, в Jünger & Mutzel (2004).
^ Tantau (2013); см. также старую презентацию GD 2012. Архивировано 27 мая 2016 г. на Wayback Machine.
Герман, Иван; Мелансон, Гай; Маршалл, М. Скотт (2000), «Визуализация графов и навигация в визуализации информации: обзор», Труды IEEE по визуализации и компьютерной графике , 6 (1): 24–43, doi :10.1109/2945.841119.
Юнгер, Майкл; Мутцель, Петра (2004), программное обеспечение для рисования графиков , Springer-Verlag, ISBN 978-3-540-00881-1.
Специализированные подтемы
Андерсон, Джеймс Эндрю; Хэд, Томас Дж. (2006), Теория автоматов и ее современные приложения, Cambridge University Press, стр. 38–41, ISBN 978-0-521-84887-9.
Бахмайер, Кристиан; Брандес, Ульрик ; Шрайбер, Фальк (2014), «Биологические сети», в Тамассиа, Роберто (ред.), Справочник по рисованию и визуализации графов , CRC Press, стр. 621–651.
Бастерт, Оливер; Матушевски, Кристиан (2001), «Слоистые рисунки орграфов», в Кауфманн, Михаэль; Вагнер, Доротея (ред.), Рисование графов: методы и модели , Lecture Notes in Computer Science, т. 2025, Springer-Verlag, стр. 87–120, doi :10.1007/3-540-44969-8_5, ISBN 978-3-540-42062-0.
Бекман, Брайан (1994), Теория спектрального графового макета, Технический отчет MSR-TR-94-04, Microsoft Research, архивировано из оригинала 2016-04-01 , извлечено 2011-09-17.
Eiglsperger, Markus; Fekete, Sándor; Klau, Gunnar (2001), "Рисование ортогональных графов", в Kaufmann, Michael; Wagner, Dorothea (ред.), Рисование графов , Lecture Notes in Computer Science, т. 2025, Springer Berlin / Heidelberg, стр. 121–171, doi :10.1007/3-540-44969-8_6, ISBN 978-3-540-42062-0.
Freese, Ralph (2004), "Автоматизированное рисование решётки", в Eklund, Peter (ред.), Концептуальные решётки: Вторая международная конференция по формальному концептуальному анализу, ICFCA 2004, Сидней, Австралия, 23-26 февраля 2004 г., Труды (PDF) , Lecture Notes in Computer Science, т. 2961, Springer-Verlag, стр. 589–590, CiteSeerX 10.1.1.69.6245 , doi :10.1007/978-3-540-24651-0_12, ISBN 978-3-540-21043-6, заархивировано (PDF) из оригинала 2016-03-14 , извлечено 2011-09-17.
Гранжан, Мартен (2014), «La connaissance est un réseau», Les Cahiers du Numérique , 10 (3): 37–54, doi : 10.3166/lcn.10.3.37-54, заархивировано из оригинала 6 июня 2015 г. 27 , получено 15 октября 2014 г..
Холтен, Дэнни; Айзенберг, Петра ; ван Вийк, Ярке Дж .; Фекете, Жан-Даниэль (2011), «Расширенная оценка читаемости конусных, анимированных и текстурированных представлений направленных ребер в графах узлов и связей», IEEE Pacific Visualization Symposium (PacificVis 2011) (PDF) , стр. 195–202, doi :10.1109/PACIFICVIS.2011.5742390, ISBN 978-1-61284-935-5, S2CID 16526781, заархивировано (PDF) из оригинала 2016-04-11 , извлечено 2011-09-29.
Холтен, Дэнни; ван Вайк, Ярке Дж. (2009), «Исследование пользователя по визуализации направленных ребер в графах», Труды 27-й Международной конференции по человеческому фактору в вычислительных системах (CHI '09) (PDF) , стр. 2299–2308, CiteSeerX 10.1.1.212.5461 , doi :10.1145/1518701.1519054, ISBN 9781605582467, S2CID 9725345, архивировано из оригинала (PDF) 2011-11-06.
Кнут, Дональд Э. (2013), «Две тысячи лет комбинаторики», в Уилсон, Робин; Уоткинс, Джон Дж. (ред.), Комбинаторика: древняя и современная , Oxford University Press, стр. 7–37.
Корен, Йехуда (2005), «Рисование графиков по собственным векторам: теория и практика», Компьютеры и математика с приложениями , 49 (11–12): 1867–1888, doi : 10.1016/j.camwa.2004.08.015 , MR 2154691.
Лонгабо, Уильям (2012), «Расчесывание волосяного комка с помощью BioFabric: новый подход к визуализации больших сетей», BMC Bioinformatics , 13 : 275, doi : 10.1186/1471-2105-13-275 , PMC 3574047 , PMID 23102059.
Misue, K.; Eades, P.; Lai, W.; Sugiyama, K. (1995), «Настройка макета и ментальная карта», Журнал визуальных языков и вычислений , 6 (2): 183–210, doi :10.1006/jvlc.1995.1010.
Пач, Янош ; Шарир, Миха (2009), «5.5 Угловое разрешение и наклоны», Комбинаторная геометрия и ее алгоритмические приложения: Лекции в Алькале , Математические обзоры и монографии, т. 152, Американское математическое общество , стр. 126–127.
Закупки, HC ; Коэн, RF; Джеймс, MI (1997), "Экспериментальное исследование основ алгоритмов рисования графов", Журнал экспериментальной алгоритмики , 2 , Статья 4, doi : 10.1145/264216.264222, S2CID 22076200.
Саати, Томас Л. (1964), «Минимальное число пересечений в полных графах», Proc. Natl. Acad. Sci. USA , 52 (3): 688–690, Bibcode : 1964PNAS...52..688S , doi : 10.1073/pnas.52.3.688 , PMC 300329 , PMID 16591215.
Скотт, Джон (2000), «Социограммы и теория графов», Анализ социальных сетей: справочник (2-е изд.), Sage, стр. 64–69, ISBN 978-0-7619-6339-4.
Zapponi, Leonardo (август 2003 г.), «Что такое детский рисунок» (PDF) , Notices of the American Mathematical Society , 50 : 788–789, архивировано (PDF) из оригинала 03.10.2021 , извлечено 28.04.2021.
Тамассиа, Роберто , ред. (2014), Справочник по рисованию и визуализации графиков, CRC Press, архивировано из оригинала 2013-08-15 , извлечено 2013-08-28.
Внешние ссылки
Библиотека GraphX для .NET Архивировано 2018-01-26 на Wayback Machine : библиотека WPF с открытым исходным кодом для расчета и визуализации графов. Поддерживает множество алгоритмов компоновки и маршрутизации ребер.
