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

Арман Эммануэль София-Септимани де Виньеро дю Плесси, граф де Шинон, 5-й герцог Ришельё

Арман Эммануэль София-Септимани де Виньеро дю Плесси, граф де Шинон, 5-й герцог Ришельё

При изучении темы «Алгоритмы на графах» нам придется столкнуться с несколькими непростыми задачами. Одна из них — визуализация графов. Мы ведь уже привыкли в процессе отладки программы следить за изменением значений переменных и объектов. Мы всегда могли рассмотреть или распечатать строку или массив. В задачах на графах также часто бывает полезным увидеть результат работы именно в виде графа. Т.е. нарисовать его.

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

С.М.Прокудин-Горский. Граф Л.Н.Толстой. Снято 23 мая 1908 г. Ясная Поляна.

С.М.Прокудин-Горский. Граф Л.Н.Толстой. Снято 23 мая 1908 г. Ясная Поляна.

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

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

Для примера, одно из рёбер окрашено в зелёный цвет.
В ориентированных графах следует писать digraph вместо graph и -> вместо —.

Преобразование графа в svg изображение можно провести при помощи утилит пакета graphviz или онлайн. Например, на сайте http://www.webgraphviz.com или https://dreampuf.github.io/GraphvizOnline. Или воспользоваться сервисом google.

Я для примера построил визуализацию The story of Miss Moppet

THE STORY OF MISS MOPPET

THE STORY OF MISS MOPPET:

Визуализация графов на сайте происходит при помощи сервиса Google. Если отправить на адрес http://chart.apis.google.com запрос с кодом описания графа на языке DOT, то в ответ будет сформирован файл картинки с изображением этого графа. Например, у нас имеется следующее простой описание графа:

Если отправить запрос следующего вида (для проверки его можно скопировать в адресную строку браузера)

мы получим такую картинку:

А вот здесь описано как создавать внутреннюю структуру словарного графа для эффективной обработки в дальнейшем.

Мазурок Игорь Евгеньевич

Мазурок Игорь Евгеньевич

Разработчик программного и информационного обеспечения.
Доцент Одесского национального университета имени И.И.Мечникова
Учёный в области защиты и противодейтствия в интеллектуальных информационных системах
Мазурок Игорь Евгеньевич

Latest posts by Мазурок Игорь Евгеньевич (see all)