/*
 *@(#)GraphTheory.java 2.0 2005/05/02
 *
 *清華大學　精密儀器與機械學系
 *范燦升　fancansheng@163.com
 */

package algorithm;

import java.util.*;

import algorithm.HamiltonSort;
import ADT.BinaryTree;

/**
 *這個類是圖論的類，里面包含一些圖論常見的算法。
 *@version	2.0, 2005/04/30
 *@author	范燦升
 *@see	Modeling
 *@see	input.GraphInput
 */

public class GraphTheory
{
	private int[][] adjacentMatrix;//鄰接矩陣
	private int[][] incidenceMatrix;//關聯矩陣
	private int[][] weightMatrix;//權矩陣
	private int matrixType;//構造時矩陣的類型
	
	/**
	 *說明構造方法所傳過來的矩陣是鄰接矩陣。
	 */
	public final static int ADJACENT=1;
	
	/**
	 *說明構造方法所傳過來的矩陣是關聯矩陣。
	 */
	public final static int INCIDENCE=2;
	
	/**
	 *說明構造方法所傳過來的矩陣是權矩陣。
	 */
	public final static int WEIGHT=3;
	
	/**
	 *圖的結點數。
	 */
	public int n;
	
	/**
	 *圖的邊數。
	 */
	public int m;
	
	/**
	 *用所給矩陣生成一個圖。
	 *@param	matrix		圖所對應的矩陣，這個矩陣在GraphTheory類中產生克隆副本，GraphTheory的成員方法不會對該矩陣生產影響。
	 *@param	matrixType	矩陣類型，可以為{@link #ADJACENT}、{@link #INCIDENCE}、{@link #WEIGHT}。
	 */
	public GraphTheory(int[][] matrix,int matrixType)
	{
		this.matrixType=matrixType;
		switch(matrixType)
		{
			case ADJACENT:
				adjacentMatrix=(int[][])matrix.clone();
				break;
			case INCIDENCE:
				incidenceMatrix=(int[][])matrix.clone();
				break;
			case WEIGHT:
				weightMatrix=(int[][])matrix.clone();
				break;
		}
	}
	
	/**
	 *Dijkstra算法，根據權矩陣計算圖中任意兩結點間的最短路。
	 *<p>計算最短路的圖必須是正權有向圖。
	 *<p>受int大小的限制，權值必須小于Integer.MAX_VALUE，即2147483647。
	 *對于無向圖，用戶必須先把它的權矩陣轉換成有向圖的權矩陣。
	 *@param	start	開始結點，結點編號從0開始
	 *@param	end		結束結點，結點編號從0開始
	 *@return	Vector類的一個實例，該Vector中只有三個元素，int[]、Integer及int[]的實例。
	 *			<p>其中第一int[]是從start結點到任一結點的最短路徑矩陣path，int[end]中所存放的是從start到end的最短路徑中end的前一結點。
	 *			<p>Integer是最短路徑的長度的整型數封裝。當Integer為-1時，說明不存在從start到end的路徑。
	 *			<p>第二個int[]是從start到各結點（包括自身）的最短路徑長度len，上面的Integer就是對int[]中第end個元素的封裝。
	 *			如果Integer為-1，則len中部分元素還保持初值Integer.MAX_VALUE。
	 *			<p>如果構造該類時的矩陣不是權矩陣，或者不是圖不是正權圖，則返回null。
	 */
	public Vector dijkstra(int start,int end)
	{
		int i,j;//循環變量
		int ii,jj;//算法中用
		int min;
		int count;//計算下面的undetermined數組中還有多少元素為true
		int lastCount=-1;//賦值為-1，下面if語句的lastCount==count第一次就肯定不會滿足
		boolean done;//用于檢查是否可以跳出算法中的循環
		n=weightMatrix.length;
		if(matrixType!=WEIGHT)
			return null;
		//不是權矩陣就返回null
		
		n=weightMatrix.length;
		for(i=0;i<n;i++)
		{
			for(j=0;j<n;j++)
			{
				if(weightMatrix[i][j]<0)
					return null;
			}
		}
		//如果權矩陣含有小于0的元素就返回null
		
		int[] path=new int[n];
		int[] len=new int[n];
		for(i=0;i<n;i++)
			path[i]=start;
		for(j=0;j<n;j++)
		{
			if(weightMatrix[start][j]>0)//從start結點到j有道路
				len[j]=weightMatrix[start][j];
			else
				len[j]=Integer.MAX_VALUE;
		}
		len[start]=0;//從start到start的長度當然為0
		
		boolean[] undetermined=new boolean[n];
		//true表示還沒有找到最短路
		for(i=0;i<n;i++)
			undetermined[i]=true;
		undetermined[start]=false;
		//初始化
		
		jj=start;
		while(true)
		{
			min=Integer.MAX_VALUE;
			for(ii=0;ii<n;ii++)
			{
				if(undetermined[ii]==true)
				{
					if(len[ii]<min)
					{
						jj=ii;
						min=len[ii];
					}
				}
			}
			//尋找len[ii]的最小值，并對取最小值時的ii用jj標記
			undetermined[jj]=false;
			
			done=true;
			count=0;
			for(i=0;i<n;i++)
			{
				if(undetermined[i]==true)
				{
					done=false;//undetermined中還有數，不能跳出while循環
					count++;
				}
			}
			if(lastCount==count)
			//兩次undetermined中為true的元素數目相等，說明下面的for循環什么不起作用，不存在start到end的路徑
				break;
			lastCount=count;
			if(done==true)
				break;
			//判斷是否可以跳出while循環
			
			for(i=0;i<n;i++)
			{
				if((weightMatrix[jj][i]>0)&&(undetermined[i]==true))
				//jj的后繼結點，且在undetermined中
				{
					if(len[i]>len[jj]+weightMatrix[jj][i])
					{
						len[i]=len[jj]+weightMatrix[jj][i];
						path[i]=jj;
					}
				}
			}//len[jj]始終不是Integer.MAX_VALUE
		}
		//完成算法的主體部分
		
		//現在len和path都有了，可以進行封裝和返回了
		if(len[end]==Integer.MAX_VALUE)
			len[end]=-1;
		Integer solutionLength=new Integer(len[end]);
		Vector vector=new Vector();
		vector.add(path);
		vector.add(solutionLength);
		vector.add(len);
		return vector;
	}
	
	
	/**
	 *用分支與界法求解旅行商問題。
	 *<p>計算旅行商問題的圖必須是無向完全圖。由于無向圖的權矩陣是對稱陣，因此該方法不檢查權矩陣是否真的為對稱陣，
	 *而是直接使用權矩陣對角線以上的元素，對權矩陣對稱性的檢查就在輸入端完成。
	 *<p>圖的結點數不能小于3。
	 *<p>受int大小的限制，權值必須小于Integer.MAX_VALUE，即2147483647。
	 *@return	整型數組int[]，其中int[].length==n+1，int[0]是哈密頓圈的長度，從int[1]到int[n]記錄哈密頓圈依次經過的結點。
	 *			結點從0從開始。
	 *			<p>以下三種情況返回null：該圖不是完全圖、結點數小于3、構造GraphTheory類時matrixType不為WEIGHT。
	 */
	public int[] hamilton()
	{
		int i,j,k;
		n=weightMatrix.length;
		if((n<3)||(matrixType!=WEIGHT))
			return null;
		int[][] edge=new int[(n*n-n)/2][5];
		//邊集合，每條邊包含五個元素，分別為邊權、結點、結點、索引、由邊生成路徑時是否已作標記
		k=0;
		for(i=0;i<n;i++)
		{
			for(j=i+1;j<n;j++)
			{
				if(weightMatrix[i][j]==0)
					return null;
				edge[k][0]=weightMatrix[i][j];
				edge[k][1]=i;
				edge[k][2]=j;
				edge[k][4]=0;//未取該邊
				k++;
			}
		}
		//檢查是否為完全圖，同時完成對待排序邊集合的初始化
		
		Arrays.sort(edge,new HamiltonSort());
		for(i=0;i<edge.length;i++)
			edge[i][3]=i;//為edge設置索引位，即排好序后在隊列中的順序
		int len=Integer.MAX_VALUE;
		//排序，設置索引和置初始邊界
		
		int[][] stack=new int[n][5];//用來存放棧中的邊
		int currentLength=0;
		int popCount;
		int[] nodeCount=new int[n];//標記各結點出現的次數
		for(i=0;i<n;i++)
			nodeCount[i]=0;
		for(i=0;i<n;i++)
		{
			stack[i]=edge[i];
			currentLength+=edge[i][0];
		}
		for(i=0;i<n;i++)
		{
			nodeCount[stack[i][1]]++;
			nodeCount[stack[i][2]]++;
		}
		popCount=n;//popCount是從后面數起索引連續的元素的個數
		
		int index;
		boolean cycled;//判斷是否構成哈密頓圈
		int[][] result=new int[n][5];//記錄最終結果
		while(true)
		{
			cycled=true;
			for(i=0;i<n;i++)
			{
				if(nodeCount[i]!=2)
				{
					cycled=false;
					break;
				}
			}
			
			if(cycled&&(currentLength<len)&&(popCount!=n))
			//stack中的元素構成哈密頓圈且該圈長度比原來的圈小，同時stack還可以往后退
			{
				len=currentLength;
				for(k=0;k<n;k++)
					result[k]=stack[k];
				index=stack[n-1-popCount][3]+1;//后面連續在stack中的前一位的下一個索引
				for(j=n-1-popCount;j<n;j++)
				//開始新分支
				{
					if(index>=edge.length)
						break;//不能再退就返回
					
					currentLength-=stack[j][0];
					nodeCount[stack[j][1]]--;
					nodeCount[stack[j][2]]--;
					
					stack[j]=edge[index];
					//stack[j]已被它對應的edge后面的邊替換
					index++;
					
					currentLength+=stack[j][0];
					nodeCount[stack[j][1]]++;
					nodeCount[stack[j][2]]++;
				}
			}
			else if(cycled&&(currentLength<len)&&(popCount==n))
			//當stack不能往后退時
			{
				len=currentLength;
				for(k=0;k<n;k++)
					result[k]=stack[k];
				break;
			}
			else if(currentLength>=len)
			//長度比界限大也要開始新分支
			{
				index=stack[n-1-popCount][3]+1;
				for(j=n-1-popCount;j<n;j++)
				//開始新分支
				{
					if(index>=edge.length)
						break;
					
					currentLength-=stack[j][0];
					nodeCount[stack[j][1]]--;
					nodeCount[stack[j][2]]--;
					
					stack[j]=edge[index];
					//stack[j]已被它對應的edge后面的邊替換
					index++;
					
					currentLength+=stack[j][0];
					nodeCount[stack[j][1]]++;
					nodeCount[stack[j][2]]++;
				}
			}
			else
			//相當于else if((!cycled)&&(currentLength<len))
			//長度比界限小，同時不構成哈密頓圈，可以繼續向下搜
			{
				for(i=0;i<n;i++)
				//從stack最后一個元素起，依次往edge后面退，只要有一個可退就中斷
				{
					if(stack[n-1-i][3]<(edge.length-1-i))//防止已經有元素退到edge的最后
					{
						currentLength-=stack[n-1-i][0];
						nodeCount[stack[n-1-i][1]]--;
						nodeCount[stack[n-1-i][2]]--;
						
						index=stack[n-1-i][3];
						index++;
						stack[n-1-i]=edge[index];
						
						currentLength+=stack[n-1-i][0];
						nodeCount[stack[n-1-i][1]]++;
						nodeCount[stack[n-1-i][2]]++;
						
						break;
					}
				}
			}
			
			popCount=1;
			for(i=n-1;i>0;i--)
			//更新popCount
			//由于是和stack[i]的前一個比較，所以i不能為0
			{
				if(stack[i][3]==(stack[i-1][3]+1))//連續
					popCount++;
				else
					break;//不馬上跳出循環的話popCount的記錄就不準
			}
			
			if((popCount==n)&&(len<Integer.MAX_VALUE))
				break;//全部連續，剩下的分支只會比len大，可以跳出循環
		}
		//完成主體算法
		//stack中的元素就是構成最小哈密頓圈的邊
		
		
		int[] path=new int[n+1];
		path[0]=len;
		path[1]=result[0][1];
		for(i=1;i<path.length-1;i++)
		{
			for(j=0;j<result.length;j++)
			{
				if(result[j][1]==path[i]&&result[j][4]==0)
				{
					path[i+1]=result[j][2];
					result[j][4]=1;
					break;
				}
				if(result[j][2]==path[i]&&result[j][4]==0)
				{
					path[i+1]=result[j][1];
					result[j][4]=1;
					break;
				}
			}
		}
		return path;
		//生成路徑并返回
	}
	
	/**
	 *Huffman算法，根據所給樹的結點鏈表對構造Huffman樹的過程作一次遞歸。
	 *<p>構造的過程是把權最小的兩個結點合并為一個結點。
	 *@param	binTree	等待構樹的結點鏈表。
	 *			<p>最終得到的binTree是這樣一個鏈表：該鏈表中只有一個元素，為Huffman樹的根結點，是一個二叉樹結點類，
	 *			根據該根結點，可以找到二叉樹的全部結點。
	 *			<p>需要注意的是：生成Huffman樹的過程是對方法自身的不斷遞歸調用，
	 *			因此得到的BinaryTree中的info域并未被初始化。
	 *			<p>要得到含有路徑信息的Huffman樹，應調用huffman方法。
	 *@see	#huffman
	 *@see	#generateHuffmanPath
	 */
	public static void generateHuffmanTree(LinkedList binTree)
	{
		if(binTree.size()==1)
			return;
		else
		{
			Collections.sort(binTree,new BinaryTreeSort());
			BinaryTree tempLeft=(BinaryTree)binTree.removeFirst();
			BinaryTree tempRight=(BinaryTree)binTree.removeFirst();
			BinaryTree tempParent=new BinaryTree();
			
			tempParent.leftChild=tempLeft;
			tempParent.rightChild=tempRight;
			tempParent.weight=tempLeft.weight+tempRight.weight;
			tempLeft.parent=tempParent;
			tempRight.parent=tempParent;
			
			binTree.addFirst(tempParent);
			generateHuffmanTree(binTree);
		}
	}
	
	/**
	 *根據已生成的Huffman樹生成樹中各結點的路徑。
	 *<p>由于Huffman樹是二叉樹，因此用0和1表示從根結點到當前結點的路徑，
	 *0表示從父結點向左走得到下一結點，1表示從父結點向右走得到下一結點。
	 *@param	currentNode	當前結點
	 *@see	#huffman
	 *@see	#generateHuffmanTree
	 */
	public static void generateHuffmanPath(BinaryTree currentNode)
	{
		if(currentNode.leftChild==null && currentNode.rightChild==null)
			return;
		else
		{
			currentNode.leftChild.info=new StringBuffer(currentNode.info.toString());
			currentNode.leftChild.info.append("0");
			generateHuffmanPath(currentNode.leftChild);
			
			currentNode.rightChild.info=new StringBuffer(currentNode.info.toString());
			currentNode.rightChild.info.append("1");
			generateHuffmanPath(currentNode.rightChild);
		}
	}
	
	/**
	 *Huffman算法，根據所給樹葉結點的權構造最優二叉樹，該樹稱為Huffman樹。
	 *@param	leafVertex	樹葉結點的權數組
	 *@return	Huffman樹的樹葉結點數組，每個結點中都含有從根到該樹葉結點的路徑。
	 *			<p>0表示向左，1表示向右。
	 *@see	#generateHuffmanTree
	 *@see	#generateHuffmanPath
	 */
	public static BinaryTree[] huffman(int[] leafVertex)
	{
		int n=leafVertex.length;
		int i;
		BinaryTree[] binTree=new BinaryTree[n];
		LinkedList binTreeList=new LinkedList();
		for(i=0;i<n;i++)
		{
			binTree[i]=new BinaryTree();
			binTree[i].weight=leafVertex[i];
			binTree[i].id=i;
			binTreeList.add(binTree[i]);
		}
		
		generateHuffmanTree(binTreeList);
		BinaryTree root=(BinaryTree)binTreeList.get(0);
		root.info=new StringBuffer();
		generateHuffmanPath(root);
		return binTree;
	}
}