Partition an array of integers into sub-arrays so that the difference of summaries (of sub-arrays) is minimal

Here is one solution (dynamic programming) for partition an array of integers into two sub-arrays so that the difference of summaries (of sub-arrays) is minimal.

// partition an array of integers into two sub-arrays so that the difference of summaries (of sub-arrays) is minimal
int balancePartitionTwoWays(int arr[], int n, int partition[2]) {

 if (n==2) {
  for (int i=0; i<2; i++) {
   partition[i]=arr[i];
  }
  return abs(partition[0]-partition[1]);
 }


 // loop through the array to find out the sum and maximum
 int sum=0;
 int maximum = -1;
 for(int i=0; i<n; i++){
  sum += arr[i];
  if (arr[i]>maximum) maximum = arr[i];
 }

 // allocate the matrix to remember
 bool memo[sum+maximum+1][2];
 for (int j = 0; j < 2; j++)
  for (int i = 0; i <= sum+maximum; i++)
    memo[i][j] = false;

 memo[0][0] = true;

 // mark memo[i][k] to true if there is a subset
    // of array [0..i-1] with sum equal to i
 for (int j = 0; j < n; j++) {
  for (int i = 0; i <= sum+maximum; i++) {

   if (memo[i][j%2]) {
    memo[i][(j+1)%2] = true;
    memo[i+ arr[j]][(j+1)%2] = true;

   }
  }
 }

 int max_diff = INT_MAX;
 int part[2];

 for (int i = 0; i <= sum+maximum; i++) {
  if (memo[i][n % 2]) {
   part[0]=i;
   part[1]=sum-i;
   int temp = abs(part[0]-part[1]) ;
   if (temp<max_diff) {
    max_diff = temp;
    partition[0] = part[0];
    partition[1] = part[1];
   }
  }
 }

 return max_diff;

}

// partition an array of integers into three sub-arrays so that the difference of summaries (of sub-arrays) is minimal
int balancePartitionThreeWays(int arr[], int n, int partition[3]) {

 if (n==3) {
  for (int i=0; i<3; i++) {
   partition[i]=arr[i];
  }
  return abs(partition[0]-partition[1]) + abs(partition[1]-partition[2]) + + abs(partition[2]-partition[0]);
 }


 // loop through the array to find out the sum and maximum
 int sum=0;
 int maximum = -1;
 for(int i =0; i<n; i++){
  sum += arr[i];
  if (arr[i]>maximum) maximum = arr[i];
 }

 // allocate the matrix to remember
 bool memo[sum+maximum+1][sum+maximum+1][2];
 for (int k = 0; k < 2; k++)
  for (int i = 0; i <= sum+maximum; i++)
   for (int j = 0; j <= sum+maximum; j++)
    memo[i][j][k] = false;

 memo[0][0][0] = true;

 // mark memo[i][j][k] to true if there is a subset
    // of array [0..i-1] with sum equal to i
 for (int k = 0; k < n; k++) {
  for (int i = 0; i <= sum+maximum; i++) {
   for (int j = 0; j <= sum+maximum; j++) {
    if (memo[i][j][k%2]) {
     memo[i][j][(k+1)%2] = true;
     memo[i+ arr[k]][j][(k+1)%2] = true;
     memo[i][j+ arr[k]][(k+1)%2] = true;
    }
   }
  }
 }

 int max_diff = INT_MAX;
 int part[3];

 for (int i = 0; i <= sum+maximum; i++) {
  for (int j = 0; j <= sum+maximum; j++) {

   if (memo[i][j][n % 2]) {
    part[0]=i;
    part[1]=j;
    part[2]=sum-i-j;

    //int temp = abs(part[0]-part[1]) + abs(part[1]-part[2]) + + abs(part[2]-part[0]);
    int temp = 0;
    for (int k=0; k<3; k++) {
     temp += abs(part[k%3]-part[(k+1)%3]);
    }
    if (temp<max_diff) {
     max_diff = temp;
     for (int k=0; k<3; k++) {
      partition[k]=part[k];
     }
    }
   }
  }
 }

 return max_diff;

}

Enjoy the journey. 

O(n^2) solution to find out if and which 3 of them add up to 0

Here is a O(n^2) solution to find out if and which 3 of them add up to zero.

The Code is in Scala.

/**
 * O(n^2) solution to find out if and which 3 of them add up to 0
 * 
 */
object FindThreeNumbersSumToZero {
  
 def sort(arr:Array[Int]): Array[Int] =   
        if (arr.length<2) arr
        else {
            val pivot = arr (arr.length / 2)
            sort (arr filter (pivot>)) ++ 
            (arr filter (pivot == )) ++ sort (arr filter(pivot <))
        }
 
 def findThreeNumbersAddedToZero (arr: Array[Int]) : (Int, Int, Int) = {

  val a : Array[Int] = sort(arr);
  
  for(i <- 0 until a.length) {
    var iter = i+1;
    var reviter = a.length-1;
    while (iter < reviter) {
      var v = a(i) + a(iter) + a(reviter);
      if (v==0) 
        return (a(i), a(iter), a(reviter));
      else if (v<0)
        iter = iter + 1;
      else 
        reviter = reviter-1;
    }
  }
  return null;
 }
 
   def main(args: Array[String]) {
  
  val arr = Array(-11, 19, -2, 22, -4, 4, 10, 6,  12, 23)
  val tuple = findThreeNumbersAddedToZero (arr);
  println("array is [" + arr.mkString(" ") + "] ");
  println("tuple is " + tuple + "");
  
 }

}

Enjoy the journey. 

Given a number K, and an array of positive integers A, find two integers in the array which sum to K.

Problem: Given a number K, and an array of positive integers A, find two integers in the array which sum to K.

 Here we have two different algorithms to solve the problem.

Solution One:
Do an in-place merge sort on the array A;
Loop through each item A[i], use a binary search to check if K-A[i] is in the array;
If found, return the pair (A[i], K-A[i]);
If not found, return the null;

Time Complexity: O ( n * log(n) )
Space Complexity: O ( 1 )

Solution Two:
Allocate the array of size K;
Find the first element in the array A[s] that is less than K, and mark m[A[s] to 1
Loop through each remaining item A[i], check to see if m[K-A(i)] is 1
If m[K-A(i)] is 1, return the pair (A[i], K-A[i]);
If not found, return the null in the end.

Time Complexity: O ( n )
Space Complexity: O ( K )

The code is in Scala.

/**
 * 
 * Problem: Given a number K, and an array of positive integers A, find two integers in the array which sum to K.
 */

object FindPairSumToK {

 /*
  * Solution One:
  * Do an in-place merge sort on the array A;  
  * Loop through each item A[i], use a binary search to check if K-A[i] is in the array;
  * If found, return the pair (A[i], K-A[i]);
  * If not found, return the null;  
  * 
  * Time Complexity: O ( n * log(n) )
  * Space Complexity: O ( 1 ) 
  */
 def findPairSumToKwithSort(A: Array[Int], K: Int)  : (Int, Int) = {
     mergeSort(A, 0, A.length-1);
     for(i <- 0 until A.length){
       var t : Int = K - A(i);
       if (t>0) {
        var idx : Int = binarySearch(A, t);
        if (idx>=0) {
          return (A(i), A(idx));
        }
       }
     }
     return null;
   }
    
 /*
  * Solution Two:
  * 
  * Allocate the array of size K;
  * Find the first element in the array A[s] that is less than K, and mark m[A[s] to 1    
  * Loop through each remaining item A[i], check to see if m[K-A(i)] is 1
  * If m[K-A(i)] is 1, return the pair (A[i], K-A[i]);
  * If not found, return the null in the end.
  * 
  * Time Complexity: O ( n )
  * Space Complexity: O ( K ) 
  *       
  */
 def findPairSumToKwithDynamicProgramming(A: Array[Int], K: Int)  : (Int, Int) = {
        var m: Array[Int] = new Array[Int](K);
        var s : Int = 0;
      while (s<A.length && A(s)>=K) {
        s = s + 1;
      }
      m(A(s)) = 1;
     for(i <- s until A.length){
       var target : Int = K - A(i);
       if (target>=0 && m(target) ==1) {
        return (A(i), target);
       }
     }
     return null;
   }
    
   def reverse(a: Array[Int]): Unit = {
     if (a.length<=1) return;
     
     var i : Int = 0;
     var j : Int = a.length-1;
     while (i<j) {
      a(i) = a(i) + a(j);
      a(j) = a(i) - a(j);
      a(i) = a(i) - a(j);
      i=i+1;
      j=j-1;
    }
 }
   
   def binarySearch(A: Array[Int], target : Int) : Int = {
    var low : Int = 0;
    var high: Int = A.length-1;
    while (low<high) {
     var mid = (low + high) / 2;
     if (target==A(mid)) 
       return mid;
     else if (target<A(mid))
       high = mid-1;
      else 
        low = mid+1;
    }
    return -1;
   }
   
    def mergeSort(a : Array[Int] ) : Unit = {
    mergeSort(a, 0, a.length-1);
 }


    def mergeSort(A: Array[Int], low: Int, high: Int) : Unit = {
  if (low >= high) {
   return;
  }
  var mid = (low + high) / 2;
  mergeSort(A, low, mid);
  mergeSort(A, mid + 1, high);
  merge(A, low, mid, high);
 }

   def merge(a: Array[Int], Low: Int, Mid: Int, High : Int) : Unit = {
    var low = Low;
    var mid = Mid;
    var high = High;

  var i : Int = mid;
  var j : Int = mid + 1;
    while ((low <= i) && (j <= high)) {
   if (a(low) < a(j)) {
    low = low+1;
   } else {
    // shift from j to low
    var t = a(j);
    for (k <- j-1 to (low, -1) ) {
     a(k+1) = a(k);
    }
    a(low) = t;
    low = low + 1;
    i = i+1;
    j = j+1;
   }
    }
   }
   

 def print(a: Array[Int]): Unit = {
    println(a.mkString(" "))
 }
  
 def main(args: Array[String]) {
     
     val a = Array( 2, 5, 6, 1, 2, 3, 8, 16, 27, 23, 9, 17, 12, 14, 9, 11);
     var p = findPairSumToKwithSort(a, 19);
     println("p=" + p);
     p = findPairSumToKwithSort(a, 99);
     println("p=" + p);
     
     val aa = Array( 2, 5, 6, 1, 2, 3, 8, 16, 27, 23, 9, 17, 12, 14, 9, 11);
     p = findPairSumToKwithDynamicProgramming(aa, 19);
     println("p=" + p);
     p = findPairSumToKwithDynamicProgramming(aa, 99);
     println("p=" + p);
 }
}

Enjoy the journey. 

Find Lowest Common Ancestor (LCA) using Range Minimum Query (RMQ) in O(N) Time

RMQ of A(i,j) – returns the index of the smallest element in the subarray A[i...j]

Given the Array E below, RMQ of E(2,7) is 3.

LCA of Tree (u,v) – given nodes u,v in Tree, returns the node furthest from the root that is an ancestor of both u and v.

Given the tree below, LCA("5", "9") is node "4". 

Suppose an algorithm has preprocessing time of f(n) and query time of g(n).

Notation for the overall complexity of an algorithm <f(n), g(n)>. 

Here we can reduce LCA problem to RMQ: If there is <f(n), g(n)> solution for RMQ, then there is an <f(2n-1)+O(n), g(2n-1)+O(1)> solution for LCA. 

The Euler tour of a tree is the path through the tree that begins at the root and ends at the root, traversing each edge exactly twice : once to enter the subtree, and once to exit it. The Euler tour of a tree is essentially the depth-first traversal of a tree that returns to the root at the end. The correspondence between a tree and its Euler tour is shown in the Figure above. Euler tour size is 2n-1 for a tree with n node. 

The LCA of nodes u and v is the shallowest node encountered between the visits to u and to v during a depth first search traversal (Euler tour) of Tree. Well, otherwise it will contradiction to the DFS tour.

On an input tree T with n nodes, we build 3 arrays.

Euler array E[1,..,2n-1] – The nodes visited in an Euler tour of T. E[i] is the label of the i-th node visited in the tour.

Level array L[1,..2n-1] – The level of the nodes we got in the tour. L[i]  is the level of node E[i]. (level is defined to be the distance from the root)

Representative array R[1,..n] – R[i] will hold the index of the first occurrence of node i in E[i]. 
R[v] = minimum of i where E[i] = v. 


To get LCA of Tree(x,y): 

All nodes in the Euler tour between the first visits to x and y are E[R[x],..,R[y]] assume that R[x] < R[y]. The shallowest node in the sub-tour is at index RMQ of L(R[x],R[y]), since L[i] stores the level of the node at E[i]. RMQ will return the index, thus we output the node at E[RMQ of L(R[x],R[y])] as LCA of Tree(x,y).


Preprocessing Complexity: L,R,E – Each is built in O(n) time, during the DFS run. Preprocessing L for RMQ is f(2n-1). 
Query Complexity: RMQ query on L is g(2n-1) and array references is O(1)
Overall Complexity: <f(2n-1)+O(n), g(2n-1)+O(1)>. 



Solution One - Dynamic Programming <O(n^2), O(1)>:

Overall Complexity: 




Here is the code implementation:

static private class FindRMQWithDynamicProgramming<T> implements FindRMQInterface <T> {
  private int[] A;
  private int[][] M;
  private int N;
  
  public FindRMQWithDynamicProgramming( int[] L) {
   super();
   this.A = L;
   this.N = L.length;
   this.M = new int[N][N];
   process(this.M, this.A, this.N);
  }


  /**
   * 
   * Dynamic Programming
   * 
   * M[i][j] = M[i][j - 1] if A[M[i][j - 1]] < A[j]
   * or M[i][j] = j 
   * @param M
   * @param A
   * @param N
   */
  private void process(int[][] M, int[] A, int N) {
   int i, j;
   for (i =0; i < N; i++)
    M[i][i] = i;
   
   for (i = 0; i < N; i++)
    for (j = i + 1; j < N; j++)
     if (A[M[i][j - 1]] < A[j])
      M[i][j] = M[i][j - 1];
     else
      M[i][j] = j;
  }
  
  public int rmq(int i, int j) {
   return this.M[i][j];
  }
 }

Solution Two - Sparse Table <O(n log(n), O(1)>:

Preprocess sub arrays of length of

With dynamic programming, the table M can be built in O( n log(n) ) time.

To get M[i,j] for arbitrary i and j, select two blocks that entirely cover the subrange [i...j], and let k = (int) log(j - i + 1), so that 2^k is the largest block that fits [i...j]. 

Overall Complexity: 

Here is the code implementation:

 static private class FindRMQWithSparseTable<T> implements FindRMQInterface <T> {
  private int[] A;
  private int[][] M;
  private int N;
  
  public FindRMQWithSparseTable( int[] L ) {
   super();
   this.A = L;
   this.N = L.length;
   this.M = new int[N][N];
   process(this.M, this.A, this.N);
  }
  
  private void process(int[][] M, int[] A, int N) {
         // initialize M for the intervals of length one
         for (int i = 0; i < N; i++)
             M[i][0] = i;

         // compute values from smaller to bigger
         for (int j = 1; 1 << j <= N; j++) {
             for (int i = 0; i + (1 << j) - 1 < N; i++) {
                 if (A[M[i][j - 1]] < A[M[i + (1 << (j - 1))][j - 1]])
                     M[i][j] = M[i][j - 1];
                 else
                     M[i][j] = M[i + (1 << (j - 1))][j - 1];
             }
         }
     }
  
  public int rmq(int i, int j) {
   int k = (int) Math.log(j - i + 1);
   if (A[M[i][k]] <= A[M[j - (1 << k) + 1][k]])
    return M[i][k];
   else
    return M[j - (1 << k) + 1][k];
  }
 }

Solution Three - <O(n), O(1)> algorithm for restricted RMQ.

Overall Complexity: <O(n), O(1)>


Here is the code implementation:

 static private class FindRestrictedRMQWithSparseTable<T> implements FindRMQInterface <T> {
  private int[] A;
  private int[] B;
  private int[] T;
  private int [] Bl;
  private int N;
  private int blockSize;
  //private int blockNum; 
  private FindRMQWithSparseTable<T> blockRMQSparseTable = null;
  
  // construct the binary blocks 
  private int [] buildBlockArray(int[] L, int b, int n) {
   // round size of B to n blocks with size b
   int [] blocks = new int[(n*b)];
   blocks[0] = L[0];
   for (int i=1; i<L.length; i++) {
    blocks[i] = L[i] - L[i-1];
    if ( blocks[i]<0 ) blocks[i] = 0;
   }
   for (int i=L.length; i<blocks.length; i++) {
    blocks[i] = blocks[i-1] + 1;
   }
   return blocks;
  }

  public FindRestrictedRMQWithSparseTable(int [] L) {
   super();
   this.A = L;
   this.N = L.length;
   
   int b = (int) Math.ceil ( ( Math.log(N)/Math.log(2) ) / (double) 2 );
   this.blockSize = b;
   int n = (int) Math.ceil (  (double) N / (double) b ) ;
   //this.blockNum = n;

   // build the binary array
   this.B = buildBlockArray(L, b, n);

   // build the lookup table 
   this.T = buildLookupTable(this.B, b, n);

   buildMinIndexLookupTable(b, n);
   
//   System.out.println("Bl=" + Arrays.toString(Bl));
//   System.out.println("T=" + Arrays.toString(T));
   
  }

  private void buildMinIndexLookupTable(int b, int n) {
   this.Bl = new int[ n ] ;
   int [] blT = new int[ n ] ;
   for (int i=0; i<n; i++) {
    int idx = getIndex(B, i*b, b);
    int s = ( idx * ( (b) * (b+1) /2 ) );
    Bl[i] = i*b + T[s+2];
    blT[i] = A[Bl[i]];
   }
   blockRMQSparseTable = new FindRMQWithSparseTable<T> (blT);
  }

  // construct the lookup table 
  private int [] buildLookupTable(int [] blocks, int b, int n) {
   int sizeT = (int) Math.pow(2, b) * ( (b) * (b+1) /2 );
   int [] table  = new int[ sizeT ] ;
   for (int k=0; k<table.length; k++) {
    table[k]=-1;
   }
   
   for (int i=0; i<n; i++) {
    for (int j=0; j<b; j++) {
     int idx = getIndex(blocks, i*b, b);
     int [][] m = preProcess(blocks, i*b, b);
     int s = ( idx * ( (b) * (b+1) /2 ) );
     if ( table[s] < 0 ) {
      for (int k=0; k<b; k++) {
       for (int l=k; l<b; l++) {
        table[ s ] = m[k][l];
        s++;
       }
      }
     }
    }
   }
   
   return table;
  }

  
  
  private int [][] preProcess(int[] A, int start, int n) {
   int [][] matrix = new int[n][n];
   int i, j;
   for (i =0; i<n; i++)
    matrix[i][i] = i;
   
   for (i = 0; i < n; i++) {
    for (j = i + 1; j < n; j++) {
     int a = A[ start + matrix[i][j - 1]];
     int b = A[ start + j];
     if ( a < b ) {
      matrix[i][j] = matrix[i][j - 1];
     } else if ( a > b ) {
      matrix[i][j] = j;
     } else if ( a == b ) {
      matrix[i][j] = j;
     }
    }
   }
       
   return matrix;
  }

  
  private int getIndex(int[] A, int start, int len) {
     int idx = 0;
     for (int i = start; i<start+len; i++) {
      idx = idx * 2;
      idx += A[i];
     }
     return idx;
     }

  
  public int rmq(int i, int j) {
   int i1 = (int) (  (double) i / (double) this.blockSize ) ;
   int j1 = (int) Math.ceil (  (double) i / (double) this.blockSize ) ;
   int i2 = (int) (  (double) j / (double) this.blockSize ) ;
   int j2 = (int) Math.ceil (  (double) j / (double) this.blockSize ) ;
   
   int blockMinimum = -1;
   if ( (j1) < (i2) ) {
    blockMinimum = Bl[blockRMQSparseTable.rmq(j1, i2)];
   } 
   int idx1 = getIndex(B, i1*this.blockSize , this.blockSize);
   int idx2 = getIndex(B, i2*this.blockSize , this.blockSize);
   
   int s1 = ( idx1 * ( (this.blockSize) * (this.blockSize+1) /2 ) );
   int s2 = ( idx2 * ( (this.blockSize) * (this.blockSize+1) /2 ) );
   int jT1 = s1 + ( (this.blockSize) * (this.blockSize+1) /2 ) * ( i- i1*blockSize)  +  ( i2- i )  ; 
   int iT2 = s2 + ( j- j2*blockSize)  ;
   
   int firstBlockMinimum = i1 * this.blockSize + T[jT1];
   int lastBlockMinimum = i2 * this.blockSize + T[iT2];

   int[] indexes = new int[] {blockMinimum, firstBlockMinimum, lastBlockMinimum};
   int index = findMinimumIndex( indexes );
   
   return indexes[index];
  }

  
  public int findMinimumIndex(int[] idx) {
   int minIndex = Integer.MAX_VALUE;
   for (int i=0; i<idx.length; i++) {
    if (idx[i]>=0) {
     if (A[i]<minIndex) minIndex = i;
    }
   }
   return minIndex;
  }

 }
 

That is it, folks. Enjoy the journey. 

Find Cycles In A Directed Graph (DAG)

In the mathematical theory of directed graphs, a graph is said to be strongly connected if every vertex is reachable from every other vertex. Wikipedia

The condensation of G is a directed acyclic graph that has a vertex for every strongly connected component of G and an edge for every two components that are connected by an edge in G. Wikipedia

An arbitrary directed graph may also be transformed into a DAG, called its condensation, by contracting each of its strongly connected components into a single supervertex. Wikipedia

The strongly connected components of a directed graph may be found using an algorithm that uses depth-first search in combination with two stacks, one to keep track of the vertices in the current component and the second to keep track of the current search path. Wikipedia

One of the best known algorithm to find the strongly connected component is Tarjan's strongly connected components algorithm. Wikipedia

The basic algorithm steps are:

1. Start from any arbitrary vertex.

2. DFS from that vertex. For each node x, keep two numbers, dfs_index[x] and dfs_lowval[x].

dfs_index[x] stores when that node is visited, while dfs_lowval[x] = min( dfs_low[k]) where

k is all the children of x that is not the directly parent of x in the dfs-spanning tree.

3. All nodes with the same dfs_lowval[x] are in the same strongly connected component.

	    public void strongConnect(AdjMatrixDirectGraph<T> graph, Vertex<T> start) {
	        start.index = index;
	        start.lowval = index;
	        index++;
	        stack.push(start);
	         
	        List<Vertex<T>> neighbors = graph.getNeighbors(start);
	         
	        for(int i = 0; i < neighbors.size(); i++) {
	        	Vertex<T> neighbor = neighbors.get(i);
	             
	            if(neighbor.index == null) {
	            	strongConnect(graph, neighbor);
	            	start.lowval = Math.min(start.lowval, neighbor.lowval);
	            }
	            else if(stack.contains(neighbor)) {
	            	start.lowval = Math.min(start.lowval, neighbor.index);
	            }
	        }
	         
	        if(start.lowval == start.index) {
	            List<Vertex<T>> subset = new ArrayList<Vertex<T>>();
	            Vertex<T> neighbor = null;
	             
	            while(start != neighbor) {
	            	neighbor = stack.pop();
	            	subset.add(neighbor);
	            }
	             
	            set.add(subset);
	        }
	         
	    }
	}

From the strongly connected component, we can construct a separate DAG, from which we can find all cycles using modified Hierholzer's algorithm. 

The key of the algorithm is to have two stacks, the first one is for storing the forward path and the other is for backtracking. The backtracking is needed to cover unvisited edges for vertexes with multiple unvisited edges. 

		public List<Edge<T>> findCycle(List<Edge<T>> prefix, Vertex<T> start) {
			Stack<Edge<T>> forward =new Stack<Edge<T>>();
			Stack<Edge<T>> backtrack =new Stack<Edge<T>>();
			Edge<T> e = getUnvisitedEdge(start);
			while (e!=null) {
				e.visited=true;
				forward.push(e);
				e = getUnvisitedEdge(e.end);
			}
			
			while ( ( !forward.isEmpty() ) ) {
				e = forward.pop();
				backtrack.push(e);
			}

			List<Edge<T>> path = new LinkedList<Edge<T>>();
			if (prefix!=null) {
				for (Edge<T> e1 : prefix) {
					path.add(e1);
				}
			}
			while(!backtrack.isEmpty()) {
				Edge<T> edge = backtrack.pop();
				path.add(edge);
			}
			return path;
		}

Here is the entire source code with a test case:

package com.stones333.algorithm.graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;


/**
 * Find all cycles in DAG
 * 
 * @author stones
 *
 */

public class GraphFindCycles {
	
	static private class Vertex<T> {
		public T label;
		public boolean visited=false;
		public Integer index=null;
		public Integer lowval=null;
		public Vertex(T n) {
			this.label=n;
		}
		@Override
		public String toString() {
			return "Vertex-" + label;
		}

		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + ((label == null) ? 0 : label.hashCode());
			result = prime * result + (visited ? 1231 : 1237);
			return result;
		}
		@Override
		public boolean equals(Object obj) {
			if (this == obj) return true;
			if (obj == null) return false;
			if (getClass() != obj.getClass()) return false;
			Vertex other = (Vertex) obj;
			if (label == null) {
				if (other.label != null) return false;
			} else if (!label.equals(other.label)) return false;
			if (visited != other.visited) return false;
			return true;
		}
	}

	static private class Edge<T> {
		public Vertex<T> start;
		public Vertex<T> end;
		public boolean visited=false;
		public Edge(Vertex<T> start, Vertex<T> end) {
			this.start=start;
			this.end=end;
		}
		@Override
		public String toString() {
			return "Edge [start=" + start + ", end=" + end + ", visited="
					+ visited + "]";
		}
		
	}

	
	static private interface GraphInterface<T> {
		public void addVertex(Vertex<T> n) ;
		public boolean isVertexExist(Vertex<T> vertex);
		public void addEdge(Vertex<T> start, Vertex<T> end, double weight) ;
		public Vertex<T> getUnvisitedChildren(Vertex<T> n);
		
	}

	static private abstract class Graph<T> implements GraphInterface<T> {
		
		//DFS traversal of a tree is performed by the dfs() function
		public void dfs(Vertex<T> start) {
			//DFS uses Stack data structure
			Stack<Vertex<T>> stack =new Stack<Vertex<T>>();
			start.visited=true;
			stack.push(start);
			printNode(start);
			while(!stack.isEmpty()) {
				Vertex<T> n= stack.peek();
				Vertex<T> child=getUnvisitedChildren(n);
				if(child!=null) {
					child.visited=true;
					stack.push(child);
					printNode(child);
				} else {
					stack.pop();
				}
			}
		}

		//BFS traversal of a graph is performed by the bfs() function
		public void bfs(Vertex<T> start)
		{
			//BFS uses Queue data structure
			Queue<Vertex<T>> que=new LinkedList<Vertex<T>>();
			start.visited=true;
			que.add(start);
			printNode(start);
			
			while(!que.isEmpty()) {
				Vertex<T> n=(Vertex<T>)que.remove();
				Vertex<T> child=null;
				while((child=getUnvisitedChildren(n))!=null) {
					child.visited=true;
					que.add(child);
					printNode(child);
				}
			}
		}


		public void printNode(Vertex<T> n) {
			System.out.print(n.label+" ");
		}
	}

	static public class DirectedGraphFindAllPath<T>  {
		List<Edge<T>> edges=new ArrayList<Edge<T>>();
		List<Vertex<T>> vetexes=new ArrayList<Vertex<T>>();

		
		public DirectedGraphFindAllPath (StronglyConnectedTarjan<T> scc, Vertex<T> start) {
			List<WeightedEdge<T>> edges = scc.findStrongConnectEdges (start);
			for (WeightedEdge<T> edge : edges ) {
				this.addEdge(edge.start, edge.end);
			}
		}
		
		public DirectedGraphFindAllPath<T> addVetex(Vertex<T> n) {
			vetexes.add(n);
			return this;
		}

		public boolean isVetexExist(Vertex<T> vetex) {
			return ( vetexes.indexOf(vetex) >=0 ) ;
		}

		public boolean isAllEdgeVisited() {
			for (Edge<T> e : edges) {
				if (! e.visited) return false;
			}
			return true;
		}


		public List<List<Edge<T>>> findCycles(Vertex<T> start) {
			List<List<Edge<T>>> pathes = new LinkedList<List<Edge<T>>>();
			
			List<Edge<T>> cycle = findCycle(null, start);
			pathes.add(cycle);
			
			List<Edge<T>> current = new LinkedList<Edge<T>>();
			for (Edge<T> edge : cycle ) {
				current.add(edge);
				if ( hasUnvisitedEdge (edge.end) ) {
					List<Edge<T>> p = findCycle(current, edge.end);
					pathes.add(p);
				}
			}
			return pathes;
		}

		
		/**
		 * The key of the algorithm is to have two stacks, 
		 * the first one is for storing the forward path and the other is for backtracking. 
		 * The backtracking is needed to cover unvisited edges for vertexes with multiple edges. 
		 * 
		 * @param prefix
		 * @param start
		 * @return
		 */
		public List<Edge<T>> findCycle(List<Edge<T>> prefix, Vertex<T> start) {
			Stack<Edge<T>> forward =new Stack<Edge<T>>();
			Stack<Edge<T>> backtrack =new Stack<Edge<T>>();
			Edge<T> e = getUnvisitedEdge(start);
			while (e!=null) {
				e.visited=true;
				forward.push(e);
				e = getUnvisitedEdge(e.end);
			}
			
			while ( ( !forward.isEmpty() ) ) {
				e = forward.pop();
				backtrack.push(e);
			}

			List<Edge<T>> path = new LinkedList<Edge<T>>();
			if (prefix!=null) {
				for (Edge<T> e1 : prefix) {
					path.add(e1);
				}
			}
			while(!backtrack.isEmpty()) {
				Edge<T> edge = backtrack.pop();
				path.add(edge);
			}
			return path;
		}
		
		/**
		 * 1. Choose any starting vertex v, and follow a trail of edges from that vertex until returning to v. 
		 * It is not possible to get stuck at any vertex other than v, because the even degree of all vertices ensures that, 
		 * when the trail enters another vertex w there must be an unused edge leaving w. 
		 * The tour formed in this way is a closed tour, but may not cover all the vertices and edges of the initial graph.
		 * 
		 * 2. As long as there exists a vertex v that belongs to the current tour but that has adjacent edges not part of the tour, 
		 * start another trail from v, following unused edges until returning to v, 
		 * and join the tour formed in this way to the previous tour. 
		 * 
		 * @param start
		 * @return
		 */
		public List<Edge<T>> findHierholzerPath(Vertex<T> start) {
			Stack<Edge<T>> forward =new Stack<Edge<T>>();
			Stack<Edge<T>> backtrack =new Stack<Edge<T>>();
			Edge<T> e = getUnvisitedEdge(start);
			while (e!=null) {
				e.visited=true;
				forward.push(e);
				e = getUnvisitedEdge(e.end);
			}
			
			while ( ( !forward.isEmpty() ) ) {
				e = forward.pop();
				backtrack.push(e);
				e = getUnvisitedEdge(e.start);
				while (e!=null) {
					e.visited = true;
					forward.push(e);
					e = getUnvisitedEdge(e.end);
				}
			}

			List<Edge<T>> path = new LinkedList<Edge<T>>();
			while(!backtrack.isEmpty()) {
				Edge<T> edge = backtrack.pop();
				path.add(edge);
			}

			return path;
		}

		public void printPath(List<Edge<T>> path) {
			for (int i=0; i<path.size(); i++) {
				System.out.print(path.get(i).start.label + "->" + path.get(i).end.label + " ");
			}
		}

		public List<Edge<T>> findHierholzerPath(Vertex<T> start, Vertex<T> end) {

			List<Edge<T>> path = findHierholzerPath(start);
			if (path==null || path.size()==0) {
				System.out.println ("No Eulerian path found!");
			} else {
				if ( path.get(path.size()-1).end == end ) {
					System.out.println ("Eulerian path found:");
					this.printPath(path);		
				} else {
					System.out.println ("No Eulerian path found!");
				}
			}
			return path;
		}


		//This method will be called to make connect two nodes
		public DirectedGraphFindAllPath<T> addEdge(Vertex<T> start, Vertex<T> end, int weight ) {
			if ( ! isVetexExist(start) ) addVetex(start);
			if ( ! isVetexExist(end) ) addVetex(end);
			
			Edge<T> edge = new Edge<T>(start, end);
			edges.add(edge);
			return this;
		}

		
		//This method will be called to make connect two nodes
		public DirectedGraphFindAllPath<T> addEdge(Vertex<T> start, Vertex<T> end) {
			if ( ! isVetexExist(start) ) addVetex(start);
			if ( ! isVetexExist(end) ) addVetex(end);
			
			Edge<T> edge = new Edge<T>(start, end);
			edges.add(edge);
			return this;
		}
		
		public Vertex<T> getUnvisitedChildren(Vertex<T> n) {
			for (Edge<T> e : edges) {
				if ( e.visited==false && e.start.equals(n) ) {
					e.visited=true;
					return e.end;
				}
			}
			return null;
		}

		public boolean hasUnvisitedEdge(Vertex<T> n) {
			for (Edge<T> e : edges) {
				if ( e.visited==false && e.start.equals(n) ) {
					return true;
				}
			}
			return false;
		}

		
		public Edge<T> getUnvisitedEdge(Vertex<T> n) {
			for (Edge<T> e : edges) {
				if ( e.visited==false && e.start.equals(n) ) {
					e.visited=true;
					return e;
				}
			}
			return null;
		}

		
		public void clearNodes() {
			for ( Edge<T> e : edges)
				e.visited=false;
			
			for ( Vertex<T> v : vetexes)
				v.visited=false;

		}
	}

	static private class AdjMatrixDirectGraph<T> extends Graph<T> implements GraphInterface<T> {
		public ArrayList<Vertex<T>> vertexes=new ArrayList<Vertex<T>>();
		public double[][] adjMatrix;

		
		public void addVertex(Vertex<T> n) {
			vertexes.add(n);
		}

		public boolean isVertexExist(Vertex<T> vertex) {
			return ( vertexes.indexOf(vertex) >=0 ) ;
		}
		
		public List<Vertex<T>> getVertexes () {
			return vertexes;
		}

		public void addEdge(Vertex<T> start, Vertex<T> end) {
			addEdge(start, end, 1);
		}

		
		//This method will be called to make connect two nodes
		public void addEdge(Vertex<T> start, Vertex<T> end, double weight) {
			if ( ! isVertexExist(start) ) addVertex(start);
			if ( ! isVertexExist(end) ) addVertex(end); 

			if ( initAdjMatrix() ) {
				int startIndex=vertexes.indexOf(start);
				int endIndex=vertexes.indexOf(end);
				if (startIndex>=0 && endIndex>=0) {
					adjMatrix[startIndex][endIndex]=weight;
				}
			}
		}

		public boolean initAdjMatrix() {
			if (vertexes.size()<=0) return false;
			adjMatrix=buildAdjMatrix(adjMatrix, vertexes.size());
			return true;
		}

		private double [][] buildAdjMatrix(double[][] prevMatrix, int newSize) {
			if (newSize==0) return null;
			double[][] matrix=new double[newSize][newSize];
			
			for (int i=0; i<newSize; i++) 
				for (int j=0; j<newSize; j++) 
					matrix[i][j] = Double.POSITIVE_INFINITY;

			if (prevMatrix!=null) {
				for (int i=0; i<prevMatrix.length; i++) 
					for (int j=0; j<prevMatrix[i].length; j++) 
						matrix[i][j] = prevMatrix[i][j];
			}
			return matrix;
		}
		
		
		public List<Vertex<T>> getNeighbors(Vertex<T> n) {
			List<Vertex<T>> list = new ArrayList <Vertex<T>>();
			int index=vertexes.indexOf(n);
			for (int j=0; j<vertexes.size(); j++) {
				if( adjMatrix[index][j]!=Double.POSITIVE_INFINITY ) {
					list.add((Vertex<T>)vertexes.get(j));
				}
			}
			return list;
		}
		
		public Vertex<T> getUnvisitedChildren(Vertex<T> n) {
			
			int index=vertexes.indexOf(n);
			int j=0;
			while(j<vertexes.size()) {
				if( adjMatrix[index][j]!=Double.POSITIVE_INFINITY && vertexes.get(j).visited==false ) {
					return (Vertex<T>)vertexes.get(j);
				}
				j++;
			}
			return null;
		}

		public List<WeightedEdge<T>> getEdges(Vertex<T> n) {
			
			List<WeightedEdge<T>> edges = new LinkedList<WeightedEdge<T>>();
			int index=vertexes.indexOf(n);
			int j=0;
			while(j<vertexes.size()) {
				if( adjMatrix[index][j]!=Double.POSITIVE_INFINITY  ) {
					edges.add(new WeightedEdge<T> (n, vertexes.get(j),  adjMatrix[index][j]) );
				}
				j++;
			}
			return edges;
		}

		public List<WeightedEdge<T>> getEdges() {
			List<WeightedEdge<T>> edges = new LinkedList<WeightedEdge<T>>();
			for (int i=0; i<adjMatrix.length; i++) {
				for (int j=0; j<adjMatrix[i].length; j++) {
					if( adjMatrix[i][j]!=Double.POSITIVE_INFINITY  ) {
						edges.add(new WeightedEdge<T> (vertexes.get(i), vertexes.get(j),  adjMatrix[i][j]) );
					}
				}
			}
			return edges;
		}


		public void printVertexes() {
			for (int i=0; i<vertexes.size(); i++ ) {
				System.out.print(vertexes.get(i) + " " );
			}
			System.out.println();
		}

		
		
		//Utility methods for clearing visited property of node
		public void clearNodes() {
			int i=0;
			while(i<vertexes.size()) {
				vertexes.get(i).visited=false;
				i++;
			}
		}
		
	}

	static private class WeightedEdge<T>  extends  Edge<T> {
		public final double weight;
		public boolean visited=false;
		public WeightedEdge(Vertex<T> start, Vertex<T> end, double weight) {
			super(start, end);
			this.weight=weight;
		}
		

		public int compareTo(WeightedEdge<T> that) {
			if (this.weight < that.weight) 
				return -1;
			else if (this.weight > that.weight) 
				return +1;
			else 
				return 0;
		 }

		@Override
		public String toString() {
			return "WeightedEdge [start=" + start + ", end=" + end
					+ ", weight=" + weight + ", visited=" + visited + "]";
		}
	}

	
	static public class StronglyConnectedTarjan<T> {
		public AdjMatrixDirectGraph<T> graph;
		public int index;
	    public Stack<Vertex<T>> stack;
	    public List<List<Vertex<T>>> set;

	    public void printConnected () {
	    	  for(int i = 0; i < set.size(); i++) {
	              System.out.println("Set " + i + ": " + Arrays.toString(set.get(i).toArray()));
	    	  }
	    }

	    public StronglyConnectedTarjan(AdjMatrixDirectGraph<T> graph) {
	    	this.graph = graph;
	    	stack = new Stack<Vertex<T>> ();
	    	set = new ArrayList<List<Vertex<T>>> ();
	    	
	    	for( Vertex<T> node : graph.vertexes) {
	            if(node.index == null) 
	            	strongConnect(graph, node);
	        }
	    }
	    
	    public List<WeightedEdge<T>> findStrongConnectEdges (Vertex<T> node) {
	    	List<WeightedEdge<T>> edges = new ArrayList<WeightedEdge<T>>();
	    	 for (List<Vertex<T>> c : set) {
	    		 if ( c.contains(node) ) {
	    			 for (int i=0; i<graph.adjMatrix.length; i++) {
	    				 for (int j=0; j<graph.adjMatrix[i].length; j++) {
	    					
	    						if( graph.adjMatrix[i][j]!=Double.POSITIVE_INFINITY 
	    								&& c.contains(graph.vertexes.get(i)) 
	    								&& c.contains(graph.vertexes.get(j)) ) {
	    							edges.add(new WeightedEdge<T> (graph.vertexes.get(i), graph.vertexes.get(j),  graph.adjMatrix[i][j]) );
	    						}

	    				 }
	    			 }
	    		 }
	    	 }
	    	
	    	
	    	return edges;
	    }
	    

	    /**
	     *
	     * 1. Start from any arbitrary vertex.
	     * 
	     * 2. DFS from that vertex. For each node x, keep two numbers, dfs_index[x] and dfs_lowval[x]. 
	     * dfs_index[x] stores when that node is visited, while dfs_lowval[x] = min( dfs_low[k]) where 
	     * k is all the children of x that is not the directly parent of x in the dfs-spanning tree.
	     * 
	     * 3. All nodes with the same dfs_lowval[x] are in the same strongly connected component.
	     * 
	     * @param graph
	     * @param start
	     */
	    public void strongConnect(AdjMatrixDirectGraph<T> graph, Vertex<T> start) {
	        start.index = index;
	        start.lowval = index;
	        index++;
	        stack.push(start);
	         
	        List<Vertex<T>> neighbors = graph.getNeighbors(start);
	         
	        for(int i = 0; i < neighbors.size(); i++) {
	        	Vertex<T> neighbor = neighbors.get(i);
	             
	            if(neighbor.index == null) {
	            	strongConnect(graph, neighbor);
	            	start.lowval = Math.min(start.lowval, neighbor.lowval);
	            }
	            else if(stack.contains(neighbor)) {
	            	start.lowval = Math.min(start.lowval, neighbor.index);
	            }
	        }
	         
	        if(start.lowval == start.index) {
	            List<Vertex<T>> subset = new ArrayList<Vertex<T>>();
	            Vertex<T> neighbor = null;
	             
	            while(start != neighbor) {
	            	neighbor = stack.pop();
	            	subset.add(neighbor);
	            }
	             
	            set.add(subset);
	        }
	         
	    }
	}

	public static void main(String[] args) {
		System.out.println("testFindCycle -->");
		testFindCycle();

	}

	private static void testFindCycle() {
		Vertex<String> nA = new Vertex<String>("A");
		Vertex<String> nB = new Vertex<String>("B");
		Vertex<String> nC = new Vertex<String>("C");
		Vertex<String> nD = new Vertex<String>("D");
		Vertex<String> nE = new Vertex<String>("E");
		Vertex<String> nF = new Vertex<String>("F");
		Vertex<String> nG = new Vertex<String>("G");
		Vertex<String> nH = new Vertex<String>("H");

		//Create the graph, add nodes, create edges between nodes
		AdjMatrixDirectGraph<String> g=new AdjMatrixDirectGraph<String>();
		
		g.addEdge(nA, nB); g.addEdge(nB, nC); g.addEdge(nC, nA); g.addEdge(nB, nA); 
		g.addEdge(nD, nB); g.addEdge(nD, nC); g.addEdge(nD, nF);
		g.addEdge(nF, nD); g.addEdge(nE, nC);
		g.addEdge(nE, nG); g.addEdge(nG, nE);
		g.addEdge(nH, nF); g.addEdge(nH, nH);

		StronglyConnectedTarjan<String> scc = new StronglyConnectedTarjan<String>(g);
//		scc.printConnected();
//	    List<WeightedEdge<String>> edges = scc.findStrongConnectEdges (nA);
//	    for (WeightedEdge<String> e: edges) {
//	    	System.out.println(e);
//	    }
	    
	    DirectedGraphFindAllPath<String> findCycle = new DirectedGraphFindAllPath<String> (scc, nA);
		List<List<Edge<String>>> pathes = findCycle.findCycles(nA);
		for (List<Edge<String>> path : pathes) {
			System.out.println("");
			System.out.print("cycle: ");
			findCycle.printPath(path);
		}

		
	}


}

The graph edges are
(nA, nB), (nB, nC), (nC, nA), addEdge(nB, nA); (nD, nB), (nD, nC), (nD, nF); (nF, nD), (nE, nC), (nE, nG); (nG, nE), (nH, nF), (nH, nH);

The output:

cycle: A->B B->A 
cycle: A->B B->C C->A 

Enjoy the journey, have fun.

Find Eulerian Path In A Directed Graph

An Eulerian path is a trail in a graph which visits every edge exactly once. There are many problems are in the category of finding Eulerian path. For example, given a stack of airplane (bus) ticket stubs, reconstruct the travel journey assuming we know where the journey starts.

Hierholzer's algorithm is an elegant and efficient algorithm. It takes linear time.

• Choose any starting vertex v, and follow a trail of edges from that vertex until returning to v. It is not possible to get stuck at any vertex other than v, because the even degree of all vertices ensures that, when the trail enters another vertex w there must be an unused edge leaving w. The tour formed in this way is a closed tour, but may not cover all the vertices and edges of the initial graph.

• As long as there exists a vertex v that belongs to the current tour but that has adjacent edges not part of the tour, start another trail from v, following unused edges until returning to v, and join the tour formed in this way to the previous tour.

The key of the algorithm is to have 2 stacks, the first one is for storing the forward path and the other is for backtracking. We need the backtracking to cover unvisited edges for vertexes with multiple edges.

    public List<Edge<T>> findHierholzerPath(Vertex<T> start) {
   Stack<Edge<T>> forward =new Stack<Edge<T>>();
   Stack<Edge<T>> backtrack =new Stack<Edge<T>>();
   Edge<T> e = getUnvisitedEdge(start);
   while (e!=null) {
    e.visited=true;
    forward.push(e);
    e = getUnvisitedEdge(e.end);
   }
   
   while ( ( !forward.isEmpty() ) ) {
    e = forward.pop();
    backtrack.push(e);
    e = getUnvisitedEdge(e.start);
    while (e!=null) {
     e.visited = true;
     forward.push(e);
     e = getUnvisitedEdge(e.end);
    }
   }

   List<Edge<T>> path = new LinkedList<Edge<T>>();
   while(!backtrack.isEmpty()) {
    Edge<T> edge = backtrack.pop();
    path.add(edge);
   }

   return path;
  }

Here is the source code in it entirety with test cases:

package com.stones333.algorithm;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

/**
 * Java implementation of Hierholzer's algorithm to find an Eulerian path in a directed graph 
 * 
 * http://en.wikipedia.org/wiki/Eulerian_path
 * 
 * @author stones333
 *
 */
public class EulerianPath {
 
 static private class Vertex<T> {
  public T label;
  public boolean visited=false;
  public Vertex(T n) {
   this.label=n;
  }
 }

 static private class Edge<T> {
  public Vertex<T> start;
  public Vertex<T> end;
  public boolean visited=false;
  public Edge(Vertex<T> start, Vertex<T> end) {
   this.start=start;
   this.end=end;
  }
 }

 
 static private interface GraphInterface<T> {
  public Graph addVetex(Vertex<T> n) ;
  public boolean isVetexExist(Vertex<T> vetex);
  public Graph addEdge(Vertex<T> start, Vertex<T> end) ;
  public Vertex<T> getUnvisitedChildren(Vertex<T> n);
  
 }
 
 static private abstract class Graph<T> implements GraphInterface<T> {

  
  //DFS traversal of a tree is performed by the dfs() function
  public void dfs(Vertex<T> start) {
   //DFS uses Stack data structure
   Stack<Vertex<T>> stack =new Stack<Vertex<T>>();
   start.visited=true;
   stack.push(start);
   printNode(start);
   while(!stack.isEmpty()) {
    Vertex<T> n= stack.peek();
    Vertex<T> child=getUnvisitedChildren(n);
    if(child!=null) {
     child.visited=true;
     stack.push(child);
     printNode(child);
    } else {
     stack.pop();
    }
   }
  }

  //BFS traversal of a graph is performed by the bfs() function
  public void bfs(Vertex<T> start)
  {
   //BFS uses Queue data structure
   Queue<Vertex<T>> que=new LinkedList<Vertex<T>>();
   start.visited=true;
   que.add(start);
   printNode(start);
   
   while(!que.isEmpty()) {
    Vertex<T> n=(Vertex<T>)que.remove();
    Vertex<T> child=null;
    while((child=getUnvisitedChildren(n))!=null) {
     child.visited=true;
     que.add(child);
     printNode(child);
    }
   }
  }

  public void printPath(List<Edge<T>> path) {
   for (int i=0; i<path.size(); i++) {
    System.out.print(path.get(i).start.label + "->" + path.get(i).end.label + " ");
   }
  }
  
  public void printEdge(Edge<T> e) {
   System.out.print(e.start.label + "->" + e.end.label );
  }

  public void printNode(Vertex<T> n) {
   System.out.print(n.label+" ");
  }
 }

 
 static private class DirectedGraph<T> extends Graph<T> implements GraphInterface<T> {
  List<Edge<T>> edges=new ArrayList<Edge<T>>();
  List<Vertex<T>> vetexes=new ArrayList<Vertex<T>>();

  public Graph addVetex(Vertex<T> n) {
   vetexes.add(n);
   return this;
  }

  public boolean isVetexExist(Vertex<T> vetex) {
   return ( vetexes.indexOf(vetex) >=0 ) ;
  }

  public boolean isAllEdgeVisited() {
   for (Edge<T> e : edges) {
    if (! e.visited) return false;
   }
   return true;
  }

  public List<Edge<T>> findHierholzerPath(Vertex<T> start) {
   Stack<Edge<T>> forward =new Stack<Edge<T>>();
   Stack<Edge<T>> backtrack =new Stack<Edge<T>>();
   Edge<T> e = getUnvisitedEdge(start);
   while (e!=null) {
    e.visited=true;
    forward.push(e);
    e = getUnvisitedEdge(e.end);
   }
   
   while ( ( !forward.isEmpty() ) ) {
    e = forward.pop();
    backtrack.push(e);
    e = getUnvisitedEdge(e.start);
    while (e!=null) {
     e.visited = true;
     forward.push(e);
     e = getUnvisitedEdge(e.end);
    }
   }

   List<Edge<T>> path = new LinkedList<Edge<T>>();
   while(!backtrack.isEmpty()) {
    Edge<T> edge = backtrack.pop();
    path.add(edge);
   }

   return path;
  }

  public List<Edge<T>> findHierholzerPath(Vertex<T> start, Vertex<T> end) {

   List<Edge<T>> path = findHierholzerPath(start);
   if (path==null || path.size()==0) {
    System.out.println ("\nNo Eulerian path found!");
   } else {
    if ( path.get(path.size()-1).end == end ) {
     System.out.println ("\nEulerian path found:");
     this.printPath(path);  
    } else {
     System.out.println ("\nNo Eulerian path found!");
    }
   }
   return path;
  }



  //This method will be called to make connect two nodes
  public Graph addEdge(Vertex<T> start, Vertex<T> end) {
   if ( ! isVetexExist(start) ) addVetex(start);
   if ( ! isVetexExist(end) ) addVetex(end);
   
   Edge<T> edge = new Edge<T>(start, end);
   edges.add(edge);
   return this;
  }
  
  public Vertex<T> getUnvisitedChildren(Vertex<T> n) {
   for (Edge<T> e : edges) {
    if ( e.visited==false && e.start.equals(n) ) {
     e.visited=true;
     return e.end;
    }
   }
   return null;
  }

  public Edge<T> getUnvisitedEdge(Vertex<T> n) {
   for (Edge<T> e : edges) {
    if ( e.visited==false && e.start.equals(n) ) {
     e.visited=true;
     return e;
    }
   }
   return null;
  }

  
  public void clearNodes() {
   for ( Edge<T> e : edges)
    e.visited=false;
   
   for ( Vertex<T> v : vetexes)
    v.visited=false;

  }
 }
 
 private static void testEulerianPathCase2() {
  //Lets create nodes as given as an example in the article
  Vertex<String> nA=new Vertex<String>("A"), nB=new Vertex<String>("B");
  Vertex<String> nC=new Vertex<String>("C"), nD=new Vertex<String>("D");
  Vertex<String> nE=new Vertex<String>("E"), nF=new Vertex<String>("F");


  DirectedGraph<String> g=new DirectedGraph<String>();
  
  g.addEdge(nA,nB); g.addEdge(nB,nC); g.addEdge(nC,nD); g.addEdge(nD,nE);
  g.addEdge(nB,nC); g.addEdge(nC,nF); g.addEdge(nF,nB);
  List<Edge<String>> path = g.findHierholzerPath(nA, nE);
 }

 private static void testEulerianPathCase1() {
  Vertex<String> nA=new Vertex<String>("A"), nB=new Vertex<String>("B");
  Vertex<String> nC=new Vertex<String>("C"), nD=new Vertex<String>("D");
  DirectedGraph<String> g=new DirectedGraph<String>();

  g.addEdge(nA,nB).addEdge(nB,nC).addEdge(nC,nD).addEdge(nD,nA).addEdge(nA,nC);
  
  List<Edge<String>> path = g.findHierholzerPath(nA, nC);
 }

 private static void testNegEulerianPathCase1() {
  Vertex<String> nA=new Vertex<String>("A"), nB=new Vertex<String>("B");
  Vertex<String> nC=new Vertex<String>("C"), nD=new Vertex<String>("D");
  DirectedGraph<String> g=new DirectedGraph<String>();
  
  g.addEdge(nA,nB).addEdge(nB,nC).addEdge(nC,nD).addEdge(nD,nA).addEdge(nA,nC);
  
  List<Edge<String>> path = g.findHierholzerPath(nA, nD);
 }
 
 public static void main(String[] args) {

  System.out.println ("\ntestEulerianPathCase1:");
  testEulerianPathCase1();
  
  System.out.println ("\ntestNegEulerianPathCase1:");
  testNegEulerianPathCase1();
  
  System.out.println ("\ntestEulerianPathCase2:");
  testEulerianPathCase2();
 }

}

Have fun and enjoy the journey.

Algorithms to sort negative and positive integer array

Here is the problem: Given an array with n integers, which has both positive and negative integers. Sort the array in the way that, the negatives are placed before positives.

i.e.

Input :    [-1, 2, 1, 12, -9, 3, -4, 4, -3, 21, 52, 4, -2]
Output : [-1, -9, -4, -3, -2, 2, 1, 12, 3, 4, 21, 52, 4]

We will consider the following:
1. Time complexity
2. Space requirement
3. Stability 

If we treat negative numbers as 0 and positive numbers as 1, this is a 0-1 sorting problem.


Algorithm 1: Loop through the array from both ends, swap negatives with positives if they are misplaced. 

Time Complexity: O(N)

Space Requirement: O(1)

But not stable. 

   
static public class NegativePositiveSwapSorter extends NegativePositiveBaseSorter implements Sorter {

  public void sort(int[] a) {
   if (a==null || a.length<=1)
    return;

   int i = 0, j = a.length-1;
   while (i<=j) {
    while (a[i]<0 && i<=j) i++;
    while (a[j]>0 && i<=j) j--;
    if (i<j ) swap(a, i, j);
    i++;
    j--;
   }
  }
 }

Algorithm 2: Loop through the array, count the number of negatives (z). Scan the array the second time, and maintain two counters c0 and c1. c0 counting the number of negatives and c1 sums up the number positives to the left of the current position.

If a[i]<0, final position is (a[i]<0 ? 0 : 1 ) * z + c0

If a[i]<0, final position is (a[i]<0 ? 0 : 1 ) * z + c1

Time Complexity: O(N)

Space Requirement: O(N)

Stable  

   static public class NegativePositiveCountSorter extends NegativePositiveBaseSorter implements Sorter {

  public void sort(int[] a) {
   if (a==null || a.length<=1) return;
   
   // z is count of negatives  
   int z=0;
   for (int i=0; i<a.length; i++) {
    if (a[i]<0) z++;
   }
   int c0=0, c1=0;
   
   int [] c = new int[a.length];
   for (int i=0; i<a.length; i++) {
    int idx=0;
    if (a[i]<0) {
     idx= (a[i]<0 ? 0 : 1 ) * z + c0;
     c0++;
    } else {
     idx= (a[i]<0 ? 0 : 1 )  * z + c1;
     c1++;
    }
    c[idx] = a[i];
   }

   System.arraycopy(c, 0, a, 0, a.length);
  }
 }

Algorithm 3: Loop through the array, and swap negative number block and positive number block with rotating (Juggling)

Time Complexity: O( N0 x N1 ) 

Space Requirement: O(1)

Stable  

    

 static public class NegativePositiveSorterViaRotationWithJuggling extends NegativePositiveBaseSorter implements Sorter {


  public void sort(int[] a) {
   if (a==null || a.length<=1)
    return;

   int start = 0, mid=0, end=0, num = 1;
   do {
    start = skipNegBlock(a, start);
    mid = skipPosBlock(a, end==0? start : end);
    end = skipNegBlock(a, mid);
    num = rotateleftByJuggling(a, start, mid-start, end-start);
   } while (num>0);
  }
 }

Here is the transformation:

Step: 1 Array: [-1, 2, 1, 12, -9, 3, -4, 4, -3, 21, 52, 4, -2]

Step: 2 Array: [-1, -9, 2, 1, 12, 3, -4, 4, -3, 21, 52, 4, -2]

Step: 3 Array: [-1, -9, -4, 2, 1, 12, 3, 4, -3, 21, 52, 4, -2]

Step: 4 Array: [-1, -9, -4, -3, 2, 1, 12, 3, 4, 21, 52, 4, -2]

Step: 5 Array: [-1, -9, -4, -3, -2, 2, 1, 12, 3, 4, 21, 52, 4]

Step: 6 Array: [-1, -9, -4, -3, -2, 2, 1, 12, 3, 4, 21, 52, 4]

Algorithm 4: Loop through the array, and swap negative number block and positive number block with double reverse

Time Complexity: O( N0 * N1 )

Space Requirement: O(1)

Stable  

    

 static public class NegativePositiveSorterViaBlockSwapWithReverse extends NegativePositiveBaseSorter implements Sorter {

  public void sort(int[] a) {
   if (a==null || a.length<=1)
    return;
   
   int start = 0, mid=0, end=0, num = 1;
   do {
    start = skipNegBlock(a, start);
    mid = skipPosBlock(a, end==0? start : end);
    end = skipNegBlock(a, mid);
    num = swapBlockWithReverse(a, start, mid, end);
   } while (num>0);
  }
 }

Here is the transformation: 

Step: 1 Array: [-1, 2, 1, 12, -9, 3, -4, 4, -3, 21, 52, 4, -2]

Step: 2 Array: [-1, -9, 2, 1, 12, 3, -4, 4, -3, 21, 52, 4, -2]

Step: 3 Array: [-1, -9, -4, 2, 1, 12, 3, 4, -3, 21, 52, 4, -2]

Step: 4 Array: [-1, -9, -4, -3, 2, 1, 12, 3, 4, 21, 52, 4, -2]

Step: 5 Array: [-1, -9, -4, -3, -2, 2, 1, 12, 3, 4, 21, 52, 4]

Step: 6 Array: [-1, -9, -4, -3, -2, 2, 1, 12, 3, 4, 21, 52, 4]

Algorithm 5: Loop through the array, Loop through the array, and swap negative number block and positive number block with rotating. 

Time Complexity: O( n log(n) )

Space Requirement: O(1)

Stable  

 
  public void sort(int[] a) {
   if (a==null || a.length<=1)
    return;

   int start = 0, mid=0, end=0, num = 1;
   do {
    start = skipNegBlock(a, start);
    mid = skipPosBlock(a, end==0? start : end);
    end = skipNegBlock(a, mid);
    num = rotateleft(a, start, mid-start, end-start);
   } while (num>0);
  }

Here is the transformation: 

Step: 1 Array: [-1, 2, 1, 12, -9, 3, -4, 4, -3, 21, 52, 4, -2]

Step: 2 Array: [-1, -9, 2, 1, 12, 3, -4, 4, -3, 21, 52, 4, -2]

Step: 3 Array: [-1, -9, -4, 2, 1, 12, 3, 4, -3, 21, 52, 4, -2]

Step: 4 Array: [-1, -9, -4, -3, 2, 1, 12, 3, 4, 21, 52, 4, -2]

Step: 5 Array: [-1, -9, -4, -3, -2, 2, 1, 12, 3, 4, 21, 52, 4]

Step: 6 Array: [-1, -9, -4, -3, -2, 2, 1, 12, 3, 4, 21, 52, 4]

Here is the entire source code:

 

package com.lei.algorithm;

import java.util.Arrays;

/**
 *
 * Algorithms to sort negatives in front of positives for an integer array
 * 
 * @author stones333
 *
 */
public class NegativePositiveIntergerSorter {


 /**
  * Sorter interface
  *
  */
 static public interface Sorter {
  void sort(int[] a);
  void print(int[] a);
 }

 /**
  * Base class for Sorter with utility methods   
  * 
  * @author stones333
  *
  */
 static public abstract class NegativePositiveBaseSorter implements Sorter {
  
  /**
   * swap array item position i and j
   *  
   * @param a
   * @param i
   * @param j
   */
  public void swap(int[] a, int i, int j) {
   a[i] = a[i] + a[j];
   a[j] = a[i] - a[j];
   a[i] = a[i] - a[j];
  }

  /**
   * reverse the array a[] between position i and j. 
   * @param a
   * @param i, inclusive 
   * @param j, exclusive 
   */
  public void reverse(int[] a, int i, int j) {
   while (i<j) {
    swap(a, i, j);
    i++;
    j--;
   }
  }

  /**
   * advance array index by n position.  
   * 
   * @param a
   * @param start
   * @param n
   * @return
   */
  public int advance(int[] a, int start, int n) {
   return ( (start+n)>a.length) ? a.length : (start+n);
  }

  /**
   * 
   * swap array block of n item starting from position i and j
   * 
   * @param a
   * @param i
   * @param j
   * @param n
   */
  public void swap(int[] a, int i, int j, int n) {
   if (i==j|| n==0) return;
   for (;n>0; n--) 
    swap(a, i++, j++);

  }

  
  /**
   * skip the negative block until positive number
   * 
   * @param a
   * @param begin
   * @return
   */
  public int skipNegBlock(int[] a, int begin) {
   int start=begin;
   while (start<a.length && a[start]<0 ) start++;
   return start;
  }

  /**
   * skip the positive block until negative  number
   * 
   * @param a
   * @param begin
   * @return
   */
  public int skipPosBlock(int[] a, int begin) {
   int start=begin;
   while (start<a.length && a[start]>0 ) start++;
   return start;
  }
  
  /**
   * swap the blocks, the first from start to mid-1, with the second from mid to end-1 
   * 
   * @param a
   * @param start
   * @param mid
   * @param end
   * @return
   */
  public int swapBlockWithReverse(int[] a, int start, int mid, int end) {
   reverse(a, start, mid-1);
   reverse(a, mid, end-1);
   reverse(a, start, end-1);
   return end-mid;
  }

  public void pickAndSwapBlock(int[] a, int start, int mid, int end) {
   
   while (start<mid && a[start]<0 ) start++;
   int start2=mid;
   while (start2<end && a[start2]<0 ) start2++;
   if (start<=mid && start2>=mid && start2<=end) {
    swapBlockWithReverse(a, start, mid, start2);
   }
  }


  /**
   * print the array content 
   * 
   * @param a
   */
  public void print(int[] a) {
   System.out.println( "Array: " + Arrays.toString(a) );
  }

  
  /**
   * print the array content with step number 
   * 
   * @param step
   * @param a
   */
  public void print(int step, int[] a) {
   System.out.println( "Step: " + step + " Array: " + Arrays.toString(a) );
  }

 }
 
 
 /**
  *
  * Algorithm 1: Loop through the array from both ends, swap negatives with positives if they are misplaced.
  * 
  * Time Complexity: O(N)
  * Space Requirement: O(1)
  * Not stable  
  * 
  * @author stones333
  *
  */
 static public class NegativePositiveSwapSorter extends NegativePositiveBaseSorter implements Sorter {

  public void sort(int[] a) {
   if (a==null || a.length<=1)
    return;

   int i = 0, j = a.length-1;
   while (i<=j) {
    while (a[i]<0 && i<=j) i++;
    while (a[j]>0 && i<=j) j--;
    if (i<j ) swap(a, i, j);
    i++;
    j--;
   }
  }
 }
 

 /**
  *
  * Algorithm 2: Loop through the array, count the number of negatives (z). Scan the array the second time, and maintain two counters c0 and c1. 
  * c0 counting the number of negatives and c1 sums up the number positives to the left of the current position.
  *
  * If a[i]<0, final position is (a[i]<0 ? 0 : 1 ) * z + c0
  * If a[i]<0, final position is (a[i]<0 ? 0 : 1 ) * z + c1
  * 
  * 
  * Time Complexity: O(N)
  * Space Requirement: O(N)
  * Stable  
  * 
  * @author stones333
  *
  */
 static public class NegativePositiveCountSorter extends NegativePositiveBaseSorter implements Sorter {

  public void sort(int[] a) {
   if (a==null || a.length<=1) return;
   
   // z is count of negatives  
   int z=0;
   for (int i=0; i<a.length; i++) {
    if (a[i]<0) z++;
   }
   int c0=0, c1=0;
   
   int [] c = new int[a.length];
   for (int i=0; i<a.length; i++) {
    int idx=0;
    if (a[i]<0) {
     idx= (a[i]<0 ? 0 : 1 ) * z + c0;
     c0++;
    } else {
     idx= (a[i]<0 ? 0 : 1 )  * z + c1;
     c1++;
    }
    c[idx] = a[i];
   }

   System.arraycopy(c, 0, a, 0, a.length);
  }
 }

 /**
  *
  * Algorithm 3: Loop through the array, and swap negative number block and positive number block with rotating (Juggling)
  * 
  * Time Complexity: O( N0 x N1 ) 
  * Space Requirement: O(1)
  * Stable  
  * 
  * @author stones333
  *
  */
 static public class NegativePositiveSorterViaRotationWithJuggling extends NegativePositiveBaseSorter implements Sorter {

  /**
   * return gcd of i and j
   * 
   * @param i
   * @param j
   * @return
   */
  public int gcd( int i, int j ) {
   if ( i == 0 ) return j;
   if ( j == 0 ) return i;
   while ( i != j ) {
    if ( i > j ) 
           i -= j;
          else        
           j -= i;
   }
   return i;
  }

  /**
   * 
   * rotates array a[] of size n by d elements, start from position st
   * 
   * Steps: 
   * 1. A is the left subarray, B is the right subarray — that is, the starting point is AB
   * 2. If A is shorter, divide B into Bl and Br, such that length of Br equals the length of A
   * 3. Swap A and Br to change ABlBr into BrBlA
   * 4. Recur on the two pieces of B
   * 5. Once A and B are of equal lengths, swap A and B
   * 
   * @param a
   * @param st
   * @param d
   * @param n
   * @return number of items rotated 
   */
  public int rotateleftByJuggling(int a[], int st, int d, int n) {
   
   if (d == 0 || d == n)
    return 0;

   int i, j, k, temp;
   for (i =0; i < gcd(d-st, n-st); i++)
   {
    /* move i-th values of blocks */
    temp = a[i+st];
    j = i;
    while(true)
    {
     k = j + d;
     if (k >= n) 
      k = k - n;
     if (k == i) break;
     a[j+st] = a[k+st];
     j = k;
    }
    a[j+st] = temp;
   }
   return d;
  }

  public void sort(int[] a) {
   if (a==null || a.length<=1)
    return;

   int step=1;
   this.print(step++, a);
   
   int start = 0, mid=0, end=0, num = 1;
   do {
    start = skipNegBlock(a, start);
    mid = skipPosBlock(a, end==0? start : end);
    end = skipNegBlock(a, mid);
    num = rotateleftByJuggling(a, start, mid-start, end-start);
    this.print(step++, a);
   } while (num>0);
  }
 }

 /**
  *
  * Algorithm 4: Loop through the array, and swap negative number block and positive number block with double reverse
  * 
  * Time Complexity: O( N0 x N1 ) 
  * Space Requirement: O(1)
  * Stable  
  * 
  * @author stones333
  *
  */
 static public class NegativePositiveSorterViaBlockSwapWithReverse extends NegativePositiveBaseSorter implements Sorter {

  public void sort(int[] a) {
   if (a==null || a.length<=1)
    return;
   
   int start = 0, mid=0, end=0, num = 1;
   do {
    start = skipNegBlock(a, start);
    mid = skipPosBlock(a, end==0? start : end);
    end = skipNegBlock(a, mid);
    num = swapBlockWithReverse(a, start, mid, end);
   } while (num>0);
  }
 }



 /**
  *
  * Algorithm 5: Loop through the array, and swap negative number block and positive number block with rotating 
  * 
  * Time Complexity: O( N0 x N1 ) 
  * Space Requirement: O(1)
  * Stable  
  * 
  * @author stones333
  *
  */
 static public class NegativePositiveSorterViaRotationWithBlockSwap extends NegativePositiveBaseSorter implements Sorter {

  /**
   * 
   * rotates array a[] of size n by d elements, start from st
   * 
   * Steps: 
   * 1. A is the left subarray, B is the right subarray — that is, the starting point is AB
   * 2. If A is shorter, divide B into Bl and Br, such that length of Br equals the length of A
   * 3. Swap A and Br to change ABlBr into BrBlA
   * 4. Recur on the two pieces of B
   * 5. Once A and B are of equal lengths, swap A and B
   * 
   * @param a
   * @param st
   * @param d
   * @param n
   * @return number of items rotated 
   */
  public int rotateleftByBlockSwap(int a[], int st, int d, int n) {
   
   if(d == 0 || d == n)
    return 0;
   
   int i, j;
   i = d;
   j = n - d;
   while (i != j)
   {
    if (i < j)  {  // A is shorter
     swap(a, st+d-i, st+d+j-i, i);
     j -= i;
    }
    else { // B is shorter
     swap(a, st+d-i, st+d, j);
     i -= j;
    }
   }
   // swap block swap A and B
   swap(a, st+d-i, st+d, i);
   return d;
  }
 

  public void sort(int[] a) {
   if (a==null || a.length<=1)
    return;

   int start = 0, mid=0, end=0, num = 1;
   do {
    start = skipNegBlock(a, start);
    mid = skipPosBlock(a, end==0? start : end);
    end = skipNegBlock(a, mid);
    num = rotateleftByBlockSwap(a, start, mid-start, end-start);
   } while (num>0);
  }
 }

 

 

 /**
  * Algorithm 6 is based on lg(N) blocking.
  * 
  * 
  * @author stones333
  *
  */
 
 static public class NegativePositiveSorterViaBlockSwap extends NegativePositiveBaseSorter implements Sorter {

  public void sort(int[] a) {
   if (a==null || a.length<=1)
    return;

   int num=2;
   int start, mid, end;  

   while (num<a.length) {
    start = 0;
    mid= advance(a, start, num/2); 
    end = advance(a, start, num);  
    while (start<end) {
     pickAndSwapBlock(a, start, mid, end);
     start=end;
     mid= advance(a, start, num/2);
     end = advance(a, start, num);  
    }
    num = num * 2;
   }
   mid= advance(a, 0, num/2);
   end = advance(a, 0, num);  
   pickAndSwapBlock(a, 0, mid, end);
  }
 }

 // test code for NegativePositiveSorterViaRotationWithJuggling
 public static void testNegativePositiveSorterViaRotationWithJuggling() {
  Sorter sorter = new NegativePositiveSorterViaRotationWithJuggling();
  int[] a = new int[] { -1, 2, 1, 12, -9, 3, -4, 4, -3, 21, 52, 4, -2 };
  sorter.sort(a);
  sorter.print(a);
 }

 // test code for NegativePositiveSorterViaRotationWithBlockSwap
 public static void testNegativePositiveSorterViaRotationWithBlockSwap() {
  Sorter sorter = new NegativePositiveSorterViaRotationWithBlockSwap();
  int[] a = new int[] { -1, 2, 1, 12, -9, 3, -4, 4, -3, 21, 52, 4, -2 };
  sorter.sort(a);
  sorter.print(a);
 }

 // test code for NegativePositiveSorterViaBlockSwapWithReverse
 public static void testNegativePositiveSorterWithBlockSwapViaReverse() {
  Sorter sorter = new NegativePositiveSorterViaBlockSwapWithReverse();
  int[] a = new int[] { -1, 2, 1, 12, -9, 3, -4, 4, -3, 21, 52, 4, -2 };
  sorter.sort(a);
  sorter.print(a);
  
 }

 // test code for NegativePositiveCountSorter
 public static void testNegativePositiveCountSorter() {
  Sorter sorter = new NegativePositiveCountSorter();
  int[] a = new int[] { -1, 2, 1, 12, -9, 3, -4, 4, -3, 21, 52, 4, -2 };
  sorter.sort(a);
  sorter.print(a);
  
 }

 // test code NegativePositiveSwapSorter
 public static void testNegativePositiveSwapSorter() {
  Sorter sorter = new NegativePositiveSwapSorter();
  int[] a = new int[] { -1, 2, 1, 12, -9, 3, -4, 4, -3, 21, 52, 4, -2 };
  sorter.sort(a);
  sorter.print(a);
  
 }

 // test code NegativePositiveSorterViaBlockSwap
 public static void testNegativePositiveSorterViaBlockSwap () {
  Sorter sorter = new NegativePositiveSorterViaBlockSwap();
  int[] a = new int[] { -1, 2, 1, 12, -9, 3, -4, 4, -3, 21, 52, 4, -2 };
  sorter.sort(a);
  sorter.print(a);
  
 }

 
 public static void main(String[] args) {
  testNegativePositiveSwapSorter();
  testNegativePositiveCountSorter();
  testNegativePositiveSorterWithBlockSwapViaReverse();
  testNegativePositiveSorterViaRotationWithBlockSwap();
  testNegativePositiveSorterViaRotationWithJuggling();
  
  testNegativePositiveSorterViaBlockSwap();
 }
}

Enjoy.