Solved–Lab Assignment 5– Solution

Description

​Getting motivated

ACME Shipping needs your help! They have obtained the rights to ship goods between a number of cities across the world. Use your newly acquired knowledge about graphs to write a program called “citysim” that can tell ACME Shipping what the shortest valid route is between any two cities. Being customer friendly, ACME Shipping wants to explore two options: (i) a cheap rate based on distance traveled and (ii) a more expensive rate based on time in transit. See details below. Lots of them.

---

​Lab submission and due date

Submit your work via Canvas no later than 11:59pm Wednesday October 23, 2019. You submit only one file called Citysim.cpp. The incremental development outlined below is merely intended to walk you through the process of completing the assignment. CS307 students will write additional code as outlined below. CS302 are free to write this code as well but there is no extra credit to be earned this time.

While it may seem like you have a long time to do this assignment, keep in mind that Fall Break is coming up. Thus, you really only a week to get the job done. Make sure you have code that compiles and does at least part of the assignment, if not all of it by the due date.

---

​Getting started and what you need to do

To help you get started, run the Hydra script /home/cs302/labs/lab5/copy to obtain the following files: scitysim (Hydra solution executable), city_list.txt (input data), Citysim.cpp (skeleton code), and a makefile. Your job is to write the citysim program and make it behave as described next.

While you have some design freedom, you must base your code on the classes and functions discussed next. How you tie them all together is up to you. Also, floating-point computations should be done using floats, not doubles. Most math functions take and produce doubles. That’s fine. Feed them floats and assign the output to floats.

Please raise concerns about assignment inconsistencies or unspoken design criteria on Piazza.com sooner rather than later, so that clarifications can be shared with the class as early as possible.

You might find it helpful to take a glance at the city_list.txt snippet included below before you continue reading.

• Version 1 should implement a city class that stores the name (string), type (string), zone (int), latitude (float), longitude (float) and population (int). Make these variables private data members. Add get_variable() functions for each variable. Overload the input and output operators to facilitate “fin >> city” and “fout << city” type code. The city type is either REGIONAL or GATEWAY. We discuss these in more detail below.

Next, implement function read_cityinfo() which reads the “city_list.txt” file in the current directory into a vector<city> array using the overloaded city input operator. Empty lines or lines that begin with a hash symbol (#) should be ignored. You may find it convenient to also implement function write_cityinfo() which writes the contents of the vector<city> array to stdout or an appropriately named file, so you know you read things correctly. See below for example output from the solution code which produces a file called “city_info.txt”. The name field is 18 characters wide. The type and population fields are 12 and 10 characters wide, respectively. The zone is 2 characters wide. The latitude and longitude fields are 8 characters wide and the output is restricted to two decimal places.

Note: The latitude and longitude values are in degrees in city_list.txt and city_info.txt. However, your program will need them to be in radians for internal use. Perform the necessary conversion when you read and write these variables. Recall that radians=degrees*(pi/180) and degrees=radians*(180/pi).

• Version 2 should implement a travelcost class which computes and contains a table of distances between all cities and a table of the time it takes to get from one city to another. Since the distance from A to B is the same as from B to A, store each of these tables in a 1D array that holds the diagonal and lower triangle of the full matrix; we don’t need the diagonal, but including it simplifies implementation. Say the equivalent 2D table[i][j] is NxN. Then the 1D table is of size N*(N+1)/2 and you access the elements using using table[i*(i+1)/2+j] where j <i. You are free to create two independent tables, but you may find it more convenient to use an array of vectors instead. That is,

vector<float> distance_table;
vector<float> time_table;

or

vector<float> table[2];

Either way, create an overloaded function operator that returns the same value for travelcost(mode,i,j) as for travelcost(mode,j,i) by looking the appropriate value in the 1D array. Here mode refers to distance (0) or time (1). Hint: Have the overloaded function operator swap arguments i and j if i <j before doing a lookup. Hint: The mode controls whether you look up a distance or a time.

Use the great-circle distance when computing the distance between two cities. This is the shortest distance between them on a sphere representing the Earth which we will assume has a radius of 3,982 miles. Don’t try to be clever and use a more accurate radius as it will throw your output off relative to the solution code which filed called “city_info.txt”. Also, use the Haversine Formula for your computation.

See http://en.wikipedia.org/wiki/Great-circle_distance for mathematical details.

Round the distances to the closest 25.0 mile distance. This will make it easier to compare your distances with those produced by the solution code. Hint: Set distance = 25.0*round(distance/25.0).

ACME Shipping has access to large fleet of trucks. They travel at an average speed of 65 mph. They also have access to planes. They travel at an average speed of 520 mph. The rules for when to use a truck versus a plane are as follows.

— Goods shipped between REGIONAL cities in the same zone go by truck.

— Goods shipped between REGIONAL cities and a GATEWAY city in the same zone go by plane.

— Goods shipped between GATEWAY cities go by plane no matter what the zone they are in.

You may find it convenient to also implement functions write_traveldistance() write_traveltime() which write the contents of the travelcost tables stdout or appropriately named files, so you know you compute these correctly. See below for example output from the solution code which produces files called “city_distancetable.txt”. and “city_timetable.txt”.

• Version 3 should implement function create_citygraph() which determines which cities are adjacent to one another (connected) thereby implicitly creating a graph. The rules for adjacency are as follows.

— A REGIONAL city is adjacent to all other REGIONAL cities in the same zone. A REGIONAL city is also adjacent to the closest GATEWAY city in the same zone.

— A GATEWAY city is adjacent to all other GATEWAY cities in the same zone. A GATEWAY city is also adjacent to the closest GATEWAY in each of the other zones if the distance is 6,000 miles or less.

— In order to make the graph undirected, adjacency is bidirectional. Thus, if A is adjacent to B, then B is also adjacent to A. This can result in a GATEWAY city becoming connected with multiple GATEWAY cities in another zone (see for example Cairo_EG below).

Hint: First extract an index list for each type of city. Then iterate thru these lists following the above rules. Use the indices to look up the pertinent information in the vector<city> array discussed above. In fact, think of these indices as pointers.

You may find it convenient to also implement a function called write_citygraph() and have it write the graph to stdout or an appropriately named fil. so you know you connected the cities correctly. See below for example output from the solution code which produces a file called “city_graph.txt”.

• Version 4 should add the ability to determine the shortest path between any two cities using Dijkstra’s algorithm. The output consists of the sequence of cities from source to sink (destination) along with the incremental and cumulative distances and travel times. This is likely the easiest step of them all. Embed the code from the Dijkstra code handout. Add logic to select between use of the distance and time edge weights you computed earlier. The algoithm works the same either way but wil produce different answers if the optimal paths are different. See an example below.

Update the main program to take one of two command-line options:

unix> Citysim -distance|time

Then have the user input an endless sequence of city pair names for which the shorted path is reported. Hint: In order to translate the names into the indices used internally, have the read_cityinfo() function create a map that links the two: “index = map[name]”. This will allow fast lookup of an index given a name.

• The following is optional for CS302 students (no extra credit this time) but required in order for CS307 students to get full credit. That is, CS307 students will have up to 10 points deducted if the functionality described next is not included or doesn’t work right.

Add the ability to input just a partial name, e.g., “Knoxville” or even just “Knox” for “Knoxville_TN”. In case of ambiguity, choose the city name that follows the partial name in a lexicographical order, e.g., “K” may produce “Kansas_City_KS” instead of “Knoxville_TN”. To be acceptable, this city must match the search prefix. Thus, “Knox” should produce a city that begins with that, e.g., “Knoxvegas_TN”. Run the solution code to determine the desired behavior. Your code should function similarly. Hint: The STL algorithm map::upper_bound() can do the lookup for you.

• See http://web.eecs.utk.edu/~jgregor/cs302/citysim.html for a Google map with the city graph displayed. You can pan and zoom using the mouse directly or the little control pad in the upper left hand corner. The trajectories stand out more clearly on the map than the satellite data. The white text is courtesy of Google who now charges for use of their maps.

---

​Input file: citylist.txt (abbreviated)

unix> cat citylist.txt
# AFRICA Zone 1
1 Cairo_EG GATEWAY  30.058 31.229 17800000
1 Johannesburg_SA GATEWAY -26.204444 28.045556 7151500

# ASIA Zone 2
2 Beijing_CN REGIONAL 39.916667 116.383333 21700000
2 Hong_Kong_CN REGIONAL 22.3 114.2 7400000
2 Taipei_TW REGIONAL 25.066667 121.516667 8500000
2 Tokyo_JP GATEWAY 35.683333 139.766667 35000000
2 Seoul_KR REGIONAL 37.55 126.983333 24472000

[...]

---

​Output file: city_info.txt (abbreviated)

unix> ./citysim -graphinfo
unix> cat ./city_info.txt

CITY INFO (N=30):

  0 Cairo_EG          GATEWAY     1   17800000   30.06   31.23
  1 Johannesburg_SA   GATEWAY     1    7151500  -26.20   28.05
  2 Beijing_CN        REGIONAL    2   21700000   39.92  116.38
  3 Hong_Kong_CN      REGIONAL    2    7400000   22.30  114.20
  4 Taipei_TW         REGIONAL    2    8500000   25.07  121.52
  5 Tokyo_JP          GATEWAY     2   35000000   35.68  139.77
  6 Seoul_KR          REGIONAL    2   24472000   37.55  126.98
  7 Bangalore_IN      GATEWAY     2   12350000   12.97   77.57

[...]

---

​Output file: city_distancetable.txt (abbreviated)

unix> ./citysim -graphinfo
unix> cat ./city_distancetable.txt

DISTANCE TABLE:

  1 Johannesburg_SA to Cairo_EG .......... 3925.0 miles

  2 Beijing_CN to Cairo_EG ............... 4725.0 miles
  2 Beijing_CN to Johannesburg_SA ........ 7325.0 miles

  3 Hong_Kong_CN to Cairo_EG ............. 5100.0 miles
  3 Hong_Kong_CN to Johannesburg_SA ...... 6700.0 miles
  3 Hong_Kong_CN to Beijing_CN ........... 1225.0 miles

  4 Taipei_TW to Cairo_EG ................ 5425.0 miles
  4 Taipei_TW to Johannesburg_SA ......... 7200.0 miles
  4 Taipei_TW to Beijing_CN .............. 1075.0 miles
  4 Taipei_TW to Hong_Kong_CN ............  500.0 miles

  5 Tokyo_JP to Cairo_EG ................. 5975.0 miles
  5 Tokyo_JP to Johannesburg_SA .......... 8475.0 miles
  5 Tokyo_JP to Beijing_CN ............... 1325.0 miles
  5 Tokyo_JP to Hong_Kong_CN ............. 1800.0 miles

[...]

---

​Output file: city_timetable.txt (abbreviated)

unix> ./citysim -graphinfo
unix> cat ./city_timetable.txt

TIME TABLE:

  1 Johannesburg_SA to Cairo_EG ..........  7.5 hours

  2 Beijing_CN to Cairo_EG ...............  9.1 hours
  2 Beijing_CN to Johannesburg_SA ........ 14.1 hours

  3 Hong_Kong_CN to Cairo_EG .............  9.8 hours
  3 Hong_Kong_CN to Johannesburg_SA ...... 12.9 hours
  3 Hong_Kong_CN to Beijing_CN ........... 18.8 hours

  4 Taipei_TW to Cairo_EG ................ 10.4 hours
  4 Taipei_TW to Johannesburg_SA ......... 13.8 hours
  4 Taipei_TW to Beijing_CN .............. 16.5 hours
  4 Taipei_TW to Hong_Kong_CN ............  7.7 hours

  5 Tokyo_JP to Cairo_EG ................. 11.5 hours
  5 Tokyo_JP to Johannesburg_SA .......... 16.3 hours
  5 Tokyo_JP to Beijing_CN ...............  2.5 hours
  5 Tokyo_JP to Hong_Kong_CN .............  3.5 hours

---

​Output file: city_graph.txt (abbreviated)

unix> ./citysim -graphinfo
unix> cat ./city_graph.txt

CITY GRAPH:

  0 Cairo_EG
     1 Johannesburg_SA     3925.0 miles   7.5 hours
     5 Tokyo_JP            5975.0 miles  11.5 hours
     7 Bangalore_IN        3200.0 miles   6.2 hours
     9 Singapore_SG        5150.0 miles   9.9 hours
    13 London_UK           2200.0 miles   4.2 hours
    16 Frankfurt_DE        1825.0 miles   3.5 hours
    25 New_York_NY         5650.0 miles  10.9 hours

  1 Johannesburg_SA
     0 Cairo_EG            3925.0 miles   7.5 hours
     7 Bangalore_IN        4325.0 miles   8.3 hours
    16 Frankfurt_DE        5425.0 miles  10.4 hours
    28 Santiago_CL         5725.0 miles  11.0 hours
    29 Rio_de_Janeiro_BR   4450.0 miles   8.6 hours

  2 Beijing_CN
     3 Hong_Kong_CN        1225.0 miles  18.8 hours
     4 Taipei_TW           1075.0 miles  16.5 hours
     5 Tokyo_JP            1325.0 miles   2.5 hours
     6 Seoul_KR             600.0 miles   9.2 hours
     8 New_Delhi_IN        2350.0 miles  36.2 hours

  3 Hong_Kong_CN
     2 Beijing_CN          1225.0 miles  18.8 hours
     4 Taipei_TW            500.0 miles   7.7 hours
     6 Seoul_KR            1300.0 miles  20.0 hours
     8 New_Delhi_IN        2350.0 miles  36.2 hours

[...]

---

​Functionality: Shortest path

unix> ./citysim -distance

Enter> Knoxville_TN Seattle_WA
    0.0 miles   0.0 hours : 21 Knoxville_TN      
 2125.0 miles  32.7 hours : 27 Seattle_WA         2125.0 miles  32.7 hours

Enter> London_UK Seoul_KR
    0.0 miles   0.0 hours : 13 London_UK         
  400.0 miles   0.8 hours : 16 Frankfurt_DE        400.0 miles   0.8 hours
 6225.0 miles  12.0 hours :  5 Tokyo_JP           5825.0 miles  11.2 hours
 6950.0 miles  13.4 hours :  6 Seoul_KR            725.0 miles   1.4 hours

unix> ./citysim -time

Enter> Knoxville_TN Seattle_WA
    0.0 miles   0.0 hours : 21 Knoxville_TN
  625.0 miles   1.2 hours : 25 New_York_NY         625.0 miles   1.2 hours
 3075.0 miles   5.9 hours : 22 Los_Angeles_CA     2450.0 miles   4.7 hours
 4050.0 miles   7.8 hours : 27 Seattle_WA          975.0 miles   1.9 hours

Enter> London_UK Seoul_KR
    0.0 miles   0.0 hours : 13 London_UK
  400.0 miles   0.8 hours : 16 Frankfurt_DE        400.0 miles   0.8 hours
 6225.0 miles  12.0 hours :  5 Tokyo_JP           5825.0 miles  11.2 hours
 6950.0 miles  13.4 hours :  6 Seoul_KR            725.0 miles   1.4 hours
unix> ./citysim -distance

Enter> Knox Seattle
    0.0 miles   0.0 hours : 21 Knoxville_TN
 2125.0 miles  32.7 hours : 27 Seattle_WA         2125.0 miles  32.7 hours

Enter> Knox S
    0.0 miles   0.0 hours : 21 Knoxville_TN
 2125.0 miles  32.7 hours : 26 San_Fransisco_CA   2125.0 miles  32.7 hours

Enter> * *
    0.0 miles   0.0 hours : 23 Mexico_City_MX
 1900.0 miles  29.2 hours : 26 San_Fransisco_CA   1900.0 miles  29.2 hours
 2250.0 miles  29.9 hours : 22 Los_Angeles_CA      350.0 miles   0.7 hours
 7750.0 miles  40.5 hours :  5 Tokyo_JP           5500.0 miles  10.6 hours
 9075.0 miles  43.0 hours :  4 Taipei_TW          1325.0 miles   2.5 hours
 9575.0 miles  50.7 hours :  3 Hong_Kong_CN        500.0 miles   7.7 hours

As shown above, the solution code accepts abbreviations. When multiple cities share the same prefix, alphabetical order applies. The solution code even accepts wildcards in which case it randomly choses a city. You can use this feature for source, destination, or both.

---

​Grading rubric

Your code most compile and run free of segmentation faults in order to be fully graded.

15: Reading city_list.txt into city objects using overloaded input operator
30: Creating travelcost object that holds city travel distances and times
30: Creating graph by determing city adjacencies (graph edges) 
30: Finding shortest path between two cities and printing result to stdout
20: Writing main program that ties data structures and function calls together 
    to achieve overall functionality (CS307 extra assignment is part of this)