how exactly an atom/1 predicate works in prolog?

Question

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. :)

Answer 1

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.