0

This is what I have so far. I need to show that if two stations are connected via a third station, they are connected to each other

station(hamburg).
station(bremen).
station(hannover).
station(berlin).
station(leipzig).
station(osnabruck).
station(stuttgart).
station(fulda).
station(munich).

adjacent(hamburg, bremen).
adjacent(hamburg, berlin).
adjacent(berlin, hannover).
adjacent(berlin, leipzig).
adjacent(leipzig, fulda).
adjacent(fulda, hannover).
adjacent(hannover, osnabruck).
adjacent(osnabruck, bremen).
adjacent(stuttgart, munich).

/* insert your clauses here */

adjacent_(X,Y) :-adjacent(Y,X) .
adjacent_(X,Y) :-adjacent(X,Y) .

connected(X,Y) :-adjacent(X,Y) .
connected(X,Z) :-connected(X,Y), adjacent_(Y,Z) .
false
  • 10,264
  • 13
  • 101
  • 209
user2338241
  • 7
  • 1
  • 2
  • Using [`closure/3`](http://stackoverflow.com/q/26946133/772868): `connected(X, Y) :- closure(adjacent_, X, Y).` – false Nov 05 '16 at 22:49

1 Answers1

0

Your first connected clause will fail for a clause like:

?- connected(bremen, hamburg).

Presumably you meant to write

connected(X,Y) :- adjacent_(X,Y) .

instead.

Other than the above bug, your code seems fine. The only thing I'd add is that you're not guarding against "cycles". E.g. if you were trying to find if berlin is connected to fulda, in theory you might never get there because of the following cycle:

berlin -> hannover -> osnabruck -> bremen -> hamburg -> berlin (and so on ad infinitum).

Therefore you could also include an accumulator in your code, containing all the nodes visited so far, such that you don't allow your clause to succeed if the current node already appears in your node "path".

PS. If you're only interested to find out whether X and Z are connected, and not in how many possible ways, you could also explicitly specify a cut (i.e. !) at the end of each connected clause.
Tasos Papastylianou
  • 21,371
  • 2
  • 28
  • 57