Рисунок графа или сетевой диаграммы — это графическое изображение вершин и ребер графа . Этот рисунок не следует путать с самим графиком: одному и тому же графику могут соответствовать самые разные макеты. [2] Говоря абстрактно, важно лишь то, какие пары вершин соединены ребрами. Однако в бетоне расположение этих вершин и ребер внутри чертежа влияет на его понятность, удобство использования, стоимость изготовления и эстетику . [3] Проблема усугубляется, если граф со временем меняется путем добавления и удаления ребер (динамическое рисование графа), и цель состоит в том, чтобы сохранить мысленную карту пользователя. [4]
Графы часто рисуются в виде диаграмм узел-связь, в которых вершины представлены в виде дисков, прямоугольников или текстовых меток, а края представлены в виде отрезков линий , полилиний или кривых на евклидовой плоскости . [3] Диаграммы узел-связь можно проследить до работ Псевдо-Лулля XIV-XVI веков, которые были опубликованы под именем Рамона Луллия , эрудита XIII века. Псевдо-Лулл рисовал диаграммы такого типа для полных графов , чтобы анализировать все парные комбинации среди наборов метафизических понятий. [5]
В случае ориентированных графов стрелки образуют обычно используемое графическое обозначение для обозначения их ориентации ; [2] однако исследования пользователей показали, что другие соглашения, такие как постепенное сокращение потребления, предоставляют эту информацию более эффективно. [6] При рисовании плоскостей вверх используется соглашение, согласно которому каждое ребро ориентировано от нижней вершины к более высокой вершине, что делает наконечники стрелок ненужными. [7]
Альтернативные соглашения для диаграмм узел-связь включают представления смежности, такие как упаковки кругов , в которых вершины представлены непересекающимися областями на плоскости, а ребра представлены смежностями между областями; представления пересечений , в которых вершины представлены непересекающимися геометрическими объектами, а ребра представлены их пересечениями; представления видимости, в которых вершины представлены областями на плоскости, а края представлены областями, имеющими беспрепятственную линию обзора друг к другу; сливающиеся рисунки, на которых края представлены плавными кривыми внутри математических железнодорожных путей ; ткани, в которых узлы представлены горизонтальными линиями, а края - вертикальными линиями; [8] и визуализации матрицы смежности графа.
Меры качества
Для графических рисунков было определено множество различных показателей качества в попытке найти объективные средства оценки их эстетики и удобства использования. [9] Помимо выбора между различными методами компоновки одного и того же графика, некоторые методы компоновки пытаются напрямую оптимизировать эти показатели.
Плоский граф , нарисованный без перекрывающихся ребер
Число пересечений рисунка — это количество пар ребер, пересекающих друг друга. Если граф плоский , то часто удобно рисовать его без пересечений ребер; то есть в данном случае рисунок графа представляет собой вложение графа . Однако в приложениях часто возникают непланарные графы, поэтому алгоритмы рисования графов обычно должны учитывать пересечение ребер. [10]
Площадь рисунка — это размер его наименьшей ограничивающей рамки относительно ближайшего расстояния между любыми двумя вершинами. Рисунки меньшей площади обычно предпочтительнее рисунков большей площади, поскольку они позволяют показать элементы рисунка в большем размере и, следовательно, более разборчиво. Соотношение сторон ограничивающей рамки также может иметь значение.
Отображение симметрии — это проблема поиска групп симметрии внутри данного графа и поиска рисунка, который отображает как можно большую часть симметрии. Некоторые методы компоновки автоматически приводят к созданию симметричных рисунков; альтернативно, некоторые методы рисования начинаются с поиска симметрий во входном графе и использования их для построения рисунка. [11]
Важно, чтобы края имели как можно более простую форму, чтобы глазу было легче следить за ними. В полилинейных рисунках сложность ребра может измеряться количеством его изгибов , и многие методы направлены на создание рисунков с небольшим количеством изгибов в целом или с небольшим количеством изгибов на одно ребро. Аналогично для сплайновых кривых сложность ребра может измеряться количеством контрольных точек на ребре.
Несколько часто используемых показателей качества касаются длины ребер: обычно желательно минимизировать общую длину ребер, а также максимальную длину любого ребра. Кроме того, может оказаться предпочтительным, чтобы длины ребер были одинаковыми, а не сильно различались.
Угловое разрешение — это мера самых острых углов на графике. Если граф имеет вершины с высокой степенью , то он обязательно будет иметь небольшое угловое разрешение, но угловое разрешение может быть ограничено снизу функцией степени. [12]
Число наклона графика — это минимальное количество различных наклонов ребер, необходимых для чертежа с ребрами сегментов прямых линий (допускающих пересечения). Кубические графы имеют число наклонов не более четырех, но графы пятой степени могут иметь неограниченное число наклонов; остается открытым вопрос о том, ограничено ли наклонное число графов степени 4. [12]
Существует множество различных стратегий компоновки графиков:
В системах компоновки, основанных на силе , программное обеспечение для рисования графов изменяет исходное размещение вершин, непрерывно перемещая вершины в соответствии с системой сил, основанной на физических метафорах, связанных с системами пружин или молекулярной механикой . Обычно эти системы сочетают силы притяжения между соседними вершинами с силами отталкивания между всеми парами вершин, чтобы найти компоновку, в которой длины ребер малы, а вершины хорошо разделены. Эти системы могут выполнять минимизацию энергетической функции на основе градиентного спуска или переводить силы непосредственно в скорости или ускорения движущихся вершин. [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.
^ аб Пач и Шарир (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 , получено 21 марта 2024 г.
^ Нахмансон, Робертсон и Ли (2008).
^ «Тюльпан - огромная структура визуализации графов», Дэвид Обер, в Junger & Mutzel (2004).
^ «yFiles - Визуализация и автоматическое размещение графиков», Роланд Визе, Маркус Эйгльспергер и Михаэль Кауфманн, в Jünger & Mutzel (2004).
^ Тантау (2013); см. также старую презентацию GD 2012. Архивировано 27 мая 2016 г. на Wayback Machine.
Герман, Иван; Мелансон, Ги; Маршалл, М. Скотт (2000), «Визуализация графов и навигация при визуализации информации: обзор», IEEE Transactions on Visualization and Computer Graphics , 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), «Многослойные рисунки орграфов», Кауфманн, Майкл; Вагнер, Доротея (ред.), Рисование графиков: методы и модели , Конспекты лекций по информатике, том. 2025, Springer-Verlag, стр. 87–120, номер документа : 10.1007/3-540-44969-8_5, ISBN.978-3-540-42062-0.
Бекман, Брайан (1994), Теория компоновки спектральных графов, Tech. Отчет MSR-TR-94-04, Microsoft Research, заархивирован из оригинала 1 апреля 2016 г. , получен 17 сентября 2011 г..
Фриз, Ральф (2004), «Автоматическое рисование решетки», Эклунд, Питер (редактор), Концептуальные решетки: Вторая международная конференция по формальному концептуальному анализу, ICFCA 2004, Сидней, Австралия, 23–26 февраля 2004 г., Материалы (PDF) ) , Конспекты лекций по информатике, вып. 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) из оригинала 14 марта 2016 г. , получено 17 сентября 2011 г..
Гранжан, Мартен (2014), «La connaissance est un réseau», Les Cahiers du Numérique , 10 (3): 37–54, doi : 10.3166/lcn.10.3.37-54, заархивировано из оригинала 06.2015 г. 27 , получено 15 октября 2014 г..
Холтен, Дэнни; Айзенберг, Петра ; ван Вейк, Ярке Дж .; Фекете, Жан-Даниэль (2011), «Расширенная оценка читаемости суженных, анимированных и текстурированных представлений с направленными краями в графах узловых связей», Тихоокеанский симпозиум по визуализации IEEE (PacificVis 2011) (PDF) , стр. 195– 202, номер домена : 10.1109/PACIFICVIS.2011.5742390, ISBN 978-1-61284-935-5, S2CID 16526781, заархивировано (PDF) из оригинала 11 апреля 2016 г. , получено 29 сентября 2011 г..
Холтен, Дэнни; ван Вейк, Ярке Дж. (2009), «Исследование пользователей по визуализации направленных ребер в графах», Материалы 27-й Международной конференции по человеческому фактору в вычислительных системах (CHI '09) (PDF) , стр. 2299–2308, CiteSeerX 10.1.1.212.5461 , номер домена : 10.1145/1518701.1519054, ISBN 9781605582467, S2CID 9725345, заархивировано из оригинала (PDF) 6 ноября 2011 г..
Кнут, Дональд Э. (2013), «Две тысячи лет комбинаторики», Уилсон, Робин; Уоткинс, Джон Дж. (ред.), Комбинаторика: древнее и современное , Oxford University Press, стр. 7–37..
Корен, Иегуда (2005), «Построение графиков по собственным векторам: теория и практика», Computers & Mathematics with Applications , 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.
Пах, Янош ; Шарир, Миха (2009), «5.5 Угловое разрешение и наклоны», Комбинаторная геометрия и ее алгоритмические приложения: Лекции в Алькале , Математические обзоры и монографии, том. 152, Американское математическое общество , стр. 126–127..
Покупка, ХК ; Коэн, РФ; Джеймс, Мичиган (1997), «Экспериментальное исследование основ алгоритмов рисования графов», Журнал экспериментальной алгоритмики , 2 , статья 4, doi : 10.1145/264216.264222, S2CID 22076200.
Саати, Томас Л. (1964), «Минимальное количество пересечений в полных графах», Proc. Натл. акад. наук. США , 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.
Заппони, Леонардо (август 2003 г.), «Что такое Dessin d'Enfant» (PDF) , Уведомления Американского математического общества , 50 : 788–789, заархивировано (PDF) из оригинала 03 октября 2021 г. , получено в 2021 г. -04-28.
Тамассия, Роберто , изд. (2014), Справочник по рисованию и визуализации графиков , CRC Press, заархивировано из оригинала 15 августа 2013 г. , получено 28 августа 2013 г..
Внешние ссылки
Библиотека GraphX для .NET. Архивировано 26 января 2018 г. на Wayback Machine : библиотека WPF с открытым исходным кодом для расчета и визуализации графиков. Поддерживает множество алгоритмов компоновки и маршрутизации ребер.
