Java Graph (Directed and weighted), simple and fast

Graphs, one of the frequently used data structures throughout the world in all sorts of applications from simple exam time table setting to social networking and even complex neural networking.

What is a graph and what are the fundamental feature to be included in a graph?

• Graph structure
• Nodes
• Edges

Here are some additional features that we may creep into

• Weighted edges 
• Directionality

Let's see how we can build a graph using Java Language. The graph consists of nodes and that's what I'm going to make first.

Node should be able to keep track of the neighbours, a unique id and the weights to it's neighbours (or simply distances as is most cases)

For the implementation of the above Node structure we'll be using class Vertex. It has a HashMap that keeps the unique ids of it's neighbours that map to the distance to that particular Node.

private final HashMap<E, Integer> neighbours;

In this scenario I'll be using generics in java which makes the code re-usable in many scenarios in future. 

The next task is to implement the graph, for that the class Graph is used. Again we're using a HashMap to keep the unique ids that map to their Vertex objects.

private final HashMap<E, Vertex<E>> graph;

As in the previous case generics are used for the re-usability.

1. The graph should be initiated with all the Vertices at the beginning

2. The edges could be added later with the weights 

The graph can be modified either to be directional or not. Only the thing we need to change is whether to keep neghbours for both the edges or not. Say we have an edge (u,v) where the distance d(u,v) = 50 units. If the graph is directional u has v as neighbour and v has u as a neighbour. If the graph is directional only one of the above may exist.

The implementation will be more complicated where we need to keep loops or multiple edges between the same nodes. The implementation mentioned in the code assumes that there are no such instances. Even there are multiple edges between same nodes we may change the code a little bit to update the edge to the shortest edge or the longest depending on whether we want to get the shortest or the longest span.

You can find the code below...

	package code_templates.GraphTheory;
	import java.util.HashMap;
	import java.util.Map;
	import java.util.Set;
	/**
	*
	* @author Anuradha Sanjeewa
	*/
	class Graph<E> {
	private final HashMap<E, Vertex<E>> graph;
	private boolean isDirected = true;
	public Graph() {
	graph = new HashMap<E, Vertex<E>>();
	}
	public Graph(boolean isDirected) {
	graph = new HashMap<E, Vertex<E>>();
	this.isDirected = isDirected;
	}
	public void addVertex(E id) {
	Vertex<E> v = new Vertex<E>(id);
	this.graph.put(id, v);
	}
	public Vertex<E> getVertex(E id) {
	if (graph.containsKey(id)) {
	return graph.get(id);
	} else {
	return null;
	}
	}
	public void addEdge(E u, E v, int w) {
	Vertex<E> ver = this.graph.get(u);
	ver.addNeighbour(v, w);
	if (isDirected) {
	ver = this.graph.get(v);
	ver.addNeighbour(u, w);
	}
	}
	public Set<E> getVertices() {
	return this.graph.keySet();
	}
	public void printGraph() {
	for (Map.Entry<E, Vertex<E>> entrySet : graph.entrySet()) {
	E key = entrySet.getKey();
	System.out.println("Vertext=" + key);
	Vertex value = entrySet.getValue();
	for (Object n : value.getNeighbours()) {
	System.out.println(" neighbour=" + (E) n + " weight=" + value.getWeight((E) n));
	}
	}
	}
	}
	class Vertex<E> {
	private E id;
	private final HashMap<E, Integer> neighbours;
	public Vertex(E id) {
	// Stores the set of neighbours and the edge weight
	this.id = id;
	this.neighbours = new HashMap<E, Integer>();
	}
	public void addNeighbour(E id, Integer weight) {
	this.neighbours.put(id, weight);
	}
	public Set<E> getNeighbours() {
	return this.neighbours.keySet();
	}
	public E getId() {
	return this.id;
	}
	public int getWeight(E id) {
	if (this.neighbours.containsKey(id)) {
	return this.neighbours.get(id);
	} else {
	return Integer.MAX_VALUE;
	}
	}
	}
	public class GraphImplementation {
	public static void main(String[] args) {
	Graph<Character> g = new Graph<Character>(false);
	g.addVertex('a');
	g.addVertex('b');
	g.addVertex('c');
	g.addVertex('d');
	g.addVertex('e');
	g.addVertex('f');
	g.addEdge('a', 'b', 5);
	g.addEdge('c', 'b', 10);
	g.addEdge('c', 'd', 15);
	g.addEdge('c', 'e', 3);
	g.printGraph();
	}
	}

view raw graph.java hosted with ❤ by GitHub