Description
Behind every Google Map, there is a much more complex structure that’s the key to your queries but hidden from your view. It contains the logic of places: their no-left-turns and freeway on-ramps, speed limits and traffic conditions. This is the data that you’re drawing from when you ask Google to navigate you from point A to point B. In this project you will be creating an application to maintain a network of towns and the roads connecting them. The application will use Dijkstra’s Shortest Path algorithm to find the shortest distance between any two towns. Learning Objectives • Implement Graph Interface • Use Graph to maintain a network of Vertices • Implement Shortest Path Algorithm Project Requirements You will be reading from a data file in order to populate the graph data structure. You are provided with two sample files: MD Towns.txt and US Towns.txt along with two PowerPoint slides showing these graphs. The MD Towns.txt files hold the information for the individual Towns and Roads, and is in the following format: road-name,miles;town-name; town-name For example: I-94,282;Chicago;Detroit Notice that the road-name and miles are separated by a comma, while the road information and the two towns are separated by semi-colons. After reading these files, you will have an initial set of vertices and edges in your Graph. Town Graph Project CMSC 204-Project 6 Provided Classes The following classes are provided for you: • GraphInterface • TownGraphManagerInterface • DriverFX , FXMainPane (GUI Driver code) Required Classes Data Element – Town (Vertex) Create a Town class that holds the name of the town and a list of adjacent towns, and other fields as desired, and the traditional methods (constructors, getters/setters, toString, etc.). It will implement the Comparable interface. This is the class header: public class Town implements Comparable Two towns will be considered the same if their name is the same. Data Element – Road (Edge) Create a class Road that can represent the edges of a Graph of Towns. The class must implement Comparable interface. The class stores references to the two vertices (Town endpoints), the distance between vertices, and a name, and the traditional methods (constructors, getters/setters, toString, etc.), and a compareTo, which compares two Road objects. Since this is an undirected graph, an edge from A to B is equal to an edge from B to A. This is the class header: public class Road implements Comparable Data Structure – Graph, implements GraphInterface Create a Graph class that implements the provided GraphInterface. For Graph<V,E>, V is the vertex type (a Town), E is the edge type (a Road). You will need to decide how to store the graph, use an adjacent matrix or an adjacency list. This is the class header: public class Graph implements GraphInterface<Town, Road> Within the Graph interface is a method shortestPath, which finds the shortest path from a given source Town to a destination Town. Since there is a unique shortest path from every vertex to the source, there is a back-pointer to the previous vertex. The method shortestPath calls dijkstraShortestPath which finds the shortest path from the source to every other vertex in the graph. You will be coding the Dijkstra’s Shortest Path algorithm. You will then be able to find the connections between two towns through the roads that connect them. You may use the adjacency matrix approach found in the text book, or you may use a set of Towns and a set of Roads. The ShortestPath algorithm typically uses a weighted graph which Town Graph Project CMSC 204-Project 6 means that the edges have a weight, and this is used to determine the shortest path. For this implementation, each weight will be the distance of the road in miles. Data Manager – TownGraphManager implements TownGraphManagerInterface Your TownGraphManager will hold an object of your Graph. Implement the TownGraphManagerInterface. There are methods to populate the graph (reading from a text file), add a town (vertices), add a road (edge), list all towns and all roads, and list towns adjacent to a given town. Your solution will find the shortest path from a start town to a destination town. It will account for the possibility of a disjoint graph (i.e., not all vertices can be reached from all other vertices.) You may add any methods as needed for your design. Exception Classes FileNotFoundException – created and thrown when the selected input file is not found. IOException – created and thrown when user selects an input file that cannot be read (check out the methods of File). Note that these exceptions exist in the Java API. Testing Notes The provided GFA (Good Faith Attempt) JUnit tests represent the minimum requirements to validate the basic functionality of your project. If the project due date has passed, your submission must pass these tests in order to be considered for course credit. In addition to the GFA tests, any GUI code and public JUnit tests are provided to assist with basic verification of your implementation. However, these do not cover all functionality. You are expected to design and run additional tests to ensure the full correctness and robustness of your project. Sample GUI Output After reading in the MD Town file After reading in the US Town file Town Graph Project CMSC 204-Project 6 Add a Town Button The user may add a new Town by typing its name in the textfield. If the textfield is blank when the Add Town button is selected, the GUI should show an error message. When a new Town is added, the TownGraphManager will add it to the graph, and the Town’s name will be added to the four ComboBoxes. Add a Road Button To add a road, a town must be selected from each of the two ComboBoxes in the Add Road section, an integer distance entered, and a road name entered. When the Add Road button is selected, the edge is created and entered in the graph Find Connection Button Display all the available towns in the ComboBoxes (in alpha order by name). When the user selects the towns, display the name in the ComboBoxes. When the user selects the “Find Connection” button, the TownGraphManager’s shortestPath method is called. The resulting list of roads connecting towns, and the distance along each road, is displayed in the text area. If the “source” town and “destination” town are the same, or if there is no route between the two, state that in the text area. Town Graph Project CMSC 204-Project 6 Deliverables Before submitting your project, ensure your code is free of syntax errors. Submissions that do not compile will receive zero points. Design Documents UML and/or Pseudo-Code Implementation Only submit files that you have created or modified, do not submit unmodified files that were provided in the project download. Place all your .java files inside a src folder. Include the entire doc folder with Javadoc for your own classes. Summary Write-Up A 2-3 paragraph write-up (eg.LearningExperience.doc) Submission Packaging You will submit two compressed .zip files: Main Project Files All student created or modified project files and data: Filename LastNameFirstName_AssignmentX.zip src/ directory containing .java files created or modified by the student doc/ directory containing student created Javadoc files LearningExperience.doc reflection and write-up Design Documents all design related documents MOSS files Only the student created or modified source code files Filename LastNameFirstName_AssignmentX_Moss.zip source files only the .java files created or modified by the student Grading Rubric Criteria Points Graph Implementation 45% Road,Town Implementation 20% TownGraphManager Implementation 35% JUnit student-written tests -5% Design and Reflection write-up -10% Code style, documentation, and Javadoc (If not provided). -5%
