0

I have been trying to solve a pathfinding problem in Prolog.where the predicates are

edge(a,b).
edge(a,c).
edge(b,d).
edge(c,d).
edge(d,e).
edge(d,f).
edge(f,g).

the rules is
edge(X,Y) :- edge(X,Z), edge(Z,Y).
then when I compiled and run the query | ?- edge(a,X). it is showing Fatal Error: local stack overflow (size: 8192 Kb, environment variable used: LOCALSZ) then I searched for the solution and found that including atom(x).,atom(y). in our rule can solve the stack overflow problem . i.e the new rule is

edge(X,Y) :- atom(X), atom(Y), edge(X,,Z), edge(Z,Y). and yes it did solved the stack overflow problem .but,I would like to know how exactly this (atom/1) predicate is solving my problem here?and what does it do to our variables X,Y to solve the StackOverflow problem? I am a newbie to Prolog any help would be appreciated thank you. :)

læran91
  • 283
  • 1
  • 15
  • 1
    You don't need atom/1 but a predicate that describes (a) path(s) between two nodes. See [this recent post](https://stackoverflow.com/a/46615555/6101159) for an example. – tas Oct 10 '17 at 07:30
  • Does `atom/1` really solve your problem? In other words, does `edge(X, Y)` really now provide all of the correct solutions to a query? All it does is ensure that its argument is an atom, so it cannot be an unbound variable. So I suspect `edge(X, Y)` does not provide all of the correct solutions. It only yields those solutions that you have direct facts for. In other words, `edge(a, d)` which is a valid path still fails. Your new `edge(X, Y)` always fails because `atom(X)` will fail if `X` is not bound. – lurker Oct 10 '17 at 10:51
  • https://stackoverflow.com/questions/44443958/prolog-routing-between-2-points-and-making-a-list-of-it/44588639#44588639 Here is similar problem, in my answer there is a solution to your problem. The difference is that I was remembering edges that I walked through, you need to remember vertices. – Armatorix Oct 10 '17 at 12:03

1 Answers1

2

First on naming, the edge/2 name doesn't describe your predicate very well. You probably really want path/2 which consists of one or more edges.

Does atom/1 really solve your problem? In other words, does edge(X, Y) really now provide all of the correct solutions to a query? All that atom/1 does is ensure that its argument is an atom, so it cannot be an unbound variable. So edge(X, Y) does not provide all of the correct solutions. It only yields those solutions that you have direct facts for, since the predicate edge(X, Y) as currently defined always fails with either X or Y unbound.

| ?- edge(a, Y).

Y = b ? ;

Y = c ? ;

no

Where is the solution Y = d for example? edge(X, Y) is only picking up the solutions that are given in your edge/2 facts, but no solutions that include multiple connected edges.

Your original problem is due to infinite recursion, which is a result of edge/2 calling itself unnecessarily. Naming can actually be important here since it makes the logic more precise and correct. We can say that edge(X, Y) means that X and Y form an edge (X and Y are directly connected). We can say that path(X, Y) means there's a path from X to Y via one or more edges. In other words, a path from x to y can either be an edge from x to y, or it can be an edge from x to z and a path from z to y.

path(X, Y) :- edge(X, Y).
path(X, Y) :- edge(X, Z), path(Z, Y).

Now we get:

| ?- path(a, X).

X = b ? a

X = c

X = d

X = e

X = f

X = g

X = d

X = e

X = f

X = g

(1 ms) no
| ?-

There are duplicates since there may be multiple ways of getting from a to e for example. If you included an argument that showed the traversed path, this would become evident.

This solution isn't the end of the story, however. Your current facts are such that there are no "circuitous" paths (paths that eventually revisit the same node if followed). To handle that, you need a predicate argument to keep track of what nodes/edges you've traversed already and avoid traversing them again.

lurker
  • 56,987
  • 9
  • 69
  • 103
  • thank you @lurker .I understood the problem now.my rule edge(X,Y) not really solving the problem but it stopped infinite recursion by including `atom(X), atom(Y).` what atom(X).atom(Y). are doing to stop infinite recursion.? – læran91 Oct 10 '17 at 11:54