# Graph Implementation with Dijkstra's Algorithm

Graph Interface:

import java.util.*;

public interface Graph<T> {

boolean removeEdge(T source, T destination);

boolean removeVertex(T vertex);

List<Edge> getNeighbours(T vertex);

}



Undirected Graph class:



import java.util.*;

public class UndirectedGraph<T> implements Graph<T> {
protected final Map<T, List<Edge>> adjacencyList = new HashMap<>();

@Override
return true;
}
return false;
}

@Override
public boolean removeVertex(T vertex) {
for (List<Edge> entry : adjacencyList.values()) {
List<Edge> list = entry;
for (Edge e : list) {
if (e.getDestination().equals(vertex)) {
list.remove(e);
}
}
}
return true;
}
return false;
}

@Override
public List<Edge> getNeighbours(T vertex) {
}

@Override
public boolean addEdge(T src, Edge dst) {
return true;
}
return false;
}

System.out.println(entry.getKey() + " " + entry.getValue().toString());
});
}

//Removes the edge from the list of the source and destination
@Override
public boolean removeEdge(T source, T destination) {
for (Edge e : adjacencyList.get(source)) {
if (e.getDestination().equals(destination)) {
return true;
}
}
}
return false;
}

}

@Override
public String toString() {
return "UndirectedGraph{" +
'}';
}
}


Directed Graph Class:

import java.util.*;

public class DirectedGraph<T> implements Graph<T> {
protected final Map<T, List<Edge>> adjacencyList = new HashMap<>();

@Override
return true;
}
return false;
}

@Override
public boolean removeVertex(T vertex) {
for (List<Edge> entry : adjacencyList.values()) {
List<Edge> list = entry;
for (Edge e : list) {
if (e.getDestination().equals(vertex)) {
list.remove(e);
}
}
}
return true;
}
return false;
}

@Override
public boolean addEdge(T src, Edge dst) {
return true;
}
return false;
}

@Override
public boolean removeEdge(T source, T destination) {
for (Edge e : adjacencyList.get(source)) {
if (e.getDestination().equals(destination)) {
return true;
}
}
}
return false;
}
}
public List<Edge> getNeighbours(T node) {
}

System.out.println(entry.getKey() + " " + entry.getValue().toString());
});
}

}


Edge Class:

public class Edge<T> {

private T destination;
private int weight;

public Edge(T destination) {
this.destination = destination;

}

public Edge(T destination, int weight) {
this.destination = destination;
this.weight = weight;
}

public T getDestination() {
return destination;
}

public int getWeight() {
return weight;
}

@Override
public String toString() {
return "Edge{" +
"destination=" + destination +
", weight=" + weight +
'}';
}
}



Pathfind class:

import java.util.*;

public class Pathfind<T> {

//Dijkstra's Algorithm
public void findShortestPath(Graph graph, T source) {
//Storing the distances here
Map<Node<T>, Integer> distances = new HashMap<>();
//Keeping track of visited vertices here
List<T> visited = new ArrayList<>();
PriorityQueue<Node> pq = new PriorityQueue<Node>(verticesCount, Node::compareTo);
//Adding all vertices to distances map and setting the value of distance to max
for (T vertex : adj.keySet()) {
distances.put(new Node(vertex), Integer.MAX_VALUE);
}
distances.put(new Node(source, 0), 0);

while (!pq.isEmpty()) {
Node<T> node = pq.poll();
T vertex = node.getNode();

for (Edge<T> edge : adj.get(vertex)) {
if (!visited.contains(edge.getDestination())) {
int totalCost = node.getCost() + edge.getWeight();
T destNode = edge.getDestination();

if (totalCost < distances.get(new Node(destNode))) {
Node<T> node1 = new Node<T>(destNode, vertex);
distances.remove(node1);
distances.put(node1, totalCost);

}
}
}

}

for (Node<T> node : distances.keySet()) {
if (distances.get(node) < Integer.MAX_VALUE) {
System.out.print(node.getNode().toString() + " ||| Cost = " + distances.get(node));

}
if (node.getPredecessor() != null) {
System.out.println(" ||| Predecessor = " + node.getPredecessor().toString());
}
}

}

public class Node<T> implements Comparable<Node<T>> {
private T node;
private int cost;
private T predecessor;

public Node(T node) {
this.node = node;
}

public Node(T node, int cost) {
this.node = node;
this.cost = cost;
}

public Node(T node, T predecessor) {
this.node = node;
this.predecessor = predecessor;
}

public Node(T node, int cost, T predecessor) {
this.node = node;
this.cost = cost;
this.predecessor = predecessor;
}

public T getNode() {
return node;
}

public int getCost() {
return cost;
}

public T getPredecessor() {
return predecessor;
}

public void setPredecessor(T predecessor) {
this.predecessor = predecessor;
}

@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Node<?> node1 = (Node<?>) o;
return Objects.equals(node, node1.node);
}

@Override
public int hashCode() {
return Objects.hash(node);
}

@Override
public int compareTo(Node<T> other) {
return Integer.compare(cost, other.getCost());
}
}
}


What could I have done better ? I have so much duplicated code in UndirectedGraph and DirectedGraph. I'm also planning to implement other pathfinding algorithms and visualizing them.

• Where are the tests? Jan 15, 2022 at 11:15

your major issue is the redunat code you say... so you should try to put things that some classes have in common into a common class

there is a very nice example of the proper usage of interfaces, of abstract classes and impolementing classes on stackoverflow - this answer provides the basic concepts.

## so what? what now?

your interface looks good so far, so you need a base implementation that does all the stuff that any would do:

public abstract class BaseGraph<T> implements Graph<T>{

//this is just a stub - most classes are not shown, do on your own!

@Override
public boolean addEdge(T src, Edge dst) {
if (containsEdge(src, dest) { //this is different
return true;
}
return false;
}

abstract boolean containsEdge(T src, Edge dst);

}


your implementing class now has to implement only the different parts of the code

class UndirectedGraph<T> extends BaseGraph<T>{

@Override
boolean containsEdge(T src, Edge dst){
}

@Override
}

}


## Note

i am not an expert on Graphs so you have to decide how far you make your abstract class BaseGraph abstract - i can not tell you how much sense it makes to have an abstract method boolean containsEdge(T src, Edge dst) (or addEdgeToAdjacency), here you have to think on your own.

## side note:

what's the difference between node and vertex? - well, there is no difference :-) so you should change your Graph class to a more proper model:

interface Graph<Node<T>> {
...
}


this way you would avoid a BUG that may occur if any T does not properly ovverwrite equals and hashCode. that would lead to errors while checking for content of the list (adjacencyList.containsKey(src)).

## side note 2

your ShortestPath method is not very readable - you start nice with bringing the algoroth into code (first lines) but then you stop with it - have a look at the Integration Operation Segregation Principle (IOSP) - it says:

IOSP calls for a clear separation:

• Either a method contains exclusively logic, meaning transformations, control structures or API invocations. Then it’s called an Operation.
• Or a method does not contain any logic but exclusively calls other methods within its code basis. Then it’s called Integration.

that would clean up your method! (your algorithm is a pure operation methode)

• Got rid of the redundant code ! thank you. Will work on making my ShortestPath method more readable. Jan 20, 2022 at 15:17

On graph node type name

I see that you named the graph node type N, which is OK since in Java we name the type arguments with a single letter according to the first letter of the name of the underlying concept. However, consider renaming it to V (as in Vertex).

I strongly suggest you use Javadoc facilities for describing your code. If nothing else, you should explain, for instance, the difference between directed and undirected graphs somewhere in your code (preferably as class comments). Also, you could explain briefly what graphs are all about.

I suggest you put all your classes in a package with a name like com.yourcompany.graph or similar.

II. Graph interface

First of all, let's take a look at your Graph interface:

import java.util.*;

public interface Graph<T> {

boolean removeEdge(T source, T destination);

boolean removeVertex(T vertex);

List<Edge> getNeighbours(T vertex);

}


import java.util.*;


I really suggest you import explicitly all the classes you use. So, the above becomes:

import java.util.List;
import java.util.Map;


In my opinion, introducing the Edge class adds an unnecessary level of indirection. I would have instead:

boolean addEdge(V sourceVertex, V targetVertex);


I would remove printAdjacencyList and provide the methods for accessing the internals of the graph through the java.util.Collections.unmodifiableXXX wrappers so that the caller cannot tamper with the internal state directly.

package com.yourcompany.graph;

import java.util.Collection;
import java.util.Set;

/**
* This interface defines the API for a graph.
*
* @param <V> the actual graph vertex type.
*/
public interface Graph<V> {

boolean hasEdge(V sourceVertex, V targetVertex);
boolean removeEdge(V sourceVertex, V targetVertex);

boolean hasVertex(V vertex);
boolean removeVertex(V vertex);

Set<V> getVertices();
Collection<V> getParentVerticesOf(V vertex);
Collection<V> getChildVerticesOf(V vertex);

int numberOfNodes();
int numberOfEdges();
}


III. Directed graph

protected final Map<T, List<Edge>> adjacencyList = new HashMap<>();


I would write:

protected final Map<V, Set<V>> childMap = new HashMap<>();
protected final Map<V, Set<V>> parentMap = new HashMap<>();


That way, you can map each vertex to a java.util.HashSet that provides (expected) $$\\mathcal{O}(1)\$$ time for add, contains and remove. (java.util.List runs contains and remove in $$\\mathcal{O}(n)\$$ worst-case time.)

The idea is that childMap.get($$\u\$$) will map $$\u\$$ to all the vertices $$\v\$$ such that there is a pair $$\(u, v)\$$ in the edge set of the graph (child nodes of u). Conversely, parentMap.get($$\u\$$) will map $$\u\$$ to all the vertices $$\v\$$ such that there is a pair $$\(v, u)\$$ in the edge set (parent nodes of u).

Having separate parentMap allows us to have the method getParentVerticesOf, which, in turn, is required in bidirectional point-to-point pathfinding (bidirectional BFS, bidirectional Dijkstra's algorithm, NBA*).

public boolean addVertex(T vertex) {
return true;
}
return false;
}


java.util.LinkedList is a poor choice. Consider java.util.ArrayList instead. The problem here is that LinkedList introduces $$\\Theta(n)\$$ worth space overhead for storing the internal linked list nodes. Also, the internal list nodes do not exhibit reference locality, so CPU cache won't help much. Consider this instead:

@Override
checkInputNotNull(vertex);

if (!childMap.containsKey(vertex)) {
childMap.put(vertex, new HashSet<>());
parentMap.put(vertex, new HashSet<>());
vertices.add(vertex); // vertices is also a HashSet!
return true;
}

return false;
}


public boolean removeVertex(T vertex) {
for (List<Edge> entry : adjacencyList.values()) {
List<Edge> list = entry;
for (Edge e : list) {
if (e.getDestination().equals(vertex)) {
list.remove(e);
}
}
}
return true;
}
return false;
}


The outer for loop iterates around (+1/-1) $$\n\$$ times and the outer loop iterates around $$\m\$$ times, so the running time is $$\\Theta(m + n + \sum_{i = 1}^n c_i) = \Theta(m + n)\$$ where $$\c_i\$$ is the number of nodes in the adjacency list of the node $$\n_i\$$. You can definitely drop this to $$\\Theta(1)\$$ with the following implementation of the method in question:

public boolean removeVertex(V vertex) {
checkInputNotNull(vertex);

if (!hasVertex(vertex)) {
return false;
}

numberOfEdges -=
(childMap.get(vertex).size() + parentMap.get(vertex).size());

childMap.remove(vertex);
parentMap.remove(vertex);
vertices.remove(vertex);
return true;
}


public boolean removeEdge(T source, T destination) {
for (Edge e : adjacencyList.get(source)) {
if (e.getDestination().equals(destination)) {
return true;
}
}
}
return false;
}


Above, the worst-case running time of the method is $$\\mathcal{O}(k^2)\$$, where $$\k = \$$ adjacencyList.get(source).size(). You can do this in constant time:

public boolean removeEdge(V sourceVertex, V targetVertex) {
checkInputNotNull(sourceVertex);
checkInputNotNull(targetVertex);

if (!childMap.containsKey(sourceVertex)) {
return false;
}

if (!childMap.get(sourceVertex).contains(targetVertex)) {
return false;
}

childMap.get(sourceVertex).remove(targetVertex);
parentMap.get(targetVertex).remove(sourceVertex);
numberOfEdges--;
return true;
}


Note III.5

public Map<T, List<Edge>> getAdjacencyList() {
}


Good!

IV. Dijkstra shortest path tree

Note IV.1

I see that you compute not a shortest path to a target vertex, but rather a shortest path tree. You could encapsulate that tree into a class that supports a query method computing the shortest path from the source vertex to any given input target vertex:

package com.yourcompany.graph;

// imports.

public class ShortestPath<V> {

private final List<V> path = new ArrayList<>();

public ShortestPath(List<V> path) {
}

public List<V> getVertexList() {
return Collections.<V>unmodifiableList(path);
}

public int getPathWeight(WeightFunction<V> weightFunction) {
int pathWeight = 0;

for (int i = 0; i < path.size() - 1; i++) {
pathWeight = pathWeight + weightFunction.getWeight(path.get(i),
path.get(i + 1));
}

return pathWeight;
}
}


... and ...

package com.yourcompany.graph;

// imports.

public class ShortestPathTreeBuilder<V> {

private final Map<V, V> parentMap = new HashMap<>();

public ShortestPathTreeBuilder(Map<V, V> parentMap) {
this.parentMap.putAll(
Objects.requireNonNull(
parentMap,
"The input parent map is null."));
}

public ShortestPath<V> buildPathTo(V targetVertex) {
List<V> path = new ArrayList<>();
V node = targetVertex;

while (node != null) {
node = parentMap.get(node);
}

Collections.<V>reverse(path);
return new ShortestPath<>(path);
}
}


I would extract the edge weights from the Edge objects, and code up a simple class for storing the weights for any single ordered pair of vertices:

package com.yourcompany.graph;

public interface WeightFunction<V> {

void setWeight(V sourceVertex, V targetVertex, int weight);
int getWeight(V sourceVertex, V targetVertex);
}


Also,

package com.yourcompany.graph.impl;

import com.yourcompany.graph.WeightFunction;
import java.util.HashMap;
import java.util.Map;

public class DirectedGraphWeightFunction<V>
implements WeightFunction<V> {

private final Map<V, Map<V, Integer>> map = new HashMap<>();

@Override
public void setWeight(V sourceVertex, V targetVertex, int weight) {
if (!map.containsKey(sourceVertex)) {
map.put(sourceVertex, new HashMap<>());
}

map.get(sourceVertex).put(targetVertex, weight);
}

@Override
public int getWeight(V sourceVertex, V targetVertex) {
return map.get(sourceVertex).get(targetVertex);
}
}


Note IV.3

//Keeping track of visited vertices here
List<T> visited = new ArrayList<>();


This will definitely limit your computation speed. The problem is that visited.contains(edge.getDestination()) will run in worst-case $$\\mathcal{O}(n)\$$ time, where $$\n\$$ is the number of vertices in the graph. This leads to the fact that your implementation runs in $$\\mathcal{O}(mn)\$$ worst-case time. Use java.util.HashSet instead and the time complexity will drop to $$\\mathcal{(m + n) \log n}\$$. (With Fibonacci heap, this drops to $$\\mathcal{O}(m + n \log n)\$$, but Fibonacci heap hides very large hidden constant factors, so its usage in practice is questionable.)

Summa summarum

I had this implementation in mind.

Hope that helps.

• that is a quite fully review +1 Jan 18, 2022 at 15:30
• I made some of the changes that i was able to understand from the review so far and I will be trying to understand the rest. Really appreciate your detailed review. Thank you Jan 20, 2022 at 15:19