DRAKON.SU

Текущее время: Четверг, 24 Сентябрь, 2020 14:34

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 2 ] 
Автор Сообщение
СообщениеДобавлено: Понедельник, 15 Август, 2016 19:56 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 4842
Откуда: Москва
Язык ДРАКОН и визуализация графов

https://ru.wikipedia.org/wiki/%D0%92%D0 ... 0%BE%D0%B2
Цитата:
Визуализация графов
Материал из Википедии — свободной энциклопедии

Визуализация или отображение графов, как ответвление теории графов, относящееся к топологии и геометрии — двумерное представление графа. В основном, это графическое представление укладки графа на плоскость (как правило, допускается пересечение рёбер), направленное, обычно, на удобное отображение некоторых свойств графа, или моделируемого объекта.

Проблема визуализации графов встаёт, например, при отображении больших интегральных схем, анализе социальных сетей, в таких областях как картография и биоинформатика.

Обзор

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

Способы визуализации

Ортогональное отображение графа

Сеточное отображение графа
В связи с большим разнообразием видов графов, существует множество различных способов отображения графов.

Например, для графов с небольшим числом вершин и сопоставимым с ним числом рёбер, самым удобным может быть прямолинейное представление. Примером такой системы может служить дорожная система города. Но для графа социальной сети прямолинейного отображения, из-за большого числа дуг, будет явно недостаточно.

Можно выделить следующие способы отображения[1]:

произвольное;
прямолинейное — рёбра представляются отрезками;
сеточное;
полигональное — для отображения рёбер используются ломаные;
ортогональное — рёбра представляются ломаными, отрезки которых — вертикальные или горизонтальные линии
планарное[2];
восходящее или низходящее (для ориентированных графов).

Эстетические критерии

Эстетические критерии определяют параметры отображения. Наиболее распространённые среди них[1]:

Пересечения: минимизация общего числа пересечений рёбер.
В идеале, если это возможно, должно быть получено планарное отображение.


Области: минимизация размеров областей.
Общая длина рёбер: минимизация суммарной длины всех рёбер.

Максимальная длина рёбер.
Универсальная длина рёбер: минимизация различий в длинах рёбер.
Общее число изгибов: уменьшение общего числа изгибов.

Максимальное число изгибов.
Угловое разрешение.
Характеристическое отношение.
Симметрия.

См. также

Теория графов
Граф
Теорема Фари
Графовые алгоритмы кластеризации

Примечания

↑ Перейти к: 1 2 Di Battista, Giuseppe; Eades, Peter; Tamassia, Roberto; Tollis, Ioannis G. Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall, 1999. 397 p. ISBN 0-13-301615-3.


В языке ДРАКОН важное значение имеют следующие эстетические критерии, учитываемые при визуализации графов:

Пересечения: минимизация общего числа пересечений рёбер. В идеале, если это возможно, должно быть получено планарное отображение.
— пересечения запрещены.
— достигнут идеал — планарное отображение графа

Области: минимизация размеров областей.
— созданы предпосылки для минимизации областей веток

Общая длина рёбер: минимизация суммарной длины всех рёбер.
— требование выполняется

Универсальная длина рёбер: минимизация различий в длинах рёбер.
— все шампуры силуэта, кроме крайнего правого, имеют одинаковую длину.

Общее число изгибов: уменьшение общего числа изгибов.
— требование выполняется

Максимальное число изгибов.
— должно быть минимальным

Угловое разрешение.
— все углы 90 градусов

Симметрия.
— цель, к которой следует стремиться в строго определенном числе слчаев.
Пример.
1. Высота всех икон Имя ветки должна быть одинаковой.
2. Высота всех икон Адрес должна быть одинаковой.
Последние два правила симметрии выполняются в ДРАКОН-конструкторе Геннадия Тышова (спасибо ему).


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 14 Октябрь, 2019 22:41 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 4842
Откуда: Москва
https://en.wikipedia.org/wiki/Graph_drawing
В английской Wikipedia в статье Graph drawing
есть раздел Graphical conventions

Перевод на русский
Цитата:
Графические соглашения

Направленный граф со стрелками, показывающими направления ребер
Графы часто рисуются в виде узловых диаграмм, в которых вершины представлены в виде дисков, блоков или текстовых меток, а края представлены в виде отрезков , полилиний или кривых в евклидовой плоскости . [3]

Узловые диаграммы можно проследить до работ 13-го века Рамона Лулла , который нарисовал диаграммы этого типа для полных графов , чтобы проанализировать все парные комбинации среди наборов метафизических понятий. [5]

В случае ориентированных графов , стрелки образуют обычно используемые графические конвенции , чтобы показать свою ориентацию ; [2]

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

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

Английский оригинал
Цитата:
Graphical conventions

Directed graph with arrowheads showing edge directions
Graphs are frequently drawn as node–link diagrams in which the vertices are represented as disks, boxes, or textual labels and the edges are represented as line segments, polylines, or curves in the Euclidean plane.[3]

Node–link diagrams can be traced back to the 13th century work of Ramon Llull, who drew diagrams of this type for complete graphs in order to analyze all pairwise combinations among sets of metaphysical concepts.[5]

In the case of directed graphs, arrowheads form a commonly used graphical convention to show their orientation;[2] however, user studies have shown that other conventions such as tapering provide this information more effectively.[6]

Upward planar drawing uses the convention that every edge is oriented from a lower vertex to a higher vertex, making arrowheads unnecessary.[7]



Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 2 ] 

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2008-2020, участники конференции «DRAKON.SU», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB