How to create a graph using Java

How to create a graph using Java

How to create a graph using Java  

Let's see simple graph creation using core java and printing all the vertex along with list of edges which goes from that particular Vertex.

public class MyGraph {

 public static void main(String[] args) {
  
  /* Initilize graph with 5 vertex and as 
   * going to be directed graph
   */
  
  Graph myGra = new Graph(5, "directed");
  
  /*
   * Add vertex 
   */
  myGra.addVertex("A");
  myGra.addVertex("B");
  myGra.addVertex("C");
  myGra.addVertex("D");
  myGra.addVertex("E");
  
  /*
   * Add edges between each vertex and their distance 
   */
  myGra.addEdge("A", "B",5);
  myGra.addEdge("A", "E",1);
  myGra.addEdge("B", "C",2);
  myGra.addEdge("C", "D",2);
  myGra.addEdge("E", "D",2);
  myGra.addEdge("E", "A",2);
  
  // Print the created graph
  myGra.printMyGraph();
  
 }
}

public class Graph {

 // Graph direction (directed / undirected graph)
 private boolean undirected = true;
 
 // No. of vertex in the graph
 private Vertex[] arrayOfVertex;
 
 private int indexCounter = 0;
 
 // Constructor to create graph vertex 
 public Graph(int noOfVertex, String graphType) {
  if (graphType.equalsIgnoreCase("directed")) {
   this.undirected = false;
  }
  arrayOfVertex = new Vertex[noOfVertex];
 }
 
 // Vertex class
 class Vertex {
  // Name of the Vertex
  private String name;
  
  // Holds the list of all edges from current vertex 
  private Edge edge;

  // Create vertex 
  public Vertex(String name, Edge aNode) {
   this.name = name;
   this.edge = aNode;
  }
 }
 
 // Edge between 2 Vertex
 class Edge {
  // Destination vertex Id
  private int vertexId;
  
  // In list point to next edge if its else null 
  private Edge next;
  
  // Weight of current edge
  private int weight;

  // Create edge
  public Edge(int vertexId, Edge next, int weight) {
   this.vertexId = vertexId;
   this.next = next;
   this.weight = weight;
  }
 }

 // Adding Vertex 
 public void addVertex(String vertexName) {
  arrayOfVertex[indexCounter] = new Vertex(vertexName, null);
  indexCounter++;
 }

 // Adding Edge
 public void addEdge(String sVertex, String dVertex, int weight) {
  int sId = indexOfName(sVertex);
  int dId = indexOfName(dVertex);

  /*
   * Find source and destination vertexId and create new Edge and 
   * point it to source edge link
   */
  arrayOfVertex[sId].edge = new Edge(dId, arrayOfVertex[sId].edge, weight);
  
  /*
   * If undirected then create 2 edge's between source and destination and 
   * destination to source 
   */
  if (undirected) {
   arrayOfVertex[dId].edge = new Edge(sId, arrayOfVertex[dId].edge, weight);
  }
 }

 /*
  * Getting indexId of given vertex name
  */
 private int indexOfName(String name) {
  for (int v = 0; v < arrayOfVertex.length; v++) {
   if (arrayOfVertex[v].name.equals(name)) {
    return v;
   }
  }
  return -1;
 }

 /*
  * Print the graph in vertex order and listing all outgoing edges from that vertex
  */
 public void printMyGraph() {
  System.out.println("VERTEX\t----> EDGES WITH WEIGHT");
  for (int v = 0; v < arrayOfVertex.length; v++) {
   System.out.print(arrayOfVertex[v].name +" \t ----> ");
   for (Edge aNode = arrayOfVertex[v].edge; aNode != null; aNode = aNode.next) {
    System.out.print( "<==>"+ arrayOfVertex[aNode.vertexId].name + ":" + aNode.weight);
   }
   System.out.println();
  }

 }
}

OUTPUT:

VERTEX         ----> EDGES WITH WEIGHT
A          ----> <==>E:1<==>B:5
B          ----> <==>C:2
C          ----> <==>D:2
D          ----> 
E          ----> <==>A:2<==>D:2

How to print singly linked list in reverse order

How to print singly linked list in reverse order

Reverse Linked List  

If we talk about Singly Linked List then it will be a 1 way traversal from head node to tail node. But if we need to print the linked list values from tail node to head node (in reverse order) with O(N) time complexity. ???

• Its simple just we need to apply recursive algorithm where we need to start from head node and reach tail which is last node.
• Next print each node values in recursive call. By this way we can achieve printing linked list in recursive order without traversing more than once which is by time complexity O(N) only. 

Lets see simple code to create Singly Linked List and printing same Linked List in reverse order with O(N) complexity.

class NODE {

 int data;
 NODE next;

 public NODE(int data) {
  this.data = data;
  this.next = null;
 }
}

public class PrintLinkedList {

 public static void main(String[] args) {

  PrintLinkedList obj = new PrintLinkedList();
  int val[] = new int[] { 1, 5, 7, 10, 89 };

  NODE head = obj.createLinkedList(val);
  obj.printLLInReverse(head);
 }

 /*
  * Recursive method to print LL in reverse order
  */
 public void printLLInReverse(NODE tmp) {
  if (tmp != null) {
   printLLInReverse(tmp.next);
   System.out.println(tmp.data);
  }
 }

 /*
  * Create linked list based on given array
  */
 public NODE createLinkedList(int val[]) {
  NODE start = null;
  for (int i : val) {
   NODE tmp = new NODE(i);
   if (start == null) {
    start = tmp;
   } else {
    NODE mover = start;
    while (mover.next != null) {
     mover = mover.next;
    }
    mover.next = tmp;
   }
  }
  return start;
 }
}

OUTPUT:

89
10
7
5
1

How to Design a simple LRU cache in Java

How to Design a simple LRU cache in Java

LRU  

Design and implement a data structure for Least Recently Used (LRU) cache by supporting set() and get() operations with O(1) complexity. 

Least Recently Used (LRU) Cache?

Its a caching mechanism where we evicts least recently used items from the cache to accommodate new entries at top. So in that case in cache we maintain only the recently used data and least used entries will be evicted once we need to set new value in cache. 

How to implement simple LRU Cache?

We can implement by using multiple data structure like stack, Queue, LinkedList etc., 
Now in this tutorial lets see how to implement by using Doubly LinkedList and map to hold the LinkedList nodes which makes O(1) complexity for our read / get() operation.

Steps:

• NodeLRU class which holds the data, next and previous node values.
• In LRUCache setting cache size as 5 to make it simple 
• set() method will check already value present in map or not. If its present remove the existing value from map and LinkedList and add the new value in LinkedList and map.
• get() method will fetch node if present in map and return the values or else return -1 if not present. 
• Once we get the value the node will be shifted to the head of LinkedList to make it as recently used. 

By this way we can implement the LRU cache with simple logic by using LinkedList and map. Lets see the java implementation for the same

import java.util.HashMap;
import java.util.Map.Entry;

/*
 * LinkedList node to hold the cached data
 */
class NodeLRU {
 int data;
 NodeLRU next;
 NodeLRU previous;

 public NodeLRU(int data) {
  this.data = data;
  this.next = null;
  this.previous = null;
 }
}

/**
 * Implementing LRU Cache using LinkedList and HashMap to get() value with O(1) 
 * time complexity.
 */
class LRUCache {

 // Total cache size 
 private final static int CACHE_SIZE = 5;

 // Map to hold the cached nodes
 private HashMap<Integer, NodeLRU> map = new HashMap<Integer, NodeLRU>(CACHE_SIZE);
 
 // Doubly LinkedList head and tail node pointer
 private NodeLRU head = null;
 private NodeLRU tail = null;

 /*
  * Set method which will add data into LinkedList
  * and if already key present then remove and ADD as new element.
  */
 public void set(int key, int val) {
  if (map.containsKey(key)) {
   removeExistingNode(key, val);
   set(key, val);
  } else {
   addNode(key, val);
  }
 }

 /*
  * Get method which will return node data if present
  * else returns -1. Once if data node present in map then
  * Fetch the node and place it @ head location. 
  */
 public int get(int key) {
  if (map.containsKey(key)) {
   NodeLRU node = map.get(key);
   makeAsRecentUsed(node);
   return node.data;
  }
  return -1;
 }
 
 /*
  * One if node present via get() method then 
  * pick out the node and stitch with head location as first node.
  * 
  */
 private void makeAsRecentUsed(NodeLRU node) {
  if (node.equals(head)) {
   return;
  } else if (node.equals(tail)) {
   tail.previous.next = null;
   tail = tail.previous;
  } else {
   node.previous.next = node.next;
   node.next.previous = node.previous;
  }
  node.previous = null;
  node.next = head;
  head.previous = node;
  head = node;
 }

 /*
  * Delete the least used node frm LinkedList and map
  */
 private void removeExistingNode(int key, int val) {
  NodeLRU tmp = map.get(key);
  if (tmp.next != null && tmp.previous != null) {
   tmp.previous.next = tmp.next;
   tmp.next.previous = tmp.previous;
  } else if (tmp.equals(tail)) {
   removeLeastUsed();
  } else if (tmp.equals(head)) {
   removeHeadNode();
  }
 }

 /*
  * Removing 1st node
  */
 private void removeHeadNode() {
  NodeLRU firstNode = head;
  tail = tail.next;
  tail.previous = null;
  removeFromMap(firstNode);
 }
 
 /*
  * Adding new node to LinkedList
  */
 private void addNode(int key, int val) {
  if (map.size() < CACHE_SIZE) {
   NodeLRU tmp = new NodeLRU(val);
   if (head == null && tail == null) {
    head = tail = tmp;
   } else {
    head.previous = tmp;
    tmp.next = head;
    head = tmp;
   }
   map.put(key, tmp);
  } else {
   removeLeastUsed();
   addNode(key, val);
  }
 }

 /*
  * Removing least/ last node from LinkedList
  */
 private void removeLeastUsed() {
  NodeLRU leastUsed = tail;
  tail = tail.previous;
  tail.next = null;
  removeFromMap(leastUsed);
 }

 /*
  * Removing from map also based on value node
  */
 private void removeFromMap(NodeLRU node) {
  for (Entry<Integer, NodeLRU> entry : map.entrySet()) {
   if (entry.getValue().equals(node)) {
    map.remove(entry.getKey());
    return;
   }
  }
 }

 /*
  * Method to print all LinkedList nodes data
  */
 public void printValueFromCache() {
  NodeLRU tmp = head;
  System.out.print("CACHE VALUES : ");
  while (tmp != null) {
   System.out.print(tmp.data + ", ");
   tmp = tmp.next;
  }
  System.out.println();
 }

 public static void main(String[] args) {

  LRUCache obj = new LRUCache();
  
  // Adding 1 to 5 values to cache
  obj.set(1, 11);
  obj.set(2, 12);
  obj.set(3, 13);
  obj.set(4, 14);
  obj.set(5, 15);

  obj.printValueFromCache();
  
  /*
   *  Reading value with key (1) which we adding 1st and
   *  placed last in LL. Once we read same value (Node) should 
   *  be placed as recent and moved to top of linked List.
   */
  
  int val = obj.get(1);
  System.out.println("READ VALUE : "+val);

  obj.printValueFromCache();
  
  /*
   * Adding some more values to Cache. Since we set cache size as 5
   * least used 3 nodes like (2,3,4) need to removed and (6,7,8)
   * values need to added to linked list 
   */
  obj.set(6, 66);
  obj.set(7, 77);
  obj.set(8, 88);

  obj.printValueFromCache();
  
  /*
   * Reading again with key (5) which makes node to shift to head
   * which will be recently used
   */
  val = obj.get(5);
  System.out.println("READ VALUE : "+val);

  obj.printValueFromCache();

 }
}

OUTPUT:

CACHE VALUES : 15, 14, 13, 12, 11, 
READ VALUE : 11
CACHE VALUES : 11, 15, 14, 13, 12, 
CACHE VALUES : 88, 77, 66, 11, 15, 
READ VALUE : 15
CACHE VALUES : 15, 88, 77, 66, 11, 

Simple, how to get only left child in BST

Simple, how to get only left child in BST

Simple  

As same as traversals like inorder, preorder, postorder and level order we need to traverse to BST and need to print only the left child of each nodes in Binary Search Tree.
From below example we need to get only the nodes including root nodlike 11, 6, 4, 17, 31

Solution:

• Place the root node in Queue.
• Iterate Queue until queue becomes empty. 
• Next Enqueue the child nodes left and right nodes inside same queue and print only the left node values. 
• Repeat the process for each leaf node.

class Node {
 Node left, right;
 int data;

 public Node(int data) {
  this.data = data;
 }
}

public class LeftNodes {

 public static void main(String[] args) {

  int a[] = { 4, 5, 3, 8, 7, 6, 100, 9, 3, 2, 1 };

  Node root = null;
  LeftNodes tree = new LeftNodes();

  for (int i = 0; i < a.length; i++) {
   root = tree.insertNode(root, a[i]);
  }
  tree.printLeftNodes(root);
 }

 public void printLeftNodes(Node root) {

  if (root == null)
   return;

  Queue<Node> queue = new LinkedList<Node>();
  queue.add(root);
  System.out.println(root.data);

  while (queue.size() > 0) {
   Node current = queue.poll();
   if (current.left != null) {
    System.out.println(current.left.data);
    queue.add(current.left);
   }
   if (current.right != null) {
    queue.add(current.right);
   }
  }
 }

 public Node insertNode(Node root, int data) {
  Node currentNode = new Node(data);
  if (root == null) {
   root = currentNode;
  } else {
   insertData(currentNode, root);
  }
  return root;
 }

 public Node insertData(Node newNode, Node root) {

  if (root.data < newNode.data) {
   if (root.right == null) {
    root.right = newNode;
   } else {
    return insertData(newNode, root.right);
   }
  } else if (root.data > newNode.data) {
   if (root.left == null) {
    root.left = newNode;
   } else {
    return insertData(newNode, root.left);
   }
  }
  return root;
 }
}

OUTPUT:

4
3
2
1
7
6
9

How to do Level order traversal in Binary Search Tree

How to do Level order traversal in Binary Search Tree

Level order traversal  

We have see lot of tutorials based on Binary tree and also other traversals like Inorder, Preorder and Postorder etc.,

Now in this tutorial lets see how to do Level order traversal of Binary Search Tree using Queue. From the given below tree we need to get output as F, D, J, B, E, G, K, A, C I, H

Solution:

• Place the root node in Queue.
• Iterate Queue until queue becomes empty. Dequeue the first node from Queue and print the value of that node.
• Next Enqueue the child nodes left and right nodes inside same queue. 
• Repeat the process until each leaf node. 

Here in above example first we need to place 'F' node inside queue. Next in loop we need to print 'F' and get the child nodes 'D' and 'J' and enqueue inside same queue. Repeat the process until all leaf nodes and when Queue becomes empty.

class Node {
 Node left, right;
 int data;

 public Node(int data) {
  this.data = data;
 }
}

public class LevelOrderTraversal {
 
 public static void main(String[] args) {

  int a[] = { 11, 6, 19, 4, 8, 5, 43, 49, 10, 31, 17, 5 };

  Node root = null;
  LevelOrderTraversal tree = new LevelOrderTraversal();

  for (int i = 0; i < a.length; i++) {
   root = tree.insertNode(root, a[i]);
  }
  tree.levelOrderTraversal(root);
 }

 public void levelOrderTraversal(Node root) {

  if (root == null)
   return;

  Queue<Node> queue = new LinkedList<Node>();
  queue.add(root);
  System.out.println(root.data);

  while (queue.size() > 0) {
   Node current = queue.poll();
   if (current.left != null) {
    System.out.println(current.left.data);
    queue.add(current.left);
   }
   if (current.right != null) {
    System.out.println(current.right.data);
    queue.add(current.right);
   }
  }
 }

 public Node insertNode(Node root, int data) {
  Node currentNode = new Node(data);
  if (root == null) {
   root = currentNode;
  } else {
   insertData(currentNode, root);
  }
  return root;
 }

 public Node insertData(Node newNode, Node root) {

  if (root.data < newNode.data) {
   if (root.right == null) {
    root.right = newNode;
   } else {
    return insertData(newNode, root.right);
   }
  } else if (root.data > newNode.data) {
   if (root.left == null) {
    root.left = newNode;
   } else {
    return insertData(newNode, root.left);
   }
  }
  return root;
 }
}

OUTPUT:

11
6
19
4
8
17
43
5
10
31
49