Graph Implementation in Java

1. In mathematics, and more specifically in graph threoy, a graph is a representation of set of objects where some pair of objects are connected by links - Wikipedia.

The graph is important for modeling any kind of relationship. So you can model road network between cities, the relationship among people (known as friendship graph) etc.

G = (V,E) 
A graph is defined as set of vertices V and set of edges (or vertex pair) E.

Let's take an example of flights between different cities, vertices represent cities and edges represent weight/cost of travel between a pair of cities. The graph can be directed if the edge(x,y) is not equivalent to the edge(y,x) otherwise it will undirected. Edges can also have the cost or weight associated with it.

Modelling the graph appropriately is quite important. Two basic data structures are - adjacency matrices and adjacency lists. Below is a weighted directed graph which represents the weighted cost of air travel between cities.

BL: Bangalore, HK: Hong Kong etc.

Adjacency Matrix represents G as an N x N matrix and matrix[i][j] = 1 if (i,j) is an edge of G, and 0 if it's not. If the graph is weighted then weight will be the value of the cell (assume that 0 means no connection). Adjacency List uses linked data structure to stores neighbors adjacent to each vertex.  If you are using adjacency list implementation to store undirected graph, the same edge (u,v) appears twice so that's extra space overhead. Each has its own pluses and minuses so which data structure you chose depends on what problem you going to solve. So think closely about the problem first before deciding the data structure. Practically adjacency list is right data structure for most of the applications.
But, the question like is (i,j) in graph? can be answered more easily if implementation is through Adjacency Matrix. 

Graph Implementation

Implementing the Adjacency Matrix is trivial, we just need a 2-dimensional array. This post, I will be implementing graph using adjacency list. Also, will be using two different approaches. 

Approach 1: The simplest possible adjacency list implementation could be a Graph class which has a collection of vertices and edges.

package graph.algo;

/**
 * Vertex represents points in a graph
 * 
 * @author Siddheshwar
 * @param <V>
 */
public class Vertex<V> {
 private V name;

 public Vertex(V name) {
  super();
  this.name = name;
 }

 public V getName() {
  return name;
 }

 @Override
 public int hashCode() {
  final int prime = 31;
  int result = 1;
  result = prime * result + ((name == null) ? 0 : 

                         name.hashCode());
  return result;
 }

 @Override
 public boolean equals(Object obj) {
  if (this == obj)
   return true;
  if (obj == null)
   return false;
  if (getClass() != obj.getClass())
   return false;
  Vertex other = (Vertex) obj;
  if (name == null) {
   if (other.name != null)
    return false;
  } else if (!name.equals(other.name))
   return false;
  return true;
 }
}

package graph.algo;

/**
 * Represents connection between two vertices.
 * 
 * @author Siddheshwar
 * @param <V>
 */
public class Edge<V> {
 private Vertex<V> source;
 private Vertex<V> destination;
 int weight;

 public Edge(Vertex<V> source, Vertex<V> destination, int weight) {
  super();
  this.source = source;
  this.destination = destination;
  this.weight = weight;
 }

 public Vertex<V> getSource() {
  return source;
 }

 public Vertex<V> getDestination() {
  return destination;
 }

 public int getWeight() {
  return weight;
 }

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

package graph.algo;

import java.util.ArrayList;
import java.util.List;

/**
 * Graph object as collection of vertices and edges
 * 
 * @author Siddheshwar
 * @param <V>
 */
public class GraphSimple<V> {
 private List<Vertex<V>> vertices;
 private List<Edge<V>> edges;

 public GraphSimple() {
  super();
  this.vertices = new ArrayList<>();
  this.edges = new ArrayList<>();
 }

 // other methods...
}

Approach 2: This approach uses the Map API of Java to create the relationship. The mapping between a vertex and node forms Edge. There is no explicit class to represent edges. So, source vertex is represented by vertex and the edge from source to target is represented by Node (by storing vertex as key and Node as value in map). The relationship or edge, in this case, gets represented by key-value in the map.

                     

package graph.algo;

/**
 * Node class to represent nodes in the graph. It will help in forming edges
 * 
 * @author Siddheshwar
 * 
 * @param <V>
 */
public class Node<V> {
 V name; // Vertex name
 int weight;

 public Node(V name, int weight) {
  super();
  this.name = name;
  this.weight = weight;
 }
 
 public V getName() {
  return name;
 }

 public int getWeight() {
  return weight;
 }

 @Override
 public String toString() {
  return "(" + this.weight + ")" + this.name;
 }
}

package graph.algo;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Graph object which maps vertex with nodes
 * 
 * @author Siddheshwar
 * 
 * @param <V>
 */
public class Graph<V> {
 // Vertex i.e. V gets mapped to list of all connecting Nodes. 
 Map<V, List<Node<V>>> adjacencyList;
 int verticesCount;
 int edgeCount;

 public Graph() {
  super();
  this.adjacencyList = new HashMap<>();
 }

 /**
  * Add a new node for the given vertex. 

         *  Vertex to node connection forms Edge.
  * 
  * @param vertex
  * @param node
  */
 public void addNewNode(V vertex, Node<V> node) {
  List<Node<V>> nodes = adjacencyList.get(vertex);
  if (nodes == null || nodes.isEmpty()) { 
   nodes = new ArrayList<Node<V>>();
   nodes.add(node);
  } else {
   nodes.add(node);
  }
  adjacencyList.put(vertex, nodes);
 }

 /**
  * Takes two vertices and checks if there is a path between v1 and v2.
  * Doesn't take vice-versa.
  * 
  * @param v1
  *            first vertex
  * @param v2
  *            second vertex
  * @return
  */
 public boolean hasRelationship(V v1, V v2) {
  if (v1 == null && v2 == null)
   return true;
  if (v1 != null && v2 == null)
   return true;
  if (v1 == null && v2 != null)
   return false;

  List<Node<V>> nodes = null;

  if (adjacencyList.containsKey(v1)) {
   nodes = adjacencyList.get(v1);
   if (nodes != null || !nodes.isEmpty()) {
    for (Node<V> v : nodes) {
     if (v.getName().equals(v2))
      return true;
    }
   }
  }
  return false;
 }

 public void print() {
  System.out.println("Graph is --->");
  for (V v : adjacencyList.keySet()){
      System.out.println(v + " --- " + adjacencyList.get(v));

                }  
 }

 //Test method
 public static void main(String[] args) {
       Graph<String> graph = new Graph<String>();
       graph.addNewNode("Bangalore", new Node<String>("SFO", 100));
       graph.addNewNode("Bangalore", new Node<String>("HongKong", 50));
       graph.addNewNode("Bangalore", new Node<String>("LA", 70));
       graph.addNewNode("LA", new Node<String>("SFO", 20));
       graph.addNewNode("HongKong", new Node<String>("LA", 60));

       graph.print();

      System.out.println(" Path between Bangalore and LA exists ? :"
    + graph.hasRelationship("Bangalore", "LA"));
 }

}

Output:
Graph is --->
HongKong --- [(60)LA]
LA --- [(20)SFO]
Bangalore --- [(100)SFO, (50)HongKong, (70)LA]

 The path between Bangalore and LA exists? : true

This was a simplistic implementation of Graph, as I wanted to stress on fundamentals. This post has more refined Adjacency List graph implementation in Java. 

---

do post your feedback!!!