Avoiding the same answer multiple times in prolog

Question

So I have this undirected graph to traverse, and I should find all the verticies those are connected to a given vertex.

edge(a, b).
edge(b, c).
edge(c, d).
edge(d, e).
edge(e, f).
edge(f, d).
edge(d, g).
edge(g, f).
edge(g, h).
edge(h, i).
edge(i, j).
edge(j, d).
edge(d, k).
edge(l, m).
edge(m, n).

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

connected(X, Y) :- undirectedEdge(X, Y).
connected(X, Y) :- connected(X, Z), connected(Z, Y), X \= Y.

And once I type connected(a, X). it goes into an infinite loop. I understand why I have it, but I have no idea how to avoid it, maybe I can find some help here?

You maintain a list, such that it does not start looping. – Willem Van Onsem Dec 27 '19 at 18:08 — Willem Van Onsem, Dec 27 '19 at 18:08

score 3 · Answer 1 · answered Dec 28 '19 at 10:20

3

Using closure0/3 and setof/3 we get:

connected(A,B) :-
   setof(t, closure0(undirectedEdge, A, B), _).

answered Dec 28 '19 at 10:20

false

10,264
13
101
209

Willem Van Onsem · Accepted Answer · 2019-12-27T18:45:16.923

1

And once I type connected(a, X). it goes into an infinite loop.

The reason this happens is because it is checking a path of the form a &rightarrow; b &rightarrow; a &rightarrow; b &rightarrow; a &rightarrow; b &rightarrow; …. So it keeps "hopping" between two nodes.

You can maintain a list of nodes that the algorithm already visisted, to prevent that like:

connected(X, Y) :-
    connected(X, Y, [X]).

connected(X, X, _).
connected(X, Z, L) :-
    undirectedEdge(X, Y),
    \+ member(Y, L),
    connected(Y, Z, [Y|L]).

You can make use of the distinct/1 predicate [swi-doc] to generate distinct answers:

?- distinct(connected(a, X)).
X = a ;
X = b ;
X = c ;
X = d ;
X = e ;
X = f ;
X = g ;
X = h ;
X = i ;
X = j ;
X = k ;
false.

edited Dec 27 '19 at 18:45

answered Dec 27 '19 at 18:11

Willem Van Onsem

443,496
30
428
555

Thanks for the quick response... Now I have 29 values for X instead of an infinite loop. But 29 still has duplicates, Is it possible to define a global list? – Question Dec 27 '19 at 18:40
@Question: most systems have a non-backtrackable store. But that is usually not a good idea. You can use the `distinct/1` meta-predicate. – Willem Van Onsem Dec 27 '19 at 18:42

Avoiding the same answer multiple times in prolog

2 Answers2