CODEWITHSUNDEEP
duplicatesprologtransitive-closure
Danny Rancher
Danny Rancher

Reputation: 2005

How can I prevent duplicates in prolog

My multiple solution problem arises due to Prolog's backtracking looping through the goals. Whilst I understand that, technically, each solution provided is correct, it is not useful to me. Is there a method to remove duplicates?

Here is my code so far:

flight(london, paris).
flight(paris, amsterdam).
flight(amsterdam, rome).
flight(rome, paris).
flight(rome, rio_de_janeiro).
route_from(A,B) :-
  flight(A,B).
route_from(A,B) :-
  flight(A,R),
  route_from(R,B).

An example query is:

?- route_from(A, paris).
A = london ;
A = rome ;
A = london ;
A = london ;
A = london ;
A = london ;
A = london ;
A = london ;
A = london ;
etc.

Regards.

Upvotes: 2

Views: 4667

Answers (2)

gusbro
gusbro

Reputation: 22585

You have a bigger issue other than returning repeated solutions. Your program, as is, will loop indefinitely as there are loops in your graph.

To avoid loops you may maintain a list of visited cities:

route_from(A,B) :-
  route_from(A,B, []).

route_from(A,B, _) :-
  flight(A,B).
route_from(A,B, Visited) :-
  flight(A,R),
  \+ member(A, Visited),
  route_from(R,B, [A|Visited]).

Now, this won't prevent returning duplicates if there are more than one way to go to a city. You can use setof/3 to obtain every solution without duplicates upon backtracking:

route_from_without_duplicates(A,B):-
  setof(t, route_from(A,B), _).

Upvotes: 4

false
false

Reputation: 10102

Using closure/3:

?- closure(flight,A,B).
   A = london, B = paris
;  A = london, B = amsterdam
;  A = london, B = rome
;  A = london, B = rio_de_janeiro
;  A = paris, B = amsterdam
;  A = paris, B = rome
;  A = paris, B = rio_de_janeiro
;  A = amsterdam, B = rome
;  A = amsterdam, B = paris
;  A = amsterdam, B = rio_de_janeiro
;  A = rome, B = paris
;  A = rome, B = amsterdam
;  A = rome, B = rio_de_janeiro
;  false.

Apparently, there are no redundancies, but just in case:

?- setof(t,closure(flight,A,B),_).
   A = amsterdam, B = paris
;  A = amsterdam, B = rio_de_janeiro
;  A = amsterdam, B = rome
;  A = london, B = amsterdam
;  A = london, B = paris
;  A = london, B = rio_de_janeiro
;  A = london, B = rome
;  A = paris, B = amsterdam
;  A = paris, B = rio_de_janeiro
;  A = paris, B = rome
;  A = rome, B = amsterdam
;  A = rome, B = paris
;  A = rome, B = rio_de_janeiro.

Upvotes: 1

Related Questions