Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: Рисование графов  (Прочитано 14407 раз)
0 Пользователей и 1 Гость смотрят эту тему.
ezus
Опытный

il
Offline Offline

« : 04-08-2010 07:42 » 

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

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

Спасибо.

Записан
lazy_troll
Интересующийся

ru
Offline Offline

« Ответ #1 : 10-08-2010 11:26 » 

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

Записан

Do not feed the troll
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #2 : 10-08-2010 14:50 » 

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

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

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

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #3 : 10-08-2010 15:37 » 

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

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

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

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #4 : 10-08-2010 15:43 » 

Красивая книжка Улыбаюсь Люблю такие
Записан

.
Молодой специалист

ru
Offline Offline
Пол: Мужской

« Ответ #5 : 04-11-2010 10:04 » 

возможно использовать библиотеку graphviz
Записан
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines