Русскоязычное программирование

Информация о пользователе

Привет, Гость! Войдите или зарегистрируйтесь.


Вы здесь » Русскоязычное программирование » базовые определения » Визуализация графов


Визуализация графов

Сообщений 1 страница 14 из 14

1

[html]<a href="https://ru.wikipedia.org/wiki/Визуализация_графов">https://ru.wikipedia.org/wiki/Визуализация_графов</a>[/html]

2003, Н.В. Касьянов, В.А. Евтигнеев "Графы в Программировании:обработка, визуализация и применение.", Глава 5
     в основном общие рассуждения на тему "ох как много вариантов, всё NP-полное, что делать, что делать..."

диаграммы
молекулы
электрические схемы

Отредактировано Лис (2017-11-06 12:03:34)

0

2

Я поэтому и использовал деревья - графы трудно представлять графически, там нужна полная n-мерность, а работа на плоскости не обеспечивает понимание графов. Писать же систему, которая может представлять графы на плоском мониторе дело утомительное и заранее неблагодарное. Потому что у большинства людей (и у меня тоже) мозг обычно плоский как монитор, им и 3 измерения дается с большим трудом, чего уже про остальное говорить.

0

3

Любой граф можно извобразить в 3D. Доказательство - расположим вершины на прямой линии, через линию проведём бесконечное количество плоскостей. Расположим каждое ребро в своей полуплоскости. Полуплоскости не пересекаются, значит и рёбра не пересекаются, задача решена.

Ты недостаточно китаец, Уткин, иначе бы ты подходил к проблеме рисования графов на плоскости более творчески.

0

4

Полуплоскости не пересекаются, значит и рёбра не пересекаются, задача решена.

Введем граф с огромным количеством вершин. Настолько большим, что число вершин на единицу пространства будет больше чем видимая глазу толщина ребра. Результат? Взрыв сверхновой. На самом деле результат может превзойти все ожидания несколько ранее, если в графе не равномерно распределены отношения между узлами. Но и это еще не все - Ваш пример чистый сферический конь в вакууме. Потому как во-первых, по фень-шую ребра должны быть прямые. Во-вторых, при числе узлов больше 20-30 и числе ребер достаточно чтобы не считать граф тупым недодеревом воспринять адекватно Вы его все равно не сможете. Патамучта мозг будет катастрофически перегружен избытком одновременных связей и будет тупо любоваться картинкой, вместо того чтобы сдавать анализы по графу. В третьих, опять же оторвавшись от теории, начинаем рисовать все это безделие не геометризируя абстрактно, а на реальном мониторе и получаем различные траблы, потому что все это либо надо анимировать (без гарантии адекватного восприятия) либо раскрашивать (с тем же эффектом) либо и то и другое и тоже неизвестно чем это кончится. Результат - у мозга нет возможности выбрать точку отсчета (банально в рисовании 3Д абстрактного графа нет указания на юг, верха или Солнца как источника света) и все приплыли - один неосторожный поворот ста вершин графа в произвольной горячо любимой Вами полуплоскости приведет к начальному состоянию - простому созерцанию красивой картинки :). В-четвертых, отбросив все теоретические разглагольствования и переходим к реальным практическим инструментам - и о чудо! нет их не фига. Максимум чего добились - условное представление молекулы ДНК, которую никто собственно не видел (но существует куча косвенных улик, указывающих на спираль). Ну и еще есть некоторые успехи в представлении химических там всяческих молекул, но тоже грубо и условно. Я может быть и не китаец, но над графами как-то думал уже. И думал конкретно использовать их языке программирования (потому как выразительная сила графа ясень пень выше чем у дерева), но не судьба. Нет там такого чтобы было дешево и сердито. Либо надо заморачиваться с матаном, либо выпрямлять всем программистам мозги, что почти одно и тоже по уровню сложности. Плюс отсутствие даже намека на примитивные операции - ну например, то же дерево в каком-нибудь HTML можно грубо говоря свернуть, если реализовывать узлы вложенными спойлерами. Получил дерево - фигак его в HTML-отчет, вот тебе счастье. Свернул узел - ты на новом уровне декомпозиции - хочешь тактический уровень, хочешь стратегический, хочешь оперативный. Графы так локализовать по уровням фигу с маслом.

Отредактировано utkin (2017-11-06 12:14:39)

0

5

[html]<a href="https://arxiv.org/pdf/1506.06745v1.pdf">GraphMaps: Browsing Large Graphs
as Interactive Maps</a>[/html]

16 million edges and 200000 nodes

Отредактировано Лис (2017-11-06 12:18:17)

0

6

Вы никак не поймете, что проблема не в рисовании, а в рисовании так, чтобы было понятно для того, кому это все рисуют. И операции над графами в простой и удобной форме также не рассмотрены.
Ну вот красивая картинка:
http://s3.uploads.ru/t/4OFmW.png
И как Вы собираетесь увидеть в этом пучке волос изменения ребер например хотя бы в 10 узлах? Или сравнить два графа между собой? Ежу понятно, что можно подобрать граф, отличающийся например, процентов на 20, но который будет выглядеть как такой-же клок волос, просто потому что количество узлов слишком велико. Но даже для малых графов с количеством узлов до 100 тяжело будет увидеть отличие в одну связь. Конечно, аналогичные проблемы есть и в деревьях, но там во-первых, такие проблемы возникают при большем числе узлов, во-вторых, имеются формальные способы (типа рекурсивного обхода) для решения проблем подобного рода.
Дичайшая проблема №2 - сравнить два графа визуально нельзя даже в 2Д ибо имеется стопятьсот вариантов рисования одного и того же графа в разных ипостясях, изометриях и прочих мракобесиях. Как не крутите, а работать с графами человек может только по приборам из-за устройства его восприятия окружающего мира.
И вообще в графах матан суровей, с деревьями все более нежно - посмотрите на Лисп, там эти скобочки есть не что иное как обход дерева и вся эта функциональщина с множественным вложенным вызовом функций это не что иное как дерево.
ЗЫ. Перевернув данную картинку на какие-нибудь 47 градусов, сможете ли Вы не зная этого и невооруженным глазом догадаться что перед нами один граф?

Отредактировано utkin (2017-11-06 13:13:19)

0

7

Я поэтому и использовал деревья - графы трудно представлять графически

Ещё бывают очень наглядны и удобны таблицы, Excel, например. Есть целая теория нормализация.

utkin написал(а):

проблема не в рисовании, а в рисовании так, чтобы было понятно для того, кому это все рисуют.

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

Любой граф можно извобразить в 3D.

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

Лис написал(а):

"ох как много вариантов, всё NP-полное, что делать, что делать..."

В естественных языках высокая сложность, но их осваивают миллиарды, многие даже более одного.

Отредактировано MihalNik (2017-11-06 17:21:18)

0

8

Ещё бывают очень наглядны и удобны таблицы, Excel, например. Есть целая теория нормализация.

Не думаю, что я смог бы превзойти реляционные базы данных :).

Число входных и выходных связей для задач как правило делают небольшим. Из графа можно делать различные вырезки, отражающие те или иные связи.

В общем, да. Но нормальных инструментов все равно нет и это жжжжжжж не спроста!

Словесность позволяет обрывать изображения узлов и связей.

Увы, в формальном представлении все это выродится во что-нибудь не читаемое, типа матрицы смежности.

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

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

В естественных языках высокая сложность, но их осваивают миллиарды, многие даже более одного.

Естественные языки гиперизбыточны.  Количество синтаксическго и семантического сахара там на десять диабетов хватит. Это несколько облегчает процесс распознавания. Кроме того, миллиарды, как правило, осваивают только сильно усечное подмножество языка. Полный язык знает очень небольшое количество пациентов. Возьмите современный словарь - уверен найдутся слова которые Вам не известны даже если отбросить церковнославянский, старые слова и специализированные термины. Все равно найдется какое-нибудь слово, которое будет в доску русское, но Вам неизвестное.

Отредактировано utkin (2017-11-06 18:58:49)

0

9

utkin написал(а):

матрицы смежности.

Какое она имеет отношение к словесности, о_О?
В словесности смежность выражается, например, согласованием окончаний.

utkin написал(а):

А все потому что граф не имеет привязки, точки отсчета.

Слова решают эту проблему, называя данные или вычислительные участки.

utkin написал(а):

Естественные языки гиперизбыточны.

Не слишком они избыточны, на уровне защиты от простейших ошибок.

utkin написал(а):

Полный язык знает очень небольшое количество пациентов.

Они вообще-то не ограничены. Вы даже можете сделать слова, которых нет в словаре, но они будут вполне понятны в соответствующем контексте.

Отредактировано MihalNik (2017-11-06 19:12:40)

0

10

Какое она имеет отношение к словесности, о_О?

Это пример, к чему приводит попытки представления графов. Наш мозг просто не приспособлен к работе с ними.

В словесности смежность выражается, например, согласованием окончаний.

Ну вот Вы сознательно начинаете сужать задачу. Библия так описывает мир: "Сначала было слово"  :crazyfun: Получается у Библии хреново.

Отредактировано utkin (2017-11-06 19:01:31)

0

11

utkin написал(а):

Ну вот Вы сознательно начинаете сужать задачу.

Нет, речь шла про то, что с передачей связи лучше всего пока что справляются обычные человеческие языки, а не примитивные.
Лисп прост, но его от всех тошнит - потому что построен на куче примитивных выражений, решающих не нужные задачи, как, например, и С++.
А Python лучше отображает собственно дерево и поэтому используется намного больше Лиспа.
Но древовидная плоскость ЯП - лишь часть графа программы, остальное передаётся обычным текстом.

Отредактировано MihalNik (2017-11-06 19:12:15)

0

12

Лисп прост, но его от всех тошнит - потому что построен на куче примитивных выражений, решающих не нужные задачи, как, например, и С++.

Лисп просто стар.

А Python лучше отображает собственно дерево и поэтому используется намного больше Лиспа.

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

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

В этом и есть проблема графов - их сложно представлять :). Вот и возвращаемся к началу темы.

Отредактировано utkin (2017-11-06 19:39:07)

0

13

utkin написал(а):

В этом и есть проблема графов - их сложно представлять

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

Отредактировано MihalNik (2017-11-06 21:01:01)

0

14

И дерево даёт только некоторый срез. Разумеется, очень полезный, который часто можно использовать как основной.

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

0


Вы здесь » Русскоязычное программирование » базовые определения » Визуализация графов