информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
За кого нас держат?Сетевые кракеры и правда о деле ЛевинаПортрет посетителя
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Три миллиона электронных замков... 
 Doom на газонокосилках 
 Умер Никлаус Вирт 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / miscellaneous
Имя Пароль
ФОРУМ
если вы видите этот текст, отключите в настройках форума использование JavaScript
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Гыг. Планарная проекция графа - вообще то NP-сложная задача. 21.02.07 20:32  Число просмотров: 2206
Автор: amirul <Serge> Статус: The Elderman
Отредактировано 21.02.07 20:37  Количество правок: 1
<"чистая" ссылка>
http://www.google.com/search?hl=ru&client=opera&rls=ru&hs=pxu&sa=X&oi=spell&resnum=1&ct=result&cd=1&q=Kamada+Kawai&spell=1

В boost-е есть
http://www.boost.org/libs/graph/doc/kamada_kawai_spring_layout.html

Еще можно сходить на http://www.graphdrawing.org/ почитать литературу.

Для всех желающих попробовать задачу на сложность:
http://legko.be/index.php?option=com_content&task=view&id=1254&Itemid=50
<miscellaneous>
Отрисовка графа - как? 20.02.07 15:05  
Автор: Yurii <Юрий> Статус: Elderman
<"чистая" ссылка>
Нужен алгоритм отрисовки графа, причем так, чтобы вершины располагались оптимальным образом, т.е. чтобы ребра пересекались минимальное число раз.
Т.е. дали на вход матрицу схемы московского метрополитена, на выходе получили что-то отдаленно ее напоминающее, а не исчерканный экран. :)
Скажите,плз, в каком направлении двигаться?
Соображения в общих чертах 20.02.07 15:29  
Автор: Heller <Heller> Статус: Elderman
<"чистая" ссылка>
Пусть координаты двух разных вершин, соединенных разными графами равны соответствено (x1;y1), (x2;y2), (x3;y3), (x4;y4). Соединены первые две точки и последние две. Можно сформулировать логическое условие их пересечения. Тут либо комбинация множества <>, либо ищешь точку пересечения двух прямых, проведенных через точки и смотришь, чтобы ее координаты попадали внутрь прямоугольника, построенного по этим точкам.

Короче должно получиться при пересечении 1, а при отсутствии оного 0.

Проверяешь пересечения для каждой пары ребер, получаешь количество пересечений, то есть критерий, который будет являться функцией кучи переменных - координат вершин. Далее применяешь любой алгоритм многомерной оптимизации и находишь оптимальное расположение точек на плоскости.
Отлично, но если узлов будет хотя бы сотня, боюсь я зависну надолго... 21.02.07 19:52  
Автор: Yurii <Юрий> Статус: Elderman
<"чистая" ссылка>
Гыг. Планарная проекция графа - вообще то NP-сложная задача. 21.02.07 20:32  
Автор: amirul <Serge> Статус: The Elderman
Отредактировано 21.02.07 20:37  Количество правок: 1
<"чистая" ссылка>
http://www.google.com/search?hl=ru&client=opera&rls=ru&hs=pxu&sa=X&oi=spell&resnum=1&ct=result&cd=1&q=Kamada+Kawai&spell=1

В boost-е есть
http://www.boost.org/libs/graph/doc/kamada_kawai_spring_layout.html

Еще можно сходить на http://www.graphdrawing.org/ почитать литературу.

Для всех желающих попробовать задачу на сложность:
http://legko.be/index.php?option=com_content&task=view&id=1254&Itemid=50
1




Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2024 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach