Tag: java

Observer Pattern

January 8th, 2023

Observer pattern is one of the behavioral design patterns used in object oriented world of programming.

Definition – Observer pattern defines a one-to-many relationship between objects. When state of one object changes, all the dependent objects are notified and updated.

There is a Subject interface and a ConcreteSubject that implements the Subject interface. There is an Observer interface and multiple observers implementing that interface. Observers use the Subject interface to register and unregister and also to get notified about the changes. Observer interface generally has one function that is called by the Subject whenever there is a state change.

One way to visualize this is the newspaper subscription in the real world. As soon as a newspaper is published, all the subscribers get the new copy.

In java, common example of observer pattern are Observer interface, EventListeners in awt and swing, Observable, JMS etc.

Best to use an example to understand this pattern.

Usecase – Let’s say there is a pantry containing items. And there are different shopping lists based on different stores we visit. As soon as any item in pantry finishes we want to add that item to all the shopping lists.

Visualizing Observer Pattern for Shopping list

Pantry is our subject. KitchenPantry is concrete subject implementing the Pantry interface. SuperStoreList is our observer interface. CostcoList and WalmartList are our observer. Both observers can register using the attach method and deregister using the detach method. As soon as the item is removed from KitchenPantry, it will be added both the observer’s lists using the update method. KitchenPantry will use notify to call that update method.

public interface Pantry
{

      public void attach(SuperStoreList list);
      public void detach(SuperStoreList list);
      public void notify();
}

public interface SuperStoreList 
{
      public void update(String item);
}

public class KitchenPantry implements Pantry
{
      private List<SuperStoreList> superStores;
      private String item;

      public KitchenPantry()
      {
             superStores = new ArrayList<SuperStoreList>();
      }
      
      public void attach(SuperStoreList list)
      {
              superStores.add(list);
      }

      public void attach(SuperStoreList list)
      {
              superStores.remove(list);
      }

      public void notify(String item)
      {
              for(SuperStoreList list: superStores)
              {
                    list.update(item);
              }
      }

      public void setItem(String item)
      {
              this.item = item;
              itemAdded();
      }

      public void itemAdded()
      {
              notify(item);
      }


      public String getItem()
      {
              return this.item;
      }

}

public class CostcoList implements SuperStoreList
{

      private List<String> costcoList;
      private KitchenPantry kitchenPantry;

      CostcoList(KitchenPantry kitchenPantry)
      {
           costcoList = new ArrayList<String>();
           this.kitchenPantry = kitchenPantry;
           kitchenPantry.attach(this);
      }

      public void update(String item)
      {
           costcoList.add(item)
      }

      public void display()
      {
          System.out.println("Costco list : ");
          for(String item : costcoList)
          {
               System.out.println(item);
          }
      }
}

public class WalmartList implements SuperStoreList
{

      private List<String> walmartList;
      private KitchenPantry kitchenPantry;

      CostcoList(KitchenPantry kitchenPantry)
      {
           walmartList = new ArrayList<String>();
           this.kitchenPantry = kitchenPantry;
           kitchenPantry.attach(this);
      }

      public void update(String item)
      {
           walmartList.add(item)
      }

      public void display()
      {
          System.out.println("Walmart list : ");
          for(String item : walmartList)
          {
               System.out.println(item);
          }
      }
}

public class App
{
       public static void main(String[] args)
       {
             KitchenPantry kitchenPantry = new KitchenPantry();
             CostcoList costcoList = new CostcoList(kitchenPantry);
             WalmartList walmartList = new WalmartList(kitchenPantry);

             kitchenPantry.setItem("milk");

             costcoList.display();
             walmart.display();
}

Hope this helps. Thanks for stopping by.

Longest Substring Without Repeating Characters

February 20th, 2020

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb" 
Output: 3 
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: "bbbbb" 
Output: 1 
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: "pwwkew" 
Output: 3 
Explanation: The answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

Bruteforce Solution

The BruteForce solution is to find all the substrings in the string and then check if they contain unique characters and updating the result with maximum of result and substring’s length. Finding all substrings of the strings require two loops and so that itself will be O(n^2). Checking if the founded substring is unique is another O(n) and so total time complexity is O(n^3), n being length of string.

As we are using a HashSet to store the letters of the substring, the space complexity will be O(n), n being length of string.

/*
Time Complexity - O(n^3)
Space Complexity - O(n)
*/

class LengthOfLongestSubStringBrute {
    
    public int lengthOfLongestSubstring(String s) {
        
        //Initialize the length of result substring with zero
        int ans = 0;
        
        //Loop i from 0 to length of string and
        //loop j from i+1 to length of string 
        //to get each and every substring 
        for(int i = 0; i < s.length(); i++){
            for(int j = i+1; j <= s.length(); j++){
                
                //Check if substring has all unique characters
                if(findIfUniqueSubstring(s, i, j)){
                    
                    //Update the result with the length of current substring
                    ans = Math.max(ans, j - i);
                }
            }
        }
        
        //return the answer
        return ans;
    }
    
    public boolean findIfUniqueSubstring(String s, int start, int end){
        
        //Initialize a HashSet to store the characters
        HashSet<Character> set = new HashSet<Character>();
        
        //Loop from starting index to ending index
        for(int i = start; i < end; i++){
            char c = s.charAt(i);
            
            //if the set contains present character then return false
            //else add the character to set.
            if(set.contains(c))
                return false;
            set.add(c);
        }
        
        //if all characters in substring are uniuq, return true;
        return true;
    }
}

Optimized Solution 1

Using HashSet as sliding window we can reduce the complexity from O(n^3) to O(n).

We start both i and j from 0. Add the jth character to HashSet if it is not present and update length to maximum of length and (j-i). Increment j. If jth character is present in HashSet, we remove the ith character and increment i. We continue this until both i and j are less than input length. The time and space complexity for this solution is O(n)

/* 
Time Complexity - O(n)
Space Complexity - O(n)
*/

class LengthOfLongestSubstringOptimized {
    
    public int lengthOfLongestSubstring(String s) {
        
        //Initialize the length of result substring with zero
        int ans = 0, i = 0, j = 0;
        
        //Initialize a HashSet to store the characters
        HashSet<Character> set = new HashSet<Character>();
        
        //Loop i from 0 to length of s and
        //loop j from 0 to length of s 
        //to get each and every substring 
        while(i < s.length() && j < s.length()){
            
            //if character at jth position is not present in set
            if(!set.contains(s.charAt(j))){
                
                //add the character to the set and set result 
                //to length of substring till now.
                set.add(s.charAt(j++));
                ans = Math.max(ans, j-i);
            }
            else{
                //remove the character at ith position and increment i;
                set.remove(s.charAt(i++));
            }
        }
        //return the answer
        return ans;
    }
        
        
}

Optimized Solution 2

This solution uses HashMap instead of HashSet. The time and space complexity is still O(n). Here we store the index of current character in hashmap. If we encounter a repeat character we update the value of i to the maximum of i and current characters(jth) index.

/* 
Time Complexity - O(n)
Space Complexity - O(n)
*/

class LengthOfLongestSubstringOptimized2 {
    
    public int lengthOfLongestSubstring(String s) {
        
        //Initialize the length of result substring with zero
        int ans = 0, i = 0, j = 0;
        
        //Initialize a HashMap to store the characters
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        
        //loop j from 0 to length of s 
        //to get each and every substring 
        for(j = 0; j < s.length(); j++){
            
            //if map contains jth character
            if(map.containsKey(s.charAt(j))){
                //update i to the index of 
                i = Math.max(i, map.get(s.charAt(j)));
            }
            
            //put the character in map with index
            map.put(s.charAt(j), j+1);
            ans = Math.max(ans, j-i+1);
        }
        
        //return the answer
        return ans;
    }
        
        
}

Source – LeetCode

SourceCode – Github

[Java] Comparable vs Comparator

July 31st, 2017

Arrays class in Java has a sort method which takes in an array and returns the sorted array. It works well for arrays of primitive types like int, char, float, double, etc., and even for String. But returns an error when we want to sort an array of objects.

Comparable

Consider the following example: Suppose we have a Player class which stores the player’s name, age, weight and number of his/her wins.

/**
* Player --- store the players information
*/
class Player{

	private String name;
	private int age;
	private int weight;
	private int wins;

	Player(String name, int age, int weight, int wins){
		this.name = name;
		this.age = age;
		this.weight = weight;
		this.wins = wins;
	}

	//Getter method for name
	public String getName(){
		return name;
	}

	//Setter method for name
	public void setName(String n){
		name = n;
	}

	//Getter method for age
	public int getAge(){
		return age;
	}

	//Setter method for age
	public void setAge(int a){
		age = a;
	}

	//Getter method for weight
	public int getWeight(){
		return weight;
	}

	//Setter method for weight
	public void setWeight(int w){
		weight = w;
	}

	//Getter method for wins
	public int getWins(){
		return wins;
	}

	//Setter method for wins
	public void setWins(int wi){
		wins = wi;
	}

	public String toString(){
		String msg = name + " " + age + " " + weight + " " + wins;
		return msg; 
	}
}

We want to sort an array of such players according to their names in ascending order. We can do this by using Arrays.sort(Object[] array) method.

public static void main(String[] args){
               Player[] players = { new Player("John", 23, 45, 5),
				    new Player("Andy", 20, 55, 7),
	    			    new Player("Mani", 25, 47, 2),
	 			    new Player("Bob", 19, 49, 9),
				    new Player("Holly", 21, 50, 2)
							};

		Arrays.sort(players);

                for(Player p: players)
			System.out.println(p.toString());
}

But we receive an error when we run the above code:

Exception in thread "main" java.lang.ClassCastException: Player cannot be cast to java.lang.Comparable
	at java.util.ComparableTimSort.countRunAndMakeAscending(ComparableTimSort.java:320)
	at java.util.ComparableTimSort.sort(ComparableTimSort.java:188)
	at java.util.Arrays.sort(Arrays.java:1246)
	at PlayerComparable.main(PlayerComparable.java:86)

This error occurred because we didn’t define the criteria according to which the objects must be sorted.

To sort objects, we have to compare them on the basis of their property. And to compare objects we need to make our object implement the Comparable interface and override its compare method.

Therefore, our class now implements the comparable interface and overrides the compare method which compares the name of the current object with the name of the passed object using the String’s compareTo method and returns the result accordingly.

class Player implements Comparable<Player>{

	private String name;
	private int age;
	private int weight;
	private int wins;

	Player(String name, int age, int weight, int wins){
		this.name = name;
		this.age = age;
		this.weight = weight;
		this.wins = wins;
	}

	//Getter method for name
	public String getName(){
		return name;
	}

	//Setter method for name
	public void setName(String n){
		name = n;
	}

	//Getter method for age
	public int getAge(){
		return age;
	}

	//Setter method for age
	public void setAge(int a){
		age = a;
	}

	//Getter method for weight
	public int getWeight(){
		return weight;
	}

	//Setter method for weight
	public void setWeight(int w){
		weight = w;
	}

	//Getter method for wins
	public int getWins(){
		return wins;
	}

	//Setter method for wins
	public void setWins(int wi){
		wins = wi;
	}

	@Override
	public int compareTo(Player p){
	 	return name.compareTo(p.getName());
	}

	public String toString(){
		String msg = name + " " + age + " " + weight + " " + wins;
		return msg; 
	}
}

Now when we sort the array using Arrays.sort(players), the players are sorted in ascending order of their names:

Andy 20 55 7
Bob 19 49 9
Holly 21 50 2
John 23 45 5
Mani 25 47 2

Comparator

The comparable interface allows us to sort an object based on only one property. Another way to compare objects is to create a Comparator class using the Comparator interface. This method allows us to sort based on multiple properties of an object. So, using Comparator we can sort based on age, weight, and number of wins.

Suppose we want to sort the array on the basis of Player’s age. We can do that by creating a class AgeComparator which implements Comparator interface and overrides its compare method. In that method, we compare the ages of both objects and returns the result accordingly. Here I converted the primitive int values to Integer values and called the Integer’s compareTo method on them.

class AgeComparator implements Comparator<Player> {

	@Override
	public int compare(Player a, Player b){
		return new Integer(a.getAge()).compareTo(new Integer(b.getAge()));
	}
}

Player[] players = { new Player("John", 23, 45, 5),
							 new Player("Andy", 20, 55, 7),
							 new Player("John", 25, 47, 2),
							 new Player("Bob", 19, 49, 9),
							 new Player("Holly", 21, 50, 2)
							};
		Arrays.sort(players, new AgeComparator());

		for(Player p: players)
			System.out.println(p.toString());

Now we call Arrays.sort(array, comparator) method for the player’s array. This method now sorts the array based on ages of the players.

Bob 19 49 9
Andy 20 55 7
Holly 21 50 2
John 23 45 5
John 25 47 2

Similarly, we can write comparators to sort the array according to weight and wins. Example:

class WeightComparator implements Comparator<Player> {

	@Override
	public int compare(Player a, Player b){
		return new Integer(a.getWeight()).compareTo(new Integer(b.getWeight()));
	}
}

class WinsComparator implements Comparator<Player> {

	@Override
	public int compare(Player a, Player b){
		return new Integer(a.getWins()).compareTo(new Integer(b.getWins()));
	}
}

We can even sort on the basis of more than one property using the comparator. One example is to sort Players according to their names and wins. If names are same, we sort the objects in decreasing order of their wins. We can do this by first comparing the string names of two players. If names are same then only we compare the wins of two players and return the result accordingly.

class NameWinsComparator implements Comparator<Player>{
	@Override
	public int compare(Player a, Player b){
		String nameA = a.getName();
		String nameB = b.getName();

		if(nameA.equals(nameB))
			return new Integer(b.getWins()).compareTo(new Integer(a.getWins()));
		else
			return nameA.compareTo(nameB);
	}
}

The output for the player’s array is:

Andy 20 55 7
Bob 19 49 9
Holly 21 50 2
John 23 45 5
John 25 47 2

Here the last two elements have the same name John and they are sorted according to their wins in decreasing order.

Code for this post: PlayerComparable, PlayerComparator

Summary

Based on the above discussion the comparison between comparable and comparator can be summarized as below:

java comparable vs comparator — Table 1: Comparable vs Comparator

If you have any questions and suggestions, please write them in the comments below.

Thanks for stopping by. See you in the next post.

Graph Search: Breadth First Search

July 24th, 2017
In the previous post, we discussed Depth First Search and its implementation in Java. In this post, we learn how to use Breadth First Search to find whether there exists a path between two vertices in a graph.

Again for this post also, we will create a graph for a directed unweighted graph as an adjacency list using the concepts discussed in this previous post. Then apply BFS on it.

How does Breadth First Search (BFS) work?

We have source node and a destination node in a graph. Our motive is to find a path between them. So we call BFS on our source and destination. In DFS, we traverse from node to its child, then to its grandchild and so on. In BFS we go level by level. First, we go through the first node(first layer), then it’s children (second layer) followed by its grandchildren(third layer) and so on until we reach the destination or we have traversed every node.

Here we first add the first node to a queue. Then check whether the first node in our queue is the destination. If yes, it returns true. Else remove the node from the queue. If the node is not in the visited set, add them to the visited set. Then we add the node’s children to our queue. Repeat the above process for every node in queue. If after traversing all nodes we don’t get a path, we return false.

Fig 1: Directed Graph

Fig 2: Adjacency List of Graph in Fig 1.

Consider the graph in Fig 4. We have to find whether a path exists between A and H.

First, we check if start is destination ie A is a destination. It is not. So we move on to A’s children B and F and check them sequentially whether they are the destination (Orange Color). They are not, so we traverse B’s children followed by F’s children i.e., C, F (Green Color), and G(Yellow Color). Next we traverse C’s, F’s and G’s children. We continue in this way till we reach our destination node H.

Fig. 3: BFS on the graph in FIg 1. Each color representing a level. Blue representing the source and destination node.

Implementation

Now we code the above concept in Java. I will break down the code into few simple steps for ease in understanding

Step 1: Create a Node class, which stores the Node’s id of primitive type along with a LinkedList/ArrayList to store adjacency list of that node.

Step 2: Create a HashMap/ArrayList to store the vertices of a graph as Node objects. Here we can create a global variable to store graph or locally in methods and then pass them as parameters. Till now, we created a global variable for the graph, for the next two videos we will create a graph in a method and pass it as parameters.

Step 3: Add all the edges into the graph by updating the adjacency list of source nodes.

Step 4: Write method to find whether a path exists between source and destination using BFS.

Now we go through each step in detail:

Step 1:

Create a Node class, which stores the Node id/name/label of primitive type along with a LinkedList/ArrayList to store adjacency list of that node. For a detailed explanation refer to this post.
```
        /**
	* Node --- class to store each vertex along with its adjacent vertices
	*/
	static class Node{		
		
		private String id;
		private LinkedList<Node> adjacent;
		
		public Node(String id){
			this.id = id;
			adjacent = new LinkedList<Node>();
		}
		
		//Getter method for start vertex
		public String getId(){
			return id;
		}
		
		//Getter method for end vertex
		public LinkedList<Node> getAdjacent(){
			return adjacent;
		}
		
		//add node to the adajcent list
		public void addAdjacent(Node vertex){
			adjacent.add(vertex);
		}

		//To print Node 
        public String toString(){
     		String msg = id + " : ";
        	for(Node node: adjacent)
        		msg = msg + node.id + " ";
        	return msg;
                }
	}
```
Step 2:

Create a HashMap/ArrayList to store the vertices of a graph as Node objects.

In our example graph in Fig 1, we have string nodes. So our HashMap will have keys of type String and Values of type Node.
```
    /**
    * Creates a HashMap with string key and Node value
    * @param input list of edges
    * @return HashMap<String,Node>
    */ 
	public static HashMap<String, Node> createGraph(String[] input){
		HashMap<String, Node> graph = new HashMap<String, Node>();
		Node node;
		for(String s: input){
			String first = String.valueOf(s.charAt(0));
			String second = String.valueOf(s.charAt(1));
			add(graph, first, second);
		}
		return graph;
	}
```
Step 3:

Add all the edges into the graph by updating the adjacency list of source nodes.

Our input is an array of strings where each string “XY” represents an edge from X to Y. So we traverse our list and do the following three steps on each of the string values.
```
//Input edges of the graph.
		 {"AB","AE","BC","BF","CG","CD","EF","FG","GH","DH"};
```
Part 1: First we separate X and Y from our string “XY”. We can do that by using the String’s charAt(index) method and assign them to a first and second variable. Then add the edge to our graph by calling the add method.
```
	public static void add(HashMap<String, Node> graph, String source, String destination){

		//Get nodes corresponding to source and destination vertices.
		Node s = getNode(graph, source);
		Node d = getNode(graph, destination);

		//add nodes to adjacent list
		s.addAdjacent(d);
	}
```
Part 2: We access the node corresponding to string X and Y in the graph. If there is no such node in our graph then we create one. This method getNode() does exactly that. It checks whether string K is present in our graph, if yes, then returns the corresponding node, else creates a new node with id K and adds it to our graph with key K.
```
    
    private static Node getNode(HashMap<String, Node> graph, String id){
		if(graph.containsKey(id))
		    return graph.get(id);
        else{
        	Node node = new Node(id);
        	graph.put(id, node);
        	return node;
        }
    }
```
Part 3: Once we have both the nodes, we can add the destination node to source node’s adjacent list. Now our graph is created.

Step 4:

Write method to find whether a path exists between source and destination.

Here we need to traverse nodes in the order they come in. So we use a LinkedList queue of type Nodes. We add them as they come and always remove the first one in the list. To keep track of visited nodes, so that we don’t go inside an infinite loop, we use a HashSet visited.

We start by adding the first node to the queue. Then we loop over this queue until the queue becomes empty. Inside the loop, we remove the first node in the list. Then check whether the node is same as the destination. If yes, we return true. If no, we add the node to visited set if it has not been added. Next, we loop through the node’s adjacent list to add all its children to the queue. If we didn’t find destination even after traversing all nodes, we return false.
```
public static boolean pathExists(HashMap<String, Node> graph, String source, String destination){

		//To store the children of nodes visited
        LinkedList<Node> queue = new LinkedList<Node>();

        //To store the visited nodes
        HashSet<String> visited = new HashSet<String>();

        //adding node of startId in the linkedlist
		queue.add(getNode(graph, source));	

		while(!queue.isEmpty()){

			Node parent = queue.remove();

			//Check if current node is the destination node
			if(parent.getId().equals(destination))
				return true;

			//add source to visited set
		    if(visited.contains(parent.getId()))
				continue;
			visited.add(parent.getId());

			//add children to the queue
			for(Node children: parent.getAdjacent())
				queue.add(children);
		}

		return false;
	}
```
Example

Consider the graph in Fig 1. We will apply the above BFS method on
1. pathExists(graph, “A”, “H”)
2. pathExists(graph, “H”, “D”)
1. pathExists(graph, “A”, “H”)

2. pathExists(graph, “H”, “D”)

The code for this post is available here.

Try BFS on a graph and experiment with different source and destination nodes. Drop your questions and thoughts in the comments below.

Thanks for stopping by. See you in the next post.
Graph Search: Depth First Search

July 11th, 2017
Graph search or finding whether one vertex is reachable from another vertex in a graph is one of the operations we can apply on graphs. There are two basic methods for this:
1. Depth First Search
2. Breadth First Search
In this post, we will study Depth First Search. We will create a graph for a directed unweighted graph as an adjacency list using the concepts discussed in this previous post. Then apply DFS on it.

What does reachability mean?

One vertex is reachable from another vertex if and only if there exists a path between them. For example in the directed graph given below, there exists a path between 1 and 6 but not between 3 and 4.

Fig 1: Directed Graph

We can either go directly from node 1 to node 6 or go from node 1 to node 5 and then to node 6. The blue color highlights the path. And the gray color highlights the lack of path between 3 and 4 in the above graph.

How does Depth First Search (DFS) work?

We have source node and a destination node in a graph. Our motive is to find a path between them. So we call DFS on our source and destination. DFS then checks whether there is a path from any of the node’s children to the destination. If there is a path it returns true. Else it continues on the current node’s children until either we reach the destination (return true) or we reach a node already traversed ( return false).

The following example will clarify this more.

Fig 2: Path does not exist

Fig 2 shows a directed unweighted graph along with adjacency list of each node. Suppose we want to find whether a path exists between 3 and 4. As per DFS, we check whether a path exists between 3’s child i.e. 6 and 4. Which further checks whether a path exists between 6’s child i.e. 2 and 4. This then checks whether a path exists between 2’s child i.e. 3 and 4. 3 is our node already traversed and so we return false. Let’s look at an example where a path exists.

Fig 3: Path exists

Suppose we want to find whether a path exists between 1 and 6. Again, we start with 1’s child i.e 2 and call our method pathExists on 2 and 6. Then again we call method pathExists method on 2’s child i.e. 3 and 6 and then finally on 6 and 6 which returns true. This True goes all the way back to our first call and we return the final result ie True.

Implementation

Now we code the above concept in Java. I will break down the code into few simple steps for ease in understanding

Step 1: Create a Node class, which stores the Node’s id of primitive type along with a LinkedList/ArrayList to store adjacency list of that node.

Step 2: Create a hashmap/ArrayList to store the vertices of a graph as Node objects. Here we can create a global variable to store graph or locally in methods and then pass them as parameters. Till now, we created a global variable for the graph, for the next two videos we will create a graph in a method and pass it as parameters.

Step 3: Add all the edges into the graph by updating the adjacency list of source nodes.

Step 4: Write method to find whether a path exists between source and destination using DFS.

Now we go through each step in detail:

Step 1:

Create a Node class, which stores the Node id/name/label of primitive type along with a LinkedList/ArrayList to store adjacency list of that node. For a detailed explanation refer to this post.
```
        /**
	* Node --- class to store each vertex along with its adjacent vertices
	*/
	static class Node{		
		
		private String id;
		private LinkedList<Node> adjacent;
		
		public Node(String id){
			this.id = id;
			adjacent = new LinkedList<Node>();
		}
		
		//Getter method for start vertex
		public String getId(){
			return id;
		}
		
		//Getter method for end vertex
		public LinkedList<Node> getAdjacent(){
			return adjacent;
		}
		
		//add node to the adajcent list
		public void addAdjacent(Node vertex){
			adjacent.add(vertex);
		}

		//To print Node 
        public String toString(){
     		String msg = id + " : ";
        	for(Node node: adjacent)
        		msg = msg + node.id + " ";
        	return msg;
                }
	}
```
Fig 4: Directed Graph

Step 2:

Create a HashMap/ArrayList to store the vertices of a graph as Node objects.

In our example graph in Fig 4, we have string nodes. So our HashMap will have keys of type String and Values of type Node.
```
    /**
    * Creates a HashMap with string key and Node value
    * @param input list of edges
    * @return HashMap<String,Node>
    */ 
	public static HashMap<String, Node> createGraph(String[] input){
		HashMap<String, Node> graph = new HashMap<String, Node>();
		Node node;
		for(String s: input){
			String first = String.valueOf(s.charAt(0));
			String second = String.valueOf(s.charAt(1));
			add(graph, first, second);
		}
		return graph;
	}
```
Step 3:

Add all the edges into the graph by updating the adjacency list of source nodes.

Our input is an array of strings where each string “XY” represents an edge from X to Y. So we traverse our list and do the following three steps on each of the string values.
```
//Input edges of the graph.
		String[] input = {"AB","BC","BE","CF","DE","EF"};
```
Part 1: First we separate X and Y from our string “XY”. We can do that by using the String’s charAt(index) method and assign them to a first and second variable. Then add the edge to our graph by calling the add method.
```
	public static void add(HashMap<String, Node> graph, String source, String destination){

		//Get nodes corresponding to source and destination vertices.
		Node s = getNode(graph, source);
		Node d = getNode(graph, destination);

		//add nodes to adjacent list
		s.addAdjacent(d);
	}
```
Part 2: We access the node corresponding to string X and Y in the graph. If there is no such node in our graph then we create one. This method getNode() does exactly that. It checks whether string K is present in our graph, if yes, then returns the corresponding node, else creates a new node with id K and adds it to our graph with key K.
```
    
    private static Node getNode(HashMap<String, Node> graph, String id){
		if(graph.containsKey(id))
		    return graph.get(id);
        else{
        	Node node = new Node(id);
        	graph.put(id, node);
        	return node;
        }
    }
```
Part 3: Once we have both the nodes, we can add the destination node to source node’s adjacent list. Now our graph is created.

Step 4:

Write method to find whether a path exists between source and destination.

We know that path exists between source and destination when the source becomes equal to the destination while traversing the graph. And we also know that if we encounter a node already visited while searching the destination then we don’t have a path between source and destination. So we need to keep track of the nodes visited so far. We do that using a HashSet visited.

We create an empty HashSet in our helper method and pass it and the source and the destination node to our main recursive method. We can get the nodes from the hashmap using getNode() method described above.

Once we are on a node, we check whether that node exists in our visited set. If it exists, we return false (no path between source and destination). If it doesn’t exist in visited, we add the node to the visited set.

Then we check whether the current node is equal to our destination. If yes, we have found a path, so we return true. Else we traverse the adjacent list of the current node and check if a path exists between its children and the destination node. If a path does exist we return true, else we return false.
```
    /**
    * Helper method for pathExists recursive method
    * @param HashMap<String, Node> graph 
    * @param source start index
    * @param destinations end index
    * @return true or false
    */ 
	public static boolean pathExists(HashMap<String, Node> graph, String source, String destination){
		HashSet<Node> visited = new HashSet<Node>();
		return pathExists(getNode(graph, source), getNode(graph, destination), visited);
	}

	/**
    * pathExists recursive method to find path between source and destination
    * @param source start index
    * @param destinations end index
    * @param visited set to store visited nodes
    * @return true or false
    */ 
	public static boolean pathExists(Node source, Node destination, HashSet<Node> visited){
		if(visited.contains(source))
			return false;

		visited.add(source);

		if(source == destination)
			return true;

		for(Node neighbor : source.getAdjacent()){
			if(pathExists(neighbor, destination, visited))
				return true;
		}
		return false;
	}
```
Example

We see recursive calls on two examples for the graph in Fig 4.
1. pathExists(graph, “A”, “F”)
2. pathExists(graph, “A”, “D”)
The adjacency list of all nodes in the graph of Fig 4 is:

Fig 5: Adjacency list of each node in the graph of Fig 4.

1. pathExists(graph, “A”, “F”)

Fig 6: pathExists(graph, “A”, “F”)

2. pathExists(graph, “A”, “D”)

Fig 6: pathExists(graph, “A”, “D”)

The code for this post is available here.

Try DFS on a graph and experiment with different source and destination nodes. Drop your questions and thoughts in the comments below.

Thanks for stopping by. See you in the next post.
Graph Representation: Adjacency Matrix

June 17th, 2017
In our previous post, we stored the graph in Edges List and Vertices List. And we saw that time complexity of performing operations in this representation is very high. So, we need another representation which can perform operations in less time.

Another representation of the graph is a 2D array of size V x V called Adjacency Matrix. Let’s call that matrix adjacencyMatrix. If we have an edge between nodes s and d, then adjacencyMatrix[s][d] is set to 1 or weight, else set to infinity.

Unweighted Undirected Graph

Consider the following graph

Fig 1: Undirected Graph

The adjacency matrix of above graph is

Fig 2: Adjacency Matrix of the graph in Fig 1.

There is an edge between 1 and 2, so we put 1 in adjacencyMatrix[1][2] and also in adjacencyMatrix[2][1] as this is an undirected graph. We give value 1 here because there is no weight for an edge. There is no edge between 1 and 3, so we put infinity in adjacencyMatrix[1][3].

In Java, we initialize a 2D array adjacencyMatrix[size+1][size+1], where size is the total number of vertices in the graph. For the above graph, the matrix will have a size of 7. We assign Integer.MIN_VALUE which is equivalent to negative infinity to adjacencyMatrix.

(Note: We can assign an index from 0 to 6 to all the vertices, but that creates confusion. Here, we use node names as the array index in this implementation. Since there is no node 0, and node start from 1, we increase the matrix size by 1. If you have string nodes, you can give them indices from zero and use size instead of size+1.)
```
public class GraphAdjacencyMatrix{
	
	//2-D array to store adjacency matrix
	private int[][] adjacencyMatrix;
	
	//variable to store size of 2-D array/adjacency matrix
	private int size;
	
	//Constructor to initialize the matrix and size
	public GraphAdjacencyMatrix(int size){
		this.size = size;
		adjacencyMatrix = new int[size][size];
		for(int[] single : adjacencyMatrix)
			Arrays.fill(single, Integer.MIN_VALUE);
	}
}
```
Add an edge

Now we add edges between two nodes using the following method. Since the graph in fig 1 is undirected, we add an edge from source to destination and destination to source by assigning one to adjacencyMatrix[destination] and adjacencyMatrix[destination].
```
public void add(int source, int destination){
		adjacencyMatrix[destination] = 1;
		adjacencyMatrix[destination] = 1;
	}
```
Find Adjacent Vertices

The findAdjacent method takes an index as input and returns anArrayList of vertices adjacent to the index. To find all adjacent vertices of the index, we need to traverseadjacencyMatrix[vertex] and add those vertices to list whose value is 1.

Since we traverse adjacencyMatrix[vertex] linearly, whose size is V (V being the number of vertices in the graph), the time complexity of this operation is O(V).
```
public ArrayList<Integer> findAdjacent(int index){
		ArrayList<Integer> adjacent = new ArrayList<Integer>();
		for(int i=1;i<size;i++){
			if(adjacencyMatrix[index][i] == 1)
				adjacent.add(i);
		}
		return adjacent;
	}
```
Find whether two nodes are connected

To find whether source and destination are connected, we just check whether adjacencyMatrix[destination] or adjacencyMatrix[destination] is equal to 1. If any of them is equal to 1, source and destination are connected else they are not connected. The time complexity of this operation is O(1) as we only access a position in a 2D matrix.
```
public boolean isConnected(int source, int destination){
		if(adjacencyMatrix[destination] == 1 || adjacencyMatrix[destination] == 1)
			return true;
		return false;
	}
```
The entire code for a unweighted undirected graph is available here.

Weighted Undirected Graph

Fig 3: Weighted Undirected Graph

If an edge between source and destination has a weight then we assign value of weight to adjacencyMatrix[destination] and adjacencyMatrix[destination].
```
public void add(int source, int destination, int weight){
		adjacencyMatrix[destination] = weight;
		adjacencyMatrix[destination] = weight;
	}
```
To find adjacent nodes of a given node, we add all those nodes to the list whose value is not equal to Integer.MIN_VALUE.
```
public ArrayList<Integer> findAdjacent(int index){
		ArrayList<Integer> adjacent = new ArrayList<Integer>();
		for(int i=1;i<size;i++){
			if(adjacencyMatrix[index][i] != Integer.MIN_VALUE)
				adjacent.add(i);
		}
		return adjacent;
	}
```
Similarly to check whether two nodes are connected or not, we check whether adjacencyMatrix[destination] or adjacencyMatrix[destination] is not equal to Integer.MIN_VALUE.
```
public boolean isConnected(int source, int destination){
		if(adjacencyMatrix[destination] != Integer.MIN_VALUE || adjacencyMatrix[destination] != Integer.MIN_VALUE)
			return true;
		return false;
	}
```
The whole code for the weighted undirected graph can be found here.

Weighted Directed Graph

Fig 4:Weighted Directed Graph

In case of directed weighted graph, we assign weight to only adjacencyMatrix[destination] and not to adjacencyMatrix[destination]. Other operations are same as those for the above graphs. The whole code for directed weighted graph is available here.

Problems in this approach

If we have a graph with million nodes, then the space this graph takes is square of million, as adjacency matrix is a 2D array. That’s a lot of space. It is good when we have a large number of vertices and equally large number of edges between them, as then we will have a dense matrix. But If we have a graph with a lot of vertices and very few edges, resulting in a sparse matrix, we store a lot of infinite values which are unnecessary and take a lot of space. The next implementation Adjacency List, which we cover in next post improves upon this.

A large number of vertices and equally large number of edges between them will produce a dense matrix. Here, using adjacency matrix is efficient. But a large number of vertices and very few edges between them will produce a sparse matrix. Here, using adjacency matrix is inefficient as we store a lot of infinite values (taking up large space) which are unnecessary. The next implementation Adjacency List, which we cover in next post improves upon this.