Find all paths for a relation without knowing nodes Prolog

1
votes

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...

  • Rel - relation,
  • S - source node (first),
  • T - target node (last),
  • [S|Cons] - Path,
  • N - length
    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.

1
prologgraph-theory
What are T and N doing here? – Willem Van Onsem
See this. – false

1 Answers

1
votes

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).