Рисование графов

[ezus]

Здравствуйте.

Имеется граф, заданный в матричной форме, и есть пакет, умеющий рисовать кружочки и палочки, но, естесственно, требующий задание координат.
Проблема: найти подходящую библиотеку или, на худой конец, подробный алгоритм расчета координат верши графа.
Разработка ведется в VC6.0.

Спасибо.

[lazy_troll]

Проще всего разместить вершины на окружности

[Dimka]

lazy_troll, этого мало. Могут быть сегменты большой связности, у которых вершины будут лежать на окружности рядом, тогда все рёбра между ними практически сольются. И это будет тем хуже, чем больше вершин у графа.

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

Можно использовать алгоритмы плоской укладки (аналогичные алгоритмам разводки печатных плат) - они дают непересекающееся размещение рёбер графов, но не во всех случаях (для полных графов и подграфов 5 или 6 вершин плоская укладка невозможна в принципе).

[Dimka]

Краткий рассказ (на 107 страниц) о различных методах визуализации самых разнообразных типов графов с достоинствами и недостатками каждого метода, а также с обсуждением языков описания визуального представления графов (простым английским языком с обилием картинок - презентация):

http://www.cs.brown.edu/~rt/papers/gd-tutorial/gd-constraints.pdf

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

[Алексей++]

Красивая книжка Люблю такие

[.]

возможно использовать библиотеку graphviz