基于斥力-张力模型的网络拓扑布局算法（php代码）

<?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();//
?>