Graph planarization & drawing layout

[singalen]

Надо нам планаризовать и нарисовать в своём проекте ER-диаграмму.
Для этого её надо как минимум планаризовать.
Ну есть ещё граничные условия типа "9 несвязанных сущностей надо красиво выстаривать в шахматном порядке 3x3".
Жеплателен исходник на .NET под свободной лицензией типа LGPL.
Сваливаю сюда ссылки, которые нарыл, далее буду разбирать.
YFiles. Стоит, как самолёт: http://www.yworks.com/en/products_yfilesdotnet_commercialinfo_prices.htm
GOBLIN - много задач и layout: http://www.math.uni-augsburg.de/~fremuth/goblin.html#intro
GLEE - от MS: http://research.microsoft.com/users/levnach/GLEEWebPage.htm
Netron тоже от MS: http://www.orbifold.net/Netron/info.php
Симпозиум в Вене по теме рисования графов, см секцию Software Exhibition: http://www.informatik.uni-trier.de/~ley/db/conf/gd/gd2001.html
Каталог Open Source Graph Visualization in Java: http://www.manageability.org/blog/stuff/open-source-graph-network-visualization-in-java/view
Graphviz - крайне симпатично: http://www.graphviz.org/
upd: Отличный обзор библиотек.

Comments

[beskov.livejournal.com]

и таки зачем нужны инструментальные средства планаризации? как не хватает головы и часа времени?

[singalen]

1. Чтобы продавать. Должно быть очень кошерно.
2. Часа времени хватит только тому, кто хорошо натренирован на алгоритмы на графах, и только на один вариант. Я был таким когда-то, но и мне понадобится минимум целый день - на проверить-отладить на репрезентативных случаях.
3. Это делаю не я.

[singalen]

Именно! А у меня две недели до релиза. И есть некий алгоритм, но его надо улучшить/переделать.
И есть ещё гора задач, которые мы и без этого не обязательно успеем сделать.

[beskov.livejournal.com]

да я про ручную планаризацию. алгоритмы известны-то

зачем автоматизировать операцию, на которую нужен 1 час раз в полгода?

[singalen]

У нас продукт отображает диаграммы, получающиеся на лету. И мы её релизим.

[http://users.livejournal.com/_adept_/]

За 1 день можно реализовать алгоритм из graphviz, причем не по его исходникам, а по прилагающейся статье. Там все прозрачно и с картинками. Ну, или использовать сам graphviz как библиотеку, возможно.

Правда, с учетом граничных условий там относительно сложно.

[http://users.livejournal.com/_adept_/]

Я ж говорю - сложно с этим.

Надо создавать всякие эфемерные невидимые линки, чтобы достичь такого эффекта.

Либо же чуть подправить алгоритм - там (в dot) отдельно обрабатываются узлы без связей - чтобы они не располагались в линию, а сбивались в кучу ...

[aleksijb.livejournal.com]

"Ну есть ещё граничные условия типа "9 несвязанных сущностей надо красиво выстаривать в шахматном порядке 3x3". "

Может, как вариант, побить граф на несвязанные компоненты? Потом каждую компоненту разбиваем на "слабосвязанные" компоненты. В результате получаем дерево компонент(например можно добавть возможность скрывать компоненты).
Первое что пришло в голову по поводу нахождения "слабозвязанных" компонент: если бы граф был сетью с истоком и стоком, то мы могли бы в сток залить скажем 1 литр и протолкнуть по графу. Дальше удаляем ребро с максимальным потоком. Опять проталиваем и удаляем, пока не разойдется на две несвязанные компоненты.

[singalen]

Та не в алгоритме ж дело :)
Вернее, не он главный. Главное - чтобы было красиво и вчера :)