Find all paths for a relation without knowing nodes Prolog

Question

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.

What are `T` and `N` doing here? – Willem Van Onsem Dec 07 '18 at 20:37 — Willem Van Onsem, Dec 07 '18 at 20:37
See [this](https://stackoverflow.com/q/30328433/772868). – false Dec 10 '18 at 13:45 — false, Dec 10 '18 at 13:45

score 1 · Accepted Answer · answered Dec 07 '18 at 20:42

1

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

answered Dec 07 '18 at 20:42

Willem Van Onsem

443,496
30
428
555

if we don't know N though how can we make that stop condition? – Steve Freed Dec 07 '18 at 20:50
1

@SteveFreed: we do not need to know `N` here, note that we use `clpfd`, so we simply define how `N` and `N-1` relate. The point here is that, if `S` and `T` can be unified, we generate that as a answer, this will not prevent backtracking, since we might be interested in *all* paths from `S` to `T`. If we only want one, it might make more sense to call `graph/5` with `once/1`. – Willem Van Onsem Dec 07 '18 at 20:52

Find all paths for a relation without knowing nodes Prolog

1 Answers1