Jump to content

Рисование графика

(Перенаправлено с визуализации сети )

Графическое представление минутной части WWW с указанием гиперссылок .

Рисование графиков — это область математики и информатики, сочетающая методы геометрической теории графов и визуализации информации для получения двумерных изображений графиков , возникающих в результате таких приложений, как анализ социальных сетей , картография , лингвистика и биоинформатика . [1]

Рисунок графа или сетевой диаграммы — это графическое изображение вершин и ребер графа . Этот рисунок не следует путать с самим графиком: одному и тому же графику могут соответствовать самые разные макеты. [2] Говоря абстрактно, важно лишь то, какие пары вершин соединены ребрами. Однако в бетоне расположение этих вершин и ребер на чертеже влияет на его понятность, удобство использования, стоимость изготовления и эстетику . [3] Проблема усугубляется, если граф со временем меняется путем добавления и удаления ребер (динамическое рисование графа), и цель состоит в том, чтобы сохранить мысленную карту пользователя. [4]

Графические соглашения

[ редактировать ]
Ориентированный график со стрелками, показывающими направления ребер.

Графы часто рисуются в виде диаграмм узлов и связей, в которых вершины представлены в виде дисков, прямоугольников или текстовых меток, а края представлены в виде отрезков линий , полилиний или кривых на евклидовой плоскости . [3] Диаграммы узлов-связей можно проследить до работ Псевдо-Лулля XIV-XVI веков, которые были опубликованы под именем Рамона Луллия , эрудита XIII века. Псевдо-Лулл ​​рисовал диаграммы такого типа для полных графов , чтобы анализировать все парные комбинации среди наборов метафизических понятий. [5]

В случае ориентированных графов стрелки образуют обычно используемое графическое обозначение для обозначения их ориентации ; [2] однако исследования пользователей показали, что другие соглашения, такие как постепенное сокращение потребления, предоставляют эту информацию более эффективно. [6] При рисовании плоскостей вверх используется соглашение, согласно которому каждое ребро ориентировано от нижней вершины к более высокой вершине, что делает наконечники стрелок ненужными. [7]

Альтернативные соглашения для диаграмм узел-связь включают представления смежности, такие как упаковки кругов , в которых вершины представлены непересекающимися областями на плоскости, а ребра представлены смежностями между областями; представления пересечений , в которых вершины представлены непересекающимися геометрическими объектами, а ребра представлены их пересечениями; представления видимости, в которых вершины представлены областями на плоскости, а края представлены областями, которые имеют беспрепятственную линию обзора друг к другу; сливающиеся рисунки, на которых края представлены плавными кривыми внутри математических железнодорожных путей ; ткани, в которых узлы представлены горизонтальными линиями, а края - вертикальными линиями; [8] и визуализации матрицы смежности графа.

Меры качества

[ редактировать ]

Для графических рисунков было определено множество различных показателей качества в попытке найти объективные средства оценки их эстетики и удобства использования. [9] Помимо управления выбором между различными методами компоновки одного и того же графика, некоторые методы компоновки пытаются напрямую оптимизировать эти показатели.

Плоский граф, нарисованный без перекрывающихся ребер
  • Число пересечений рисунка — это количество пар ребер, пересекающих друг друга. Если граф плоский , то часто удобно рисовать его без пересечений ребер; то есть в данном случае рисунок графа представляет собой вложение графа . Однако в приложениях часто возникают непланарные графы, поэтому алгоритмы рисования графов обычно должны учитывать пересечение ребер. [10]
  • Площадь рисунка — это размер его наименьшей ограничивающей рамки относительно ближайшего расстояния между любыми двумя вершинами. Рисунки меньшей площади обычно предпочтительнее рисунков большей площади, поскольку они позволяют показать элементы рисунка в большем размере и, следовательно, более разборчиво. Соотношение сторон ограничивающей рамки также может иметь значение.
  • Отображение симметрии — это проблема поиска групп симметрии внутри данного графа и поиска рисунка, который отображает как можно большую часть симметрии. Некоторые методы компоновки автоматически приводят к созданию симметричных рисунков; альтернативно, некоторые методы рисования начинаются с поиска симметрий во входном графе и использования их для построения рисунка. [11]
  • Важно, чтобы края имели как можно более простую форму, чтобы глазу было легче следить за ними. В полилинейных рисунках сложность ребра может измеряться количеством его изгибов , и многие методы направлены на создание рисунков с небольшим количеством изгибов в целом или с небольшим количеством изгибов на одно ребро. Аналогично для сплайновых кривых сложность ребра может измеряться количеством контрольных точек на ребре.
  • Несколько часто используемых показателей качества касаются длины ребер: обычно желательно минимизировать общую длину ребер, а также максимальную длину любого ребра. Кроме того, может оказаться предпочтительным, чтобы длины ребер были одинаковыми, а не сильно различались.
  • Угловое разрешение — это мера самых острых углов на графике. Если граф имеет вершины с высокой степенью , то он обязательно будет иметь небольшое угловое разрешение, но угловое разрешение может быть ограничено снизу функцией степени. [12]
  • Число наклона графика — это минимальное количество различных наклонов ребер, необходимых для чертежа с ребрами сегментов прямых линий (допускающих пересечения). Кубические графы имеют число наклонов не более четырех, но графы пятой степени могут иметь неограниченное число наклонов; остается открытым вопрос, ограничено ли наклонное число графов степени 4. [12]

Методы компоновки

[ редактировать ]
Силовая сетевая визуализация. [13]
Визуализация компоновки спектрального графика.

Существует множество различных стратегий компоновки графиков:

  • В системах компоновки, основанных на силе , программное обеспечение для рисования графов изменяет начальное размещение вершин, непрерывно перемещая вершины в соответствии с системой сил, основанной на физических метафорах, связанных с системами пружин или молекулярной механикой . Обычно эти системы сочетают силы притяжения между соседними вершинами с силами отталкивания между всеми парами вершин, чтобы найти компоновку, в которой длины ребер малы, а вершины хорошо разделены. Эти системы могут выполнять на основе градиентного спуска минимизацию энергетической функции или переводить силы непосредственно в скорости или ускорения движущихся вершин. [14]
  • Методы спектральной компоновки используют в качестве координат собственные векторы матрицы , например лапласиан, полученный из матрицы смежности графа. [15]
  • Методы ортогональной компоновки, которые позволяют краям графика проходить горизонтально или вертикально параллельно осям координат компоновки. Эти методы изначально были разработаны для задач СБИС и компоновки печатных плат , но они также были адаптированы для рисования графиков. Обычно они включают в себя многоэтапный подход, при котором входной граф планаризуется путем замены точек пересечения вершинами, находится топологическое вложение планаризованного графа, выбираются ориентации ребер для минимизации изгибов, вершины размещаются в соответствии с этими ориентациями и, наконец, создается макет. Стадия уплотнения уменьшает площадь рисунка. [16]
  • Алгоритмы компоновки дерева показывают корневое древовидное образование, подходящее для деревьев . Часто в методе, называемом «воздушным шаром», дочерние элементы каждого узла в дереве рисуются на круге, окружающем узел, при этом радиусы этих кругов уменьшаются на более низких уровнях дерева, чтобы эти круги не перекрывались. [17]
  • Методы рисования многоуровневых графов (часто называемые рисованием в стиле Сугиямы) лучше всего подходят для ориентированных ациклических графов или графов, которые почти ацикличны, например графиков зависимостей между модулями или функциями в программной системе. В этих методах узлы графа распределяются по горизонтальным слоям с использованием таких методов, как алгоритм Коффмана-Грэма , таким образом, что большинство ребер идут вниз от одного слоя к другому; после этого шага узлы внутри каждого слоя располагаются так, чтобы минимизировать пересечения. [18]
Диаграмма дуги
  • Дуговые диаграммы — стиль компоновки, возникший в 1960-х годах. [19] расположить вершины на линии; края могут быть нарисованы в виде полукругов над или под линией или в виде плавных кривых, соединенных вместе из нескольких полукругов.
  • Методы круговой компоновки помещают вершины графа в круг, тщательно выбирая порядок вершин вокруг круга, чтобы уменьшить количество пересечений и разместить соседние вершины близко друг к другу. Края могут быть нарисованы либо как хорды круга, либо как дуги внутри или снаружи круга. В некоторых случаях можно использовать несколько кругов. [20]
  • При рисовании доминирования вершины размещаются таким образом, что одна вершина расположена вверх, вправо или обе относительно другой тогда и только тогда, когда она достижима из другой вершины. Таким образом, стиль макета делает отношение достижимости графа визуально очевидным. [21]

Графические чертежи для конкретных приложений

[ редактировать ]

Графики и графические рисунки, возникающие в других областях применения, включают:

Кроме того, размещения и маршрутизации этапы электронного проектирования (EDA) во многом аналогичны рисованию графов, как и проблема жадного встраивания в распределенные вычисления , а литература по рисованию графов включает несколько результатов, заимствованных из литературы EDA. Однако эти проблемы также различаются по нескольким важным аспектам: например, в EDA минимизация площади и длина сигнала важнее эстетики, а проблема маршрутизации в EDA может иметь более двух терминалов на сеть, в то время как аналогичная проблема при построении графов вообще включает только пары вершин для каждого ребра.

Программное обеспечение

[ редактировать ]
Интерфейс рисования графиков ( Gephi 0.9.1)

Программное обеспечение, системы и поставщики систем для рисования графиков включают:

  • Программное обеспечение с открытым исходным кодом BioFabric для визуализации больших сетей путем рисования узлов в виде горизонтальных линий.
  • Cytoscape , программное обеспечение с открытым исходным кодом для визуализации сетей молекулярного взаимодействия.
  • Gephi — программное обеспечение для сетевого анализа и визуализации с открытым исходным кодом.
  • Graph-tool бесплатная библиотека Python для анализа графиков.
  • Graphviz — система рисования графиков с открытым исходным кодом от корпорации AT&T. [28]
  • Linkurious — коммерческое программное обеспечение для сетевого анализа и визуализации графовых баз данных.
  • Mathematica — универсальный вычислительный инструмент, включающий в себя инструменты визуализации 2D и 3D графиков и анализа графов. [29]
  • Microsoft Automatic Graph Layout , библиотека .NET с открытым исходным кодом (ранее называвшаяся GLEE) для компоновки графиков. [30]
  • NetworkX — это библиотека Python для изучения графов и сетей.
  • Тюльпан , [31] инструмент визуализации данных с открытым исходным кодом
  • yEd , графический редактор с функциональностью макета графика. [32]
  • PGF/TikZ 3.0 с graphdrawing пакет (требуется LuaTeX ). [33]
  • LaNet-vi , программное обеспечение для визуализации крупных сетей с открытым исходным кодом.

См. также

[ редактировать ]
  1. ^ Баттиста и др. (1998) , стр. 101-1. vii–viii; Герман, Мелансон и Маршалл (2000) , Раздел 1.1, «Типичные области применения».
  2. ^ Jump up to: а б Ди Баттиста и др. (1998) , с. 6.
  3. ^ Jump up to: а б Ди Баттиста и др. (1998) , с. viii.
  4. ^ Мисуэ и др. (1995) .
  5. ^ Кнут (2013) .
  6. ^ Холтен и ван Вейк (2009) ; Холтен и др. (2011) .
  7. ^ Гарг и Тамассия (1995) .
  8. ^ Лонгабо (2012) .
  9. ^ Ди Баттиста и др. (1998) , Раздел 2.1.2, Эстетика, стр. 14–16; Покупка, Коэн и Джеймс (1997) .
  10. ^ Ди Баттиста и др. (1998) , стр. 14.
  11. ^ Ди Баттиста и др. (1998) , с. 16.
  12. ^ Jump up to: а б Пач и Шарир (2009) .
  13. ^ Гранжан (2014) .
  14. ^ Ди Баттиста и др. (1998) , раздел 2.7, «Подход, направленный на силу», стр. 29–30, и глава 10, «Методы, направленный на силу», стр. 303–326.
  15. ^ Бекман (1994) ; Корен (2005) .
  16. ^ Ди Баттиста и др. (1998) , Глава 5, «Поток и ортогональные рисунки», стр. 137–170; Эйгльспергер, Фекете и Клау (2001) .
  17. ^ Герман, Мелансон и Маршалл (2000) , Раздел 2.2, «Традиционная планировка – обзор».
  18. ^ Сугияма, Тагава и Тода (1981) ; Бастерт и Матушевски (2001) ; Ди Баттиста и др. (1998) , Глава 9, «Многослойные рисунки орграфов», стр. 265–302.
  19. ^ Саати (1964) .
  20. ^ Догрусоз, Мэдден и Мэдден (1997) .
  21. ^ Ди Баттиста и др. (1998) , Раздел 4.7, «Рисунки доминирования», стр. 112–127.
  22. ^ Скотт (2000) ; Брандес, Фриман и Вагнер (2014) .
  23. ^ Ди Баттиста и др. (1998) , стр. 15–16, и глава 6, «Поток и восходящая плоскостность», стр. 171–214; Фриз (2004) .
  24. ^ Заппони (2003) .
  25. ^ Андерсон и Хэд (2006) .
  26. ^ Баттиста и Римондини (2014) .
  27. ^ Бахмайер, Брандес и Шрайбер (2014) .
  28. ^ «Graphviz и Dynagraph - инструменты для рисования статических и динамических графиков», Джон Эллсон, Эмден Р. Ганснер, Элефтериос Кутсофиос, Стивен К. Норт и Гордон Вудхалл, в Jünger & Mutzel (2004) .
  29. ^ «Введение в рисование графиков» , Центр документации Wolfram Language & System , получено 21 марта 2024 г.
  30. ^ Нахмансон, Робертсон и Ли (2008) .
  31. ^ «Тюльпан - огромная структура визуализации графов», Дэвид Обер, в Jünger & Mutzel (2004) .
  32. ^ «yFiles – визуализация и автоматическое размещение графиков», Роланд Визе, Маркус Эйгльспергер и Михаэль Кауфманн, в Jünger & Mutzel (2004) .
  33. ^ Тантау (2013) ; см. также старую презентацию GD 2012. Архивировано 27 мая 2016 г. на Wayback Machine.

Общие ссылки

[ редактировать ]

Специализированные подтемы

[ редактировать ]

Дальнейшее чтение

[ редактировать ]
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 3e67951c17a0b217bffe97a48b47aee0__1721264580
URL1:https://arc.ask3.ru/arc/aa/3e/e0/3e67951c17a0b217bffe97a48b47aee0.html
Заголовок, (Title) документа по адресу, URL1:
Graph drawing - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)