图布局FR算法的研究与实现

开篇：润墨网以专业的文秘视角，为您筛选了一篇图布局FR算法的研究与实现范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要：近年来，对信息技术可视化的研究越来越广泛，信息技术可视化也在各个领域中得到越来越广泛的应用。图布局是用图结构解决现实世界中信息可视化问题的一种重要技术。该文介绍图布局fr算法的基本模型，研究FR算法实现方法，及FR算法的优化。

关键词：图布局；FR算法

中图分类号：TP391 文献标识码：A 文章编号：1009-3044（2013）12-2864-02

1 概述

近年来对信息技术可视化的研究越来越广泛，信息技术可视化也在各个领域中得到越来越广泛的应用。信息可视化充分利用了人类视觉感知系统，将信息以图形化方式进行展示，直观快速地解释信息的意义。

绘图技术是信息可视化与应用数学的一个交叉领域，主要研究从图到几何空间的映射关系。 绘图技术的内容极其丰富，主要是根据不同的实际应用需求，满足绘图的基本要求。从图布局的观点来看，在图的绘制中，主要解决的是图中节点的布局问题。

2 FR算法的基本模型

1984年，Eades首次提出了用弹力模型实现图布局算法。弹力模型即力学中常用的虎克定律：在弹性限度内，物体的形变跟引起形变的外力成正比。Eades将图中的边看成力学中的弹簧，利用弹力关系决定图点的布局。

弹簧模型提出后，许多学者在此基础上进行了深入的研究。最典型的算法有Fruchterman和Reingold提出的FR算法。

FR算法在经典弹簧算法的基础上进行了改进，引入了力导引模型。力导引模型建立在粒子物理理论的基础上，将无向图中的节点模拟成原子，通过模拟原子间的力场来计算节点间的位置关系。算法通过考虑原子间引力和斥力的互相作用，经过不断的迭代计算，系统最终进入一种动态平衡状态。

FR 算法也没有太严格地遵照物理规则来进行模拟，而是进行了一些简化。FR 算法在所有的实体之间计算排斥力，而吸引力只在相互连接的实体之间进行计算。

FR 算法的每次迭代主要分为三个部分：首先是计算节点之间相互的排斥力，然后是计算图中有边连接的节点之间相互的吸引力，最后综合吸引力和排斥力，并通过最大位移来限制移动的距离。

对于一个高度为H ，宽度为W 的显示区域，其中任意节点v 有两个布局参数（分量）：节点的位置pos和所受合力产生的位置偏移量disp。

FR的基本定义如下：

显示区域：

[area=W×H]

其中：[W]和[H]是显示区域的宽和高；

平衡距离：

FR 算法的伪代码如下：

for （i = 1； i < 迭代次数；i++）

{

// 计算排斥力

// 计算吸引力

// 对点坐标进行置换，防止置换超出边界

foreach（ v in V）

// 减少温度，使布局更好

t = cool（t）

}

在FR 算法中：cool（t）为模拟退火函数。

3 应用模拟退火算法进行优化

模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在各个温度中都达到平衡态，最后在常温时达到基态，内能减为最小。

在图布局算法中，常采用模拟退火算法，在算法中给出“温度”和“冷却”的概念，用于限制节点的最大位移，并且最大位移随着迭代次数的增大而减小。这是因为随着迭代次数的增大，图形的布局效果越来越好，相应需要的调整也更加细微。“温度”应该从一个初始值开始逐渐衰退到0。温度控制节点的位置移动范围，使得布局越来越好，调整越来越小。

模拟退火算法遵循Boltzmann函数：

其中：p（E）指出状态E的能量值的概率分布，作为温度T和Boltzmann常数k的函数。一方面，对每一个温度，各个能量E有非零的概率，因此，系统能以较高的温度改变它的状态。另一方面，在降低温度时，系统趋向于非常低的能量状态，当全局能量最小时，达到温度零。

在本算法中，采用了线性算法。首先设置一个初始温度，即节点允许的最大位移量。如果初始温度足够高，节点可以任意地移动。因此，将节点初始最大位移量设置为绘图矩形区域长边的1/2，其后是温度减少的过程，典型的是一个多项式算法。

本文使用线性数，温度下降过程的表达式为：，[γ]称为冷却系数，在0.6到0.95之间，一般使用用[γ=0.8]。

按照式上述公式，模拟退火算法的迭代次数由初始温度、冷却系数、迭代终止下界决定。初始温度T0一般设置为显示区域边长的1/2，每次迭代后，温度T的值乘以冷却系数，因冷却系数小于1，温度T的值递减，直至温度Tn到达迭代终止下界。迭代终止下界是一个很小的值，即节点的最小位移量。

我们用FR算法对100个节点的图进行了布局计算。迭代300次后的执行效果见图（b）。可以看到，布局效果并不太好。

模拟退火算法的迭代次数由初始温度、冷却系数和迭代终止下界决定。在计算中，初始温度T0设置为显示区域边长的1/2，冷却系数为0.9，迭代终止下界为1。因此迭代了315次。显然比前面不用模拟退火算法循环300次的效果要好了许多。

由运行测试与分析，模拟退火算法在FR算法中起着比较重要的作用，它能有效地防止节点位移的振荡，因此，在按循环次数迭代时，也引入了模拟退火算法来限制节点位移的最大偏移量，按循环次数使节点位移最大偏移量递减。

4 结束语

本文主要研究图的布局算法与实现方法。阐述了FR算法的原理，给出了算法的伪代码。并应用模拟退火算法对FR算法进行优化，分析及其执行效果，为后继数据分析工作建立一个坚实的基础。