Graf prolog

<image> http://imageshack.us/photo/my-images/266/graftm.jpg/ </image>

Zapisz graf z rysunku w postaci faktów luk/2. Następnie napisz predykat droga(X,Y) w postaci reguł które wnioskują czy istnieje droga od wierzchołka X do wierzchołka Y.

Program będzie sprawdzany na grafie Petersena , grafie niespójnym zawierającym 2 komponenty, drzewie

na razie mam tyle i teraz z tych łuków czyli istnienie wierzchołka np. A do wierzchołka np. B mam stworzyć predykat droga(X,Y). który sprawdzi czy istnieje taka droga?

luk(A,B).
luk(A,D).
luk(B,C).
luk(B,E).
luk(C,F).
luk(D,E).
luk(D,G).
luk(E,F).
luk(E,H).
luk(F,I).
luk(G,H).
luk(H,I).

Jeśli graf jest DAGiem i nie zawiera cykli to:

connect(X, Y) :- luk(X,Y).
connect(X, Y) :- luk(X,Z), connect(Z, Y).

Ok tylko mam jeszcze pytanie jeśli to ma być sprawdzane na 3 różnych grafach to mam zrobić 3 kody działające dla konkretnego grafu, czy ma to być jeden graf, który będzie działał dla wszystkich trzech.

co do jednej z części zadania można coś takiego dopisać

droga (X,X). %zeby nie miec nieskonczonych sciezek
droga (X, Y) :-
luk(X,Z)
droga(Z,Y).

Predykaty dla szukania ścieżki są zawsze takie same i występują raz - zmieniasz jedynie graf w swoich luk(skad, dokad) - przynajmniej ja tak robiłem pisząc w sicstusie. Skoro masz odpalić program dla 3 różnych grafów to robisz 3 pliki i w każdym definiujesz sobie graf i reguły do szukania drogi pod spodem. Czy da się to jakoś wyciągnąć - nie wiem, nigdy mnie to nie interesowało, tylko robiłem copy-paste. Twój dodatek jest niepoprawny i zbędny - jeśli graf jest dagiem to i tak nie możesz mieć nieskończonych ścieżek. A jeśli w grafie są cykle to potrzebujesz akumulatora.

droga(X,Y) :-

luk(A,B).
luk(A,D).
luk(B,C).
luk(B,E).
luk(C,F).
luk(D,E).
luk(D,G).
luk(E,F).
luk(E,H).
luk(F,I).
luk(G,H).
luk(H,I).

jeśli stworzę to, a następnie w SWI Prolog zadam pytanie droga(A,E) wyskoczy mi true, lecz jeśli podam np. droga(B,M) też wyskoczy mi true, czy tutaj należy dopisać więcej własności

Stałe w Prologu piszemy z małej litery. Żeby nie było niedomówień - tak wygląda kompletny program:

luk(a,b).
luk(a,d).
luk(b,c).
luk(d,e).
luk(c,f).
luk(d,e).
luk(d,g).
luk(e,f).
luk(e,h).
luk(f,i).
luk(g,h).
luk(h,i).

droga(X, Y) :- luk(X,Y).
droga(X, Y) :- luk(X,Z), droga(Z, Y).

I można zadawać pytania.

Ok dzięki

teraz w SWI Prolog mogę sprawdzić czy np. istnieje droga z wierzchołka X do Y poleceniem

?- droga(X,Y).

otrzymam odpowiedź X=a, Y=b.

Czyli dla tego grafu, który mam podanego w załączniku to już kompletne rozwiązanie? jakim poleceniem mogę sprawdzić czy istnieje droga np. z a do i?

Czy dla grafu Petersena (na wikipedii jest jak wygląda, myślę, że jest tylko jedna taka możliwość jego narysowania) trzeba nieco pozamieniać warunki w kodzie?

czy dobrze wskazuje listę wierzchołków z których jest droga do ustalonego wierzchołka:-? droga(X,b).

dla takiego przykładu po wpisaniu do SWI Prolog wyskakuje, że X=a, dalej po naciśnięciu średnika(czyli czy istnieją inne możliwości) wyskakuje false, więc jest dobrze, lecz dla drogi:

droga(X,i).
X=f, X=h,dalej występuje X=a lecz jest ich 6 razy(w kolejnych wierszach) dalej X=b, 2 razy X=d, raz X=c, 3 razy X=d, 2 razy X=e i raz X=g następnie wypisany zostaje false.

Czy taka "odpowiedź" programu na podanie polecenie jest poprawne?

bo z a do i można wybrać kilka dróg, podobnie z d do i, lecz czy tak jak zostało wyświetlone, czyli kilkukrotne wypisanie X=dana litera pod spodem jest poprawne?

można prosić o pomoc jeszcze przy tym zadaniu?

można jeszcze prosić o pomoc w tym zadaniu?

Ja oddałem do sprawdzenia takie coś i miałem zaliczone:

luk(a,b).
luk(a,d).
luk(b,c).
luk(b,e).
luk(c,f).
luk(d,e).
luk(d,g).
luk(e,f).
luk(e,h).
luk(f,i).
luk(g,h).
luk(h,i).

droga(X, Y) :- luk(X, Y).
droga(X, Y) :- luk(X, Z), droga(Z, Y).

Sprawdzasz np.

?- droga(b,g).
false

?- droga(b,h).
true ;
false

To, że potem tam jest false za true to już nie ważne. Mi też pokazuje X= i kilka liter potarza się, ale to normalne chyba, bo tak jest napisany algorytm i ja bym się tam nie przejmował. Najważniejsze, żeby Ci mówiło true lub false dla konkretnej drogi z wierzchołka do wierzchołka, tak jak to pokazałem w przykładzie.

czy dobrze wskazuje listę wierzchołków z których jest droga do ustalonego wierzchołka:-? droga(X,b).

dla takiego przykładu po wpisaniu do SWI Prolog wyskakuje, że X=a, dalej po naciśnięciu średnika(czyli czy istnieją inne możliwości) wyskakuje false, więc jest dobrze, lecz dla drogi:

To, że potem tam jest false za true to już nie ważne. Mi też pokazuje X= i kilka liter potarza się, ale to normalne chyba, bo tak jest napisany algorytm i ja bym się tam nie przejmował. Najważniejsze, żeby Ci mówiło true lub false dla konkretnej drogi z wierzchołka do wierzchołka, tak jak to pokazałem w przykładzie.

Jeśli chcecie żeby dawało tylko jeden wynik i nie pisało 'false':
http://en.wikibooks.org/wiki/Prolog/Cuts_and_Negation