Prolog Infinite loop (cyclic graph)

Question

this might be a simple problem but I need to do it differently. The problem is that I have to find in prolog the possible routes of airflights. I have this knowledge base

from_to(fresno,seattle).
from_to(fresno,albany).          
from_to(albany,dallas).     
from_to(fresno,boston). 
from_to(dallas,seattle).         
from_to(dallas,albany).
from_to(seattle,dallas).           
from_to(seattle,omaha).         
from_to(atlanta,albany).
from_to(atlanta,dallas).
from_to(atlanta,boston).
from_to(omaha,atlanta).         
from_to(omaha,albany).
from_to(albany,seattle).

And I have to make a predicate route(X,Y) that checks if we can go from X to Y. What I did is this:

route(X,Y):-from_to(X,Y).
route(X,Y):-from_to(X,Z), route(Z,Y).

But it doesn't work because the graph is cyclic. I searched on the internet and the only thing everyone said is to use a list and check the visited paths. But I can't use lists! I have to make a predicate route(X,Y) without using lists, how can I accomplish this without a list? Thank you

Answer 1

I would try

:- dynamic visited/1.

route(X,Y) :- retractall(visited(_)), route_(X,Y).
route_(X,Y) :- from_to(X,Y).
route_(X,Y) :- from_to(X,Z), \+ visited(Z), asserta(visited(Z)), route_(Z,Y).

test:

1 ?- route(fresno, omaha).
true ;
false.

2 ?- route(fresno, omaha).
true ;
false.

3 ?- route(fresno, fresno).
false.

4 ?- route(atlanta, atlanta).
true ;
false.

Since the graph is defined in source code, an alternative could be:

:- dynamic from_to/2.

route(X,Y):-retract(from_to(X,Y)).
route(X,Y):-retract(from_to(X,Z)), route(Z,Y).

but after the first call, a reload of the KB is needed.

Answer 2

If you are not strictly required to use SWI-Prolog, you can easily do this in a Prolog system with tabling support. In B-Prolog, I just added :- table route/2. and now it works:

?- route(fresno, omaha).
yes

?- route(fresno, fresno).
no

?- route(atlanta, atlanta).
yes

?- route(atlanta, X).
X = albany ?;
X = dallas ?;
X = boston ?;
X = seattle ?;
X = omaha ?;
X = atlanta
yes

Answer 3

So you can't use lists (I wonder why) but can you use a counter variable? Try iteratively deepening search where you do depth-first search first in the depth of 1, then 2, and so on. That would prevent the infinite loops with cycles.

Remember to have an upper limit for search depth to avoid infinite looping in case where there is no connection.

Answer 4

route(X0,X) :-
   from_to(X0,X1),
   closure0(from_to,X1,X).

See this question for a definition of closure0/3.