Print all the paths between two nodes in a Graph

No Comments

In this tutorial we will learn how to find all the simple paths(paths without a cycle) between two nodes in a graph. We are given a graph, a source node, and a destination node and we have to find all the paths originating from source node to ending at destination node.
Depth First Search(DFS) is generally used when finding a simple path between two nodes. Our problem is similar to that as we have to find out not just any single path but all the paths. So we will tweak the DFS algorithm a little to print all possible paths. The basic idea is that, after the destination node is found by DFS, print the path and mark it as unvisited so that DFS could continue finding all the remaining paths.

For example, let’s take a complete graph for five nodes. Graph is given as 2-D matrix. Here’s the graph

0 1 1 1 1
1 0 1 1 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 0
1
5

The last two entries of 1 and 5 are source and destination nodes respectively. This graph will look like this
completed-graph-five-nodes
A sample solution to the problem :


import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.io.InputStreamReader;


class AllPathBetweenTwoNodes{
	 static int dim = 5; // dim is number of nodes in graph

	//color is used to mark if the node is visited or not
    static boolean[] color = new boolean[dim + 1];
    
    //graph is given in 2-D matrix form
    static int[][] graph = new int[10][10];
    
    // this list will store nodes on the path from source to destination
    static ArrayList<Integer> list = new ArrayList<Integer>();
    
    // this is the size of "list" declared above
    // size is used to remember index of the node in the list to be removed
    // when  the node is marked unvisited
    static int size;
    
	public static void main (String ... args) throws IOException{
	
		BufferedReader br = new BufferedReader (/*new FileReader("input.txt")*/new InputStreamReader ((System.in)));
        for (int I = 1; I <= dim; I++) {
			
            String[] input = br.readLine().split(" ");
            int len = input.length;
            
            for (int J = 1; J <= len; J++) {
                graph[I][J] = Integer.parseInt(input[J - 1]);
            }
        }
        
        Arrays.fill(color, false);      // initially all are unvisited
 
        int src = Integer.parseInt(br.readLine());      //Source node
        int dst = Integer.parseInt(br.readLine());      //Destination node
 
        dfs(src, dst);  // backtracking
	}
	
	 static void dfs(int src, int dst) {
		//node added to path
        list.add(src);
        size++;
        
        //node marked as visited
        color[src] = true;
        
        //when the destination node is found
        if (src == dst) {
			
			// Print the path
            for (Integer node : list) {
                System.out.print(node + "  ");
            }
            System.out.println();
            return;
        }
        
        
        for (int I = 1; I <= dim; I++) {
			// if there's an edge between  src and node
            if (graph[src][I] == 1) {
				
				//and that node is not visited yet
                if (color[I] == false) {
					
					//start dfs from that node
                    dfs(I, dst);
                    
                    //This line is critical to understand
                    //it marks the node unvisited which we have just visited
                    //so that the dfs could find another path to destination
                    color[I] = false;
                    
                    //size of list reduced by 1
                    //as the node is marked unvisited
                    //hence removed from the list
                    size--;
                    
                    //remove that node at index "size" from list
                    list.remove(size);
                }
            }
        }
    }
}

This code print all the paths between node 1(source) and 5(destination). All the paths will be :

1  2  3  4  5
1  2  3  5
1  2  4  3  5
1  2  4  5
1  2  5
1  3  2  4  5
1  3  2  5
1  3  4  2  5
1  3  4  5
1  3  5
1  4  2  3  5
1  4  2  5
1  4  3  2  5
1  4  3  5
1  4  5
1  5

Comments in the code make it self-explanatory, still for any doubts please drop a comment. Thanks for reading. Have a nice day!!!

Categories: Algorithm Tags:

Bit Shift Operators in Java

No Comments

Java provide us some operators which shifts the bit pattern of the integral type data. There are three such operators, signed right shift(>>), signed left shift(<<), and unsigned right shift(>>>) operator. Difference between signed and unsigned is that signed operator depends on the sign of the data type. Let’s take an int data type which by default is a 32-bit signed two’s complement integer, which has a minimum value of -231 and a maximum value of 231-1. The left most bit in the int represents the sign of it, 1 for negative, and 0 for positive.
The signed right shift operator (>>) will shift the bit pattern to the right and the resulting gap produced by this shifting would be filled with the sign value of int, i.e. if left most bit is 1(int has negative value), there would be 1’s in the gap and similarly if the left most bit is 0(int has positive value), the gap would be filled by 0’s. In case of signed left shift (<<), there would be no gap in the left and gap created in the right side would be filled with zeros. Also keep in mind that in left shift, shifting could re-write the sign bit of an int so it's possible to apply left shift on negative int (1 in left most bit) and making it positive (0 in left most bit) and vice versa. In case of unsigned right shift operator, the gap produced in left because of shifting the bits to right will always be filled with zeros. Let's see an example code which would make it more clear.

class ShiftOperatorDemo{
	public static void main (String … args){
		
		int I = 255;		
		//0000 0000 0000 0000 0000 0000 1111 1111
		
		int J = -256;
		//1111 1111 1111 1111 1111 1111 0000 0000
		
		/**
		 *  signed right shift operatore demo
		 **/
		
		I = I >> 4;		
		//Resulting value after shifting to 4 places right
		//0000 0000 0000 0000 0000 0000 0000 1111
		System.out.println ("After signed right shift to 4 places, I is " + I);
		
		J = J >> 4;
		//Resulting value after shifting to 4 places right
		//1111 1111 1111 1111 1111 1111 1111 0000
		System.out.println ("After signed right shift to 4 places, J is " + J);
		
		
		
		/**
		 * signed left shift operator demo
		 **/
		 
		I = I << 8;
		//Resulting value after shifting to 8 places left
		//0000 0000 0000 0000 0000 1111 0000 0000
		System.out.println ("After signed left shift to 8 places, I is " + I);
		
		
		J = J << 8;
		//Resulting value after shifting to 8 places left
		//1111 1111 1111 1111 1111 0000 0000 0000
		System.out.println ("After signed left shift to 8 places, J is " + J);
		
		/**
		 * Unsigned right shift operator demo
		 **/
		 I = I >>> 4;
		 //0000 0000 0000 0000 0000 0000 1111 0000
		 System.out.println ("After unsigned right shift to 4 places, I is " + I);
		 
		 J = J >>> 4;
		 //0000 1111 1111 1111 1111 1111 0000 0000
		 System.out.println ("After unsigned right shift to 4 places, J is " + J);
	}
}

Also note that shifting right to x positions is equal to dividing by 2x and shifting to left by x positions is equivalent of multiplication by 2x. If the value of x exceeds 32 which is the number of bits in an int, the modulo operator will be used. This modulo operator will provide us the remainder when x is divided by 32. For example if you shift an int to 64 places its value will remain the same as 64%32 == 0 (% is modulo operator in Java). These bit shifting makes code faster but also a little hard to read and understand but that shouldn’t stop us from learning this useful feature Java provides.

In case of any doubts please drop a comment. Stay tuned for more articles. Thanks for reading. Have a nice day!!!

Categories: Java Tags:

Lazy propagation in Segment Tree

No Comments

In the last last tutorial we learned how to build a Segment tree, query it and update point values to it. You can find it at Introduction to Segment Tree. In this tutorial we will learn a useful technique Lazy Propagation for Segment trees. Using lazy propagation we can update a range in the tree efficiently. In this technique we update the value in a lazy manner, as the name suggests itself. Being lazy, values are not updated unless needed. Hence “lazy propagation” roughly translates to propagating values from root in a lazy manner.

Let’s make it clear with an example. Suppose we’ve built a Segment tree and there are two types of queries available on the tree. First one is update, which adds some value to nodes in a particular range. Second type is query for sum, which asks for sum of node values for a given range. In lazy propagation, “Lazy” refers to the idea that we will not update the range down to the leaf nodes every time it is called. Because the query for sum is called in the last, we will accumulate the values in an another array every time update() is called and these accumulated values will provide sum only for query which asks for sum in a range. Let’s take an example to make the concept clear.

Question

You are given an array of N elements, which are initially all 0. After that you will be given C commands. They are:
* 0 p q v – you have to add v to all numbers in the range of p to q (inclusive), where p and q are two indexes of the array.

* 1 p q – output a line containing a single integer which is the sum of all the array elements between p and q (inclusive)

Input:

In the first line you’ll be given T, number of test cases.

Each test case will start with N (N<=100 000) and C (C<=100 000). After that you'll be given C commands in the format as mentioned above. 1 <= p,q <= N and 1 <= v <= 107.

Output:

Print the answers of the queries.

Source of the question : SPOJ – HORRIBLE

import java.io.BufferedReader;
import java.io.IOException;
import java.util.Arrays;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.FileInputStream;

class lazypropagation {
	long tree[];		//the Segment tree 
	long helper[];	//this array accumulates value to be updated
	//if true, values are pending for this node to be updated
	boolean flag[];
	
	lazypropagation(){
		tree = new long [262145];
        helper = new long [262145];
        flag  = new boolean [262145];
        
        //initialize all node of tree and helper with zero
		Arrays.fill (tree, 0);
        Arrays.fill (helper, 0);
        
        //initially set all flags to false as their is no pending value for any node
        Arrays.fill (flag, false);
	}
	
	
	/**
	 * @param nodeToUpdate node in tree to be updated
	 * @param valueToUpdate value to be updated
	 * @param left is beginning index of array
	 * @param right is ending index of array
	 * @param start is beginning index of query
	 * @param end is ending index of query
	 **/
	private void update (int node, int value, int left, int right, int start, int end){
		/**
		 * 		Legends:
		 * 		S = Start, E = End, L = Left, R = Right
		 * 		dotted lines ---- represents array
		 * 		square brackets [ ] denote range of query
		 * 
		 **/
		
		// When range to be updated does not intersect 
		// with the array indices [left, right]
		//	...E]  L------R	[S...
		 if ( end <left || start > right )
            return ;
         
        // left == right means we've reached to a single element of array. 
        if (left == right ){
            tree[node]+= value;
            
            //flag is true mean some value is pending in helper[node]
            //so we should add this to tree[node] and clear helper[node]
            if (flag[node]==true){
                tree[node] += helper[node];
                helper[node]=0;
            }
            return;
        }
        
        int leftChild = 2*node;
        int rightChild = 2*node + 1;
        
        //Each of the below case finds a range by right-left+1 or end-left+1
        //this range should be multiplied by value and should be added to tree[node]
        
        //  	[S   L------R	E]
        if (start <= left && right <= end){
            helper[leftChild] += value;
            helper[rightChild] += value;
            
            flag[leftChild] = flag[rightChild] = true;
            
            tree[node] += (value *(right - left +1));
            return ;
        }
        //		---[S---R   E]
        else if (start <= right &&  right < end)
            tree[node ] += (value*(right - start +1));
        
        //		[S    L----E]----
        else if (start < left && left <= end )
            tree[node] += (value*(end - left + 1));
            
        //		----L----[S-----E]-----R-----
        else if (left <= start && end <= right)
            tree[node] += (value*(end - start + 1));
 
        update (leftChild, value, left, (left+right)/2, start, end );
        update (rightChild, value, ((left+right)/2)+1, right, start, end);
	}
	
	private long sum_of_range (int node, int left, int right, int start, int end){
		// query does not overlaps with array range
		//	---R---- [S		E]----L-----
        if (right < start || end < left)
            return 0;
            
        int leftChild = 2*node;
		int rightChild = 2*node+1;
		
		// true means value updates are pending for the node
        if (flag[node] == true){
			
			//update value in tree node
			// right-left+1 gives the range for which 
			//values to be updated in parent node which here is tree[node]
            tree[node] += (helper[node] *(right-left+1));
            
            //after values are updated, set flag to false
            flag[node]=false;
            
            // if it's not a leaf node
            if (left != right){
				
				//push the flag downward to children of node because
				//after recursive call these children will act as parent
				//and then tree[node] would be calculated
                flag [ leftChild ] = flag [ rightChild ] = true;
                 
                //push down the parent value to leftChild and rightChild
                //hence updated values for child nodes would be the sum of their own values + parent node value
                helper[ leftChild ] += helper[node];
                helper[ rightChild ] += helper[node];
            }
            
            //as value of helper[node] is already added to its children
            // set helper[node] = 0 to receive fresh values
            helper[node]=0;
        }
        
		// return value of tree[node] as query completely overlaps the array range
		// hence no need to go further on its children nodes.
		//	[S---L---R---E]
        if (start <= left && right <= end){
            return tree[node];
        }
        
        //sum returned for left half of tree intersecting with query
        long s1 = sum_of_range(leftChild, left, (left+right)/2, start, end);
        
        //sum returned for right half of tree intersecting with query
        long s2 = sum_of_range(rightChild, ((left+right)/2)+1, right, start, end);
        return s1+s2;
    }
    
	public static void main (String [] args) throws IOException{
		// for reading input from console use new InputStreamReader (System.in)
        BufferedReader br = new BufferedReader (new InputStreamReader (new FileInputStream("input.txt")));
        StringTokenizer st =null;
        int t = Integer.parseInt(br.readLine());
        for(;t>0;t--){
            st = new StringTokenizer (br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int C = Integer.parseInt(st.nextToken());
            lazypropagation segtree = new lazypropagation();
            for (int I=1;I<=C;I++){
                st = new StringTokenizer(br.readLine());
                if (st.nextToken().equals("0")){
                    int P = Integer.parseInt(st.nextToken());
                    int Q = Integer.parseInt(st.nextToken());
                    int V = Integer.parseInt(st.nextToken());
                    segtree.update (1, V, 1, N, P,Q);
                }
                else {
                    int P = Integer.parseInt(st.nextToken());
                    int Q = Integer.parseInt(st.nextToken());
                    long ans = segtree.sum_of_range (1,1,N, P,Q);
                    System.out.println(ans);
                }
            }
        }
    }
}

In the above code, update() is responsible for both building the tree and updating the values in it. In update(), we took array indices left to 1 and right to N as N is the number of elements in array. There are four possible cases regarding intersection of array range and query range. All those cases are represented in the comments of update(). Basic idea of update() is to accumulate the value to be updated for those node which are the intersection of query range and array range in helper[node]. These values will be accumulated for each update() and will be processed when sum_of_range() is called. I’ve put a lot of comments in the code to make it self-explanatory. Still for any doubts please drop a comment. Thanks for reading. Have a nice day!!!

Introduction to Segment Tree

2 Comments

Segment tree is a data structure similar to heap. Every node of this tree has zero or two children. Nodes having zero child are called leaf nodes and represent the single element from the given array for which Segment tree would be built. Each node of the tree will hold information about a range from the given array. The closer the node to root, the more range it covers. Because it’s a tree, we can perform queries in O(log2N) where N is number of elements given. Here base of this logarithm is two as every node of this tree will have at most two child nodes. Left child will hold information for left half of the parent range and right child will hold info for remaining right half. For the interval [A, B] ([A,B] represents closed interval for A and B) in the given array, the Segment tree would be defined in the following recursive manner:

  • The root node will hold the information for the interval [A, B]
  • For A < B, the left child will hold the information for interval [A, (A+B)/2] and right child will hold the information for the interval [((A+B)/2)+1, B]
  • For example, Segment tree for an array having thirteen elements in an array [0, 12] would look like,
    segment tree

    Let’s take an example. Suppose we are given an array of 13 integers and numerous queries to find out maximum value between a given range. To perform our queries in O(log2N) time we will build a Segment tree from this array. Each of its node will hold maximum value for a particular interval for which this node is responsible for as shown in the above figure. The tree is built in O(N) and let us do queries in O(log(N)). Here is the code for the above example. In this code the Segment tree is built for an array and queries maximum value for a range.

    import java.util.Random;
    import java.util.Arrays;
    
    class SegmentTree{
            // arr is given array
    	// segTree is our Segment tree in form of array
    	public int arr [], segTree [];
    	
    	SegmentTree(int arrayLength){
    		arr = new int [arrayLength];
    		Random generator = new Random();
    		
    		for (int I=0; I<arrayLength; I++){
    			//putting random values in array
    			arr[I] = generator.nextInt(100);
    		}
    
    		//We will be building seg tree for array of length 13
    		//for now let's take segTree length 32
    		
    		int segTreeLen = 32;
    		segTree = new int [segTreeLen];
    		Arrays.fill (segTree, 0);
    	}
    	
    	/**
    	 * @param node is the root node of tree
    	 * @param left is the beginning index of array
    	 * @param right is the ending index of array
    	 **/
    	private void buildSegmentTree(int node, int left, int right){
    		if (left == right){
    			segTree [ node ] = arr[left];
    		}
    		else {
    			//recursively approach left half of tree until a leaf is found
    			buildSegmentTree (2 * node, left, (left+right)/2 );
    			
    			//recursively build the right half of tree
    			buildSegmentTree (2 * node + 1, ((left+right)/2)+1, right);
    			
    			// value in left child of node
    			int valueInLeftChild = segTree [2 * node];
    			
    			// value in right child of node
    			int valueInRightChild = segTree [ 2 * node +1];
    			
    			
    			// comapare both childs for greater value
    			// and assign to node that value
    			if ( valueInLeftChild  >= valueInRightChild ){
    				segTree [ node ] = valueInLeftChild;
    			}
    			else segTree [ node ] = valueInRightChild;
    		}
    	}
    	
    	/**
    	 * @param node is the root node of tree
    	 * @param left is the beginning of the array index
    	 * @param right is ending index of array
    	 * @param start is the beginning index of the query
    	 * @param end is ending index of query
    	 **/
    	private int query (int node, int left, int right, int start, int end){
    		
    		// if query range is out of array interval no valid value is returned
    		if ( start > right || end < left){
    			return -1;
    		}
    		
    		/**
    		 * if query range includes the array interval
    		 * return the value of node in the tree
    		 * which holds the maximum value for the range
    		 * Segment tree saves our computation in this manner
    		 * because segTree[treeNode] already holds maximum value for this range
    		 **/ 
    		if ( start <= left &&  end >= right){
    			return segTree [node];
    		}
    		
    		int half = (left+right)/2;
    		
    		//Computing maximum value in left half of the tree
    		int leftMax = query (2*node, left, half, start, end);
    		
    		//Computing maximum value in right half of the tree
    		int rightMax = query (2*node+1, half+1, right, start, end);
    		
    		int leftCorner, rightCorner;
    		leftCorner =(start<left)?left:start;
    		rightCorner = (right<end)?right:end;
    		
    		/**
    		 * Below if-else statements updates the node value
    		 * according to the maxium value from its child node
    		 **/
    		if (leftMax == -1){
    			System.out.println ("max value is " + rightMax + " between index " + leftCorner  + " and " + rightCorner);
    			return segTree[node] = rightMax;
    		}
    		if (rightMax == -1){
    			System.out.println ("max value is " + leftMax + " between index " + leftCorner + "  " + rightCorner);
    			return segTree[node] = leftMax;
    		}
    		if (leftMax > rightMax){
    			System.out.println ("max value is " + leftMax + " between index " + leftCorner + "  " + rightCorner);
    			return segTree[node] = leftMax;
    		}
    		else {
    			System.out.println ("max value is " + rightMax + " between index " + leftCorner + "  " + rightCorner);
    			return segTree[node] = rightMax;
    		}
    	}
    		
    	
    	public static void main (String ... args){
    		//Build the Segment tree for an array having 13 elements
    		SegmentTree tree = new SegmentTree (13);
    		
    		//Print the given array
    		System.out.println (Arrays.toString(tree.arr));
    		
    		// 0 is the left index from array and 12 is the right index
    		// 1 is choosen as root node because we need to calculate left and right child
    		// by using formula 2*node and 2*node+1 which won't work for 0 
    		tree.buildSegmentTree(1, 0, 12);
    		
    		// Uncomment below line to print the Segment tree
    		//System.out.println (Arrays.toString(tree.segTree));
    		
    		// We are finding maximum value between index 3 and 11 of given array for now
    		System.out.println ("Max value between index 3 and 11 is " + tree.query (1, 0, 12, 3, 11));
    	}
    }
    

    For this example we are asking for maximum value between range [3,11]. In the figure below, path is show in the red which includes the starting and ending index 3 and 11 respectively. Query starts from the root node. As it continues down, those nodes will not be queried down further which are completely in the queried range.

    segment-tree-with-path-traced-between-nodes

    We’ve build a static Segment tree. Static means once the tree is built it does not change. We perform queries which are read-only, they don’t modify the tree. Let’s take another operation of updating an element in array as well as in the tree. Again this point update operation would be performed in O(log(N)). And it’s code is almost similar to buildSegmentTree(). Here’s the code for updating point values:

    	private void update (int nodeToUpdate, int valueToUpdate){
    		update (nodeToUpdate, valueToUpdate, 1, 0, 12);
    	}
    		
    	/**
    	 * @param nodeToUpdate is the node to be updated in array and tree
    	 * @param valueToUpdate is the value to be updated at the nodeToUpdate
    	 * @param node root node of tree
    	 * @param left is the beginning index of array
    	 * @param right is the ending index of array
    	 **/
    	private void update(int nodeToUpdate, int valueToUpdate, int node, int left, int right){
    		if (left == right){
    			segTree [ node ] = arr[left];
    			// only the below if condition is different from buildSegmentTree()
    			// which does the job of point update.
    			if ( left == nodeToUpdate){
    				segTree[node] = arr[left] = valueToUpdate;
    			}
    		}
    		else {
    			update (nodeToUpdate, valueToUpdate, 2 * node, left, (left+right)/2 );
    			update (nodeToUpdate, valueToUpdate, 2 * node + 1, ((left+right)/2)+1, right);
    			
    			
    			int valueInLeftChild = segTree [2 * node];
    			int valueInRightChild = segTree [ 2 * node +1];
    			
    			if ( valueInLeftChild  >= valueInRightChild ){
    				segTree [ node ] = valueInLeftChild;
    			}
    			else segTree [ node ] = valueInRightChild;
    		}
    	}
    

    We need to call this function from main() as

    tree.update (nodeToUpdate, valueToUpdate);
    // e.g. tree.update (4, 99);
    

    In this article we learned how to build a Segment tree, performing queries over it and do point updates. In case of any doubts regarding this tutorial, please drop a comment. In the next part of this series we will learn about updating the tree using lazy propagation which is a very useful technique and saves a lot of calculation. So stay tuned. Have a nice day!!!

    Update: You can find the next part of this series at Lazy propagation in Segment tree

    Categories: Data structure Tags: