Арман Эммануэль София-Септимани де Виньеро дю Плесси, граф де Шинон, 5-й герцог Ришельё
При изучении темы «Алгоритмы на графах» нам придется столкнуться с несколькими непростыми задачами. Одна из них — визуализация графов. Мы ведь уже привыкли в процессе отладки программы следить за изменением значений переменных и объектов. Мы всегда могли рассмотреть или распечатать строку или массив. В задачах на графах также часто бывает полезным увидеть результат работы именно в виде графа. Т.е. нарисовать его.
Забегая вперед, скажу, что еще одна интересная задача это генерация тестов. Т.е. задача генерации графа с указанными свойствами (например, связного графа с заданным числом вершин и ребер). При создании таких тестов необходимо использовать генераторы случайных чисел иногда с весьма специфическими распределениями вероятностей.
С.М.Прокудин-Горский. Граф Л.Н.Толстой. Снято 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:
Визуализация графов на сайте происходит при помощи сервиса Google. Если отправить на адрес http://chart.apis.google.com запрос с кодом описания графа на языке DOT, то в ответ будет сформирован файл картинки с изображением этого графа. Например, у нас имеется следующее простой описание графа:
|
1 |
digraph{A->B->C->A} |
Если отправить запрос следующего вида (для проверки его можно скопировать в адресную строку браузера)
|
1 |
http://chart.apis.google.com/chart?cht=gv&chl=digraph{A->B->C->A} |
мы получим такую картинку:
А вот здесь описано как создавать внутреннюю структуру словарного графа для эффективной обработки в дальнейшем.