Задача по графам

Задан граф.Для пары его вершин определить:
  а)Кратчайший путь между ними
  б)Сколько между ними существует путей менее заданного n
  в)Сколько между ними существует простых путей(т.е. проходящих дважды через какую-либо вершину)

Вот как делала,но пункты б И в не работают
belong(r(X,Y),[Head|Tail]):- r(X,Y)=Head; belong(r(X,Y),Tail).
belongList(X,[Head|Tail]):- X=Head.
belongList(X,[Head|Tail]):- not X=Head,belongList(X,Tail).

adjacent(X,Y,1,graf(Vertex,Rib)):- belong(r(X,Y),Rib); belong(r(Y,X),Rib).

path(A,Z,graf(Vertex,Rib),Path,Cost):- path1(A,[Z],0,graf(Vertex,Rib),Path,Cost).
path1(A,[A|Path1],Cost1,graf(Vertex,Rib),[A|Path1],Cost1).
path1(A,[Y|Path1],Cost1,graf(Vertex,Rib),Path,Cost):- adjacent(X,Y,1,graf(Vertex,Rib)),
                                                      not belongList(X,Path1),
                                                      Cost2 is Cost1+1,
                                          path1(A,[X,Y|Path1],Cost2,graf(Vertex,Rib),Path,Cost).

minPath(V,V1,graf(Vertex,Rib),MinCost,Path):- path(V,V1,graf(Vertex,Rib),Path,MinCost),
            not (path(V,V1,graf(Vertex,Rib),_,VXCost),VXCost<MinCost).

include(Path,L,[Path|L]).
belongPath(Path,[Head|Tail]):- Path=Head; belongPath(Path,Tail).

count(V,V1,graf(Vertex,Rib),N,Kolvo,SetPaths):- path(V,V1,graf(Vertex,Rib),Path,MinCost),
     not belongPath(Path,SetPaths),MinCost<N,include(Path,SetPaths,S1),Kolvo1 is Kolvo+1,
     count(V,V1,graf(Vertex,Rib),N,Kolvo1,S1).

% countCircles(a,d,graf([a,b,c,d],[r(a,b),r(b,d),r(b,c),r(c,d)]),0,K,[])

countCircles(V1,V2,graf(Vertex,Rib),Kolvo,Kolvo2,SetPaths):- path(V1,V2,graf(Vertex,Rib),Path,_),
not belongPath(Path,SetPaths),include(Path,SetPaths,S1),Kolvo2 is Kolvo+1,
     countCircles(V1,V2,graf(Vertex,Rib),Kolvo2,K,S1).

Граф задается меожеством  вершин и множеством ребер
graf([a,b,c,d],[r(a,b),r(b,d),r(b,c),r(c,d)])
домены не использовала.

Спасибо за совет.
Прошу помочь написать предикат для нахождения путей(как простых так и циклических) между двумя вершинами в неориентированном графе.
Мой предикат path находит только простые пути.А  у самой не получается.(

Задача для ациклических путей мной решена полностью,(все 3 процедуры)
Если Вы уже сталкивались с подобной задачей или четко видите как ее можно реализовать/доработать уже существующий предикат,то прошу ответить.

Вы забыли сделать это:

А вообще я Вам посоветовал бы для начала просто упростить то, что у Вас уже есть. Уберите все операторы сравнения, когда Вы просто одну переменную сравниваете с другой, уберите все операторы сравнения на неравенство - в большинстве случаев это решается введением отсечений, уберите все точки с запятой - пишите лучше несколько утверждений. После таких изменений программа станет яснее и в нее проще будет добавить нужную Вам функциональность. popoff, форумы popoff.donetsk.ua

Без этого в Вашей программе и черт ногу сломит, не только Вы или Я.
Я могу помочь Вам на примере, остальное Вам придется сделать самостоятельно. Ничего нового Вам писать тут не нужно. Просто улучшите вид уже имеющегося.

belong(r(X,Y),[Head|Tail]):- r(X,Y)=Head; belong(r(X,Y),Tail). target, форумы popoff.donetsk.ua

Пишем в два предиката и убираем все сравнения.

belongList(X,[Head|Tail]):- X=Head. belongList(X,[Head|Tail]):- not X=Head,belongList(X,Tail). target, форумы popoff.donetsk.ua

Отрицание здесь излишне: в предыдущем предикате Вы его не ставили, зачем поставили здесь? Но даже если Вам так хочется обезопаситься, Вы можете это сделать, введя отсечение:

adjacent(X,Y,1,graf(Vertex,Rib)):- belong(r(X,Y),Rib); belong(r(Y,X),Rib). target, форумы popoff.donetsk.ua

Я не знаю, с какой версией Пролога Вы работаете. Я привык к простенькому турбопрологу. Это строготипизированный язык. В нем существует раздел доменов, в котором описываются типы. В Вашей программе используются сложные объекты, не зная, как эти объекты устроены, мне сложно понять, что делает этот предикат.

Тем не менее, я могу предположить, что в этой строчке на этапе компиляции должно выводиться предупреждение: переменная используется только один раз. Я не знаю, что насчет Вашей версии Пролога, но в турбопрологе это предупреждение можно отключить. От отключения предупреждения, однако, ошибка в тексте программы не исчезает примерно по той же причине, по которой не исчезает опасность, если бы страус прятал голову в песок.

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

И еще - точки с запятой - это как неправильное выравнивание. От того, что в программе не соблюдены отступы, она не перестает работать, но разобраться в ней становится очень тяжело.

Я написал бы как-нибудь так:

%-------------------------------------------------------- % ?бьединение 2х списков в один %-------------------------------------------------------- include(Path,L,[Path|L]). target, форумы popoff.donetsk.ua

Нет, без доменов и без версии Пролога я не понимаю.

В классическом прологе, если мне не изменяет память, список как раз тем и отличается от структуры, что все элементы списка имеют один тип. А это означает, что Ваш комментарий «обьединение 2х списков в один» никак не вяжется с “include(Path,L,[Path|L]).”, разве что только L - это список списков элементов такого же типа, как список Path. Фактически получается, что L - это дерево, которое можно описать только используюя альтернативные домены.

Если L - это дерево, то этот предикат не выполняет объединение двух списокв в один, а добавляет в дерево новую вершину, самым левым ребенком корневой вершины.

Вы уверены, что Вы запускали эту программу?

С остальным, думаю, Вы можете разобраться самостоятельно.

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

Если не секрет, для чего Вы решаете эту задачу?

Ну, выложили бы решение, чтобы люди пользовались