CODEWITHSUNDEEP
prolog
technazi
technazi

Reputation: 958

Prolog - Does path exist from X to Y in graph

Its just been two hours i have written my first Prolog hello world program.

I saw this tutorial which i am trying to refer :

enter image description here

Objective :

I am trying to check path from node x to node y. I want to use recursion, but not sure how to give a base case to it. Plus How to run the possibilities of link(X,?). Like in the above image, the grand_parent function is passed a variable which gives all the possible outputs of A.

Example :

I am trying to check if there is a path(b,d) I want it to make the following iterations : 

link(b,d) 

link(b,p) -> link(p,d) is false

link(b,c) -> link(c,d) is true so return yes.

Here is my code : 

link(a, b).
link(b, p).
link(b, c).
link(c, d).
link(d, q).
link(d, r).

link(X,Y) :-
    for all A links from X:
    link(A,Y).

check_for_node(X,Y) :-
    node(X),
    node(Y).

check_reverse_path(X,Y) :-
    link(Y,X).

path(X,Y) :-
    check_for_node(X,Y),
    link(X,Y).

path(X,Y) :-
    check_for_node(X,Y),
    check_reverse_path(X,Y).

Upvotes: 0

Views: 641

Answers (2)

technazi
technazi

Reputation: 958

I found it here 

node(a).
node(b).
node(c).
node(d).
node(p).
node(q).
node(r).

link(a, b).
link(b, p).
link(b, c).
link(c, d).
link(d, q).
link(d, r).

check_for_node(A,B) :-
    node(A),
    node(B).

connected(A,B) :- link(A,B);link(B,A).

travel(A,B,P,[B|P]) :- 
    connected(A,B).

travel(A,B,Visited,Path) :-
   connected(A,C),           
   C \== B,
   \+member(C,Visited),
   travel(C,B,[C|Visited],Path). 

path(A,B,Path) :-
    check_for_node(A,B),
    travel(A,B,[A],Q), 
    reverse(Q,Path).

Upvotes: 0

Scott Hunter
Scott Hunter

Reputation: 49803

Now that you have different predicates for links and paths, we can do the following:

path(X,Y) :-
    link(X,Y).

path(X,Y) :-
    link(X,A),
    A != Y, ; to avoid repeating what was caught by above, tho probably not necessary
    path(A,Y).

Upvotes: 1

Related Questions