Monday, August 18, 2014

Graph.java

Check here, for Graph basics. Below is adjacency list based graph implementation in Java.

package graph.algo;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Objects;
import java.util.Set;

/**
 * Graph object which maps source and destination vertex. It's adjacency list
 * implementation. It maps vertex to node. Node encapsulates a vertex and the
 * weight.
 * 
 * It is represented as : vertexSource ---------> Node
 * 
 * So in above relationship- the weight is put in Node class. It is implicitly
 * same as putting weight on the edge. And to allow more than one Node
 * connection; map stores the list of Nodes.
 * 
 * Set<V> vertices : for fast retrieval instead of traversing the graph and
 * getting the list of vertices.
 * 
 * Can be used to model : 1) Directed graph 2) Undirected graph : make sure to
 * call addEdge(src,dest, wt) and addEdge(dest, src, wt) 3) Weighted and
 * Unweighted : make weight as 0/default value for Unweighted graph
 * 
 * Required Java Version = 7
 * 
 * @author Siddheshwar
 * 
 * @param <V>
 */
public class Graph<V> {
 private Map<V, List<Node<V>>> adjacencyList;
 private Set<V> vertices;
 private static final int DEFAULT_WEIGHT = Integer.MAX_VALUE;

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

 /**
  * Node class to represent nodes in the graph. The weight attribute allows
  * you to represent weighted graph.
  * 
  * @param <V>
  */
 private static class Node<V> {
  private V name; // Vertex name
  private int weight;

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

  public V getName() {
   return name;
  }

  public int getWeight() {
   return weight;
  }

  @Override
  public int hashCode() {
   return this.getName().hashCode();
  }

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

 /**
  * Getter method for graph object
  * 
  * @return Map<V, List<Node<V>>>
  */
 public Map<V, List<Node<V>>> getGraph() {
  return this.adjacencyList;
 }

 /**
  * Checks if graph is empty ? Even if there is a single vertex; it won't be
  * considered as empty.
  * 
  * @return
  */
 public boolean isEmpty() {
  return this.vertices.isEmpty();
 }

 /**
  * Add a new neighbor node or adjacent node for the given source vertex.
  * Vertex to node connection forms Edge.
  * 
  * @param src
  * @param destNode
  */
 private void addEdge(V src, Node<V> destNode) {
  List<Node<V>> adjacentVertices = adjacencyList.get(src);
  if (adjacentVertices == null || adjacentVertices.isEmpty()) {
   adjacentVertices = new ArrayList<Node<V>>();
   adjacentVertices.add(destNode);
  } else {
   adjacentVertices.add(destNode);
  }
  adjacencyList.put(src, adjacentVertices);
 }

 /**
  * Add an edge between src and destination vertices
  * 
  * @param src
  * @param dest
  * @param weight
  */
 public void addEdge(V src, V dest, int weight) {
  Objects.requireNonNull(src);
  Objects.requireNonNull(dest);

  this.addEdge(src, new Node<>(dest, weight));

  // update vertices set
  this.vertices.add(src);
  this.vertices.add(dest);
 }

 /**
  * Add an edge between src and destination vertices overloaded method to
  * create Unweighted graph
  * 
  * @param src
  * @param dest
  * @param weight
  */
 public void addEdge(V src, V dest) {
  Objects.requireNonNull(src);
  Objects.requireNonNull(dest);

  this.addEdge(src, new Node<>(dest, DEFAULT_WEIGHT));

  // update vertices set
  this.vertices.add(src);
  this.vertices.add(dest);
 }

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

  List<Node<V>> nodes = null;

  if (adjacencyList.containsKey(source)) {
   nodes = adjacencyList.get(source);
   if (nodes != null && !nodes.isEmpty()) {
    for (Node<V> neighbors : nodes) {
     if (neighbors.getName().equals(destination))
      return true;
    }
   }
  }
  return false;
 }

 /**
  * get weight of the edge
  * 
  * @param src
  * @param dest
  * @return weight
  */
 public int getWeight(V src, V dest) {
  int weight = DEFAULT_WEIGHT;
  if (this.hasRelationship(src, dest)) {
   List<Node<V>> adjacentNodes = this.adjacencyList.get(src);
   for (Node<V> node : adjacentNodes) {
    if (node.getName().equals(dest)) {
     weight = node.getWeight();
    }
   }
  }
  return weight;
 }

 /**
  * Get adjacent vertices of the given vertex. This method returns all edges
  * starting from the given vertex. You can call this method iteratively on
  * all vertices to get all edges.
  * 
  * @param vertex
  *            source vertex
  * @return List<V> list of adjacent vertices
  */
 public List<V> getAdjacentVertices(V vertex) {
  List<Node<V>> adjacentNodes = this.adjacencyList.get(vertex);
  List<V> neighborVertex = new ArrayList<>();

  if ((adjacentNodes != null) && !adjacentNodes.isEmpty()) {
   for (Node<V> v : adjacentNodes) {
    neighborVertex.add(v.getName());
   }
  }
  return neighborVertex;
 }

 /**
  * Returns the unmodifiable collection of all vertices of the graph
  * 
  * @return Set<V>
  */
 public Set<V> getAllVertices() {
  return Collections.unmodifiableSet(this.vertices);
 }

 /**
  * Remove vertex and it's relationship from the graph. Also remove vertex
  * from the vertices set
  * 
  * 
  * 1---->2---->3 removeVertex(2) will leave graph as 1 3 It will remove 2 as
  * well as it's relationship
  * 
  * @param vertex
  */
 public boolean removeVertex(V vertex) {
  Objects.requireNonNull(vertex);

  if (!this.vertices.contains(vertex))
   return false;

  Iterator<Entry<V, List<Node<V>>>> itr = this.adjacencyList.entrySet()
    .iterator();

  while (itr.hasNext()) {
   Entry<V, List<Node<V>>> e = itr.next();
   List<Node<V>> vs = e.getValue();
   // remove vertex if it's found as a key in map
   if (vertex.equals(e.getKey())) {
    itr.remove();
   }

   Iterator<Node<V>> listIterator = vs.iterator();
   while (listIterator.hasNext()) {
    Node<V> ver = listIterator.next();
    // remove vertex if it's found as a value in mapped list
    if (vertex.equals(ver.getName())) {
     listIterator.remove();
    }
   }
  }

  // remove vertex from vertices collection
  Iterator<V> itrVertices = this.vertices.iterator();
  while (itrVertices.hasNext()) {
   if (vertex.equals(itrVertices.next())) {
    itrVertices.remove();
    break;
   }
  }
  return true;
 }

 /**
  * Returns graph as a string returns set of edges and vertices
  */
 public String toString() {
  StringBuilder sb = new StringBuilder();
  sb.append("Set of Edges :\n");
  for (V v : this.adjacencyList.keySet()) {
   List<Node<V>> neighbour = this.adjacencyList.get(v);
   for (Node<V> vertex : neighbour) {
    if (vertex.getWeight() != DEFAULT_WEIGHT) {
     sb.append(v + " -- (" + vertex.getWeight() + ")--->"
       + vertex.getName() + "\n");
    } else {
     sb.append(v + " ------->" + vertex.getName() + "\n");
    }

   }
  }
  sb.append("& Set of vertices :" + this.getAllVertices());
  return sb.toString();
 }

 /**
  * Method to unit test
  */
 public static void main(String[] args) {
  Graph<String> graph = new Graph<String>();
  graph.addEdge("BLR", "SFO", 100);
  graph.addEdge("BLR", "HK", 50);
  graph.addEdge("BLR", "LA", 70);
  graph.addEdge("LA", "SFO", 20);
  graph.addEdge("HK", "LA", 60);

  System.out.println(graph.toString());

  System.out.println("\n Path between BLR and LA exists ? :"
    + graph.hasRelationship("BLR", ""));

  System.out.println(" Remove vertex BLR ? " + graph.removeVertex("LA"));
  System.out.println(graph.toString());
 }
}


Output:
Set of Edges :
HK -- (60)--->LA
LA -- (20)--->SFO
BLR -- (100)--->SFO
BLR -- (50)--->HK
BLR -- (70)--->LA
& Set of vertices :[HK, LA, BLR, SFO]

 Path between BLR and LA exists ? :false
 Remove vertex BLR ? true
Set of Edges :
BLR -- (100)--->SFO
BLR -- (50)--->HK

& Set of vertices :[HK, BLR, SFO]

5 comments:

  1. Wouldn't the following two lines create 2 separate nodes for the same string "LA":
    graph.addEdge("BLR", "LA", 70);
    graph.addEdge("HK", "LA", 60);

    If your graph contained the following map, you would have just one node with a particular string "LA" in your full map:
    Map, Map, weght>> adjacencyList

    ReplyDelete
    Replies
    1. Yeah, you are right. There will be two entries in the map. This conceptually makes sense by agree it's not space efficient.

      Delete
  2. Map< Node < V >, Map< Node < V >, Weight>> adjacencyList

    ReplyDelete
    Replies
    1. Yeah, multi map is a good option, but it makes things confusing. While implementing graph it makes sense to make data structure simpler so that solving the actual problem is not very tricky.

      3rd party libraries which has support of multi map through API will be a more suitable option.

      Delete
  3. This comment has been removed by the author.

    ReplyDelete