package pkg1;

import java.awt.BorderLayout;
import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

import javax.swing.JFrame;
//getLenArrayRec(int) gives the array M of int-lenth longest paths 
//M[i][j] showing the total weight on this path starting from node pair ij.
public class matrix {
		
	
	public int length;
	//M_2, a[i][j][0] = weightonlink, a[i][j][1] = j. e.g., [[[0, 0], [3, 1], [0, 2], [0, 3], [0, 4]],......
	public int[][][] M2;
	//array of length matrices, aka M3, M4, M5.....
	public ArrayList<int[][][]> lenList = new ArrayList<int[][][]>();
	public int[][] row;
	//a hash table for all the paths' each page's next page, the key is first two pages
	public HashMap<ArrayList<Integer>, ArrayList<Integer>> paths = new HashMap<ArrayList<Integer>, ArrayList<Integer>>();
	//a hash table for all the paths' each page's visiting number, the key is first two pages
	public HashMap<ArrayList<Integer>, ArrayList<Integer>> pathsNum = new HashMap<ArrayList<Integer>, ArrayList<Integer>>();
	
	/*
	 * The recursive function for generating all the length's arrays
	 * pathLength = hopLength+1
	 */
	public int[][][] getLenArrayRec(int n)
	{ 
		this.length = n;
		if(n<3)
			return lenList.get(0);
		else if(lenList.size()>n)
			return lenList.get(n);//reuse the list data
		else
			return getLenArray(lenList.get(0), getLenArrayRec(n-1));
	}
	/*
	 * This function is the main algorithm that creates the list of all the length arrays
	 */
	public int[][][] getLenArray(int[][][] a, int[][][] b)
	{ 
		int mt[] = new int[2];
		int[][][] r = new int[a.length][a.length][2];//the new array generated
		int i, j, count,k ;
		//make a copy for current path hash
		HashMap<ArrayList<Integer>, ArrayList<Integer>> curPaths = new HashMap<ArrayList<Integer>, ArrayList<Integer>>();
	    curPaths = cloneHash(paths, lenList.size()-1);
		for(i = 0; i< a.length; i++)
		{
			for(j = 0; j < a.length; j++)
			{
				if(a[i][j][0] != 0)
				{
					count = 1;
					this.row = new int[a.length][2];
					for( k = 0; k < a.length; k++)
					{
						this.row[k][0] = b[j][k][0];
						this.row[k][1] = b[j][k][1];
					}
					mt = maxInaRow(this.row, i, j, paths);
					ArrayList<Integer> temp = new ArrayList<Integer>();
					temp.add(i);
					temp.add(j);
					ArrayList<Integer> tp = new ArrayList<Integer>();
					tp.add(j);
					tp.add(mt[2]);
					if((mt[0] != 0) && (lenList.size() > 3))//when path lenth > 3, there is circle problem
					{
						while((mt[1] == i)|| paths.get(tp).contains(paths.get(temp).get(0)) )//when there is circle, redo this
						{
							count++;
							if(count==b[j].length)
							{
								mt[0] = mt[1] = 0;
								break;
							}
							else
							{
							int[][] tempRow = setZero(mt[0]);//set the max num to 0
							mt = maxInaRow(tempRow,i, j,curPaths);
							}
						}
					}
					if(mt[0] == 0)
					{
						r[i][j][0] = r[i][j][1] = 0;
					}
					else
					{
						r[i][j][0] = a[i][j][0] + mt[0];
						r[i][j][1] = mt[1];
						//update the paths hash
						if(lenList.size() < 4)
							curPaths.get(temp).add(mt[1]);
						else
						{
							for(k = 1; k < lenList.size()-1; k++)  
							{ 
								if((paths.get(tp).size()>k-1)&&(curPaths.get(temp).size()>k))
									curPaths.get(temp).set(k, paths.get(tp).get(k-1)); //add new page at the end
							}
							if(paths.get(tp).size()>k-1)
								curPaths.get(temp).add(paths.get(tp).get(k-1));
						}
					}
				}
			}
		}
		//copy back hashtable
		paths = cloneHash(curPaths, lenList.size());
		lenList.add(r);
		updateHash(r);
		return r;
	}
	//forADLs*****************
	//For test A: print out list with ADLs that path's length larger or equal to N
	public void createADLA(int length)
	{
		HashMap<Integer, String> ADLs= new HashMap<Integer, String>();//used for printing out activities
		ADLs.put(0,"sleeping");
		ADLs.put(1, "toileting");
		ADLs.put(2, "showering");
		ADLs.put(3, "breakfast");
		ADLs.put(4,"grooming");
		ADLs.put(5, "spare_time/TV");
		ADLs.put(6,"leaving");
		ADLs.put(7, "lunch");
		ADLs.put(8, "snack");	
		System.out.println("ALL PATH IDS:");
		for(ArrayList<Integer> a: paths.keySet())
		{
			if(paths.get(a).size() >= length)
			{
				for(int i = 0 ; i < paths.get(a).size(); i++)
				{
					System.out.print(ADLs.get(paths.get(a).get(i)));
					System.out.print(" ");
				}
				System.out.print(":");
				//print out each path weights
				System.out.print(pathsNum.get(a));
				int sum = addNum(pathsNum.get(a));
				System.out.print(":");
				System.out.println(sum);
			}
		}
	}
	
	//For test B: print out list with ADLs that path's length larger or equal to N
	public void createADLB(int length)
	{
		HashMap<Integer, String> ADLs= new HashMap<Integer, String>();//used for printing out activities
		ADLs.put(0,"spare_Time/TV");
		ADLs.put(1, "grooming");
		ADLs.put(2, "toileting");
		ADLs.put(3, "sleeping");
		ADLs.put(4,"breakfast");
		ADLs.put(5, "showering");
		ADLs.put(6,"snack");
		ADLs.put(7, "lunch");
		ADLs.put(8, "leaving");	
		System.out.println("ALL PATH IDS:");
		for(ArrayList<Integer> a: paths.keySet())
		{
			if(paths.get(a).size() >= length)
			{
				for(int i = 0 ; i < paths.get(a).size(); i++)
				{
					System.out.print(ADLs.get(paths.get(a).get(i)));
					System.out.print(" ");
				}
				System.out.print(":");
				//print out each path weights
				System.out.print(pathsNum.get(a));
				int sum = addNum(pathsNum.get(a));
				System.out.print(":");
				System.out.println(sum);
			}
		}
	}
	//***************************************************************************************************
	//return the sum of an arraylist
	public int addNum(ArrayList<Integer> path)
	{
		int sum = 0;
		for(int i = 0 ; i < path.size(); i++)
			sum = sum + path.get(i);
		return sum;
	}
	/*
	 * singlePathHash() returns each single length path's corresponding seq list
	 * means showing which seqs have A->B
	 */
	public HashMap<ArrayList<Integer>, ArrayList<Integer>> singlePathHash(ArrayList<ArrayList<Integer>> seq)
	{
		int i = 0, j, k;
		HashMap<ArrayList<Integer>, ArrayList<Integer>> pathToSeqHash = new HashMap<ArrayList<Integer>, ArrayList<Integer>>();
		ArrayList<ArrayList<Integer>> s = seq;
		for(i = 0; i < s.size(); i++)//current sequence number
		{
			j = s.get(i).size();
			for(k = 0 ; k < j-1; k++)
			{
				ArrayList<Integer> eachSinglePath = new ArrayList<Integer>();
				eachSinglePath.add(s.get(i).get(k));
				eachSinglePath.add(s.get(i).get(k+1));
				if(pathToSeqHash.containsKey(eachSinglePath))
					pathToSeqHash.get(eachSinglePath).add(i);
				else
				{
					ArrayList<Integer> newSeqList = new ArrayList<Integer>();
					newSeqList.add(i);
					pathToSeqHash.put(eachSinglePath, newSeqList);
				}
			}
		}
		//System.out.print(pathToSeqHash);
		return pathToSeqHash;
	}
	/*
	 * nodesinGraph() returns how many nodes a graph have according to the given hashtable of edge:weight
	 * the hashtable's edge's must have two nodes and all the nodes' ID are from 0-n-1
	 * so the number of nodes is n
	 */
	public int nodesinGraph(HashMap<ArrayList<Integer>, Integer> h) 
	{
		int nodesN = 0;
		int i;
		for(ArrayList<Integer> keys: h.keySet())
		{
			if(nodesN < keys.get(0))
				nodesN = keys.get(0);
			if(nodesN < keys.get(1))
				nodesN = keys.get(1);
		}
		return nodesN+1;
	}
	/*
	 * This function creates a n*n matrix showing any two hyperedges' sharing number of vertices
	 * (any edge's weight)
	 * the parameter is a hashtable of list of edges with weights
	 */
	public int[][] createHyperShareUsingHash(HashMap<ArrayList<Integer>, Integer> h)
	{   
		int nodesN = nodesinGraph(h);
		int[][] share = new int[nodesN][nodesN]; 

		for(ArrayList<Integer> keys: h.keySet())
		{
			share[keys.get(0)][keys.get(1)] = h.get(keys);
		}
		return share;
	}
	/*
	 * This function creates a n*n matrix showing any two hyperedges' sharing number of vertices
	 * (any edge's weight)
	 */
	public int[][] createHyperShare(ArrayList<ArrayList<Integer>> seq, HashMap<Integer, Integer> h)
	{
		int i;
		//hash each page with an ID
		HashMap<Integer, Integer> hsh = h;
		int num = hsh.size();
		int[][] share = new int[num][num];
		ArrayList<ArrayList<Integer>> s = seq;
		for(ArrayList<Integer> current: s)
		{
			int len = current.size();
			for(i = 0 ; i < len-1; i++)
			{
				share[hsh.get(current.get(i))][hsh.get(current.get(i+1))] 
						//= share[hsh.get(current.get(i+1))][hsh.get(current.get(i))]//should be directed
						= share[hsh.get(current.get(i))][hsh.get(current.get(i+1))]+1;
			}
		}
		//diagonal all 0s
		for(i = 0; i < share.length; i++)
		{
			share[i][i] = 0;
		}
		/*/print out the matrix
		for(i = 0 ; i < share.length; i++)
		{
			for(int j = 0; j < share[0].length; j++)
				System.out.print(share[i][j]);
			System.out.println();
		}*/
		return share;
	}
	/*
	 * find the largest element in a row except the pth one, but here each elem in a row has two element, just check row[i][j][0]
	 * max[0] = the maximum in the row
	 * max[1] = the index of the max
	 */
	public int[] maxInaRow(int[][] row, int p, int q , HashMap<ArrayList<Integer>, ArrayList<Integer>> Paths)
	{
		int flag = 0;
		
		this.row = row;//set the global variable to row
		int i,j;
		int max[] = new int[3];
		max[0] = 0;//the max number found
		max[1] = 0;//the last page id for max, for not circling
		max[2] = 0;//the column id for max
		HashMap<ArrayList<Integer>, ArrayList<Integer>> curPaths = Paths;
		for(i = 0; i < row.length; i++)
		{
			if((row[i][0] > max[0]) && (row[i][1] != q) && (row[i][1] != p) && (i != p))
			{
				ArrayList<Integer> pos = new ArrayList<Integer>();
				pos.add(q);//next page number
				pos.add(i);
				ArrayList<Integer> path = curPaths.get(pos);
				for(j = 1; j < path.size(); j++)
				{
					if(path.get(j) == p)
						flag = 1;
				}
				if(flag == 0)
				{
					max[0] = row[i][0];
					max[1] = row[i][1];	
					if(lenList.size() < 4)
						max[2] = q; //at the beginning , the column is the last position number
					else
						max[2] = i; //if length is > 2, then last position number is the one found in the row
				}
			}
		}
		return max;
	}
	/*
	 * Set the largest element to 0 in a row
	 */
	public int[][] setZero(int max)
	{
		int[][] arrayNewMax = this.row;
		for(int i = 0; i < arrayNewMax.length; i++)
		{
			if(arrayNewMax[i][0] == max)
			{
				arrayNewMax[i][0] = 0;
				break;
			}
		}
		this.row = arrayNewMax;
		return arrayNewMax;
	}
	/*
	 * initiate the array that the diagonal elem are all 0, and convert it to 3D with 0elem = a[i][j] 1elem=j;
	 */
	public int[][][] initArray(int[][] a)
	{
		int[][][] aa = new int[a.length][a[0].length][2];
		int i,j;
		for(i = 0; i < aa.length; i++)
		{
			aa[i][i][0] = 0;
			aa[i][i][1] = 0;
		}
		for(i = 0; i < aa.length; i++)
		{
			for(j = 0 ; j < aa[0].length; j++)
			{
				aa[i][j][0] = a[i][j];
				aa[i][j][1] = j;
			}
		}
		M2 = aa;
		return aa;
	}
	/*
	 * draw the matrix relationship in a directed graph
	 */
	public void drawG(int[][][] a)
	{
		draw d = new draw(a);
		JFrame frame = new JFrame();
		frame.getContentPane().add(d,BorderLayout.CENTER);
		//JButton button = new JButton("Hi");
		frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
		//frame.getContentPane().add(button);
		frame.setSize(1000,1000);
		frame.setVisible(true);
	}
	/*
	 * This function initiate the hash table for each unzero path 
	 */
	public void initHash(int[][][] a)
	{
		int[][][] array = a;
		int i, j;
		for(i = 0; i < array.length; i++)
		{
			for(j = 0 ; j < array.length; j++)
			{
				if(array[i][j][0] != 0)
				{
					ArrayList<Integer> temp1 = new ArrayList<Integer>();
					temp1.add(i);
					temp1.add(j);
					ArrayList<Integer> temp2 = new ArrayList<Integer>();
					temp2.add(i); 
					temp2.add(array[i][j][1]); 
					paths.put(temp1, temp2);
					ArrayList<Integer> temp3 = new ArrayList<Integer>();
					temp3.add(array[i][j][0]);
					pathsNum.put(temp1, temp3);
				}
			}
		}
	}
	/*
	 * This function update the hash table for each unzero path's weight, update para: pahtsNum
	 */
	public void updateHash(int[][][] a)
	{
		int[][][] array = a;
		int i, j, k;
		for(i = 0; i < array.length; i++)
		{
			for(j = 0 ; j < array.length; j++)
			{
				if(array[i][j][0] != 0)
				{
					//i, j not changing, used for keys
					ArrayList<Integer> temp1 = new ArrayList<Integer>();
					temp1.add(i);
					temp1.add(j);
					ArrayList<Integer> temp2 = paths.get(temp1);		
					ArrayList<Integer> newPathsNum = pathsNum.get(temp1);
					int size = temp2.size();
					if(size > 2)
					{
						//first remove starting from 2nd to the end of the path numbers
						for(k = size-3; k > 0; k--)
						{
							newPathsNum.remove(k);
						}
						//start from the second element in the pathNum, update
						for(k = 1; k < size-1; k++)
						{
							int t1 = temp2.get(k);//e.g. path[0,1,5,2]->[0,1,4,6,7] weight(22,33,44)->(22,66,77,88)
							int t2 = temp2.get(k+1);
							newPathsNum.add(M2[t1][t2][0]); 
						}
					} 
				}
			}
		} 
	}
	/*
	 * every element in the array represent start from rowi next to columnj and the maxV path.
	 * to avoid circles, each element also indicates the end hyperedge, so using three dimensional array to store
	 */
	public int[][][] getPathArray(int[][][] a, int[][][] b)
	{
		int[][][] pathArray = new int[a.length][a[0].length][2];
		int i, j;
		int m[] = new int[2];
		int[][][] aa = a;
		int[][][] bb = b;
		for(i = 0; i < aa.length; i++)
		{
			for(j = 0; j < aa[0].length; j++)
			{
				if(aa[i][j][0] == 0)
				{
					pathArray[i][j][0] = 0;
					pathArray[i][j][1] = 0;
				}
				else
				{
					m = maxInaRow(b[j],i, j, paths);
					pathArray[i][j][0] = aa[i][j][0] + m[0];
					pathArray[i][j][1] = m[1];
				}
			}
		}
		return pathArray;
	}
	
	/*
	 * This function initialize the lenth list
	 */
	public void initLenList(int[][][] a)
	{
		this.lenList.add(a);//0th, 1st, 2nd element are both a, to consist with the length
		this.lenList.add(a);
		this.lenList.add(a);
		initHash(a);
	}


  public Set<Integer> union(Set<Integer> list1, Set<Integer> list2) {
        Set<Integer> set = new HashSet<Integer>();

        set.addAll(list1);
        set.addAll(list2);

        return set;
    }

  public Set<ArrayList<Integer>> unionForArraylistSet(Set<ArrayList<Integer>> list1, Set<ArrayList<Integer>> list2) {
	  Set<ArrayList<Integer>> set = new HashSet<ArrayList<Integer>>();

      set.addAll(list1);
      set.addAll(list2);

      return set;
  }
   public Set<Integer> intersection(Set<Integer> list1, Set<Integer> list2) {
       Set<Integer> set = new HashSet<Integer>();

        for (Integer t : list1) {
            if(list2.contains(t)) {
                set.add(t);
            }
        }

        return set;
    }
   public Set<ArrayList<Integer>> intersectionForArraylistSet(Set<ArrayList<Integer>> list1, Set<ArrayList<Integer>> list2) {
	   Set<ArrayList<Integer>> set = new HashSet<ArrayList<Integer>>();

        for (ArrayList<Integer> t : list1) {
            if(list2.contains(t)) {
                set.add(t);
            }
        }

        return set;
    }
   public ArrayList<Integer> intersectionArr(ArrayList<Integer> list1, ArrayList<Integer> list2) {
	   ArrayList<Integer> arr = new ArrayList<Integer>();

        for (Integer t : list1) {
            if(list2.contains(t)) {
                arr.add(t);
            }
        }

        return arr;
    }
   /*
    * This function duplicates a hashtable, not make a referece pointing to it
    */
   public HashMap<ArrayList<Integer>, ArrayList<Integer>> cloneHash(HashMap<ArrayList<Integer>, ArrayList<Integer>> h, int pathLen)
   {
	   HashMap<ArrayList<Integer>, ArrayList<Integer>> r = new HashMap<ArrayList<Integer>, ArrayList<Integer>>();
	   int[][] a = new int[h.keySet().size()][2]; 
	   int[][] b = new int[h.keySet().size()][pathLen]; //BUGGGGGGGGGGGG:there might be path less than pathlen but the return value r IS RIGHT
	   int ind = 0;
	   int i, j;
	   for(ArrayList<Integer> eachKey : h.keySet())
	   {
		   a[ind][0] = eachKey.get(0);
		   a[ind][1] = eachKey.get(1);
		   for(i = 0; i < h.get(eachKey).size(); i++)
		   { 
			   b[ind][i] = h.get(eachKey).get(i);
		   } 

		   ind++;
	   }
	   for(i=0; i < ind; i++)
	   {
		   ArrayList<Integer> tmp1 = new ArrayList<Integer>();
		   tmp1.add(a[i][0]);
		   tmp1.add(a[i][1]);
		   ArrayList<Integer> tmp2 = new ArrayList<Integer>();
		   for(j = 0; j < h.get(tmp1).size(); j++)
		   {
			   tmp2.add(b[i][j]);
		   } 
		   r.put(tmp1, tmp2);
	   }
	   return r;
   }

	/*
	 * print 3D matrix func
	 */
	public void p3DArray(int[][][] a)
	{
		int i, j, k;
		System.out.println("(matrix.p3DArray:)THE ARRAY IS");
		for(i = 0 ; i < a.length; i++)
		{
			for(j = 0; j< a[0].length; j++)
			{
				for(k = 0; k < a[0][0].length; k++)
					System.out.print(a[i][j][k]);
				System.out.print(",");
			}
			System.out.println();
		}
	}
	/*
	 * print path hashes, at the end print each path's weights
	 */
	public void pHash()
	{ 
		System.out.println("(matrix.pHash:)ALL PATH IDS:");
		for(ArrayList<Integer> a: paths.keySet())
		{
			System.out.print(a);
			System.out.print(":");
			System.out.print(paths.get(a));
			//print out each path weights
			System.out.println(pathsNum.get(a));
		}
		
	}
	/*
	 * print out the largest weight path
	 */
	public ArrayList<Integer> largestPath()
	{
		ArrayList<Integer> largestPath = new  ArrayList<Integer>();
		int max = 0;
		int[][][] last = lenList.get(lenList.size()-1);
		int i, j ;
		for(i = 0; i < last.length; i++)
		{
			for(j = 0; j < last.length; j++)
			{
				if(last[i][j][0] > max)
				{
					ArrayList<Integer> temp = new ArrayList<Integer>();
					temp.add(i);
					temp.add(j);
					if(paths.get(temp).size()>lenList.size()-2)
					{
						largestPath = paths.get(temp);
						max = last[i][j][0];
					}
				}
			}
		}
		//System.out.print("largest path is ");
		//System.out.println(largestPath);
		return largestPath;
	}
	/*
	 * print out the largest weight
	 */
	public int largestW()
	{ 
		int max = 0;
		int[][][] last = lenList.get(lenList.size()-1);
		int i, j ;
		for(i = 0; i < last.length; i++)
		{
			for(j = 0; j < last.length; j++)
			{
				if(last[i][j][0] > max)
				{
					ArrayList<Integer> temp = new ArrayList<Integer>();
					temp.add(i);
					temp.add(j);
					if(paths.get(temp).size()>lenList.size()-2)
					{ 
						max = last[i][j][0];
					}
				}
			}
		}
		//System.out.print("largest W is ");
		//System.out.println(max);
		return max;
	}
	/*
	 * TopN paths returns a list of top N paths
	 */
	public int TopNpaths(ArrayList<ArrayList<Integer>> a, int n)
	{ 
		if(a.size() < n)
			System.out.print("NOt enough paths");
		int totalW = 0;
		int[] topn = new int[n];
		int[][][] last = lenList.get(lenList.size()-1);
		int i, j ;
		for(i = 0; i < a.size(); i++)
		{
			for(j = 0 ; j < n; j++)
			{
				if(last[a.get(i).get(0)][a.get(i).get(1)][0] > topn[j])
				{
					topn[j] = last[a.get(i).get(0)][a.get(i).get(1)][0];
					break;
				}
			}
		}
		for(j = 0; j < n; j++)
			totalW = totalW + topn[j];
		return totalW;
		
	}
	/*
	 * print out the all paths weight sum
	 */
	public int pathW(ArrayList<ArrayList<Integer>> a)
	{ 
		int totalW = 0;
		int[][][] last = lenList.get(lenList.size()-1);
		int i, j , count=0;
		for(i = 0; i < a.size(); i++)
		{
			totalW = totalW + last[a.get(i).get(0)][a.get(i).get(1)][0];
		}
		return totalW;
		
	}
	/*
	 * print path hashes according to a pathlength>=n
	 */
	public ArrayList<ArrayList<Integer>> pHashN(int n)
	{
		ArrayList<ArrayList<Integer>> printPaths = new  ArrayList<ArrayList<Integer>>();
		int[][][] last = lenList.get(lenList.size()-1);
		int i, j , count=0;
		for(i = 0; i < last.length; i++)
		{
			for(j = 0; j < last.length; j++)
			{
				if(last[i][j][0] > n)
				{
					ArrayList<Integer> temp = new ArrayList<Integer>();
					temp.add(i);
					temp.add(j);
					if(paths.get(temp).size()>lenList.size()-2)
					{
						printPaths.add(paths.get(temp));
						System.out.println("this path's total weight:"+last[i][j][0]);
						count++;
					}
				}
			}
		}
		System.out.print("(m.pHashN)total number of paths is ");
		System.out.println(count);
		return printPaths;
	}
	
	/*
	 * checkFlag() checks if a list of flags are all 1
	 */
	public boolean checkFlag(int[] a)
	{
		int i;
		int product = 1;
		for(i = 0 ; i < a.length; i++)
		{
			product = product * a[i];
		}
		if(product == 0)
			return false;
		else
			return true;
	}
	/*
	 * distinctPaths() gives total different paths in a path lists.
	 * 1st, get the largest total weight path, put it in set S
	 * 2nd, compare each of the rest with it, if there is no overlap then put it in array S
	 * except the first element in S, the others might also have overlaps, so next step is from 2nd element in S
	 * check if there is overlap from 3rd - nth. then check 3rd to 4th-nth......
	 *  return S 
	 */
	public ArrayList<ArrayList<Integer>> distinctPaths(double thresh, HashMap<ArrayList<Integer>, Integer> pathWithWeight)//thresh=0 means finding no overlap paths
	{
		ArrayList<ArrayList<Integer>> S = new ArrayList<ArrayList<Integer>>();
		int maxW = 0;
		ArrayList<Integer> temp= new ArrayList<Integer>();//store which path has the largest weight
		int size = pathWithWeight.size();
		int len = -1;
		System.out.print("(matrix.distinctPaths:)"+size); 
		int i, j;
		
		for(ArrayList<Integer> key: pathWithWeight.keySet())
		{
			len = key.size();
			if(maxW < pathWithWeight.get(key))
			{
				maxW = pathWithWeight.get(key); 
				temp = key;
			}
		}
		S.add(temp);
		//add all the other paths with no overlap with the maxWeight one to S
		for(ArrayList<Integer> key: pathWithWeight.keySet())
		{
			Set<Integer> mySet1 = new HashSet<Integer>(temp);
			Set<Integer> mySet2 = new HashSet<Integer>(key);
			if( intersection(mySet1, mySet2).size() <= thresh* len)
				S.add(key);
		}
		//use a flag to tell if the element in S is useful, 0 means we need to check it, 1 means it should be discarded
		int flag[] = new int[S.size()];
		//filter all the paths in S in case they still have overlaps
		for(i = 1; i < S.size(); i++)//compare to S.get(i)
		{
			if(flag[i] != 1)
			{
				for(j = i + 1; j < S.size(); j++)
				{			
					if(flag[j] == 0)
					{
						Set<Integer> mySet1 = new HashSet<Integer>(S.get(i));
						Set<Integer> mySet2 = new HashSet<Integer>(S.get(j));
						if( intersection(mySet1, mySet2).size() > thresh* len)//there is overlap->flag[j]=1
							flag[j]=1;
					}
				}
			}
		}
		for(i = 0 ; i < S.size(); i++)
		{
			if(flag[i] == 1)
				S.remove(i);
		}
		return S;
	}
	/*
	 * pathGrouping() groups an array of paths into groups. If two strings' overlap is larger than the threshold(e.g. 50%)
	 * put them together as a group G, and test the next string's overlap with G, if >50% of this string, merge this string to the group
	 * for example [1,2,3,4], [2,4,5,6], [7,8,9,0], after testing the first two , group them together and make arraylist[0] : [1,2,3,4,5,6] and use
	 * this array to test others
	 */
	public ArrayList<ArrayList<Integer>> pathGrouping(double thresh, ArrayList<ArrayList<Integer>> p)
	{
		ArrayList<ArrayList<Integer>> r = new ArrayList<ArrayList<Integer>>();
		int[] flag = new int[p.size()]; //showing which element in the path array has grouped, only return the grouped
		int i, j, k;		
		for(i = 0; i < p.size() ; i++)
		{
			if(flag[i] != 2)//not merged into groups
			{
				for(j = i+1; j < p.size(); j++)
				{
					if(flag[j] != 2)//not merged into groups
					{
						Set<Integer> union = new HashSet<Integer>();
						Set<Integer> inter = new HashSet<Integer>();
						Set<Integer> mySet1 = new HashSet<Integer>(p.get(i));
						Set<Integer> mySet2 = new HashSet<Integer>(p.get(j));
						union = union(mySet1, mySet2);
						inter = intersection(mySet1, mySet2);
						if(inter.size() >= p.get(j).size()*thresh)// intersection > threshold
						{
							flag[i] = 1;//flag = 1 means this is a based grouped path
							flag[j] = 2;//flag = 2 means this path is merge to somepath.
							for(Integer temp: union)
								mySet1.add(temp);
							for(Integer temp: mySet1)
							{
								if(!p.get(i).contains(temp))
									p.get(i).add(temp);
							}
						}
					}	
				}
			}
		}
		for(i = 0; i < p.size(); i++)
		{
			System.out.println("(matrix.pathGrouping)"+p.get(i));
		}
		for(i = 0; i < p.size(); i++)
		{
			if(flag[i] == 1)
				r.add(p.get(i));
		}
		if (r.size()==0)
			r = p;
		for(i = 0; i < r.size(); i++)
		{
			System.out.println("(matrix.pathGrouping)"+r.get(i));
		}
		return r;
	}
	//print out the total weight
	public double totalWeight(ArrayList<Integer> arr)
	{
		int i;
		double ave=0; 
		for(i = 0; i < arr.size()-1; i++)
		{
			ave = ave + M2[arr.get(i)][arr.get(i+1)][0];
		}	
		return ave;
	} 
	//print out the visiting numbers on the path THIS IS REAL DEVIATION
	public void visitings(ArrayList<Integer> arr)
	{
		int i;
		double ave=0;
		double dev = 0;
		for(i = 0; i < arr.size()-1; i++)
		{
			ave = ave + M2[arr.get(i)][arr.get(i+1)][0];
			System.out.print("(matrix.visitings:)"+M2[arr.get(i)][arr.get(i+1)][0]+",");
		}		
		System.out.print("(matrix.visitings:)total:"+ave+",std:");
		ave = ave/(arr.size()-1);
		for(i = 0; i < arr.size()-1; i++)
			dev = dev + (M2[arr.get(i)][arr.get(i+1)][0] - ave) * (M2[arr.get(i)][arr.get(i+1)][0] - ave);
		dev = dev/(arr.size()-2);
		dev = Math.sqrt(dev);
		System.out.println("(matrix.visitings:)"+dev);
		
	}
	//calculate each path's visiting's deviation on pathlength >= n
	public void deviation(int n, int length)
	{

		int[][][] last = lenList.get(lenList.size()-1);
		int i, j, k;
		float ave, dev;
		double totalMax = 0;
		for(i = 0; i < last.length; i++)
		{
			for(j = 0; j < last.length; j++)
			{
				if(last[i][j][0] > n)
				{
					int count = 0;
					ave = 0;
					dev = 0;
					ArrayList<Integer> temp = new ArrayList<Integer>();
					temp.add(i);
					temp.add(j); 
					ArrayList<Integer> curPath = pathsNum.get(temp);
					for(k = 0; k < curPath.size(); k++)
						ave = ave + curPath.get(k);
					ave = ave/curPath.size();
					for(k = 0; k < curPath.size(); k++)
						dev = dev + (curPath.get(k) - ave) * (curPath.get(k) - ave);
					if(curPath.size() > length-2)//print out the pathsVisitings with length>
					{
						//System.out.print("weights are:");
						//System.out.println(pathsNum.get(temp));
						//System.out.println(curPath);
						//System.out.println("average:"+ave);
						//System.out.println("dev:"+dev);
						visitings(paths.get(temp));
						double tmp = totalWeight(paths.get(temp));
						if(tmp > totalMax)
							totalMax = tmp;
					}
				}
			}
		}
		System.out.print("(matrix.deviation:)"+totalMax+",");

	}
}