<?php	//**********************************************************//	//date:2014.11.07 @ bupt	//本PHP文件包括顶点类Point、图类Graph、以及相关函数	//Graph对象的构造函数的输入为(顶点个数:$_Nv,x轴最小值:$_xmin,x轴最大值:$_xmax,y轴最小值:$_ymin,y轴最大值:$_ymax,邻接矩阵$_mat)	//Graph对象的initLayoutProc()方法是初始化布局过程	//Graph对象的layOut()方法是进行一次布局	//当Graph对象的成员变量温度T小于1时,停止布局，根据画布大小进行平移和缩放	//**********************************************************//	//	//示例程序如下:	//$tNv = 4;//顶点的个数	//$txmin = 0;//x轴最小值	//$txmax = 400;//x轴最大值	//$tymin = 0;//y轴最小值	//$tymax = 400;//y轴最大值	//	////邻接矩阵	//$tmat = array(	//	0=>array(0,1,1,0),	//	1=>array(1,0,1,1),	//	2=>array(1,1,0,1),	//	3=>array(0,1,1,0)	//	);	//	//	//$g = new Graph($tNv,$txmin,$txmax,$tymin,$tymax,$tmat);//初始化拓扑图	//$g->initLayoutProc();//初始化布局过程	//$g->outPut();//输出图	//while ($g->T >= 1) {	//	//$g->layOut();//进行一次布局	//}		//$g->layOut();//$this->T<1时，此时布局部已完成，进行平移和缩放	//$g->outPut();//	//**********************************************************//	//	//	//	//需要用到的函数	function init3($v,$x,$y){//初始化		$v[0]=$x;		$v[1]=$y;		return $v;	}	function len3($v){//计算模		$len=sqrt($v[0]*$v[0]+$v[1]*$v[1]);		if($len==0)$len=0.001;		return $len;	}	function len3_2($v){//计算平方和		return $v[0]*$v[0]+$v[1]*$v[1];	}	function sub3($a,$b,$rs){//计算向量的差		$rs[0]=$a[0]-$b[0];		$rs[1]=$a[1]-$b[1];		return $rs;	}	function add3($a,$b,$rs){//计算向量的和		$rs[0]=$a[0]+$b[0];		$rs[1]=$a[1]+$b[1];		return $rs;	}	function mul3($k,$v,$rs){//计算向量与常数的乘积		$rs[0]=$k*$v[0];		$rs[1]=$k*$v[1];		return $rs;	}	function fa($d,$K){//引力位移		return $d*$d/$K;	}	function fr($d,$K){//斥力位移		return $K*$K/$d;	}	////////////////////////////////////////////////	//顶点类	class Point	{		var $pos;//点的位置		var $offset;//点的位移		var $weight;//点的重量		var $degree;//点的度数		var $force;//合力		function __construct()//构造函数		{			$this->pos = array(0,0);			$this->offset = array(0,0);			$this->weight=0;			$this->degree=0;			$this->force=array(0,0);		}	}	//图类	class Graph	{				var $Nv;//顶点的个数		var $xmin;//x轴最小值		var $xmax;//x轴最大值		var $ymin;//y轴最小值		var $ymax;//y轴最大值		var $mat;//邻接矩阵vector<vector<bool> > mat;		var $vlist;//顶点列表vector<Cvertex> vlist;				//引力-斥力模型		var $K;//引力常数		var $T;//当前温度		var $Jf;//前一次的目标函数值		var $decay;//衰减常数		function __construct($_Nv,$_xmin,$_xmax,$_ymin,$_ymax,$_mat)//复杂构造函数		{			$this->Nv=$_Nv;			$this->xmin=$_xmin;			$this->xmax=$_xmax;			$this->ymin=$_ymin;			$this->ymax=$_ymax;			$this->mat=$_mat;			$this->decay=0.85;			for($i=0;$i<$_Nv;$i++){				$this->vlist[$i]=new Point();				$this->vlist[$i]->pos[0] = rand($this->xmin,$this->xmax);				$this->vlist[$i]->pos[1] = rand($this->ymin,$this->ymax);			}		}		function shutLayoutProc(){//关闭布局过程			$this->T=0;		}		function initLayoutProc(){//初始化布局过程		//初始化引力常数			$INF=100000000;			$area=($this->xmax-$this->xmin)*($this->ymax-$this->ymin);			$this->K=pow($area/$this->Nv,0.5);					//初始化温度			$this->T=($this->xmax-$this->xmin);			//初始化目标函数值			$this->Jf=$INF;			//初始化衰减系数			$decay=0.9;		}		function layOut(){//进行一次布局			$INF=100000000;			if($this->T<=1){	//T为当前温度				//此时布局部已完成，进行平移和缩放				//求外接矩形					$left=$INF;					$right=-$INF;					$up=-$INF;					$down=$INF;					for($i=0;$i<=$this->Nv-1;$i++){						if($this->vlist[$i]->pos[0]<$left)$left=$this->vlist[$i]->pos[0];						if($this->vlist[$i]->pos[0]>$right)$right=$this->vlist[$i]->pos[0];						if($this->vlist[$i]->pos[1]>$up)$up=$this->vlist[$i]->pos[1];						if($this->vlist[$i]->pos[1]<$down)$down=$this->vlist[$i]->pos[1];					}//得到left,right,up,down					echo "</br>left:".$left.",right:".$right.",up:".$up.",down:".$down."</br></br>";					//求外接矩形中心					$_cx=($left+$right)/2;					$_cy=($up+$down)/2;					//求画板中心					$cx=($this->xmin+$this->xmax)/2;					$cy=($this->ymin+$this->ymax)/2;					//由外接矩形中心向画板中心的平移向量					$vec = array($cx-$_cx,$cy-$_cy);					//按平移向量对图形进行平移，但只移若干分之一，而不一步到位，为的是动画效果					for($i=0;$i<=$this->Nv-1;$i++){						$this->vlist[$i]->pos[0]+=$vec[0];						$this->vlist[$i]->pos[1]+=$vec[1];					}					//求外接矩形的最大边心距					$r=max(($this->xmax-$this->xmin)/2,($this->ymax-$this->ymin)/2);					//求边心距的最大可增加量					$dr=min(($this->xmax-$this->xmin)/2-($right-$left)/2,($this->ymax-$this->ymin)/2-($up-$down)/2);					$dr=$dr-($this->xmax-$this->xmin)/15;//防止顶天					//$_dr=$dr/1000;//只取最大可增加量的若干分之一，为的是动画效果					//求缩放系数					$k=($r+$dr)/$r;					//按k对图形进行缩放，					for($i=0;$i<=$this->Nv-1;$i++){						$this->vlist[$i]->pos[0]=($this->vlist[$i]->pos[0]-$_cx)*$k+$_cx;						$this->vlist[$i]->pos[1]=($this->vlist[$i]->pos[1]-$_cy)*$k+$_cy;					}								return;			}			//将各顶点的offset恢复为0			for($i=0;$i<=$this->Nv-1;$i++){				$this->vlist[$i]->offset = init3($this->vlist[$i]->offset,0,0);			}			//在斥力作用下位移			for($i=0;$i<=$this->Nv-1;$i++){				for($j=0;$j<$i;$j++){					//计算位移向量offset和_offset					$diff=array(0,0);					/*					echo "i:".$i.",j:".$j;					echo "</br>vlist_i_pos:";					echo $this->vlist[$i]->pos[0];					echo ",";					echo $this->vlist[$i]->pos[1];					echo "</br>";					echo "</br>vlist_j_pos:";					echo $this->vlist[$j]->pos[0];					echo ",";					echo $this->vlist[$j]->pos[1];					echo "</br>";//*/					$diff = sub3($this->vlist[$i]->pos,$this->vlist[$j]->pos,$diff);					$len_diff = len3($diff);//|diff|					/*					echo "</br>diff:";					echo $diff[0];					echo ",";					echo $diff[1];					echo "</br>";					echo "</br>len_diff:";					echo $len_diff;					echo "</br>";//*/					$e_diff = array(0,0);//diff/|diff|					$e_diff = mul3(1.0/$len_diff,$diff,$e_diff);					$offset = array(0,0);//(diff/|diff|)*fr(|diff|)					$offset = mul3(fr($len_diff,$this->K),$e_diff,$offset);					$_offset = array(0,0);//-offset					$_offset = mul3(-1,$offset,$_offset);					//累计位移量					$this->vlist[$i]->offset = add3($this->vlist[$i]->offset,$offset,$this->vlist[$i]->offset);					$this->vlist[$j]->offset = add3($this->vlist[$j]->offset,$_offset,$this->vlist[$j]->offset);				}			}			//在引力作用下位移			for($i=0;$i<=$this->Nv-1;$i++){				for($j=0;$j<$i;$j++){					if($this->mat[$i][$j]){						//计算位移向量offset和_offset						$diff=array(0,0);						$diff=sub3($this->vlist[$i]->pos,$this->vlist[$j]->pos,$diff);						$len_diff=len3($diff);//|diff|						$e_diff=array(0,0);//diff/|diff|						$e_diff=mul3(1.0/$len_diff,$diff,$e_diff);						$offset=array(0,0);//(diff/|diff|)*fr(|diff|)						$offset=mul3(fa($len_diff,$this->K),$e_diff,$offset);						$_offset=array(0,0);//-offset						$_offset=mul3(-1,$offset,$_offset);						//累计位移量						$this->vlist[$i]->offset=add3($this->vlist[$i]->offset,$_offset,$this->vlist[$i]->offset);						$this->vlist[$j]->offset=add3($this->vlist[$j]->offset,$offset,$this->vlist[$j]->offset);					}				}			}			//进行位移(限制移动距离不超过T)			for($i=0;$i<=$this->Nv-1;$i++){				$len_offset=array(0,0);				/*				echo "</br>vlist_offset";				echo $this->vlist[$i]->offset[0];				echo ",";				echo $this->vlist[$i]->offset[1];				echo "</br>";//*/				$len_offset=len3($this->vlist[$i]->offset);//位移量的模				$e_offset=array(0,0);//位移量的方向				$e_offset=mul3(1.0/$len_offset,$this->vlist[$i]->offset,$e_offset);//得到e_offset				$len_offset=min($len_offset,$this->T);//得到len_offset				$offset=array(0,0);//位移量				$offset=mul3($len_offset,$e_offset,$offset);//得到offset				/*				echo "</br>len_offset:";				echo $len_offset;				echo "</br>";				echo "</br>e_offset:";				echo $e_offset[0];				echo ",";				echo $e_offset[1];				echo "</br>";				echo "</br>offset:";				echo $offset[0];				echo ",";				echo $offset[1];				echo "</br>";//*/				$this->vlist[$i]->pos=add3($this->vlist[$i]->pos,$offset,$this->vlist[$i]->pos);			}			//降温	    	$this->T=$this->decay*$this->T;			}		function outPut(){			echo "Point Number:".$this->Nv;			echo "</br>";			echo "</br>";			echo "Adjacent Matrix:";			echo "</br>";			for($i=0;$i<$this->Nv;$i++){				for($j=0;$j<$this->Nv;$j++){					echo $this->mat[$i][$j];					echo " ";				}				echo "</br>";			}			echo "</br>";			echo "x:".$this->xmin.",".$this->xmax;			echo "</br>";			echo "y:".$this->ymin.",".$this->ymax;			echo "</br>";			echo "</br>";			echo "Repulsive Const:".$this->K;			echo "</br>";			echo "Now Temperature:".$this->T;			echo "</br>";			echo "Prev Function Value:".$this->Jf;			echo "</br>";			echo "Attenuation Const:".$this->decay;			echo "</br>";			echo "</br>";			echo "Point Pos:";			echo "</br>";			for($i=0;$i<$this->Nv;$i++){				echo $i;				echo ":";				echo $this->vlist[$i]->pos[0];				echo ",";				echo $this->vlist[$i]->pos[1];				echo "</br>";			}		}	}	//echo $INF;	$tNv = 4;//顶点的个数	$txmin = 0;//x轴最小值	$txmax = 400;//x轴最大值	$tymin = 0;//y轴最小值	$tymax = 400;//y轴最大值	//邻接矩阵	$tmat = array(		0=>array(0,1,1,0),		1=>array(1,0,1,1),		2=>array(1,1,0,1),		3=>array(0,1,1,0)		);	$g = new Graph($tNv,$txmin,$txmax,$tymin,$tymax,$tmat);//初始化拓扑图	$g->initLayoutProc();//初始化布局过程	$g->outPut();//输出图	while ($g->T >= 1) {		$g->layOut();//进行一次布局	}		$g->outPut();//	$g->layOut();//$this->T<1时，此时布局部已完成，进行平移和缩放	$g->outPut();//?>