CS 201 Homework Assignment 4

In this homework, you will work on an extended version of the HPAir problem that we studied in the class, which is also explained in Section 6.4 in your text book (Carrano’s book, 6’th edition). In this assignment, we will provide you with a directed ight graph that shows the connections between cities. A connection between two cities consists of a \ ight id" and a \cost". By using this ight graph, your program must nd all possible paths (sequences of ights) between the given departure and destination cities. It also should nd the least cost path among all paths. A sample graph is shown in Figure 1.



Z


11,600
10,550



Y



7,400


8,450
W
4,250
S





1,100
6,350
5,300
9,500



R
P
T


2,150

3,200
X   Q

Figure 1: Sample    ight graph.

In Figure 1, each vertex corresponds to a city and each edge represents a ight between two cities. Each edge has a ight id and a cost. For example, in Figure 1, the red colored edge’s id is \1" and its cost is \100". The graph can be stored by using adjacency lists as described in the Carrano book or by using an adjacency matrix where the rows and columns correspond to individual cities. Given this graph, when the departure city is selected as \P" and the destination city is selected as \Z", your program must nd the paths \P ! R ! Z", \P ! W ! Y ! Z", and \P ! W ! Y ! R ! Z", and since the second path has a cost of 1050, it is selected as the least cost path.

We will provide you with three les: cityFile, flightFile, and requestFile. The \cityFile" includes the names of all cities in the ight graph. Each line has exactly one city name. The le for the example graph is:

P

Q

R

S

T

W

X

Y

Z

City names can have any number of letters and can include spaces (e.g., Los Angeles). They can be given in an arbitrary order (i.e., not necessarily in alphabetical order).


1

The \flightFile" includes the edge list of the ight graph where each line describes an edge with its origin city, destination city, ight id, and cost, separated by commas. The le for the example graph is:

P,W,1,100

R,X,2,150

Q,X,3,200

W,S,4,250

S,T,5,300

T,W,6,350

W,Y,7,400

Y,R,8,450

P,R,9,500

Y,Z,10,550

R,Z,11,600

The    ights can be given in an arbitrary order (i.e., not necessarily sorted according to    ight id or cost).

Both    ight ids and costs can be assumed to be positive integers.

The \requestFile" includes a pair of city names in each line. First city name is assumed to be the departure city and the second city name is assumed to be the destination city. Each line has exactly one pair of cities. An example is:

P,Z

Q,X

Your solution must be implemented in a class called FlightMap. Below is the required public part of the FlightMap class. The interface for the class must be written in a le called FlightMap.h and its implementation must be written in a le called FlightMap.cpp. You can de ne additional public and private member functions and data members in this class. You can also de ne additional classes in your solution.


class FlightMap {

public:

FlightMap( const string cityFile, const string flightFile ); ~FlightMap();


void displayAllCities() const;

void displayAdjacentCities( const string cityName ) const; void displayFlightMap() const;

void findFlights( const string deptCity, const string destCity ) const; void findLeastCostFlight( const string deptCity, const string destCity )

const;

void runFlightRequests( const string requestFile ) const;

};


The member functions are de ned as follows:

FlightMap: Constructor. Reads the ight graph information from the les cityFile and flightFile given as parameters and stores the ight graph. The graph can be stored by using adjacency lists as described in the Carrano book or by using an adjacency matrix where the rows and columns correspond to individual cities.

displayAllCities:    Displays all cities in the    ight graph.




2

displayAdjacentCities: Displays the cities adjacent to the given city (i.e., all cities that have a ight coming from the given city).

displayFlightMap: Displays all adjacent cities for all cities in the graph. In other words, this function displays the whole ight graph.

findFlights: Finds and displays all paths (sequences of ights) from the departure city to the desti-nation city. If there is no such path, displays a warning message.

findLeastCostFlight: Finds and displays all paths and identi es the least cost path from the depar-ture city to the destination city. If there are multiple paths that have the same lowest cost, only one of them will be displayed (any one of them is acceptable).

runFlightRequests: For each request given in the requestFile, nds and displays all paths from the departure city to the destination city as well as the least cost path.

Here is an example test program that uses this class and the corresponding output. We will use a similar program to test your solution so make sure that the name of the class is FlightMap, its interface is in the le called FlightMap.h, and the required functions are de ned as shown above.

Example test code:

#include "FlightMap.h"

int main() {

FlightMap fm( "files/cityFile.txt", "files/flightFile.txt" );

cout << "The list of the cities that HPAir serves is given below:" << endl;

fm.displayAllCities();

cout << endl;

cout << "The cities adjacent to W are:" << endl; fm.displayAdjacentCities( "W" ); cout << endl;


cout << "The whole flight map is shown below:" << endl;

fm.displayFlightMap();

cout << endl;

fm.findFlights( "W", "Z" );

cout << endl;

fm.findFlights( "S", "P" );

cout << endl;

fm.findLeastCostFlight( "Y", "Z" );

cout << endl;

fm.findLeastCostFlight( "P", "X" );

cout << endl;

fm.runFlightRequests( "files/requestFile.txt" );

return 0;

}


3

Output of the example test code:

The list of the cities that HPAir serves is given below:

P, Q, R, S, T, W, X, Y, Z,

The cities adjacent to W are:

W->Y,S,

The whole flight map is shown below:

P->R,W,

Q->X,

R->Z,X,

S->T,

T->W,

W->Y,S,

X ->

Y->Z,R,

Z ->

Request is to fly from W to Z:

Flight #7 from W to Y
Cost: 400 TL
Flight #8 from Y to R
Cost: 450 TL
Flight #11 from R to Z
Cost: 600 TL
Total Cost .......... 1450 TL

Flight #7 from W to Y
Cost: 400
TL
Flight #10 from Y to Z
Cost: 550
TL
Total Cost .......... 950 TL


Request is to fly
from S to P:
Sorry. HPAir does
not fly from S to P
Request is to fly
from Y to Z:
Flight #8 from Y to R
Cost: 450 TL
Flight #11 from R to Z
Cost: 600 TL
Total Cost .......... 1050 TL
Flight #10 from Y to Z
Cost: 550 TL

Total Cost .......... 550 TL

A least cost path from Y to Z is Y -> Z and its cost is 550 TL

Request is to fly from P to X:

Flight #1 from P to W
Cost: 100 TL
Flight #7 from W to Y
Cost: 400 TL
Flight #8 from Y to R
Cost: 450 TL
Flight #2 from R to X
Cost: 150
TL
Total Cost .......... 1100 TL

Flight #9 from P to R
Cost: 500
TL
Flight #2 from R to X
Cost: 150
TL

Total Cost .......... 650 TL

A least cost path from P to X is P -> R -> X and its cost is 650 TL

Request is to fly from P to Z:


4

Flight #1 from P to W    Cost: 100 TL

Flight #7 from W to Y    Cost: 400 TL

Flight #8 from Y to R    Cost: 450 TL

Flight #11 from R to Z    Cost: 600 TL

Total Cost .......... 1550 TL

Flight #1 from P to W    Cost: 100 TL

Flight #7 from W to Y    Cost: 400 TL

Flight #10 from Y to Z    Cost: 550 TL

Total Cost .......... 1050 TL

Flight #9 from P to R    Cost: 500 TL

Flight #11 from R to Z    Cost: 600 TL

Total Cost .......... 1100 TL

A least cost path from P to Z is P -> W -> Y -> Z and its cost is 1050 TL

Request is to fly from Q to X:

Flight #3 from Q to X    Cost: 200 TL

Total Cost .......... 200 TL

A least cost path from Q to X is Q -> X and its cost is 200 TL



Below is an example code segment for reading from text les. You can modify it according to the speci c format of the text les in this assignment.

//Declare variables

string fileName = "test.txt";

string text;

ifstream inputFile;

...

//Open the stream for the input file inputFile.open( fileName.c_str(), ios_base::in ); ...

//Continue until the end of the file

while ( inputFile.eof() == false ) {

//Read until a comma

getline( inputFile, text, ’,’ );

//Read until the end of the line

getline( inputFile, text, ’\n’ );

}

...

//Close the input file stream

inputFile.close();














5
IMPORTANT NOTES:

Do not start your homework before reading these notes!!!


Output message for each operation should match the format shown in the output of the example code.


NOTES ABOUT IMPLEMENTATION:

    1. You MUST use the nonrecursive solution using a stack to implement the search algorithm for nding the paths between the cities as discussed in the class. You will get no points if you use any other algorithm for the solution of the search problem. You can use other data structures to help with your implementation but the main search algorithm must be implemented using a stack.

    2. You MUST use your own implementation of a stack in this assignment. In other words, you cannot use any existing stack code from any other source. However, you can adapt the stack codes in the Carrano book or in our lecture slides.

    3. You are NOT ALLOWED to modify the given parts of the class de nition. Note that you can de ne additional public and private member functions and data members in the given class. You can also de ne additional classes in your solution.

    4. You are NOT ALLOWED to use any global variables or any global functions.

    5. Your code MUST NOT have any memory leaks. You will lose points if you have memory leaks in your program even though the outputs of the operations are correct.

    6. Make sure that each le that you submit (each and every le in the zip archive) contains your name, section, and student number at the top as comments.


NOTES ABOUT SUBMISSION:

    1. This assignment is due by 23:59 on December 28, 2020. This homework will be graded by your TA Aydamir Mirzayev (aydamir.mirzayev at bilkent edu tr). Please direct your homework related questions to him.

    2. You MUST have separate interface and implementation les (i.e., separate .h and .cpp les) for your classes. We will test your implementation by writing our own driver .cpp le which will include your header le. For this reason, your class’ name MUST be \FlightMap" and your les’ name MUST be \FlightMap.h" and \FlightMap.cpp". You should upload these two les (and any additional les if you wrote additional classes in your solution) as a single zip le. In this zip le, there should not be any le containing the main function. The name of this zip le should be secX_Firstname_Lastname_StudentID.zip where X is your section number. The submissions that do not obey these rules will not be graded. We also recommend you to write your own driver le to test each of your functions. However, you MUST NOT submit this test code (we will use our own test code). In other words, your submitted code should not include any main function.

    3. No hard copy submission is needed. The standard rules about late homework submissions ap-ply. Please see the course web page for further discussion of the late homework policy as well as academic integrity.

    4. You are free to write your programs in any environment (you may use either Linux or Windows). Yet, we will test your programs on \dijkstra.ug.bcc.bilkent.edu.tr" and we will expect your programs to compile and run on the dijkstra machine. If we could not get your program properly work on the dijkstra machine, you would lose a considerable amount of points. Therefore, we recommend you to make sure that your program compiles and properly works on dijkstra.ug.bcc.bilkent.edu.tr before submitting your assignment.






6