TownGraphManager Interface.java

import java.util.*;

public interface TownGraphManagerInterface {

/**

* Adds a road with 2 towns and a road name

* @param town1 name of town 1 (lastname, firstname)

* @param town2 name of town 2 (lastname, firstname)

* @param roadName name of road

* @return true if the road was added successfully

*/

public boolean addRoad(String town1, String town2, int weight, String roadName);

/**

* Returns the name of the road that both towns are connected through

* @param town1 name of town 1 (lastname, firstname)

* @param town2 name of town 2 (lastname, firstname)

* @return name of road if town 1 and town2 are in the same road, returns null if not

*/

public String getRoad(String town1, String town2);

/**

* Adds a town to the graph

* @param v the town's name (lastname, firstname)

* @return true if the town was successfully added, false if not

*/

public boolean addTown(String v);

/**

* Determines if a town is already in the graph

* @param v the town's name (lastname, firstname)

* @return true if the town is in the graph, false if not

*/

public boolean containsTown(String v);

/**

* Determines if a road is in the graph

* @param town1 name of town 1 (lastname, firstname)

* @param town2 name of town 2 (lastname, firstname)

* @return true if the road is in the graph, false if not

*/

public boolean containsRoadConnection(String town1, String town2);

/**

* Creates an arraylist of all road titles in sorted order by road name

* @return an arraylist of all road titles in sorted order by road name

*/

public ArrayList allRoads();

/**

* Deletes a road from the graph

* @param town1 name of town 1 (lastname, firstname)

* @param town2 name of town 2 (lastname, firstname)

* @param roadName the road name

* @return true if the road was successfully deleted, false if not

*/

public boolean deleteRoadConnection(String town1, String town2, String road);

/**

* Deletes a town from the graph

* @param v name of town (lastname, firstname)

* @return true if the town was successfully deleted, false if not

*/

public boolean deleteTown(String v);

/**

* Creates an arraylist of all towns in alphabetical order (last name, first name)

* @return an arraylist of all towns in alphabetical order (last name, first name)

*/

public ArrayList allTowns();

/**

* Returns the shortest path from town 1 to town 2

* @param town1 name of town 1 (lastname, firstname)

* @param town2 name of town 2 (lastname, firstname)

* @return an Arraylist of roads connecting the two towns together, null if the

* towns have no path to connect them.

*/

public ArrayList getPath(String town1, String town2);

}

GarphInterface.java

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);

}

Graph.java

import java.util.ArrayList;

import java.util.Collections;

import java.util.HashMap;

import java.util.HashSet;

import java.util.Iterator;

import java.util.LinkedList;

import java.util.List;

import java.util.Map;

import java.util.Map.Entry;

import java.util.Set;

import java.util.TreeSet;

public class Graph implements GraphInterface{

private Set towns;

private Map> connections;

private Map paths;

/*private List vertices;//Store vertices

private Map adjacencyList ; // [vertices] -> [edge]

private List edges;//store edges

//private List > list;//adjacency list

//creates an empty graph

*/

/**

* non-arg Constructor.

*/

public Graph(){

towns = new TreeSet();

connections = new HashMap>();

}

/**

* 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.

*/

@Override

public Road getEdge(Town sourceVertex, Town destinationVertex) {

Iterator edges = connections.get(sourceVertex).iterator();

Road destination;

while (edges.hasNext()) {

destination = edges.next();

if(destination.getDestination().compareTo(destinationVertex) == 0)

return destination;

}

return null;

}

/**

* Tests the given vertices for null and for membership in the graph.

*

* @param v1 First vertex to examine.

* @param v2 Second vertex to examine.

* @throws IllegalArgumentException If any vertex is not part of this graph.

* @throws NullPointerException If any vertex is null.

*/

protected void checkVertices(Town v1, Town v2) {

if (!this.containsVertex(v1)) {

throw new IllegalArgumentException();

}

if (!this.containsVertex(v2)) {

throw new IllegalArgumentException();

}

}

/**

* 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 IllegalArgumentException if source or target vertices are not

* found in the graph.

* @throws NullPointerException if any of the specified vertices is null.

*/

@Override

public Road addEdge(Town sourceVertex, Town destinationVertex, int weight, String description) {

if (sourceVertex==null || destinationVertex==null)

throw new NullPointerException();

else if (!containsVertex(sourceVertex) || !containsVertex(destinationVertex))

throw new IllegalArgumentException();

else if(getEdge(sourceVertex, destinationVertex)==null&&getEdge(destinationVertex, sourceVertex)==null){

Road connection1= new Road(sourceVertex, destinationVertex, 1, description);

Road connection2= new Road(destinationVertex, sourceVertex, 1, description);

connections.get(sourceVertex).add(connection1);

connections.get(destinationVertex).add(connection2);

return connection1;

}

return null;

}

/**

* 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.

*/

@Override

public boolean addVertex(Town v) {

if(v==null) throw new NullPointerException();

if (!containsVertex(v)){

towns.add(v);

return true;

}

else return false;

}

@Override

public boolean containsEdge(Town sourceVertex, Town destinationVertex) {

/**

* 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.

*/

Iterator e = connections.get(sourceVertex).iterator();

while(e.hasNext()) {

if(e.next().getDestination().compareTo(destinationVertex) == 0)

return false;

}

return true;

}

/**

* 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.

*/

@Override

public boolean containsVertex(Town v) {

for (Town a: towns){

if (a.compareTo(v) == 0)

return true;

}

return false;

}

@Override

public Set edgeSet() {

return (Set) connections;

}

/**

* 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.

*/

@Override

public Set edgesOf(Town vertex) {

Set edges= new TreeSet();

if (vertex==null) throw new NullPointerException();

else if(!containsVertex(vertex)) throw new IllegalArgumentException();

else{

if(((Road) connections).getSource().compareTo(vertex)==0||((Road) connections).getDestination().compareTo(vertex)==0){

edges.add((Road) connections);

}

}

return edges;

}

@Override

public Road removeEdge(Town sourceVertex, Town destinationVertex, int weight, String description) {

if(containsEdge(sourceVertex, destinationVertex)== true){

connections.remove(getEdge(sourceVertex, destinationVertex));

return getEdge(sourceVertex, destinationVertex);

}

else {

return null;

}

}

@Override

public boolean removeVertex(Town v) {

try{

towns.remove(v);

}

catch(NullPointerException e){

return false;

}

return true;

}

/**

* 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.

*/

@Override

public Set vertexSet() {

Set returnSet = new HashSet();

for(Town a : towns)

returnSet.add(a);

return returnSet;

}

@Override

public ArrayList shortestPath(Town sourceVertex, Town destinationVertex) {

ArrayList asPath = new ArrayList(); // holds the output

Road edge; // holds iterations of LinkedList stored in Path object

paths = new HashMap(this.towns.size()); // Map of Actors to Path Objects

for(Town a : towns)

paths.put(a, new Path());

paths.put(sourceVertex, new Path());

// set path length to self to zero. This is

// the base path all other paths start from in

// dijkstra's.

paths.get(sourceVertex).pathStart();

dijkstraShortestPath(sourceVertex); // invoke dijkstra's algorithm on sourceVertex

if(paths.get(destinationVertex).getPathLength() != Integer.MAX_VALUE) {

Iterator iEdge = (Iterator) paths.get(destinationVertex); // iterate minPath linked to destinationVertex

// generate ArrayList output

while(iEdge.hasNext()){

edge = iEdge.next();

asPath.add(edge.getSource().toString() + " via " + edge.getName() + " to " + edge.getDestination().toString());

}

// return output

return asPath;

}

else

return null;

}

/**

* 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

*

*/

@Override

public void dijkstraShortestPath(Town sourceVertex) {

// Path newPath;

// One inefficiency of recursion is that I will check going back the direction I just came from, adding one iteration of the for

// loop per recursion. Rewriting with sets of resolved vertices and unresolved vertices would eliminate that.

for(Road e: edgesOf(sourceVertex)) {

// add edge e to the path arriving at e.getDestination in new minimum Path candidate

Path newPath = new Path(e, paths.get(e.getSource()));

// if the new path is shorter than the one currently in the map

// replace with new path. If it is not a shorter path, do not replace

// and we also cease recursion down this path.

if ( newPath.getPathLength() < paths.get(e.getDestination()).getPathLength() ) {

paths.put(e.getDestination(), newPath); // map new path to that actor

if(edgesOf(e.getDestination()).size() > 1) // only recurse at this point if degree of the destination node > 1

dijkstraShortestPath(e.getDestination()); // recursive call on the destination of e

}

}

}

public Town getVertex(String town1) {

for ( Town act : towns ){

if(((String) act.getName()).compareTo(town1) == 0)

return act;

}

return null;

}

}

GraphTest.java

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");

}

}

Town Graph Manager.java

import java.util.ArrayList;

import java.util.Collections;

import java.util.Set;

public class TownGraphManager implements TownGraphManagerInterface{

private Graph actorGraph;

/**

* Constructor

*/

public TownGraphManager(){

actorGraph = new Graph();

ArrayList towns;

}

/**

* Adds a movie with 2 actors and a movie name

* @param town1 name of actor 1 (lastname, firstname)

* @param town2 name of actor 2 (lastname, firstname)

* @param roadName name of movie

* @return true if the movie was added successfully

*/

//@Override

public boolean addRoad(String town1, String town2, String roadName)

{

Town sourceVertex = actorGraph.getVertex(town1);

Town destinationVertex = actorGraph.getVertex(town2);

if(actorGraph.containsVertex(actorGraph.getVertex(town1))

&& actorGraph.containsVertex(actorGraph.getVertex(town2))

&& !actorGraph.containsEdge(actorGraph.getVertex(town1), actorGraph.getVertex(town2))) {

actorGraph.addEdge(sourceVertex, destinationVertex, 1, roadName);

return true;

} else

return false;

}

/**

* Returns the name of the movie that both actors are connected through

* @param town1 name of actor 1 (lastname, firstname)

* @param town2 name of actor 2 (lastname, firstname)

* @return name of movie if actor 1 and town2 are in the same movie, returns null if not

*/

public String getRoad(String town1, String town2) {

return actorGraph.getEdge(actorGraph.getVertex(town1),

actorGraph.getVertex(town2)).getName();

}

/**

* Adds an actor to the graph

* @param v the actor's name (lastname, firstname)

* @return true if the actor was successfully added, false if not

*/

public boolean addTown(String v) {

return actorGraph.addVertex(new Town(v));

}

/**

* Determines if a movie is in the graph

* @param town1 name of actor 1 (lastname, firstname)

* @param town2 name of actor 2 (lastname, firstname)

* @return true if the movie is in the graph, false if not

*/

/**

* Creates an arraylist of all movie titles in sorted order

* @return an arraylist of all movie titles in sorted order

*/

/**

* Deletes a movie from the graph

* @param town1 name of actor 1 (lastname, firstname)

* @param town2 name of actor 2 (lastname, firstname)

* @param roadName the movie name

* @return true if the movie was successfully deleted, false if not

*/

//@Override

public boolean deleteRoadConnection(String town1, String town2, String roadName) {

if(actorGraph.removeEdge(new Town(town1), new Town(town2), 1, roadName)!=null)

{ return true;

}else

return false;

}

/**

* Deletes an actor from the graph

* @param v name of actor (lastname, firstname)

* @return true if the actor was successfully deleted, false if not

*/

//@Override

public boolean deleteTown(String v) {

if (actorGraph.removeVertex(actorGraph.getVertex(v))){

return true;

}else

return false;

}

/**

* Creates an arraylist of all actors in alphabetical order (last name, first name)

* @return an arraylist of all actors in alphabetical order (last name, first name)

*/

//@Override

public ArrayList allTowns() {

ArrayList output = new ArrayList();

Set vertices = actorGraph.vertexSet();

for(Town a: vertices)

output.add((String) a.getName());

Collections.sort(output);

return output;

}

/**

* Returns the shortest path from actor 1 to actor

* @param town1 name of actor 1 (lastname, firstname)

* @param town2 name of actor 2 (lastname, firstname)

* @return an Arraylist of Movies connecting the two actors together, null if the

* actors have no path to connect them.

*/

//@Override

public ArrayList getPath(String town1, String town2) {

return actorGraph.shortestPath(actorGraph.getVertex(town1), actorGraph.getVertex(town2));

}

@Override

public boolean addRoad(String town1, String town2, int weight, String roadName) {

Town sourceVertex = actorGraph.getVertex(town1);

Town destinationVertex = actorGraph.getVertex(town2);

if(actorGraph.containsVertex(actorGraph.getVertex(town1))

&& actorGraph.containsVertex(actorGraph.getVertex(town2))

&& !actorGraph.containsEdge(actorGraph.getVertex(town1), actorGraph.getVertex(town2))) {

actorGraph.addEdge(sourceVertex, destinationVertex, 1, roadName);

return true;

} else

return false;

}

/*@Override

public boolean containsTown(String v) {

if(actorGraph.getVertex(v)==null)

return true;

else

return false;// TODO Auto-generated method stub

}*/

@Override

public boolean containsRoadConnection(String town1, String town2) {

return actorGraph.containsEdge(new Town(town1), new Town(town2));

}

@Override

public ArrayList allRoads() {

ArrayList array = new ArrayList();

Set edges = actorGraph.edgeSet();

for(Road e: edges)

array.add(e.getName());

Collections.sort(array);

return array;

}

}

TownGraphManagerTest.java

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");

}

}

Path.java

import java.util.Iterator;

import java.util.LinkedList;

import java.util.Set;

public class Path {

private int pathLength;

private LinkedList path;

/**

* The default constructor. pathLength is set to max value for Integer

*/

public Path() {

this.path = new LinkedList();

pathLength = Integer.MAX_VALUE;

}

/**

* The parameterized constructor takes the next

* edge to be traversed, and the Path leading to

* where we are considered to be in the graph.

*

* @param e the nextEdge the next MovieEdge to travel.

* @param path the Path we have taken so far.

*/

public Path(Road e, Path path) {

Road edge = null;

this.pathLength = 0;

this.path = new LinkedList();

Iterator edges = path.getPath().iterator();

while(edges.hasNext()) { // iterate the MovieEdges in inPath's path attribute

edge = edges.next(); // save iteration for use with multiple commands

this.path.add(edge); // add iteration to path

this.pathLength += edge.getWeight(); // add weight to the pathLength

}

this.path.add(edge); // adds the new edge to the path

this.pathLength += edge.getWeight(); // adds weight of the edge to the pathLength attribute

}

/**

* The getPath method returns the LinkedList of MovieEdges in the Path.

* @return LinkedList of the MovieEdge objects we have traveled through.

*/

public LinkedList getPath() {

return this.path;

}

/**

* The getPathLength method gets the length of the path

* @return the amount stored in pathLength object.

*

*/

public int getPathLength() {

return this.pathLength;

}

/**

* The pathStart method alters a path object to represent no movement, and length of 0.

* This will only be used on one object hopefully in my implementation of Dijkstra's.

*/

public void pathStart() {

this.pathLength = 0;

}

}

Road(edge).java

public class Road implements Comparable{

private Town source;

private int weight;

private Town destination;

private String roadName;

/**

* Constructor for MovieEdge

*

* @param source - Actor object - one end of edge

* @param destination - Actor object - other end of edge

* @param weight -use 1 for all MovieEdge objects

* @param movieName - name of movie that connects these two Actors

*/

public Road(Town source, Town destination, int weight,String roadName)

{

this.source = source;

this.destination = destination;

this.weight = weight;

this.roadName = roadName;

}

/**

* Return the first end of the edge.

* @return first end of edge

*/

public Town getSource(){

return source;

}

/**

* Return the second end of the edge.

* @return second end of the edge.

*/

public Town getDestination(){

return destination;

}

/**

* Return the weight of this edge. Use 1 for finding movie paths.

* @return weight of edge.

*/

public int getWeight(){

return weight;

}

/**

* Return the movie name that connects these two Actors together.

* @return the movieName

*/

public String getName(){

return roadName;

}

/**

* String representation of this class in the follow format:

* source + "to" + destination + "via" + movieName.

* @return string

*/

@Override

public String toString() {

return source+ "to"+ destination + "via" + roadName;

}

/**

* Considered an equal edge if source = source && destination =

* destination or if source = destination && destination = source

* @param o the movie edge's object

* @return s return true if the direct and undirect graph works

* successfully.

*/

public boolean equals(Road o){

boolean s = false;

if(source.equals(o.source)&& destination.equals(o.destination) ||

source.equals(o.destination) && destination.equals(o.source))

{

s =true;

return true;

}

return s;

}

/**

* Compare the weights of the edges.

* @param o -- object class to compare against

* @return 1 if o is smaller, -1 if o is larger, 0 if same.

*/

@Override

public int compareTo(Road o) {

Integer w = weight;

return w.compareTo(o.getWeight());

}

}

Town.java

import java.util.HashMap;

import java.util.LinkedList;

import java.util.List;

import java.util.Map;

import java.util.Set;

import java.util.ArrayList;

public class Town implements Comparable{

//private ArrayList towns;

private String name;

private Town templateTown;

private int wt;

//constructor

/**

* @param name

*/

public Town(String name) {

this.name=name;

String[] details = name.split(" of ");

String[] names = details[0].split(" ");

}

public Town(Town templateTown) {

this.setTemplateTown(templateTown);

}

@Override

public int hashCode() {

// TODO Auto-generated method stub

return super.hashCode();

}

@Override

public boolean equals(Object obj) {

// TODO Auto-generated method stub

if (this == obj) return true;

if (obj == null || getClass() != obj.getClass()) return false;

Town friend = (Town) obj;

if (name != null ? !name.equals(friend.name) : friend.name != null) return false;

// if (lname != null ? !lname.equals(friend.lname) : friend.lname != null) return false;

// return !(hometown != null ? !hometown.equals(friend.hometown) : friend.hometown != null);

return super.equals(obj);

}

/**

* @param name

*/

public void setName(String name) {

this.name = name;

}

/**

* @return

*/

public String getName() {

// TODO Auto-generated method stub

return name;

}

/* (non-Javadoc)

* @see java.lang.Comparable#compareTo(java.lang.Object)

*/

@Override

public int compareTo(Town o) {

// TODO Auto-generated method stub

/*if(this.name.equals(o.getName()))

{

return 0;

}

/*if(this.weight==(o.weight))

{

return 1;

}*/

/*else return -1;*/

return name.compareTo(o.getName());

}

public String toString()

{

return name;

}

public Town getTemplateTown() {

return templateTown;

}

public void setTemplateTown(Town templateTown) {

this.templateTown = templateTown;

}

public int getWt() {

return wt;

}

/**

* @param i

*/

public void setWt(int i) {

this.wt=i;

}

/*public ArrayList getTowns() {

return towns;

}

public void setTowns(ArrayList towns) {

this.towns = towns;

}

*/

}

The Junit tests are not passing for both TestManager and Graph Test

Following JUnit test is throwing null pointer exception too. Did I do something wrong?