For the five problems in this assignment, we define a relation flight(Src,Dst) representing a direct flight from a city Src to another city Dst. Assume city Src and city Dst are different. For example, the fact flight(0,1) represents a direct flight from city 0 to city 1.
You can assume all input are valid in the PROLOG interpreter.
Examples are based on the following database:
/* The database of flight facts */
flight(0, 1).
flight(1, 2).
flight(2, 0).
flight(2, 3).
flight(3, 4).
flight(4, 3).
Question 1.
Define a relation reachable(Src, Dst) that queries whether we can fly from city Src to city Dst via a direct flight or connecting flights.
Examples:
?- reachable(0, 1).
true.
?- reachable(0, 2).
true.
?- reachable(0, 0).
true.
?- reachable(4, 2).
false.
?- reachable(Src,4).
Src = 3 ;
Src = 4 ;
false.
?- reachable(5, Dst).
false.
Question 2.
Define a relation all_cities(L, N) that specifies a list L of N cities in the order the cities appear in the flight facts. N is less than or equal to the total number of the cities appearing in the flight facts.
Question 3.
Write a relation search_destination(L, Len, Src) that specifies a list L of cities each of which is reachable from the city Src within the given path (containing one or more than one flight) length Len. The city IDs in L is unique, but the order of city IDs in L is unimportant.
Question 4.
Write a relation count_paths(Src, Dst, N) in which N is the number of paths from city Src to city Dst. All cities in each counted path must be unique, i.e., no city appears more than once in the path.
Question 5.
Write a relation shortest_paths(Src, Dst, L) that specifies a list L containing all the shortest paths from city Src to city Dst. If more than one path is the shortest, all these paths are included in L. If there is no path from city Src to city Dst, L is an empty list. The paths in L are unique, but the order these paths appear in L is unimportant.
Examples:
?- shortest_paths(0, 1, L).
L = [[0,1]].
?- shortest_paths(0, 2, [[0,2]]).
true.