LAB 3— The flight routing problem Due Tuesday February 19th at 23:59.

Remark: late submissions wont be marked.

Problem Statement.

Revise the solution in your book for the HPAir flight routing problem (section 7.5 of your textbook) to output a path from an origin city to a destination city if such a path exists.

Input files:

The program has 3 input files as follows

1) A file called “cities.txt” containing the names of the cities that HPAir serves. Each line contains a city name which is one word.
E.g.
Paris
Vancouver
Esfahan
Rome
Seattle
Victoria

2) A file called “flights.txt” containing pairs of city names; each line contains a pair of cities (separated by space) representing origin and destination of one of HPAir’s flights
E.g.
Vancouver Paris
Vancouver Seattle
Vancouver Victoria
Paris Esfahan
Paris Rome
Rome Seattle
Rome Vancouver
Rome Paris
Seattle Rome
Seattle Vancouver
Esfahan Paris
Victoria Vancouver

3) A file called “request.txt” containing pairs of city names; each line contains a pair of cities (separated by space) representing a request to fly from origin to destination.
E.g.
Vancouver Rome
Vancouver Esfahan
Seattle Esfahan
Paris Rom
Paris Victoria

Output:

The program should then produce the following output.

Request if to fly from Vancouver to Rome.
HPAirs flies from Vancouver to Rome  through Paris.

Request if to fly from Vancouver to Esfahan.
HPAirs flies from Vancouver to Esfahan  through Paris.

Request if to fly from Seattle to Esfahan.
Sorry. HPAirs does not fly from Seattle to Esfahan.

Request if to fly from Paris to Rome.
HPAirs flies from Paris to Rome directly.

Request if to fly from Paris to Victoria.
HPAirs flies from Paris to Victoria through Rome, Seattle.

Implementation.

The major part of the program i.e the isPath(City originCity, …) method is implemented in your text book. However, you need to modify to return the path from origin to destination if such path exists. The isPath() method uses the class StackReferenceBased which is also implemented and you can use in your program. You can download these codes from here.  You also need to implement the City class that implements the Comparable interface and also the methods unvisitAll(), markVisited(City), and getNextCity(City).

For Java programmers: You must name your main class  (the class with the main method) hpairs.java.

Style: part of the grade is for having proper style which includes proper indenting and having enough comments.

Submission: zip all your source files and submit it through submission server submit.cs.sfu.ca. The submission server only accepts the zipped files. You can zip your assignment files using the winzip program or the zip, gzip linux command. Include your name and student number in your source file that includes the main function.

Remark: there will be four submission groups for each lab assignment make sure you submit to the group that you belong to (if you are registered in the first lab submit to the first group, and so on) otherwise there will be a 50% penalty.

Implementation Language: The programming problems in assignments, can be written in either JAVA or C++. It’s not necessary to learn JAVA for those who know only C++ and to learn C++ for those who know only JAVA.

---