You will be coding the backbone of a map travel system. The goal would be to model something like an air travel system, which allows you to plan trips between any city in the world based on some cost to travel between nodes. Note: not every city has a connection to every other city.
This project is for practicing algorithms and graph programming. You will need to code your own graph/graphnode/other classes (20 points) and anything other base class/algorithm to support your program. For any sorting, you need to code your own merge or bubble sort.
Comments are important. You can utilitze java’s built in DS for hashtables and heaps but your own lists, stacks, linked lists and disjointed sets.
You will use a file called worldcities.txt which contains the GPS coordinates of 9117 cities around the world. The format of the file is :
- N (number of cities) city comma state (sometimes its just a city, so need to check for this and count it for both city and state) (hint: check for comma)
- Lat
- Long
You will create a simulated path system and costs between cities using the following algorithm:
Once you load up all your cities, for each city, decide how many directed connections it has ( between 2-8 connections (randomly)) and assign it to any other random cities in the set. For example: for city n, we randomly choose 4, which means you add 4 directed edges to 4 randomly chosen cities starting at this one (directed edges). And so on. For each connection choose a random weight between 100-2000. You will need to check for duplicate edges so that for any two city pairs, only one directed edge exists in a specific direction.
Once you are done, sweep across all N cities, if a city doesn’t have any incoming edges add ONE incoming edge from a random node in the graph. This will ensure every node has both enter and exit points.
Note2: the names of the cities might have spaces (and some might be missing state information, in which case just copy from city name). In addition I will provide a short test file called fict100.txt which has a sample of 100 fake cities. (the format is the same). Do not hard code the number of cities, but rather have your program read in the number on the first line to know how many cities to process.
You MUST handles error and weird conditions correctly.
Your README needs to list all the files involved with notes on each (if you wrote it or took from book etc) and runtimes for all algorithms, which you are running on your graph and in the system.
Important: besides the .java code and readme you need to submit, the project must be bundled as a jar file : project.jar and make sure I can execute it as java -jar project.jar
You will need to present the user with the following menu items either printed to terminal or GUI:
- Load a text file into the system
- load a graph from a file called mygraph.bin
- save current graph to file called mygraph.bin
- Search for state and list all cities of that state with the in/out counts for each.
- Search for city and display some information about it. (gps and in/out count)
- Set City X as current (X is between 0-N cities)
- print current city
- Find n closest cities to current city using gps distances.
- Find all cities from current city with directed edge costs less than Y
- Find shortest path between current and some target city
- quit
Here is an explanation of the above menu choices and the points of each of the problems:
- Load up file (10) will allow the user to add in a file to the current set of data, it should give the user the option of removing all the current information (in case you want to remove old graph). when you process the file of gps locations use the algorithm mentioned earlier to create random edges.
- load graph (5) load a graph from a serialized file called mygraph.bin
- save graph (5) serialize the graph to a file called mygraph.bin
- Search for state and list all cities of that state with the in/out counts for each (10) will return all cities associated with the specific state. For example if the user enters ‘d’, prompt for state, and if they enter “New York” show all cities in new york.....along with some ID number (which you create) and in and out counts from the directed graph created with algorithm described earlier.
- Search for city and display some information about it. (gps and in/out count) (10) will return the ID number and some information of the specific city if its in the system like gps, in/out etc
- Set city X as current (5) will take an ID number between 0-N and remember it as the current city
- Show current city (5) will print the currently set city’s information
- Find n closest cities using gps distances (ignoring directed edges) (20) for calculating gps distances see: http://www.meridianworlddata.com/Distance- Calculation.asp
- n is provided by the user
- Find n closest using cost of edges Y (15) find the n closest cities from the current city, if the current has not been set choose a random city as current, Y is a number provided by the user. You will use the randomly generated directed edges to measure cost and print all those which are less than Y away.
- Find shortest path (30) will take an ID and calculate all shortest hops from the current city to the destination city, finding the shortest path by directed weight. Feel free to reuse dijkstra’s algorithm from the book. You must credit if you use the books code vs writing it on your own.
- Quit (1) Have fun and please specify in your README and comments which algorithms you are implementing and their expected runtimes.... note: if you see yourself coding a n10 algorithm...find a better one
