I am learning graph theory in CS and for practice, I have implemented Djikstra's algorithm in Java. I have created a GraphVertex
class that contains information about the vertex and WeightedEdge
class which contains information about the edges and their weights. DirectedGraphWithHeights
class contains the implementation of the algorithm.
I received feedback earlier on Code Review and I have tried to improve on the naming convention I use in the classes.
I wanted to understand if the methodology I am taking towards solving the algorithm and constructing the graph is up to the mark or not.
DirectedGraphWithWeights
public class DirectedGraphWithWeights {
private HashMap<GraphVertex, LinkedList<WeightedEdge>>
adjacentVerticesByVertex;
private Set<GraphVertex> vertexSet;
/**
* Constructor
*/
DirectedGraphWithWeights() {
adjacentVerticesByVertex = new HashMap<>();
vertexSet = new HashSet<>();
}
/**
* Returns the number of vertices in the Graph
* @return Returns the number of vertices
*/
public int getNumberOfVertices() {
return this.vertexSet.size();
}
/**
* Adds a node to the graph. VertexA -> VertexB, adding a vertex creates an
* edge between VertexA and VertexB with the specified weight
* @param vertexA Vertex A
* @param vertexB Vertex B
* @param weight Weight of the edge
*/
public void addEdge(int vertexA, int vertexB, int weight) {
GraphVertex graphVertexA = new GraphVertex(vertexA);
GraphVertex graphVertexB = new GraphVertex(vertexB);
vertexSet.add(graphVertexA);
vertexSet.add(graphVertexB);
WeightedEdge weightedEdge = new WeightedEdge(weight, graphVertexA,
graphVertexB);
if(!adjacentVerticesByVertex.containsKey(graphVertexA))
adjacentVerticesByVertex.put(graphVertexA, new
LinkedList<WeightedEdge>());
adjacentVerticesByVertex.get(graphVertexA).add(weightedEdge);
}
/**
* Returns all the adjacent nodes
* @param source Source node
* @return Returns all the adjacent nodes
*/
public Iterable<WeightedEdge> getAdjacentVertices(int source) {
GraphVertex tempNode = new GraphVertex(source);
return adjacentVerticesByVertex.get(tempNode);
}
/**
* Djikstra's algorithm implementation
*/
public void calculateShortedPath(int source) {
Set<GraphVertex> visitedVertices = new HashSet<>();
GraphVertex sourceVertex = new GraphVertex(source);
HashMap<GraphVertex, Integer> shortestPathMap = new HashMap<>();
// Set the value of all vertex -> weight to infinity and to the source
// to 0
for(GraphVertex vertex : vertexSet) {
if(vertex.equals(sourceVertex)) shortestPathMap.put(sourceVertex, 0);
else shortestPathMap.put(vertex, Integer.MAX_VALUE);
}
// TODO: Move this to a function later
// Get all the nodes which can be visited from the start node
for(WeightedEdge edge : adjacentVerticesByVertex.get(sourceVertex)) {
shortestPathMap.put(edge.getDestination(), edge.getEdgeWeight());
}
visitedVertices.add(sourceVertex);
// The function will work until there are no more nodes to visit
while(true) {
// Next closest vertex
GraphVertex currentVertex = getLowestWeightVertex(shortestPathMap,
visitedVertices);
if(visitedVertices.size() == vertexSet.size()) {
break;
}
visitedVertices.add(currentVertex);
// Get the adjacent vertices to the currentVertex and update the
// shortestPathMap
if(adjacentVerticesByVertex.containsKey(currentVertex)) {
for(WeightedEdge edge : adjacentVerticesByVertex.get(currentVertex)) {
if(!visitedVertices.contains(edge.getDestination())) {
int edgeWeightCumulative =
shortestPathMap.get(currentVertex) +
edge.getEdgeWeight();
int edgeDestinationWeight =
shortestPathMap.get(edge.getDestination());
if(edgeWeightCumulative < edgeDestinationWeight) {
shortestPathMap.put(edge.getDestination(),
edgeWeightCumulative);
}
}
}
}
}
System.out.println(shortestPathMap);
}
/**
* Gets
* @param shortestPathMap
* @param visitedVertices
* @return
*/
private GraphVertex getLowestWeightVertex(
HashMap<GraphVertex, Integer> shortestPathMap,
Set<GraphVertex> visitedVertices) {
int lowestWeight = Integer.MAX_VALUE;
GraphVertex lowestVertex = null;
for(GraphVertex vertex : vertexSet) {
if(!visitedVertices.contains(vertex)) {
if(shortestPathMap.get(vertex) < lowestWeight) {
lowestWeight = shortestPathMap.get(vertex);
lowestVertex = vertex;
}
}
}
return lowestVertex;
}
}
WeightedEdge.java
public class WeightedEdge {
private GraphVertex source;
private GraphVertex destination;
private int edgeWeight;
WeightedEdge(int edgeWeight, GraphVertex source, GraphVertex destination) {
this.edgeWeight = edgeWeight;
this.source = source;
this.destination = destination;
}
public GraphVertex getSource() {
return source;
}
public void setSource(GraphVertex source) {
this.source = source;
}
public GraphVertex getDestination() {
return destination;
}
public void setDestination(GraphVertex destination) {
this.destination = destination;
}
public int getEdgeWeight() {
return edgeWeight;
}
public void setEdgeWeight(int edgeWeight) {
this.edgeWeight = edgeWeight;
}
}
GraphVertex.java
public class GraphVertex implements Comparator<GraphVertex> {
private int value;
GraphVertex(int value) {
this.value = value;
}
public int getValue() {
return this.value;
}
@Override
public int hashCode() {
return new Integer(this.value).hashCode();
}
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if (obj == null) return false;
if (getClass() != obj.getClass()) return false;
GraphVertex other = (GraphVertex) obj;
if(value != other.getValue()) return false;
return true;
}
/**
* Compares two nodes. The comparison is based on the value in the node
* @param one
* @param two
* @return
*/
public int compare(GraphVertex one, GraphVertex two) {
if(one.value == two.value) return 0;
return one.value > two.value ? 1 : -1;
}
}