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, use 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 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 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.

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.

#GraphInterface

import java.util.*;

/** * The root interface in the graph hierarchy. A mathematical graph-theory graph * object G(V,E) contains a set V of vertices and a set * E of edges. Each edge e=(v1,v2) in E connects vertex v1 to vertex v2. * * Through generics, a graph can be typed to specific classes for vertices * V and edges E. Such a graph can contain * vertices of type V and all sub-types and Edges of type * E and all sub-types. */ public interface GraphInterface { //~ Methods ---------------------------------------------------------------- /** * Returns an edge connecting source vertex to target vertex if such * vertices and such edge exist in this graph. Otherwise returns * null. If any of the specified vertices is null * returns null * * In undirected graphs, the returned edge may have its source and target * vertices in the opposite order. * * @param sourceVertex source vertex of the edge. * @param destinationVertex target vertex of the edge. * * @return an edge connecting source vertex to target vertex. */ public E getEdge(V sourceVertex, V destinationVertex); /** * Creates a new edge in this graph, going from the source vertex to the * target vertex, and returns the created edge. * * The source and target vertices must already be contained in this * graph. If they are not found in graph IllegalArgumentException is * thrown. * * * @param sourceVertex source vertex of the edge. * @param destinationVertex target vertex of the edge. * @param weight weight of the edge * @param description description for edge * * @return The newly created edge if added to the graph, otherwise null. * * @throws NullPointerException if any of the specified vertices is null. */ public E addEdge(V sourceVertex, V destinationVertex, int weight, String description); /** * Adds the specified vertex to this graph if not already present. More * formally, adds the specified vertex, v, to this graph if * this graph contains no vertex u such that * u.equals(v). If this graph already contains such vertex, the call * leaves this graph unchanged and returns false. In combination * with the restriction on constructors, this ensures that graphs never * contain duplicate vertices. * * @param v vertex to be added to this graph. * * @return true if this graph did not already contain the specified * vertex. * * @throws NullPointerException if the specified vertex is null. */ public boolean addVertex(V v); /** * Returns true if and only if this graph contains an edge going * from the source vertex to the target vertex. In undirected graphs the * same result is obtained when source and target are inverted. If any of * the specified vertices does not exist in the graph, or if is * null, returns false. * * @param sourceVertex source vertex of the edge. * @param destinationVertex target vertex of the edge. * * @return true if this graph contains the specified edge. */ public boolean containsEdge(V sourceVertex, V destinationVertex); /** * Returns true if this graph contains the specified vertex. More * formally, returns true if and only if this graph contains a * vertex u such that u.equals(v). If the * specified vertex is null returns false. * * @param v vertex whose presence in this graph is to be tested. * * @return true if this graph contains the specified vertex. */ public boolean containsVertex(V v); /** * Returns a set of the edges contained in this graph. The set is backed by * the graph, so changes to the graph are reflected in the set. If the graph * is modified while an iteration over the set is in progress, the results * of the iteration are undefined. * * * @return a set of the edges contained in this graph. */ public Set edgeSet(); /** * Returns a set of all edges touching the specified vertex (also * referred to as adjacent vertices). If no edges are * touching the specified vertex returns an empty set. * * @param vertex the vertex for which a set of touching edges is to be * returned. * * @return a set of all edges touching the specified vertex. * * @throws IllegalArgumentException if vertex is not found in the graph. * @throws NullPointerException if vertex is null. */ public Set edgesOf(V vertex); /** * Removes an edge going from source vertex to target vertex, if such * vertices and such edge exist in this graph. * * If weight >- 1 it must be checked * If description != null, it must be checked * * Returns the edge if removed * or null otherwise. * * @param sourceVertex source vertex of the edge. * @param destinationVertex target vertex of the edge. * @param weight weight of the edge * @param description description of the edge * * @return The removed edge, or null if no edge removed. */ public E removeEdge(V sourceVertex, V destinationVertex, int weight, String description); /** * Removes the specified vertex from this graph including all its touching * edges if present. More formally, if the graph contains a vertex * u such that u.equals(v), the call removes all edges * that touch u and then removes u itself. If no * such u is found, the call leaves the graph unchanged. * Returns true if the graph contained the specified vertex. (The * graph will not contain the specified vertex once the call returns). * * If the specified vertex is null returns false. * * @param v vertex to be removed from this graph, if present. * * @return true if the graph contained the specified vertex; * false otherwise. */ public boolean removeVertex(V v); /** * Returns a set of the vertices contained in this graph. The set is backed * by the graph, so changes to the graph are reflected in the set. If the * graph is modified while an iteration over the set is in progress, the * results of the iteration are undefined. * * * @return a set view of the vertices contained in this graph. */ public Set vertexSet(); /** * Find the shortest path from the sourceVertex to the destinationVertex * call the dijkstraShortestPath with the sourceVertex * @param sourceVertex starting vertex * @param destinationVertex ending vertex * @return An arraylist of Strings that describe the path from sourceVertex * to destinationVertex */ public ArrayList shortestPath(V sourceVertex, V destinationVertex); /** * Dijkstra's Shortest Path Method. Internal structures are built which * hold the ability to retrieve the path, shortest distance from the * sourceVertex to all the other vertices in the graph, etc. * @param sourceVertex the vertex to find shortest path from * */ public void dijkstraShortestPath(V sourceVertex); }

#GraphTest

import static org.junit.Assert.*; import org.junit.Test; import static org.junit.Assert.*; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.Iterator; import java.util.Set; import org.junit.After; import org.junit.Before; import org.junit.Test; public class GraphTest { private GraphInterface graph; private Town[] town; @Before public void setUp() throws Exception { graph = new Graph(); town = new Town[12]; for (int i = 1; i < 12; i++) { town[i] = new Town("Town_" + i); graph.addVertex(town[i]); } graph.addEdge(town[1], town[2], 2, "Road_1"); graph.addEdge(town[1], town[3], 4, "Road_2"); graph.addEdge(town[1], town[5], 6, "Road_3"); graph.addEdge(town[3], town[7], 1, "Road_4"); graph.addEdge(town[3], town[8], 2, "Road_5"); graph.addEdge(town[4], town[8], 3, "Road_6"); graph.addEdge(town[6], town[9], 3, "Road_7"); graph.addEdge(town[9], town[10], 4, "Road_8"); graph.addEdge(town[8], town[10], 2, "Road_9"); graph.addEdge(town[5], town[10], 5, "Road_10"); graph.addEdge(town[10], town[11], 3, "Road_11"); graph.addEdge(town[2], town[11], 6, "Road_12"); } @After public void tearDown() throws Exception { graph = null; } @Test public void testGetEdge() { assertEquals(new Road(town[2], town[11],6, "Road_12"), graph.getEdge(town[2], town[11])); assertEquals(new Road(town[3], town[7],1, "Road_4"), graph.getEdge(town[3], town[7])); } @Test public void testAddEdge() { assertEquals(false, graph.containsEdge(town[3], town[5])); graph.addEdge(town[3], town[5], 1, "Road_13"); assertEquals(true, graph.containsEdge(town[3], town[5])); } @Test public void testAddVertex() { Town newTown = new Town("Town_12"); assertEquals(false, graph.containsVertex(newTown)); graph.addVertex(newTown); assertEquals(true, graph.containsVertex(newTown)); } @Test public void testContainsEdge() { assertEquals(true, graph.containsEdge(town[2], town[11])); assertEquals(false, graph.containsEdge(town[3], town[5])); } @Test public void testContainsVertex() { assertEquals(true, graph.containsVertex(new Town("Town_2"))); assertEquals(false, graph.containsVertex(new Town("Town_12"))); } @Test public void testEdgeSet() { Set roads = graph.edgeSet(); ArrayList roadArrayList = new ArrayList(); for(Road road : roads) roadArrayList.add(road.getName()); Collections.sort(roadArrayList); assertEquals("Road_1", roadArrayList.get(0)); assertEquals("Road_10", roadArrayList.get(1)); assertEquals("Road_11", roadArrayList.get(2)); assertEquals("Road_12", roadArrayList.get(3)); assertEquals("Road_2", roadArrayList.get(4)); assertEquals("Road_8", roadArrayList.get(10)); } @Test public void testEdgesOf() { Set roads = graph.edgesOf(town[1]); ArrayList roadArrayList = new ArrayList(); for(Road road : roads) roadArrayList.add(road.getName()); Collections.sort(roadArrayList); assertEquals("Road_1", roadArrayList.get(0)); assertEquals("Road_2", roadArrayList.get(1)); assertEquals("Road_3", roadArrayList.get(2)); } @Test public void testEdgesOfSTUDENT() { fail("Test not implemented yet"); } @Test public void testRemoveEdge() { assertEquals(true, graph.containsEdge(town[2], town[11])); graph.removeEdge(town[2], town[11], 6, "Road_12"); assertEquals(false, graph.containsEdge(town[2], town[11])); } @Test public void testRemoveEdgeSTUDENT() { fail("Test not implemented yet"); } @Test public void testRemoveVertex() { assertEquals(true, graph.containsVertex(town[2])); graph.removeVertex(town[2]); assertEquals(false, graph.containsVertex(town[2])); } @Test public void testVertexSet() { Set roads = graph.vertexSet(); assertEquals(true,roads.contains(town[1])); assertEquals(true, roads.contains(town[10])); assertEquals(true, roads.contains(town[11])); assertEquals(true, roads.contains(town[2])); assertEquals(true, roads.contains(town[3])); } @Test public void testTown_1ToTown_11() { String beginTown = "Town_1", endTown = "Town_11"; Town beginIndex=null, endIndex=null; Set towns = graph.vertexSet(); Iterator iterator = towns.iterator(); while(iterator.hasNext()) { Town town = iterator.next(); if(town.getName().equals(beginTown)) beginIndex = town; if(town.getName().equals(endTown)) endIndex = town; } if(beginIndex != null && endIndex != null) { ArrayList path = graph.shortestPath(beginIndex,endIndex); assertNotNull(path); assertTrue(path.size() > 0); assertEquals("Town_1 via Road_1 to Town_2 2 mi",path.get(0).trim()); assertEquals("Town_2 via Road_12 to Town_11 6 mi",path.get(1).trim()); } else fail("Town names are not valid"); } @Test public void testTown1ToTown_10() { String beginTown = "Town_1", endTown = "Town_10"; Town beginIndex=null, endIndex=null; Set towns = graph.vertexSet(); Iterator iterator = towns.iterator(); while(iterator.hasNext()) { Town town = iterator.next(); if(town.getName().equals(beginTown)) beginIndex = town; if(town.getName().equals(endTown)) endIndex = town; } if(beginIndex != null && endIndex != null) { ArrayList path = graph.shortestPath(beginIndex,endIndex); assertNotNull(path); assertTrue(path.size() > 0); assertEquals("Town_1 via Road_2 to Town_3 4 mi",path.get(0).trim()); assertEquals("Town_3 via Road_5 to Town_8 2 mi",path.get(1).trim()); assertEquals("Town_8 via Road_9 to Town_10 2 mi",path.get(2).trim()); } else fail("Town names are not valid"); } @Test public void testTown_4ToTown_11() { String beginTown = "Town_4", endTown = "Town_11"; Town beginIndex=null, endIndex=null; Set towns = graph.vertexSet(); Iterator iterator = towns.iterator(); while(iterator.hasNext()) { Town town = iterator.next(); if(town.getName().equals(beginTown)) beginIndex = town; if(town.getName().equals(endTown)) endIndex = town; } if(beginIndex != null && endIndex != null) { ArrayList path = graph.shortestPath(beginIndex,endIndex); assertNotNull(path); assertTrue(path.size() > 0); assertEquals("Town_4 via Road_6 to Town_8 3 mi",path.get(0).trim()); assertEquals("Town_8 via Road_9 to Town_10 2 mi",path.get(1).trim()); assertEquals("Town_10 via Road_11 to Town_11 3 mi",path.get(2).trim()); } else fail("Town names are not valid"); } @Test public void testTown_5ToTown_2STUDENT() { fail("Test not implemented yet"); } }

#TownGraphManagerTest

import static org.junit.Assert.*; import org.junit.Test; import static org.junit.Assert.*; import java.util.ArrayList; import org.junit.After; import org.junit.Before; import org.junit.Test; public class TownGraphManagerTest { private TownGraphManagerInterface graph; private String[] town; @Before public void setUp() throws Exception { graph = new TownGraphManager(); town = new String[12]; for (int i = 1; i < 12; i++) { town[i] = "Town_" + i; graph.addTown(town[i]); } graph.addRoad(town[1], town[2], 2, "Road_1"); graph.addRoad(town[1], town[3], 4, "Road_2"); graph.addRoad(town[1], town[5], 6, "Road_3"); graph.addRoad(town[3], town[7], 1, "Road_4"); graph.addRoad(town[3], town[8], 2, "Road_5"); graph.addRoad(town[4], town[8], 3, "Road_6"); graph.addRoad(town[6], town[9], 3, "Road_7"); graph.addRoad(town[9], town[10], 4, "Road_8"); graph.addRoad(town[8], town[10], 2, "Road_9"); graph.addRoad(town[5], town[10], 5, "Road_10"); graph.addRoad(town[10], town[11], 3, "Road_11"); graph.addRoad(town[2], town[11], 6, "Road_12"); } @After public void tearDown() throws Exception { graph = null; } @Test public void testAddRoad() { ArrayList roads = graph.allRoads(); assertEquals("Road_1", roads.get(0)); assertEquals("Road_10", roads.get(1)); assertEquals("Road_11", roads.get(2)); assertEquals("Road_12", roads.get(3)); graph.addRoad(town[4], town[11], 1,"Road_13"); roads = graph.allRoads(); assertEquals("Road_1", roads.get(0)); assertEquals("Road_10", roads.get(1)); assertEquals("Road_11", roads.get(2)); assertEquals("Road_12", roads.get(3)); assertEquals("Road_13", roads.get(4)); } @Test public void testGetRoad() { assertEquals("Road_12", graph.getRoad(town[2], town[11])); assertEquals("Road_4", graph.getRoad(town[3], town[7])); } @Test public void testAddTown() { assertEquals(false, graph.containsTown("Town_12")); graph.addTown("Town_12"); assertEquals(true, graph.containsTown("Town_12")); } @Test public void testDisjointGraph() { assertEquals(false, graph.containsTown("Town_12")); graph.addTown("Town_12"); ArrayList path = graph.getPath(town[1],"Town_12"); assertFalse(path.size() > 0); } @Test public void testContainsTown() { assertEquals(true, graph.containsTown("Town_2")); assertEquals(false, graph.containsTown("Town_12")); } @Test public void testContainsRoadConnection() { assertEquals(true, graph.containsRoadConnection(town[2], town[11])); assertEquals(false, graph.containsRoadConnection(town[3], town[5])); } @Test public void testAllRoads() { ArrayList roads = graph.allRoads(); assertEquals("Road_1", roads.get(0)); assertEquals("Road_10", roads.get(1)); assertEquals("Road_11", roads.get(2)); assertEquals("Road_8", roads.get(10)); assertEquals("Road_9", roads.get(11)); } @Test public void testDeleteRoadConnection() { assertEquals(true, graph.containsRoadConnection(town[2], town[11])); graph.deleteRoadConnection(town[2], town[11], "Road_12"); assertEquals(false, graph.containsRoadConnection(town[2], town[11])); } @Test public void testDeleteTown() { assertEquals(true, graph.containsTown("Town_2")); graph.deleteTown(town[2]); assertEquals(false, graph.containsTown("Town_2")); } @Test public void testDeleteTownSTUDENT() { fail("Test not yet implemented"); } @Test public void testAllTowns() { ArrayList roads = graph.allTowns(); assertEquals("Town_1", roads.get(0)); assertEquals("Town_10", roads.get(1)); assertEquals("Town_11", roads.get(2)); assertEquals("Town_2", roads.get(3)); assertEquals("Town_8", roads.get(9)); } @Test public void testGetPath() { ArrayList path = graph.getPath(town[1],town[11]); assertNotNull(path); assertTrue(path.size() > 0); assertEquals("Town_1 via Road_1 to Town_2 2 mi",path.get(0).trim()); assertEquals("Town_2 via Road_12 to Town_11 6 mi",path.get(1).trim()); } @Test public void testGetPathA() { ArrayList path = graph.getPath(town[1],town[10]); assertNotNull(path); assertTrue(path.size() > 0); assertEquals("Town_1 via Road_2 to Town_3 4 mi",path.get(0).trim()); assertEquals("Town_3 via Road_5 to Town_8 2 mi",path.get(1).trim()); assertEquals("Town_8 via Road_9 to Town_10 2 mi",path.get(2).trim()); } @Test public void testGetPathB() { ArrayList path = graph.getPath(town[1],town[6]); assertNotNull(path); assertTrue(path.size() > 0); assertEquals("Town_1 via Road_2 to Town_3 4 mi",path.get(0).trim()); assertEquals("Town_3 via Road_5 to Town_8 2 mi",path.get(1).trim()); assertEquals("Town_8 via Road_9 to Town_10 2 mi",path.get(2).trim()); assertEquals("Town_10 via Road_8 to Town_9 4 mi",path.get(3).trim()); assertEquals("Town_9 via Road_7 to Town_6 3 mi",path.get(4).trim()); } @Test public void testGetPathSTUDENT() { fail("Test not yet implemented"); } }