In prolog, why doesn't adding “edge(X, Y) :- edge(Y, X).” alone work for converting a directed graph definition to an undirected graph

Question

I'm just learning Prolog, and I'm reviewing lecture notes and all the notes say is that:

given the following definition for directed graphs:

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

If we wanted to make this an undirected graph, defining edge(X, Y) :- edge(Y, X). alone doesn't work, and I can't figure out why. X to Y has an edge if Y to X has an edge. Seems to make sense to me.

The notes don't really clarify why not, but it does define that the proper solution would be:

edge1(X, Y) :- edge(X, Y).
edge1(X, Y) :- edge(Y, X). 

to what we already had.

Can anyone explain this to me, please and thanks? <3

Answer 1

Because rules don't work the same as facts, and you are spiraling off into an infinite loop if you use the same predicate.

Let's take the example ?-edge(5,2). We will end up calling --

edge(5,2) :- edge(2,5).

Ok, what happens when we call edge(2,5)?

edge(2,5) :- edge(5,2).

... Uh oh. Logic circle.

When using edge1, you are simply creating a wrapper for your predicate to escape the recursive definition.

Answer 2

There are several potential sources of non-termination in your program.

First, with the rule edge(X, Y) :- edge(Y, X). your program will never terminate. Regardless of where you add this rule to your program. What is often quite irritating is that your program will still produce many answers which somewhat suggests that it works. However, it will never stop.

The best way to understand this, is to consider a slightly modified program, called a failure-slice. This modified program will share many properties with your program. Not all of them, but some. We will add goals false into your program. If the resulting program loops, the original program will loop as well.

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

edge(a, b) :- false.
edge(X, Y) :- edge(Y, X).

Second, there is another source of non-termination in your improved program. Here is the related failure-slice:

path(X, Y) :- false, edge1(X, Y).
path(X, Y) :- edge1(X, Z), path(Z, Y), false.

edge1(X, Y) :- edge(X, Y).
edge1(X, Y) :- edge(Y, X).

edge(a, b).

edge1/2 now always contains cycles, so this fragment will loop for path(a, Y). and more generally also path(X, Y), false.

To solve this problem, you will have to rewrite path/2.

You can rewrite this in a generic manner by using closure0/3 and path/4!

So path/2 can be defined as:

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