Assignment 6 CMSC204 New concepts tested by this program Implement Graph Interface Use Graph to maintain a network of Vertices Implement Shortest Path Algorithm Every conversation in our area ends up in a discussion about traffic. In this project you will be creating an application to maintain a network of towns and roads connecting them. The application will use Dijkstras Shortest Path algorithm to find the shortest distance between any two towns. Follow the interfaces, the below specifications, and the JUnit test files. 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. 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 a 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 The Data Structure Graph, implements GraphInterface Create a Graph class that implements the GraphInterface given you. For Graph, V is the vertex type (a Town), E is the edge type (a Road). You will need to decide how to store the graph, using an adjacent matrix, an adjacency list, or a Set and Set. This is the class header: public class Graph implements GraphInterface Within the Graph interface is a method shortestPath, which finds the shortest path from a given 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 Dijkstras 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 or list 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 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. The Data Manager implements DataManagerInterface 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. Populating the Data Structure You will be reading from a data file. You are provided with two sample files: MD Towns.txt and US Towns.txt along with two PowerPoint slides showing these graphs. The 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. ? The GUI The GUI will have four sections: an Add Town section, an Add Road section, a Find Connection section, and an administration section. There will be four ComboBoxes each containing the same list of Towns. On startup the graph will be empty. 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 Towns 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 TownGraphManagers 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.? Read File Button The Towns.txt files hold information for 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. Exit Button The program will terminate. Implementation: The deliverables will be packaged as follows. Two compressed files in the following formats: LastNameFirstName_Assignment6.zip [containing:] doc [a directory] include the entire doc folder with the javadoc for student generated files file1.html (example) file2.html (example) src [a directory] contains your driver (javafx application), enumerated class, data element, data structure, data manager and Junit Test (.java) files File1.java (example) File2.java (example) File_Test.java (example) LastNameFirstName_Assignment6_Moss.zip [containing:] contains .java file which includes the driver (javafx application), enumeration class, data element, data structure, data manager and Junit Test (.java) files NO FOLDERS!! File1.java (example) File2.java (example) ? Grading Rubric CMSC 204 Project #6 Name _____________________________ PROGRAMMING (100 pts) Compiles 40 pts _____ Accuracy Passes public JUnit tests 10 pts _____ Passes STUDENT JUnit tests 5 pts _____ Passes private instructor tests 10 pts _____ Execution: runs without errors (either run-time or logic errors) 35 pts _____ Possible Sub-total 100 pts REQUIREMENTS (Subtracts from Programming total) Documentation: Javadoc was not provided - 5 pts _____ Documentation within source code was missing or incorrect - 5 pts _____ Description of what class does was missing Authors Name, @author, was missing Methods not commented properly using Javadoc @param, @return JUnit Test Class: STUDENT methods not implemented - 5 pts _____ Programming Style: Incorrect use of indentation, statements, structures - 5 pts _____ Design: Implementation does not follow design - 10 pts _____ Classes do not have the functionality specified, i.e., 1. Town - 6 pts _____ holds the name implements standard methods - constructors, getters/setters, toString, etc. implements the Comparable interface 2. Road - 6 pts _____ implements Comparable stores references to both Actor objects, weight (1) and movie name implements standard methods - constructors, getters/setters, toString, etc 3. Graph - 6 pts _____ implements GraphInterface uses an adjacency matrix, adjacency list, or sets to store graph 4. TownGraphManager - 6 pts _____ Implements TownGraphManagerInterface Contains a Graph 5. GUI details - 6 pts _____ User cannot add a Town and a Road. User cannot choose from list of available Towns (alpha order, no duplicates) Town list is not updated when adding a Town Find Connection does not print out path Possible decrements: -60 pts _____ Possible total grade: 100 pts _____