Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Языки программирования > Prolog
Перезагрузить страницу Генерация полносвязных неориентированных n-графов
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
Винитарх Винитарх вне форума
Специалист
 
Аватар для Винитарх
 
Сообщений: 7,861
Сказал(а) спасибо: 2
Поблагодарили 287 раз(а) в 287 сообщениях
Регистрация: 01.03.2003
Адрес: Краснодар
По умолчанию Генерация полносвязных неориентированных n-графов - 06.10.2005, 01:49

Генерация полносвязных неориентированных графов с заданным числом вершин, без кратных ребер (каждая дуга была представлена по одному разу) и петель:
Все рёбра - случайные real между 0 и 1.
Вершины - unsigned от 1 до N.
Граф представляется фактами:
ребро(Вершина1,Вершина2,Ребро) - это ребро из Вершины1 в Вершину2 длинной Ребро.
Из-за того, что граф неориентированный:
ребро(Вершина1,Вершина2,Ребро) = ребро(Вершина2,Вершина1,Ребро)
Поэтому в памяти будет храниться только треугольная матрица, например для n=4:
Код:
ребро(1,2,0.5629069064)
ребро(1,3,0.2831495256)
ребро(1,4,0.3849221752)
ребро(2,3,0.147424759)
ребро(2,4,0.4040648871)
ребро(3,4,0.6793343371)
Вот прога:
Код:
facts
ребро(unsigned Вершина1,unsigned Вершина2,real Ребро)
predicates
ген_граф(unsigned Число_вершин)
ген_граф1(unsigned Вершина,unsigned Вершина,unsigned Вершина)
goal ген_граф(4).
clauses 
ген_граф(N):-ген_граф1(1,2,N).
ген_граф1(K,_,K):-!.
ген_граф1(I,K,K):-random(X),
   assert(ребро(I,K,X)),
   I1=I+1,I2=I+2,!,ген_граф1(I1,I2,K).
ген_граф1(I,J,K):-random(X),
   assert(ребро(I,J,X)),
   J1=J+1,!,ген_граф1(I,J1,K).
Ответить с цитированием
  (#2 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,771
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 06.10.2005, 12:41

Это хорошо и для полного графа, конечно, просто.
Но если граф не полный? Но связный. Т.е. если число вершин задано, а количество ребер случайно? Либо пусть и число ребер задано, но сами они случайны?
Ответить с цитированием
Ads
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Теория графов для нахождения маршрута kobagusev Вопросы начинающих программистов 0 16.12.2010 19:38
Раскраска плоских графов как реализовать lac0ste Haskell 4 14.05.2010 20:45
Визуализация графов с чего начать _sas_ С/С++ 0 13.04.2010 08:26
Как реализовать редактор графов sistem32 WinAPI 3 15.01.2010 22:54
Генерация документов .doc или .xls Constantine Общие вопросы создания ПО 3 04.09.2009 23:40
Декартово произведение графов Flash[n2o] Prolog 11 16.02.2009 14:11
Генерация лабиринтов noobas Prolog 4 08.12.2007 08:05
Генерация блоков в txt SIRIV C++ Builder 9 12.09.2006 17:00
Редактор графов Лёхыч Задания за деньги 1 27.03.2006 17:22
Число графов, изоморфных данному AlexI Prolog 1 26.05.2005 16:40
Как задать набор графов в Delphi Diver Delphi 3 15.06.2004 20:48
Генерация документации Sergeevich Общие вопросы создания ПО 3 23.05.2004 07:45



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов