基于斥力-张力模型的网络拓扑布局算法（php代码）
浏览数：56 /
时间：2015年06月08日
根据之前的C++代码改写：
<?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();//
?>
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
