I asked about this same project recently but every time I fix an error another one pops up. The problem is mostly with NullPointerExceptions when referencing the adjacentVertices Hashtable. Currently I'm having an issue with the for each loop in breadthFirstSearch(), it says "Vertex.getAdjacentVertices(vertex)" has a NullPointerException, so it wasn't initialized properly somewhere but I can't figure out what the null object is or how to re-initialize it for that loop. I have attached the entire code below.
import java.util.Map;
import java.util.Hashtable;
import java.util.LinkedList;
import java.util.Queue;
import java.util.ArrayList;
import java.util.Scanner;
class Vertex //Creates a class that will be used to add vertices to the graph, a separate class is needed because the Vertex is not a recognized Java object
{
int label; //The label for the vertex, which the vertex will be called
Vertex(int label) //Constructor, uses an int to create a Vertex
{
this.label = label; //Initializes the label for use outside the method
}
public String toString() //Overwrites Java's toString method to print the int value of the Vertex and not an object code
{
return "" + this.label + "";
}
public static LinkedList<Vertex> getAdjacentVertices(int label) //A method for getting adjacent vertices, which will be used in Graph class
{
return Graph.adjacentVertices.get(new Vertex(label)); //Obtains the vertex adjacent to the current vertex
}
}
public class Graph //A new class is needed for Graph because it is an object
{
static Hashtable<Vertex, LinkedList<Vertex>> adjacentVertices = new Hashtable(); //Creates a graph with a vertex and a list of adjacent vertices, using a Hashtable
static LinkedList<Vertex> visitedNodes = new LinkedList<Vertex>(); //Creates a list of visited nodes, currently empty, to be used by BFS
public static void addVertex(int label) //Method for creating a vertex
{
Vertex vertex = new Vertex(label); //Creates a new Vertex using the int in the parameter
LinkedList<Vertex> list = new LinkedList<Vertex>(); //Creates an empty list that will hold vertices connected to that vertex by an edge
adjacentVertices.put(vertex, list); //Adds the new Vertex and accompanying list to the Graph
}
public static void addEdge(int startVertex, int endVertex) //Method to create an edge using a start and end vertex
{
Vertex start = new Vertex(startVertex); //Creates a new vertex from the first parameter
Vertex end = new Vertex(endVertex); //Creates a new vertex from the second parameter
LinkedList<Vertex> list = adjacentVertices.get(start); //This line makes a list to be used in the rest of this method, that will reference the original list
if(list == null) //If the list for the first vertex is empty or nonexistent, this will create a new list to add edges
{
list = new LinkedList<Vertex>();
adjacentVertices.put(start, list);
}
LinkedList<Vertex> list2 = adjacentVertices.get(end); //This does the same thing for the end vertex
if(list2 == null)
{
list2 = new LinkedList<Vertex>();
adjacentVertices.put(end, list2);
}
adjacentVertices.get(start).addFirst(end); //Puts the second vertex into the first vertex's list of adjacent vertices
adjacentVertices.get(end).addFirst(start); //If vertex A is adjacent to vertex B, then vertex B is adjacent to vertex A
}
public static void breadthFirstSearch(Graph G, int root) //Initializes a search of the graph using the graph and a vertex to start from (default: 0)
{
Vertex rootVertex = new Vertex(root); //Creates a reference to the original root vertex to be used to make a "cloud of vertices"
Queue<Vertex> queue = new LinkedList<Vertex>(); //Makes a Queue that will hold the visited vertices
queue.add(rootVertex); //Adds the root vertex to the Queue
visitedNodes.add(rootVertex); //Adds the root vertex to the list of visited vertices since it has been visited
while(!queue.isEmpty()) //This loop will be executed until the Queue is empty
{
Vertex refVertex = queue.poll();
String listHead = "" + refVertex + ""; //Obtains the first vertex in the queue and converts it to a String
Scanner scan = new Scanner(listHead); //This is so the String can be converted to an int with Scanner's nextInt() and be made into a Vertex for referencing
int vertex = scan.nextInt(); //This needs to be an int because getAdjacentVertices() uses an int parameter
for(Vertex v : Vertex.getAdjacentVertices(vertex)) //"For every vertex in the current vertex's list of adjacent vertices" this loop will execute
{
if(!visitedNodes.contains(v)) //If the vertex is not in the list of visited nodes, now it is!
{
visitedNodes.add(v);
queue.add(v);
}
}
}
String BFSorder = ""; //Initializes an empty String that will hold the list of visited vertices in the order in which they were visited
for(int i = 0; i < visitedNodes.size(); i++) //Iterates through the list of visitedNodes
{
String currNode = "" + visitedNodes.get(i) + " "; //Transforms the current vertex into a String so it can be added to BFSorder
BFSorder = BFSorder + currNode; //Adds the String representing the current Node to BFSorder
}
System.out.println("Graph nodes visited in BFS Order: " + BFSorder + ""); //Prints out the list of visited vertices
}
public static void print(Graph G) //This method prints out an Adjacency List Matrix using the parameter Graph
{
for(int i = 0; i < visitedNodes.size(); i++) //Iterates through the list of visited nodes
{
String adjVertex = "Adjacency list for vertex " + visitedNodes.get(i) + " Head "; //For each node, a new String is made
String currVertex = "" + visitedNodes.get(i) + ""; //These next three lines convert the vertex to an integer so it can be used for the for loop
Scanner scan = new Scanner(currVertex);
int vertex = scan.nextInt();
for(Vertex v : Vertex.getAdjacentVertices(vertex)) //Goes through the list of vertices adjacent to the current Vertex
{
String currNode = " -> " + v + ""; //Makes the vertex into a String with special formatting
adjVertex = adjVertex + currNode; //Adds the new string to adjVertex
}
System.out.println(adjVertex); //Prints out the list of adjacent vertices for the current vertex
}
}
}
Sorry for asking tons of questions, and thanks for your time.
UPDATE: The full error is
Exception in thread "main" java.lang.NullPointerException
at Graph.breadthFirstSearch(Graph.java:69)
at GraphProject.main(GraphProject.java:16)
Line 69 is "for(Vertex v : Vertex.getAdjacentVertices(vertex))" Graph is the class that is posted above. GraphProject is the name of the class with the main method, that specific line calling breadthFirstSearch.