пятница, февраля 10, 2006

Нарисовать граф красиво

Давным-давно передо мной стояла такая задача: в базе данных лежат несколько графов и хорошо бы их красиво вывести на печать. Чтобы и узлы друг на друга не залезали, чтобы прочитать названия узлов и переходов можно было и чтобы это все было оптимально размещено на листе формата А4. Вариант "двигать квадратики в Visio" и т.п. отметаем с негодованием.
Информации по этому поводу на русском языке очень мало. В основном натыкаешься на вопросы таких же страждущих. Что странно, потому что бывает весьма полезно представить в виде графа какие-нибудь данные, структуры, все сразу становится понятнее.


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

Я в итоге старательно поспрашивала Google на английском и нашла очень много чего интересного.

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

1. Программы для отрисовки графов.
Вам нужно распечатать граф на бумажке, чтобы лучше разобраться в происходящем или чтобы с гордостью показать начальнику/менеджеру. Для этого достаточно скачать какую-нибудь программу, желательно бесплатную, которая умеет графы рисовать.

2. Библиотеки для отрисовки графов.
Вы хотите, чтобы ваша программа рисовала граф унутри себя и вам для этого достаточно библиотеки, которая с этим всем справится.

3. Теория отрисовки графов (Graph Drawing Theory).
Вам интересна именно теория отрисовки графов с научной точки зрения. Здесь я расскажу все, что знаю про эту теорию, и дам ссылки на книги и ресурсы по этой теме.

Ссылки по теме:
visualcomplexity.com Коллекция ссылок на проекты, занимающиеся визуализацией сложных сетей.
Швейцарский нож, или Визуализация графов. Статья Андрея Зубинского.

11 коммент.:

singalen комментирует...

Сначала граф желательно планаризовать... планаризация делается через выделение планарных "шаблонных графов"... дальше не помню.
Потом это всё утряхивать в лист А4 с учётом надписей.
Таскание прямоугольников мышой в Visio выглядит всё более привлекательно %)

Alena комментирует...

Сначала граф желательно планаризовать... планаризация делается через выделение планарных "шаблонных графов"... дальше не помню.

С планарными графами работать проще. Но можно и непланарный отрисовать. Ну будут пересечения у ребер, какая разница. Потом, если рисовать граф в 3Д, то вопрос о планарности снимается. :-)

Потом это всё утряхивать в лист А4 с учётом надписей.

Вот в этом собственно и вся фишка.

Таскание прямоугольников мышой в Visio выглядит всё более привлекательно %)

А если граф постоянно меняется и его надо отрисовывать раз в неделю? Что если этих графов 100 штук? А если в нем 10000 узлов?
Кстати, я заинтересовалась этим вопросом после того как весь наш отдел убился двигать все это в Visio.

Marduk комментирует...

>>А если граф постоянно меняется и его надо отрисовывать раз в неделю? Что если этих графов 100 штук? А если в нем 10000 узлов?
Кстати, я заинтересовалась этим вопросом после того как весь наш отдел убился двигать все это в Visio.


Может, теперь в Вашем отделе появится Unix-like OS, на которой с требуемой периодичностью буду обрабатываться Makefile'ы, генерирующие средствами GraphViz все эти графы ;)? Это конечно утрируя, win32-версия GraphViz имеется, да и Cygwin может пригодится...
Со страшным интересом ждём-с продолжения :)

Prokrust комментирует...

Есть еще один аспект графов, существенный для программистов :).
Статья "Visualize function calls with Graphviz" от M. Tim Jones. Возможность автоматического построения графа вызовов функций в программе написанной на GCC меня просто завораживает.

Анонимный комментирует...

Здравствуйте, Алена. Спасибо за статью :)Не могли бы вы мне помочь?! Дело то вроде, на первый взгляд, простое,но так как мне это вновинку, то возникли сложности. По задумке, мне нужно по данным файла отрисовать дерево... как можно (и можно ли вообще) вызвать выполнение Графвиза из своей программы(на Builder'e), указав ему путь к файлу?

Светлана.(lashes@yandex.ru)

J()KER комментирует...

Интересно, а если, например, нужно построить гриф on-line как карту ссылок на взаимосвязанные материалы сайта?!

Алёна комментирует...

2J()KER:
Интересно, а если, например, нужно построить гриф on-line как карту ссылок на взаимосвязанные материалы сайта?!

Тут в общем неважно граф чего строить. Можно попробовать тем же GraphViz'ом формировать gif и его отдавать.

alex комментирует...

Привет, Алёна
Познакомился с Вашим материалом и решил задать вопрос как эксперту. Что советуете посмотреть (какие программы или библиотеки), если требуется нарисовать граф расписания движения? Речь о графе на экране компьютера. Желательно чтобы он «лежал» на географической карте и, для начала, просто показывал связи между пунктами (городами). Затем потребуется показать интенсивность движения по рёбрам графа (толщиной, построением параллельных рёбер, числом рейсов и т.п.). Ну и совсем здорово, если бы по щелчку на вершине (ребре) передать управление в отдельный модуль с целью отображения загрузки данной вершины или расписания данного ребра.
О себе: профессиональный разработчик-прикладник, сейчас использую Java (Java 2D), поэтому Java рекомендации особенно желательны.
Кстати в разделе aiSee вроде мелкая ошибка: «Очень настраивают на том,», а похоже надо «Очень настаивают на том,»

Алёна комментирует...

2alex:Привет, АлёнаПриветствую!

Познакомился с Вашим материалом и решил задать вопрос как эксперту.Я написала этот пост три года назад и с тех пор отрисовкой графов не занималась. Так что я тут не эксперт ни разу. И затрудняюсь что-либо посоветовать....

Кстати в разделе aiSee вроде мелкая ошибка: «Очень настраивают на том,», а похоже надо «Очень настаивают на том,»Угу, спасибо, поправила.

Nick комментирует...

Есть прекрасная утилита dotty. Нужно лишь сформировать для нее шаблон.

Nat S комментирует...

ссылка на статью Андрея Зубинского к сожалению не работает...