График

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

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

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

Содержание

• 1 Графические соглашения
• 2 Меры качества
• 3 Методы компоновки
• 4 Графические рисунки для конкретного приложения
• 5 Программное обеспечение
• 6 Ссылки
• 7 Внешние ссылки

Графические обозначения

Направленный график со стрелками, показывающими направления краев

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

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

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

Показатели качества

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

Плоский граф, нарисованный без перекрывающихся ребер

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

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

Визуализация сети на основе силы.

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

• В принудительно- на основе систем макета, программное обеспечение для рисования графов изменяет начальное размещение вершин, непрерывно перемещая вершины в соответствии с системой сил, основанной на физических метафорах, связанных с системами пружин или молекулярной механики. Как правило, эти системы объединяют силы притяжения между соседними вершинами с силами отталкивания между всеми парами вершин, чтобы найти компоновку, в которой длины ребер малы, а вершины хорошо разделены. Эти системы могут выполнять минимизацию на основе градиентного спуска функции энергии , или они могут преобразовывать силы непосредственно в скорости или ускорения для движущихся вершин.
• Спектральная компоновка использовать в качестве координат собственные векторы матрицы , например, лапласиан, полученный из матрицы смежности графа.
• Методы ортогональной компоновки, которые позволяют краям графа располагаться горизонтально или вертикально, параллельно осям координат компоновки. Эти методы изначально были разработаны для задач компоновки VLSI и PCB, но они также были адаптированы для построения графиков. Обычно они включают многофазный подход, при котором входной граф планаризуется путем замены точек пересечения вершинами, обнаруживается топологическое вложение планаризованного графа, ориентация ребер выбирается для минимизации изгибов, вершины размещаются в соответствии с этими ориентациями и, наконец, макет Стадия уплотнения уменьшает область чертежа.
• Алгоритмы компоновки дерева показывают формирование дерева с корнями, подходящего для деревьев. Часто в технике, называемой «компоновка балуна», дочерние элементы каждого узла в дереве рисуются по кругу, окружающему узел, причем радиусы этих кругов уменьшаются на более низких уровнях дерева, чтобы эти круги не перекрывались.
• Рисование многоуровневых графиков методы (часто называемые рисованием в стиле Сугияма) лучше всего подходят для направленных ациклических графиков или графиков, которые почти ациклические, например графиков зависимостей между модулями или функциями в программном обеспечении. система. В этих методах узлы графа организованы в горизонтальные слои с использованием таких методов, как алгоритм Коффмана – Грэма, таким образом, что большинство ребер идут вниз от одного уровня к другому; после этого шага узлы внутри каждого слоя располагаются так, чтобы минимизировать пересечения.

Дуговая диаграмма

• Дуговая диаграмма, стиль компоновки, восходящий к 1960-м годам, размещает вершины на линии; ребра могут быть нарисованы как полукруги над или под линией или как плавные кривые, соединенные вместе несколькими полукругами.
• Круговая компоновка методы помещают вершины графа в круг, тщательно выбирая порядок вершин вокруг круг, чтобы уменьшить количество пересечений и разместить смежные вершины близко друг к другу. Края могут быть нарисованы либо как хорды круга, либо как дуги внутри или снаружи круга. В некоторых случаях можно использовать несколько окружностей.
• Рисунок доминирования размещает вершины таким образом, что одна вершина находится вверх, вправо или обе вершины другой тогда и только тогда, когда она достижима из другая вершина. Таким образом, стиль макета делает отношение достижимости графика визуально очевидным.

Графические рисунки для конкретного приложения

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

• Социограммы, рисунки социальной сети, часто предлагаемые программным обеспечением для анализа социальных сетей
• диаграммы Хассе, тип графического рисунка, специализированный для частичных порядков
• Dessin d ' enfants, тип рисунка графа, используемый в алгебраической геометрии
• Диаграммы состояний, графические представления конечных автоматов
• диаграммы компьютерных сетей, изображения узлов и соединения в компьютерной сети
• Блок-схемы и drakon-charts, чертежи, на которых узлы представляют этапы алгоритма , а края представляют поток управления между шагами.
• Диаграммы потоков данных, чертежи, на которых узлы представляют компоненты информационной системы, а края представляют перемещение информации от одного компонента к другому.
• Биоинформатика, включая филогенетические деревья, белок-белковые взаимодействия сети и метаболические пути.

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

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

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

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

• BioFabric открытый - исходное программное обеспечение для визуализации больших сетей путем рисования узлов в виде горизонтальных линий.
• Cytoscape, программное обеспечение с открытым исходным кодом для визуализации сетей молекулярного взаимодействия
• Gephi, программное обеспечение для анализа и визуализации сетей с открытым исходным кодом
• graph-tool, free/libre библиотека Python для анализа графиков.
• Graphviz, система рисования графиков с открытым исходным кодом от ATT Corporation
• Linkurious, коммерческое программное обеспечение сетевого анализа и визуализации для графических баз данных
• Mathematica, универсальный вычислительный инструмент, который включает в себя 2D и 3D визуализацию графиков и инструменты анализа графиков.
• Microsoft Automatic Graph Layout, библиотека.NET с открытым исходным кодом (ранее называвшаяся GLEE) для компоновки графиков
• NetworkX - это библиотека Python для изучения графиков и сетей.
• Tom Sawyer Software Tom Sawyer Perspectives - это графическое программное обеспечение для построения графиков корпоративного класса, а также приложений для визуализации и анализа данных. Это пакет разработки программного обеспечения (SDK) с графическим дизайном и средой предварительного просмотра.
• Tulip (программное обеспечение), инструмент визуализации данных с открытым исходным кодом
• yEd, редактор графиков с макетом графиков функциональность
• PGF / TikZ 3.0 с пакетом graphdrawing(требуется LuaTeX ).
• LaNet-vi, программное обеспечение для визуализации больших сетей с открытым исходным кодом
• Edraw Max Программное обеспечение для построения 2D-технических диаграмм

Ссылки

Сноски

Общие ссылки

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

Внешние ссылки

• Библиотека GraphX ​​для.NET : библиотека WPF с открытым исходным кодом для графов расчет и визуализация. Поддерживает множество алгоритмов компоновки и разводки краев.
• Архив электронной печати для рисования графиков : включая информацию о статьях из всех симпозиумов по рисованию графиков.
• Рисование графиков в Curlie для многих дополнительных ссылок, связанных с рисованием графиков.