Prolog - finding all path options

Question

One piece of the program I am writing in Prolog has to do with finding all possible path options from the starting location to the ending location.

Here is what I have so far:

findAllRoutes(Start, End, Path) :-
     findAllRoutes(Start, _, End, Path),
     print('Successful route: '), print(Route).

findAllRoutes(End, _, End, [End]). %route was successfully finished

 findAllRoutes(Start, Temp, End, [Start|Rest_of_List]) :-
     path(Start, Temp),
     findAllRoutes(Temp, _, End, Rest).

Here is the data to be read in:

%path(Start, End).
path(1, 4). %find all the possible paths from location 1 to location 4.

%paths_in_place[[Start, End, Distance]].
paths_in_place[[1, 2, 250], [2, 4, 250], [1, 3, 400], [3, 4, 300]].

My question is, is this an accurate way to cycle through paths_in_place while also saving the order of the points reached on the way from the starting location to the ending location?

Also, what happens to Distancewhen findAllRoutesis called without any mention of the Distance field? Is it legal in Prolog to pass the parameters of Start, End, Routeeven though in paths_in_place the fields are Start, End, Distance?

Any help is much appreciated. Let me know if I need to clarify anything.

Answer 1

Prolog data are symbolic. You could be passing distance in meters, and treat it as distance in feet. That's how one of Mars missions got crashed, although they used another language. So it's ultimately up to you.

As to your code,

findAllRoutes(Start, End, Path) :-
     findAllRoutes(Start, _, End, Path),
     print('Successful route: '), print(Route).

Route? What Route? It's an uninstantiated "singleton" variable. SWI Prolog warns us to that effect. Perhaps you meant Path.

findAllRoutes(End, _, End, [End]).  % route was successfully finished

findAllRoutes(Start, Temp, End, [Start|Rest_of_List]) :-
     path(Start, Temp),
     findAllRoutes(Temp, _, End, Rest).

again, Rest_of_List and Rest probably should have the same name (be the same logical variable).

Otherwise it looks OK, except for its name: it finds one path, not "AllRoutes", on each invocation/backtracking. The name "AllRoutes" suggests it finds all of them and returns them all in its result argument; it's not.

Then comes your data and it's out of sync with your code:

%path(Start, End).
path(1, 4). %find all the possible paths from location 1 to location 4.

%paths_in_place[[Start, End, Distance]].
paths_in_place([[1, 2, 250], [2, 4, 250], [1, 3, 400], [3, 4, 300]]).
  % ! must be in parentheses !

Your path(Start, Temp) call in your code suggests Temp is an immediate successor to Start. Not so according to these data. Plus, path/2 definition is missing. But you can just have a bunch of facts instead of the list to define the data.