CODEWITHSUNDEEP
prologgraph-theory
Steve Freed
Steve Freed

Reputation: 91

Find all paths for a relation without knowing nodes Prolog

I want to get all paths in a relation but I do not know how to do this if I am not given an ending Node. I have tried multiple ways to implement this and here is what I currently have...

    graph(Rel, S, T, [S|Cons], N) :-
       call(Rel, S, X),
       (X = T; graph(Rel, X, T, [X|Cons], N)).

When I test it with...

graph(myRelation, _, _, _, _), false.

It just infinitely loops. I am assuming it is because I am not given any variables of terms besides the relation but I thought when I use call it will assign X so I can populate the paths ([S|Cons]) this way.

Upvotes: 1

Views: 93

Answers (1)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 477824

You here defined a predicate that will each time call itself (unless call(Rel, S, X) fails, but even then there is never a way to "retrieve" a result), you need a condition to stop.

That condition is when the source S, and the target T are the same, in that case, we return as path a list containing S, as well as N=0:

graph(_, S, S, [S], 0).

Furthermore in the recursive case, we have to do proper bookkeeping with N and the "path":

graph(Rel, S, T, [S|Rest], N) :-
    call(Rel, S, X),
    N1 #= N-1,
    graph(Rel, X, T, Rest, N1).

so in full, we obtain:

:- use_module(library(clpfd)).

graph(_, S, S, [S], 0).
graph(Rel, S, T, [S|Rest], N) :-
    N #> 0,
    call(Rel, S, X),
    N1 #= N-1,
    graph(Rel, X, T, Rest, N1).

Upvotes: 1

Related Questions