Graph Interface:
import java.util.*;
public interface Graph<T> {
boolean addEdge(T src, Edge edge);
boolean removeEdge(T source, T destination);
boolean addVertex(T vertex);
boolean removeVertex(T vertex);
void printAdjacencyList();
List<Edge> getNeighbours(T vertex);
Map<T, List<Edge>> getAdjacencyList();
}
Undirected Graph class:
import java.util.*;
public class UndirectedGraph<T> implements Graph<T> {
protected final Map<T, List<Edge>> adjacencyList = new HashMap<>();
@Override
public boolean addVertex(T vertex) {
if (!adjacencyList.containsKey(vertex)) {
adjacencyList.put(vertex, new LinkedList<Edge>());
return true;
}
return false;
}
@Override
public boolean removeVertex(T vertex) {
if (adjacencyList.containsKey(vertex)) {
adjacencyList.remove(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) {
return adjacencyList.get(vertex);
}
@Override
public boolean addEdge(T src, Edge dst) {
if (adjacencyList.containsKey(src) && adjacencyList.containsKey(dst.getDestination())) {
adjacencyList.get(src).add(dst);
adjacencyList.get(dst.getDestination()).add(new Edge(src, dst.getWeight()));
return true;
}
return false;
}
//Prints the adjacecny list
public void printAdjacencyList() {
adjacencyList.entrySet().forEach(entry -> {
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) {
if (adjacencyList.containsKey(source) && adjacencyList.containsKey(destination)) {
for (Edge e : adjacencyList.get(source)) {
if (e.getDestination().equals(destination)) {
adjacencyList.get(source).remove(e);
return true;
}
}
}
return false;
}
public Map<T, List<Edge>> getAdjacencyList() {
return Collections.unmodifiableMap(adjacencyList);
}
@Override
public String toString() {
return "UndirectedGraph{" +
"adjacencyList=" + adjacencyList +
'}';
}
}
Directed Graph Class:
import java.util.*;
public class DirectedGraph<T> implements Graph<T> {
protected final Map<T, List<Edge>> adjacencyList = new HashMap<>();
@Override
public boolean addVertex(T vertex) {
if (!adjacencyList.containsKey(vertex)) {
adjacencyList.put(vertex, new LinkedList<Edge>());
return true;
}
return false;
}
@Override
public boolean removeVertex(T vertex) {
if (adjacencyList.containsKey(vertex)) {
adjacencyList.remove(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) {
if (adjacencyList.containsKey(src) && adjacencyList.containsKey(dst.getDestination())) {
adjacencyList.get(src).add(dst);
return true;
}
return false;
}
@Override
public boolean removeEdge(T source, T destination) {
if (adjacencyList.containsKey(source)) {
for (Edge e : adjacencyList.get(source)) {
if (e.getDestination().equals(destination)) {
adjacencyList.get(source).remove(e);
return true;
}
}
}
return false;
}
public Map<T, List<Edge>> getAdjacencyList() {
return Collections.unmodifiableMap(adjacencyList);
}
public List<Edge> getNeighbours(T node) {
return adjacencyList.get(node);
}
//Prints the adjacecny list
public void printAdjacencyList() {
adjacencyList.entrySet().forEach(entry -> {
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) {
//gets the adjacency list
Map<T, List<Edge>> adj = graph.getAdjacencyList();
int verticesCount = adj.size();
//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);
pq.add(new Node(source, 0));
while (!pq.isEmpty()) {
Node<T> node = pq.poll();
T vertex = node.getNode();
visited.add(vertex);
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);
}
pq.add(new Node(destNode, totalCost, vertex));
}
}
}
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.
