CODEWITHSUNDEEP
prologtransitive-closure
Yuval Simon
Yuval Simon

Reputation: 335

Prolog Out of local stack error

I tried some basic example from a book and it makes "Out of local stack" error (I'll tell more after the code). here is the code:

edge(a,b).
edge(a,e).
edge(b,d).
edge(b,c).
edge(c,a).
edge(e,b).
tedge(Node1,Node2) :-
    edge(Node1,SomeNode),
    edge(SomeNode,Node2).
edge(X,Y) :- tedge(X,Y).

I tried for example to write query edge(a,b) and it returned true and then I entered ';' and it made the error. What's the problem here?

Upvotes: 0

Views: 219

Answers (1)

Wouter Beek
Wouter Beek

Reputation: 3407

The problem is that you have defined what an edge is in a cyclic way. While looking for a second path from a to b Prolog is looping through tedge(a,VAR), edge(a,VAR), tedge(a,VAR), etc.

Notice that Prolog would loop even if you had not defined your edges to be symmetric, namely due to the cycle a -> b -> c -> a.

The solution is to keep track of vertices and/or edges that have been visited before. Checking for non-recurring vertices can be straightforwardly implemented using closure0/3 (a predicate I learned from SO user false). If you use that predicate, you only need your edge/2 facts and the following query:

?- closure0(edge, a, b).

Upvotes: 2

Related Questions