图布局FR算法探究和实现

《图布局FR算法探究和实现》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、图布局FR算法探究和实现摘要：近年来，对信息技术可视化的研究越来越广泛，信息技术可视化也在各个领域中得到越来越广泛的应用。图布局是用图结构解决现实世界中信息可视化问题的一种重要技术。该文介绍图布局FR算法的基本模型，研究FR算法实现方法，及FR算法的优化。关键词：图布局；FR算法中图分类号：TP391文献标识码：A文章编号：1009-3044(2013)12-2864-021概述近年来对信息技术可视化的研究越来越广泛，信息技术可视化也在各个领域中得到越来越广泛的应用。信息可视化充分利用了人类视觉感知系统，将信息以图形化方式进行展示，直观快速地解释信息的意义。绘图

2、技术是信息可视化与应用数学的一个交叉领域，主要研究从图到几何空间的映射关系。绘图技术的内容极其丰富，主要是根据不同的实际应用需求，满足绘图的基本要求。从图布局的观点来看，在图的绘制中，主要解决的是图中节点的布局问题。2FR算法的基本模型1984年,Eades首次提出了用弹力模型实现图布局算法。弹力模型即力学中常用的虎克定律：在弹性限度内，物体的形变跟引起形变的外力成正比。Eades将图中的边看成力学中的弹簧，利用弹力关系决定图点的布局。弹簧模型提出后，许多学者在此基础上进行了深入的研究。最典型的算法有Fruchtennan和Reingold提出的FR算法。FR算

3、法在经典弹簧算法的基础上进行了改进，引入了力导引模型。力导引模型建立在粒子物理理论的基础上，将无向图中的节点模拟成原子，通过模拟原子间的力场来计算节点间的位置关系。算法通过考虑原子间引力和斥力的互相作用，经过不断的迭代计算，系统最终进入一种动态平衡状态。FR算法也没有太严格地遵照物理规则来进行模拟，而是进行了一些简化。FR算法在所有的实体之间计算排斥力,而吸引力只在相互连接的实体之间进行计算。FR算法的每次迭代主要分为三个部分:首先是计算节点之间相互的排斥力，然后是计算图中有边连接的节点之间相互的吸引力，最后综合吸引力和排斥力，并通过最大位移来限制移动的距离。对

4、于一个高度为H,宽度为W的显示区域，其中任意节点V有两个布局参数（分量）：节点的位置pos和所受合力产生的位置偏移量diSPoFR的基本定义如下：显示区域：［area=WXH］其中：［W］和［H］是显不区域的宽和高；平衡距离：FR算法的伪代码如下：for(i=1；i其中：p(E)指出状态E的能量值的概率分布，作为温度T和Boltzmann常数k的函数。一方面，对每一个温度，各个能量E有非零的概率，因此，系统能以较高的温度改变它的状态。另一方面，在降低温度时，系统趋向于非常低的能量状态，当全局能量最小时，达到温度零。在本算法中，采用了线性算法。首先设置一个初始温度

5、,即节点允许的最大位移量。如果初始温度足够高，节点可以任意地移动。因此，将节点初始最大位移量设置为绘图矩形区域长边的1/2,其后是温度减少的过程，典型的是一个多项式算法。本文使用线性数，温度下降过程的表达式为：，［V］称为冷却系数，在0.6到0.95之间，一般使用用］Y=0.8］o按照式上述公式，模拟退火算法的迭代次数由初始温度、冷却系数、迭代终止下界决定。初始温度T0一般设置为显示区域边长的1/2,每次迭代后，温度T的值乘以冷却系数，因冷却系数小于1,温度T的值递减，直至温度Tn到达迭代终止下界。迭代终止下界是一个很小的值，即节点的最小位移量。我们用FR算法对

6、100个节点的图进行了布局计算。迭代300次后的执行效果见图（b）。可以看到，布局效果并不太好。模拟退火算法的迭代次数由初始温度、冷却系数和迭代终止下界决定。在计算中，初始温度T0设置为显示区域边长的1/2,冷却系数为0.9,迭代终止下界为1。因此迭代了315次。显然比前面不用模拟退火算法循环300次的效果要好了许多。由运行测试与分析，模拟退火算法在FR算法中起着比较重要的作用，它能有效地防止节点位移的振荡，因此，在按循环次数迭代时，也引入了模拟退火算法来限制节点位移的最大偏移量，按循环次数使节点位移最大偏移量递减。4结束语本文主要研究图的布局算法与实现方法。阐

7、述了FR算法的原理，给出了算法的伪代码。并应用模拟退火算法对FR算法进行优化，分析及其执行效果，为后继数据分析工作建立一个坚实的基础。