So I have this class GraphUtility which handles all my inputs for a graph system I am creating. My issue here is that the dijkstra method is not working how I want it to work. I am sure that my file reading is working correctly because it worked for breadth-first search.
/**
* GraphUtility class
*/
public class GraphUtility {
// Class variable
private Graph graph;
/**
* Default constructor for class
*/
public GraphUtility() {
graph = null;
}
/**
* Getter for graph
* @return graph
*/
public Graph getGraph() {
return graph;
}
/**
* Setter for graph
* @param graph
*/
public void setGraph(Graph graph) {
this.graph = graph;
}
/**
* TODO: Documentation
* @param file given file path
* @throws Exception if error or exception occurs
*/
public void readFile(File file) throws Exception {
try (BufferedReader br = new BufferedReader(new FileReader(file))) {
graph = new Graph();
String line;
int y = 0;
while ((line = br.readLine()) != null) {
String[] tokens = line.split(",");
populateVertices(tokens.length);
for (int x = 0; x < tokens.length; x++) {
int weight = Integer.parseInt(tokens[x].trim());
if (weight != 0) {
Vertex sourceVertex = graph.getNodes().get(y);
Vertex destinationVertex = graph.getNodes().get(x);
graph.addEdge(sourceVertex, destinationVertex, weight);
}
}
y++;
}
} catch (Exception e) {
e.printStackTrace();
throw new Exception("Error reading the file.");
}
}
private void populateVertices(int verticesCount) {
if (graph != null) {
List<Vertex> vertices = new ArrayList<>();
String labels = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
char symbol;
for (int i = 0; i < verticesCount; i++) {
symbol = labels.charAt(i);
Vertex vertex = new Vertex(String.valueOf(symbol));
vertex.setId(i); // Assign unique ID to each vertex
vertices.add(vertex);
graph.addVertex(vertex);
}
graph.setNodes(vertices);
} else {
graph = new Graph();
}
}
public static double[] dijkstra(Graph graph, Vertex source) {
double[] distance = new double[graph.getNodes().size()];
boolean[] visited = new boolean[graph.getNodes().size()];
// Initialize distances
Arrays.fill(distance, Integer.MAX_VALUE);
distance[source.getId()] = 0;
// Use PriorityQueue to efficiently get the minimum distance vertex
PriorityQueue<VertexDistancePair> pq = new PriorityQueue<>();
pq.add(new VertexDistancePair(source, 0));
while (!pq.isEmpty()) {
VertexDistancePair currentPair = pq.poll();
Vertex currentVertex = currentPair.getVertex();
if (!visited[currentVertex.getId()]) {
visited[currentVertex.getId()] = true;
for (Edge neighbor : currentVertex.getNeighbors()) {
int neighborIndex = neighbor.getEnd().getId();
if (!visited[neighborIndex]) {
double newDist = distance[currentVertex.getId()] + neighbor.getWeight();
if (newDist < distance[neighborIndex]) {
distance[neighborIndex] = newDist;
pq.add(new VertexDistancePair(neighbor.getEnd(), (int) newDist));
}
}
}
}
}
// Add this inside your dijkstra method before the return statement
System.out.println("Debug Output:");
System.out.println("Vertex IDs: " + Arrays.toString(graph.getNodes().stream().map(Vertex::getId).toArray()));
System.out.println("Edge Weights: " + graph.getEdges().stream().map(Edge::getWeight).collect(Collectors.toList()));
System.out.println("Distances: " + Arrays.toString(distance));
return distance;
}
}
class VertexDistancePair implements Comparable<VertexDistancePair> {
private Vertex vertex;
private int distance;
public VertexDistancePair(Vertex vertex, int distance) {
this.vertex = vertex;
this.distance = distance;
}
public Vertex getVertex() {
return vertex;
}
public int getDistance() {
return distance;
}
@Override
public int compareTo(VertexDistancePair other) {
return Double.compare(this.distance, other.distance);
}
}
This is my vertex class
public class Vertex{
//Class variables
private String label;
private List<Edge> neighbors;
private int id;
public Vertex() {
label = "";
neighbors = null;
}
public Vertex(String label) {
this.label = label;
this.neighbors = new ArrayList<>();
}
public Vertex(String label, List<Edge> neighbors) {
this.label = label;
this.neighbors = neighbors;
}
public void setLabel(String label) {
this.label = label;
}
public void setNeighbors(List<Edge> neighbors) {
this.neighbors = neighbors;
}
public String getLabel() {
return label;
}
public List<Edge> getNeighbors() {
return neighbors;
}
public String toString() {
return label;
}
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (obj == null || getClass() != obj.getClass()) {
return false;
}
Vertex otherVertex = (Vertex) obj;
return label.equals(otherVertex.label);
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
}
This is my edge class
public class Edge {
// Class Variables
private Vertex start;
private Vertex end;
private int weight;
private int id;
/**
* Default Constructor
*/
public Edge() {
start = null;
end = null;
weight = 0;
id = 0;
}
/**
* Constructor for edge without weight
* @param start : vertex
* @param end : vertex
*/
public Edge(Vertex start, Vertex end) {
this.start = start;
this.end = end;
this.weight = 0;
id = 0;
}
/**
* Constructor for edge with weight
* @param start
* @param end
* @param weight
*/
public Edge(Vertex start, Vertex end, int weight) {
this.start = start;
this.end = end;
this.weight = weight;
}
/**
* Setter for start vertex
* @param start : Vertex
*/
public void setStart(Vertex start) {
this.start = start;
}
/**
* Setter for end vertex
* @param end : Vertex
*/
public void setEnd(Vertex end) {
this.end = end;
}
/**
* Setter for weight of edge
* @param weight : double
*/
public void setWeight(int weight) {
this.weight = weight;
}
/**
* Setter for ID
* @param id : id
*/
public void setId(int id) {
this.id = id;
}
/**
* Getter for start
* @return : Vertex
*/
public Vertex getStart() {
return start;
}
/**
* Getter for end
* @return : Vertex
*/
public Vertex getEnd() {
return end;
}
/**
* Getter for weight
* @return : weight
*/
public double getWeight() {
return weight;
}
/**
* Getter for id
* @return id
*/
public int getId() {
return id;
}
/**
* toString method
* @return string representation
*/
public String toString() {
return "(" + start + "," + end + ")";
}
}
This is my graph class
public class Graph {
//Class variables
private List<Vertex> nodes; // nodes are a list of vertices
private List<Edge> edges;
private int count;
/**
* Default Constructor
*/
public Graph() {
nodes = new ArrayList<>();
edges = new ArrayList<>();
count = 0;
}
/**
* Constructor
* @param nodes : List<Vertex
* @param count : int
*/
public Graph(List<Vertex> nodes, int count) {
this.nodes = nodes;
this.count = count;
}
/**
* Method to add a vertex
* @param vertex : Vertex
*/
public void addVertex(Vertex vertex) {
if (!nodes.contains(vertex)) {
this.nodes.add(vertex);
this.count++;
}
}
/**
* Method to add edge
* @param start : Vertex
* @param end : Vertex
*/
public void addEdge(Vertex start, Vertex end) {
edges.add(new Edge(start, end));
}
public void addEdge(Vertex start, Vertex end, int weight) {
edges.add(new Edge(start, end,weight));
}
/**
* Setter to set nodes
* @param nodes : List<Vertex
*/
public void setNodes(List<Vertex> nodes) {
this.nodes = nodes;
}
/**
* Setter to set edges
* @param edges : List<Edge
*/
public void setEdges(List<Edge> edges) {
this.edges = edges;
}
/**
* Setter to set count
* @param count
*/
public void setCount(int count) {
this.count = count;
}
/**
* Getter to get nodes
* @return
*/
public List<Vertex> getNodes() {
return nodes;
}
/**
* Getter to get edges
*/
public List<Edge> getEdges() {
return edges;
}
/**
* Getter for count
* @return
*/
public int getCount() {
return count;
}
/**
* toString method
* @return string representation
*/
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("V={");
for (Vertex vertex : this.nodes) {
sb.append(vertex + ",");
}
sb.append("}\n");
sb.append("E={");
for (Edge edge : this.edges) {
sb.append(edge + ",");
}
sb.append("}");
return sb.toString();
}
}
This is where I create my GraphUtility class object and where I attempt to call the dijkstra method.
public class Test {
public static void main(String[] args) {
// Instantiate GraphUtility and read graph from file
GraphUtility graphUtility = new GraphUtility();
try {
File file = new File("graphs/weighted-directed-matrix"); // Replace with your file path
graphUtility.readFile(file);
} catch (Exception e) {
e.printStackTrace();
return;
}
// Get the graph from GraphUtility
Graph graph = graphUtility.getGraph();
// Choose a source vertex (you can change this as needed)
Vertex source = graph.getNodes().get(0);
// Dijkstra's algorithm
double[] distance = dijkstra(graph, graph.getNodes().get(0));
// Printing results
for (int i = 0; i < graph.getNodes().size(); i++) {
String vertexLabel = graph.getNodes().get(i).getLabel();
String distanceString = (distance[i] == Integer.MAX_VALUE) ? "Unreachable" : String.valueOf(distance[i]);
System.out.println("Vertex: " + vertexLabel + " & Distance from Source: " + distanceString);
}
}
}
The contents of the file "graphs/weighted-directed-matrix" include this:
2,2,2,4,2
4,5,1,3,4
1,2,3,3,5
3,5,5,6,5
3,5,3,4,5
this is my output:
Debug Output:
Vertex IDs: [0, 1, 2, 3, 4]
Edge Weights: [2.0, 2.0, 2.0, 4.0, 2.0, 4.0, 5.0, 1.0, 3.0, 4.0, 1.0, 2.0, 3.0, 3.0, 5.0, 3.0, 5.0, 5.0, 6.0, 5.0, 3.0, 5.0, 3.0, 4.0, 5.0]
Distances: [0.0, 2.147483647E9, 2.147483647E9, 2.147483647E9, 2.147483647E9]
Vertex: A & Distance from Source: 0.0
Vertex: B & Distance from Source: Unreachable
Vertex: C & Distance from Source: Unreachable
Vertex: D & Distance from Source: Unreachable
Vertex: E & Distance from Source: Unreachable
I do not understand why my distance from source for B,C,D, and E say unreachable. Furthermore, I was hoping to implement a system where I could pass in an end vertex alongside my start vertex to the dijkstra method and have my code just output the travel path from my start vertex to my end vertex. How do I go about resolving my issue and implementing this functionality. I have been at this for the whole day and I cannot figure out where the issue lies in the code I have presented. I understand that this question was answered using another method in another post, but I would really like to know where I went wrong in my own code.
There are two issues:
Your dijkstra function looks for neighbors with:
for (Edge neighbor : currentVertex.getNeighbors())
...but getNeighbors() always returns an empty list. This is because there is no code that populates it.
To fix this, add the following method to the Vertex class:
public void addEdge(Edge edge) {
this.neighbors.add(edge);
}
Next, call it from the addEdge method of Graph:
public void addEdge(Vertex start, Vertex end, int weight) {
Edge edge = new Edge(start, end, weight);
edges.add(edge);
start.addEdge(edge); // <--- calling the newly added method
}
In GraphUtility, the readFile function calls populateVertices repeatedly, where each call detaches the previously created vertices from graph.nodes, and creates a new set of vertices with the same ids. This is wrong, because it creates many vertices with the same IDs (and labels), using them to create edges, but only the last batch is retained in graph.nodes, while graph.edges has references to nodes that are not in graph.nodes.
To correct this, make sure to only call populateVertices once, at a moment you don't have registered any yet.
So change this:
populateVertices(tokens.length);
to:
if (graph.getCount() == 0) {
populateVertices(tokens.length);
}
With these two fixes it should work.