Implement a graph data structure for a practical application.

Task Description: Input: Two files - one contains city data and the other contains road data. city.dat: This file contains information about cities, where each line has 5 attributes: City Number, City_Code (2 letters), Full_City_Name, Population, and Elevation.

road.dat: This file contains information about roads, where each line has 3 attributes: From_City, To_City, and Distance. Note that all roads are assumed to be one-way. Output: A menu driven system which has the following options.

Read the original data files and store the data to appropriate data structures. Let the user of this program enter a City Code and your program should print out the city information (the whole record). Find the connection between two cities. The user will be asked to enter two City Codes. The program finds the shortest distance between the two cities. Insert a road (edge) between two cities The user will be asked to enter two City Codes and its Distance. Note that if a pair of City Codes already exists or if the City Code doesn't exist, print out a warning message. Delete a road (edge) The user will be asked to enter two City Codes for a road. Note that if the road entered doesn't exist, print out a warning message. Exit.

Your program should resemble the following output (the user inputs are bold):

% java Project3 Command? H

Q Query the city information by entering the city code. D Find the minimum distance between two cities. I Insert a road by entering two city codes and distance. R Remove an existing road by entering two city codes. H Display this message. E Exit.

Command? Q

City code: LV 12 LV LEE VINING 8390 5983 Command? D City codes: CH PM The minimum distance between CHINO HILLS and POMONA is 143 through the route: CH, xxx, ..., xxx, PM. Command? I City codes and distance: GG BO 100 You have inserted a road from GARDEN GRPVE to BOSSTOWN with a distance of 100. Command? R City codes: KV MP The road from KERNVILLE and MOUNTAIN PASS doesn't exist. Command? E

Programming Guides Create a Java Digraph (directed graph) class to store the city and road information. Use Dijkstra's algorithm discussed in class for finding the shortest distances between cities. In your project report, please discuss the data structures you used for the graph and dijkstra's algorithm. You will also need to analyze the time complexity of your program with your selected data structures.

Content of the city.dat file 1 AN ANAHEIM 1273000 310 2 BK BAKERSFIELD 31100 390 3 BO BOSSTOWN 790 10 4 BR BREA CANYON 529000 1242 5 CH CHINO HILLS 52200 1381 6 ED EDWIN DOM 12 8719 7 FI FORT IRWIN 4120 932 8 GD GARDENA 653210 674 9 GG GARDEN GROVE 913330 952 10 KV KERNVILLE 6530 3925 11 LI LAKE ISABELLA 981 2194 12 LV LEE VINING 8390 5983 13 MP MOUNTAIN PASS 76 7190 14 PD PARKER DAM 2190 1829 15 PM POMONA 698300 298 16 PR PICO RIVERA 189820 1190 17 SB SAN BERNADINO 1293200 1033 18 TR TORRANCE 169400 829 19 VV VICTORVILLE 57460 2190 20 WW WRIGHTWOOD 9234 7910

Content of the road.dat file 1 19 36 1 4 212 1 2 732 2 9 111 2 1 66 2 12 29 2 19 14 2 17 65 3 2 17 3 11 38 3 14 122 3 17 211 3 1 390 3 18 78 3 9 11 4 3 273 4 5 29 4 12 42 5 4 122 5 16 12 5 20 102 5 9 32 6 5 211 6 1 62 6 8 132 6 12 871 7 11 122 7 2 200 7 13 81 7 4 41 7 1 20 7 14 11 8 6 5 8 3 210 8 16 74 9 2 95 9 11 2 9 7 120 9 20 11 10 12 121 10 20 653 10 3 925 11 2 81 11 12 219 11 4 90 11 16 211 12 19 122 12 8 390 12 5 98 12 7 122 12 3 11 13 9 9 12 17 121 13 17 26 13 1 719 13 20 832 14 20 219 14 10 182 14 9 13 14 3 22 15 6 22 16 11 73 16 18 98 17 20 190 17 1 77 17 11 21 17 12 93 17 9 200 18 10 33 18 16 940 18 8 29 18 20 121 18 15 33 19 2 322 19 5 74 19 6 219 19 10 111