вторник, февраля 14, 2006

Программы для отрисовки графов

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

GraphViz

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

Прежде чем начать работать лучше почитать хелп, который лежит в директории GraphViz/doc. Интуитивно понятный интерфейс вас там не ждет. На самом деле GraphViz - это набор из нескольких программ, я пользовалась одной из них, dotty. dotty умеет считывать граф из текстового файла, где граф преставлен в несложном формате, и красиво выводит его на экран. Если что-то не понравится, узлы можно подвинуть, подправить самостоятельно. Здесь же можно добавить/удалить узлы, можно вообще здесь же граф нарисовать. Если зарыться в документацию, то можно узнать, что dotty делает иерархическую раскладку, а GraphViz умеет и другие, но можно в это и не вникать. Это идеальное решение, если хочешь просто нарисовать граф, не забивая себе голову деталями, раскладками и т.п.
У меня граф лежал в виде списка узлов и переходов в базе данных. Я написала небольшой скрипт, который вытягивал этот граф из базы и писал его в текстовый файл в формате, понятном dotty. Потом скармливала этот граф dotty. Мне вполне этого хватило.
Как написано у них на сайте, отрисованный граф можно экпортировать в графические форматы, SVG, Postscript. Экспортом я не пользовалась, мне надо было только распечатывать.
Есть варианты под Windows, пэкаджи для Линукса, разных Юниксов, MacOS. Есть исходники.

Следующими программами я не пользовалась, цитирую то, что написано у них на сайте.

yEd
yEd построена на базе java-библиотеки для отрисовки графов под названием yFiles. Библиотека не бесплатна, а вот программа yEd бесплатная. Интерфейс красивый, на сайте много скриншотов с отрисованными графами. Пользователей затравливают красивыми картинками.
Есть экспорт в форматы SVG, WMF, BMP, JPG и GIF.

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



Органическая раскладка


Ортогональная раскладка.

Примеры отрисовки больших графов.


Большая кластеризованная сеть


Большая сеть отрисована в круговой раскладке


Древовидная стукрура, 10000 узлов


Большая карта сети, отрисованная в органической раскладке

aiSee
Это уже за деньги, но есть 30-дневная урезанная триал-версия. Ее можно получить для некоммерческого использования, но некоммерческая версия тоже урезана.



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

Что представляет собой особенный интерес - есть версия сайта на русском. И очень интересный пример графа я там откопала. Они перевели карту московского метрополитена в формат GDL (graph description language), в котором они хранят все графы, и отрисовали. То, что у них получилось, уж больно похоже на официальную карту метрополитена.

Умеет экспортировать в форматы SVG, PNG и HTML.
Есть версии для Windows, Linux, Solaris, и Mac OS X.


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



WilmaScope 3D




Walrus


Обе написаны на Java с использованием Java3D, у обеих исходники открытые.

Проектов по отрисовке графов огромное количество. Постоянно появляются новые, старые умирают. Вот несколько ссылок на проекты, которые не вошли в мой рассказ.
GVF - The Graph Visualization Framework
Graph Visualisation
uDraw(Graph)
Comp.compilers: tools for graph visualization - summary. Очень старое обсуждение программ для отрисовки графов.

Это продолжение рассказа об отрисовке графов. Начало можно найти тут: Нарисовать граф красиво.

19 коммент.:

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

Здравствуй, Алена! Я совсем не давно познакомился с твоим блогом, интересные статьи можно у тебя почитать. Спасибо тебе большое :-)

Но вижу реклама и сюда добралась :-( Комерция - двигатель прогресса.

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

Здравствуй, Алена! Я совсем не давно познакомился с твоим блогом, интересные статьи можно у тебя почитать. Спасибо тебе большое :-)

:-)

Но вижу реклама и сюда добралась :-(

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

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

Прикольно, долг рассматривал графы по ссылочке, особенно понравился граф вызовов WIn32API

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

Спасибо за обзор! Не думаю, чтобы Вам было нужно средство визуализации структуры ПО, но вот ещё что интересно: Rigi. Ну и, как обычно, статья А.Зубинского о нём:
http://itc.ua/article.phtml?ID=19289 :-)

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

Здравствуйте, Алёна,

а вы с этим вот милым списком случайно не знакомы?

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

Здравствуйте, Алёна,

Приветствую!

а вы с этим вот милым списком случайно не знакомы?

Да, видела. Еще на dmoz.org есть аналогичный.

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

Да, Google его оттуда и берёт.

(А схему метро Первопрестольной на GDL моя малость переводила. Очень рад, что вам понравилось.)

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

Да, Google его оттуда и берёт.

Хм, то-то я смотрю, похожи они :-)

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

О! Может прольете тогда свет на этот граф? Я внимательно почитала, что по его поводу написано, но так и не поняла до конца. Раскладка была получена с помощью aiSee? Или раскладка была жестко забита, а весь смысл перевода в граф состоит в том, чтобы можно было его обрабатывать и дополнительную информацию вводить?

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

Да, раскладка была жёстко забита. Точнее, были забиты координаты узлов, а aiSee нарисовал всё остальное, т. е. рёбра и этот самый "subgraph wrapping" (простите, с ходу не соображу, как его по-нашему кликают).

Впрочем, секрета мы из этого не делаем. Загляните в GDL-исходник, там для каждого узла так и написано: loc: {x: такой-то, y:сякой-то}.

Сделано это было по той простой причине, что в данном случае перед нами не граф как граф, а помесь графа с географической картой.

То есть, aiSee и сам бы раскладку вычислил (на то он и создан), но тогда карта перестала бы быть картой. Ща усё бросют, будут нам Кузьминки с Преображенкой местами меняться, только потому, что какой-то там софт решил, что так красивше будет.

Говоря короче: да, смысл данного конкретного перевода состоит в том, чтобы можно было граф обрабатывать, интерактивно прятать линии метро, переводить в SVG итдитп.

Хотя на самом деле это всё враки. Если честно, то я просто дурью маялся. С ностальгии. Скучал, грустил, руку никому не подавал. Вот и соорудил матушке-столице памятник на чужбине. В формате GDL.

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

Здравствуйте, Алена.
Попытался установить GraphViz себе и попробовать на тестовых примерах. Но dotty отрисовывает графы вовсе не так красиво, как на демонстрационных картинках. Я что-то делаю не так?

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

2rigidus:
Здравствуйте, Алена.

Приветствую!

Попытался установить GraphViz себе и попробовать на тестовых примерах. Но dotty отрисовывает графы вовсе не так красиво, как на демонстрационных картинках. Я что-то делаю не так?

Сложно сказать. Насколько я помню, у GraphViz'а есть возможность отрисовки графов с помощью нескольких разных алгоритмов, можно попробовать с этим поковыряться...
Те графы, в которыми я экспериментировала, он отрисовал очень достойно. Причем сразу же, без каких-либо экспериментов с настройками. Хотя один из этих графов был очень неудобный: здоровый и практически полносвязный.

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

Я использую те примеры, которые даны в галлерее - например вот: http://www.graphviz.org/Gallery/twopi/twopi2.html
Но когда я запускаю этот граф у меня получается совсем другая картинка: http://gehirn.ru/bad/graphbad.jpg

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

2rigidus:
Я использую те примеры, которые даны в галлерее - например вот: http://www.graphviz.org/Gallery/twopi/twopi2.html

Но когда я запускаю этот граф у меня получается совсем другая картинка: http://gehirn.ru/bad/graphbad.jpg

Дык эта, в примере Radial layout. И там еще сверху приписано "Drawn using twopi". Возможно, это их модуль какой-то.

А graphbad.jpg нарисован не в радиальной раскладке, а в какой-то другой. На метод Сугиямы вообще похоже.

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

Здраствуйте Алёна!
Странно, что уже 2 раз при поиски натыкаюсь на ваш блог. Я бы ещё к программам добавил Графоанализатор, хотя он не такой крутой, но бесплатных, хоть и оринтирован на курс дискретной матиматики.

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

а КАК это продать, не всмысле денег заработать, а КОМУ это вообще нужно, куча красивой графики для SF и больше ничего .... ?

pure virtual комментирует...

Огромное спасибо за такую подборку с живыми ссылками!

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

Надеюсь, что-то из этого списка таки справится out-of-the-box:)

brain-ripper комментирует...

Интересный пример с графом московского метрополитена для программы aiSee. Но в исходниках этого графа (язык GDL) указаны координаты всех станций - не очень понятно, что тогда делают алгоритмы визуализации графа - делов-то просто отобразить точки с заданными координатами...

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

Алёна, yEd - прекрасен!! Я так долго искала тулзу для отрисовки графов!! Ине для диплома больше 20-ти штук нарисовать надо, а всё не то попадалось!! А тут - и стилей куча, и экспортнуть можно в 100500 форматов!! Я в восторге!! Огромное спасибо за такой обзор!!

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

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