Test gives NullPointer Exception even though I think I should have correctly populated the Map.
I am trying to implement a Graph which is a set of vertices and the set of edges. Each vertise also has a HashMap of adjacent Vertices together with the weight of the edge.
public class TownGraphManagerTest {
private TownGraphManager 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], "Road_1");
graph.addRoad(town[1], town[3], "Road_2");
graph.addRoad(town[1], town[5], "Road_3");
graph.addRoad(town[3], town[7], "Road_4");
graph.addRoad(town[3], town[8], "Road_5");
graph.addRoad(town[4], town[8], "Road_6");
graph.addRoad(town[6], town[9], "Road_7");
graph.addRoad(town[9], town[10], "Road_8");
graph.addRoad(town[8], town[10], "Road_9");
graph.addRoad(town[5], town[10], "Road_10");
graph.addRoad(town[10], town[11], "Road_11");
graph.addRoad(town[2], town[11], "Road_12");
graph.addRoad(town[7], town[6], "Road_13");
}
@After
public void tearDown() throws Exception {
graph = null;
}
@Test
public void testGetPath() {
ArrayList<String> path = graph.getPath(town[1],town[11]);
assertNotNull(path);
assertTrue(path.size() > 0);
assertEquals("Town_2 via Road_12 to Town_11 1
mi",path.get(0).trim());
assertEquals("Town_1 via Road_1 to Town_2
1mi",path.get(1).trim());
}
}
This is the class that actually add the entry into the map in the addDestination() method.
public class Town implements Comparable<Town>{
private String name;
private Integer distance = Integer.MAX_VALUE;
private Map<Town, Integer> adjTowns;
private Set<Road> adjRoads;
private LinkedList<Town> shortestPath = new LinkedList<Town>();
/**
*
*/
public Town() {
super();
this.adjTowns=new HashMap<Town, Integer>();
}
/**
* @param string
*/
public Town(String name) {
this.name = name;
this.adjTowns=new HashMap<Town, Integer>();
}
/**
* @return the adjTowns
*/
public Map<Town, Integer> getAdjTowns() {
return adjTowns;
}
/**
* @param adjTowns the adjTowns to set
*/
public void setAdjTowns(Map<Town, Integer> adjTowns) {
this.adjTowns=new HashMap<Town, Integer>();
this.adjTowns = adjTowns;
}
public void addDestination(Town destination, int distance) {
this.adjTowns.put(destination, distance);
}
@Override
public String toString() {
return name;
}
@Override
public int hashCode(){
return this.name.hashCode();
}
@Override
public boolean equals(Object t){
return this.toString().hashCode()==t.toString().hashCode();
}
@Override
public int compareTo(Town o) {
return this.getName().compareToIgnoreCase(o.getName());
}
/**
* @return the shortestPath
*/
public LinkedList<Town> getShortestPath() {
return shortestPath;
}
/**
* @param shortestPath the shortestPath to set
*/
public void setShortestPath(LinkedList<Town> shortestPath) {
this.shortestPath = shortestPath;
}
}
I also implemented a Graph class which passes similar tests
public class Graph<V, E> implements GraphInterface<Town, Road>{
private HashSet<Town> vert;
private HashSet<Road> edges;
Graph(){
vert=new HashSet<Town>();
edges=new HashSet<Road>();
}
/* (non-Javadoc)
* @see GraphInterface#getEdge(java.lang.Object, java.lang.Object)
*/
@Override
public Road getEdge(Town sourceVertex, Town destinationVertex) {
for(Road r: edges){
if(((r.getVert1().compareTo(sourceVertex)==0)
&&(r.getVert2().compareTo(destinationVertex)==0))
||((r.getVert2().compareTo(sourceVertex)==0)
&&(r.getVert1().compareTo(destinationVertex)==0)))
return r;
}
return null;
}
/* (non-Javadoc)
* @see GraphInterface#addEdge(java.lang.Object, java.lang.Object, int, java.lang.String)
*/
@Override
public Road addEdge(Town sourceVertex, Town destinationVertex, int weight, String description) {
Road temp=new Road (sourceVertex, destinationVertex, weight, description);
edges.add(temp);
sourceVertex.addDestination(destinationVertex, weight);
destinationVertex.addDestination(sourceVertex, weight);
return temp;
}
/* (non-Javadoc)
* @see GraphInterface#addVertex(java.lang.Object)
*/
@Override
public boolean addVertex(Town v) {
return vert.add(v);
}
/* (non-Javadoc)
* @see GraphInterface#containsEdge(java.lang.Object, java.lang.Object)
*/
@Override
public boolean containsEdge(Town sourceVertex, Town destinationVertex) {
for(Road r: edges){
if(r.contains(sourceVertex)&&r.contains(destinationVertex))
return true;
}
return false;
}
/* (non-Javadoc)
* @see GraphInterface#edgesOf(java.lang.Object)
*/
@Override
public Set<Road> edgesOf(Town vertex) {
Set<Road> res=new HashSet<Road>();
for(Road t: this.edges){
if(t.contains(vertex))
res.add(t);
}
return res;
}
/* (non-Javadoc)
* @see GraphInterface#removeEdge(java.lang.Object, java.lang.Object, int, java.lang.String)
*/
@Override
public Road removeEdge(Town sourceVertex, Town destinationVertex, int weight, String description) {
Road temp=new Road (sourceVertex, destinationVertex, weight, description);
edges.remove(temp);
return new Road (sourceVertex, destinationVertex, weight, description);
}
/* (non-Javadoc)
* @see GraphInterface#removeVertex(java.lang.Object)
*/
@Override
public boolean removeVertex(Town v) {
return vert.remove(v);
}
/* (non-Javadoc)
* @see GraphInterface#shortestPath(java.lang.Object, java.lang.Object)
*/
@Override
public ArrayList<String> shortestPath(Town sourceVertex, Town destinationVertex) {
for(Road r:this.edgeSet())
{
this.addEdge(r.getVert1(), r.getVert2(), r.getDistance(), r.getName());
r.getVert1().addDestination(r.getVert2(), r.getDistance());
r.getVert2().addDestination(r.getVert1(), r.getDistance());
}
dijkstraShortestPath(sourceVertex) ;
ArrayList<String> shortestPath=new ArrayList<String>();
LinkedList<Town> shortestPath1=destinationVertex.getShortestPath();
for(int i=0;i<shortestPath1.size()-1;i++){
shortestPath.add(shortestPath1.get(i).toString()+" via "
+ ""+this.getEdge(shortestPath1.get(i), shortestPath1.get(i+1))+" to "
+ shortestPath1.get(i+1).getName()
+" " + this.getEdge(shortestPath1.get(i), shortestPath1.get(i+1)).getDistance()
+" mi");
}
shortestPath.add(shortestPath1.getLast().toString()+" via "
+ ""+this.getEdge(shortestPath1.getLast(), destinationVertex)+" to "
+ destinationVertex.getName()
+" " + this.getEdge(shortestPath1.getLast(), destinationVertex).getDistance()
+" mi");
Collections.reverse(shortestPath);
for(Town a:destinationVertex.getShortestPath()){
System.out.print(a.getName()+ " ");
}
System.out.println("\n");
return shortestPath;
}
/* (non-Javadoc)
* @see GraphInterface#dijkstraShortestPath(java.lang.Object)
*/
@Override
public void dijkstraShortestPath(Town startVertex) {
startVertex.setDistance(0);
Set<Town> settledNodes = new HashSet<>();
Set<Town> unsettledNodes = this.vert;
unsettledNodes.add(startVertex);
while (unsettledNodes.size() != 0) {
Town currentNode = getLowestDistanceNode(unsettledNodes);
unsettledNodes.remove(currentNode);
for (Entry < Town, Integer> adjacencyPair : currentNode.getAdjTowns().entrySet()) {
Town adjacentNode = adjacencyPair.getKey();
Integer edgeWeight = adjacencyPair.getValue();
if (!settledNodes.contains(adjacentNode)) {
CalculateMinimumDistance(adjacentNode, edgeWeight, currentNode);
unsettledNodes.add(adjacentNode);
}
}
settledNodes.add(currentNode);
}
}
private static Town getLowestDistanceNode(Set < Town > unsettledNodes) {
Town lowestDistanceNode = null;
int lowestDistance = Integer.MAX_VALUE;
for (Town node: unsettledNodes) {
int nodeDistance = node.getDistance();
if (nodeDistance < lowestDistance) {
lowestDistance = nodeDistance;
lowestDistanceNode = node;
}
}
return lowestDistanceNode;
}
private static void CalculateMinimumDistance(Town evaluationNode,Integer
edgeWeigh, Town sourceNode) {
Integer sourceDistance = sourceNode.getDistance();
if (sourceDistance + edgeWeigh < evaluationNode.getDistance()) {
evaluationNode.setDistance(sourceDistance + edgeWeigh);
LinkedList<Town> shortestPath = new LinkedList<>
(sourceNode.getShortestPath());
shortestPath.add(sourceNode);
evaluationNode.setShortestPath(shortestPath);
}
}
}
