0

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?

false
  • 10,264
  • 13
  • 101
  • 209
Yuval Simon
  • 335
  • 1
  • 10
  • The short answer is that it went into infinite recursion. If you do a `trace`, you'll see what's happening. Why did you defined `edge(X,Y) :- tedge(X,Y).`? It's bound to create a loop scenario since `edge/2` also defines facts which `tedge/2` refers to. Just leave it at `tedge/2` and query `tedge(a,b).`. – lurker Dec 30 '14 at 18:15

1 Answers1

2

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).
Community
  • 1
  • 1
Wouter Beek
  • 3,307
  • 16
  • 29