Find path and its length between nodes in a graph

Question

I'm trying to solve this problem and I've already read this answer, but my problem is with infinte looping even if I've used a visited node list.

Let's see my two tries:

edge(1,2).
edge(1,4).
edge(1,3).
edge(2,3).
edge(2,5).
edge(3,4).
edge(3,5).
edge(4,5).


% ------ simple path finding in a directed graph

% -----  simple exploration

path0(A,B, Result) :-
    path0(A, B, [], Result).

path0(A, B, _, [e(A,B)]):- 
    edge(A,B).    
path0(A, B, Visited, [e(A,X)|Path]):-
    edge(A, X), dif(X, B),
    \+ member(X, Visited),
    path0(X, B, [A|Visited], Path ).    


%---- 1. exploration and length    

path(A, B, _, [e(A,B)], 1):- 
    edge(A,B).    
path(A, B, Visited, [e(A,X)|Path], Length):-
    edge(A, X),
    \+ member(X, Visited),
    length(Path, L),        % ERR: Path refers to a open list
    Length is L + 1,
    path(X, B, [A|Visited], Path, _).

% --- 2. not working

path2(A,B, Result, Length) :-
    path2(A, B, [], Result, Length).

path2(A, B, [], [e(A,B)], 1):- 
    edge(A,B).    
path2(A, B, Visited, [e(A,X)|Path], Length):-
    edge(A, X), dif(X, B),
    \+ member(X, Visited),
    path2(X, B, [A|Visited], Path, Len),
    Length is Len + 1.

Which give me similar answers, i.e.:

 ?- path(1,3, Path, Length).
Path = [e(1, 3)],
Length = 1 ;
Path = [e(1, 2), e(2, 3)],
Length = 2 ;

And then the Swi-Prolog IDE freezes.

• What should I define as the base case ?
• Why is the second implementation looping, if it's the case, even if I used the visited node list and the dif() to be sure to avoid unification go back and forth? I misstyped the function name.

I would like to get rid of the length/2 use. Thanks.

Edit:

So, I figured out this should be the cleaner way of doing it, even if I would like something more similar to the second implementation which would be easier to transform in a shortest path problem solver, since it would be just a min{ pathLengths } from the first call of path3/4.

% ---- 3. working    
%   
min(A,B,A):- A =< B, !.       % for future use (shortest path)
min(_,B,B).

path3(From, To, Path, Len):-    
    path0(From, To, [], Path),
    length(Path, Len).
    %min(Len, MinLength, ?)

---

And this is the corrected version of the second implementation path2:

% --- 2. 
% errors: 1. in base case I have to return Visited trough _, 
%             I can't pass a void list []
%         2. dif(X,B) is unuseful since base case it's the first clause

path2(A,B, Result, Length) :-
    path2(A, B, [], Result, Length).

path2(A, B, _, [e(A,B)], 1):-      % If an edge is found
    edge(A,B).    
path2(A, B, Visited, [e(A,X)|Path], Length):-
    edge(A, X),  
    %tab(1),write(A),write('-'),write(X),
    \+ member(X, Visited),
    %tab(1),write([A|Visited]),write(' visited'),nl,
    path2(X, B, [A|Visited], Path, Len),
    Length is Len + 1.

Answer 1

The reason why both path/4 and path2/4 expose similar non-termination behavior is because both use the very same auxiliary predicate path/5. You probably meant path2/5 instead:

path2(A,B, Result, Length) :-
    path(A, B, [], Result, Length).
 %  ^^^^ replace by path2

Maybe first, let's look why your path/4 definition loops. To see this, I will insert goals false into your program. These goals will reduce the number of inferences. When the remaining fragment still loops, we can be sure that we see a part that is responsible for non-termination. After some experiments, I found the following fragment, called a failure-slice:

edge(1,2).
edge(1,4) :- false.
edge(1,3) :- false.
edge(2,3) :- false.
edge(2,5) :- false.
edge(3,4) :- false.
edge(3,5) :- false.
edge(4,5) :- false.

path(A,B, Result, Length) :-
    path(A, B, [], Result, Length), false.

path(A, B, _, [e(A,B)], 1):- false,
    edge(A,B).
path(A, B, Visited, [e(A,X)|Path], Length):-
    edge(A, X),
    \+ member(X, Visited),
    length(Path, L), false,
    Length is L + 1,
    path(X, B, [A|Visited], Path, _).

So essentially it's the use of the length/2 predicate. As long as the length of the path is not fixed, this fragment will not terminate. So for the query

?- path(1, 3, Path, N).

The Path is not limited in its length and thus length/2 will find infinitely many solutions - and thus will not terminate.

But, after all, why do you want to know the length anyway? The path argument describes it already implicitly.

For your definition path/4,5 consider what the query

?- path(1, X, Path, N).

should produce as an answer. Should Path = [1] be a solution, too? It's a bit a question of the exact definition of a path/walk. I think it should.

For a generic solution, please refer to this answer. With it, you can define the predicates that you are interested in like so:

yourpath(A,B, Path, N) :-
   path(edge, Path, A,B),
   length(Path, N).

But, I would rather not add the extra argument about the length of the path. You can add that information later anytime anyway.