finding path using prolog

Question

I want to find whether there is a path from one point to another or not.

For example, 2 -> 4 -> 7 1 -> 3 -> 2 -> 9 5 -> 1 -> 6 -> 8

these are the path. I want to write a predicate path(Start, End), and arcs are represented by a set of arc(From, To) facts.

For example, when path(1, 7) is given this must return true. when path(6, 1) is given this must return false. because arcs are directed.

Answer 1

Try to answer splitting the problem in elementary problems.

path(From, To) :-
  arc(From, Intermediate),
  path(Intermediate, To).

But, do you see where path should stop? And if there are cycles, what happens?

What's miss it's the trivial case, stating that path(X, X) it's always true. Add to above rule:

path(To, To).

Maybe it's clearer if we write a single rule, using If Then Else

path(From, To) :-
  (   From \= To
  ->  arc(From, Intermediate),
      path(Intermediate, To)
  ;   true
  ).

Answer 2

1. If there is an arc between X and Y, then Path=arc(X,Y). That is, if arc(X,Y) then path(X,Y)). Or, in Prolog this is:

   path(X,Y,[arc(X,Y)]) :- arc(X,Y).

2. Otherwise, if there is an arc between X and some other node Z, and there is a path from Z to Y, then there is a path from X to Y too. That is, if arc(X,Z) and path(Z,Y) then path(X,Y). In Prolog this is:

   path(X,Y,[arc(X,Z)|P]) :- arc(X,Z),path(Z,Y,P).

Taken from this site.

You could also bundle this into one predicate that simply takes a list of arcs and recursively searches for a path