文档章节

布点算法

阿山
 阿山
发布于 2013/09/26 14:55
字数 1079
阅读 254
收藏 0

布点算法的作用是将已知的图结构以较美观的形式展示出来,需要尽量遵循的原则有五个:

  • 对称性:绘制网络对应将具有相同结构的子图围绕绘图中心平衡布局
  • 正交性:绘制网格对应的以网格为背景,并尽量将节点布局在网格交叉处,使边可以沿着网格线绘制。
  • 连接角最大化原则,使同一节点任意两条边形成的角度尽量大
  • 边交叉数量最小原则(最重要):绘图时应尽量减少相互交叉边的数量。
  • 直线边原则:边尽量直线,避免曲线

布点算法之力导引布局

       力导引布局的方法可以产生相当优美的网络布局,并充分展现网络的整体结构及其自同构特征。该方法最早由Eades在1984年提出。其基本思想是将网络看成一个顶点为钢环,边为弹簧的物理系统,系统被赋予某个初始状态以后,弹簧弹力(引力和斥力)的作用会导致钢环移动,这种运动直到系统总能量减少到最小值停止。每次循环都要计算任意一对点的斥力和相邻两个点的引力,计算复杂度为O(N2

      Kamada和Kawai改进了Eades的弹簧模型,提出KK算法。KK算法主要通过求系统的总能量:image的最小值来确定节点的位置。其中Pi和pj 表示节点vi和vj的位置,lij表示vi和vj之间的弹簧的初始长度,kij表示弹性系数。在此模型中遵循了胡克定律。KK算法中加入了非相邻节点间理想距离的概念,两个节点的理想距离和它们之间的最短路径的长度成正比。当系统处于稳定状态时,弹簧的距离接近与他们的理想距离。KK算法的复杂度依然是N2,但是在收敛性方面得到了很大的提高。

     Davidson和Harel提出的DH算法根据顶点分布、边界靠近,边长及边交叉等约束来建立系统的能量函数。调整约束的权重能量满足了不同的美学标准,而且他们使用了模拟退火算法(SA,Simulated Annealing)来求解能量函数的最小值。SA算法解得的结果非常接近能量最小点,并且他们在算法的最后阶段加入了针对边交叉及边点交叠的两个罚函数,使得该算法与其他算法相比能够产生效果更好的节点布局。但是比较耗时。

    Fruchterman和Reingold基于再次改进的弹簧模型提出了FR算法。该算法主要遵循两个原则:有边连接的节点应该相互靠近;节点间不能离的太近。FR算法主要将无向图中的节点模拟成原子,通过模拟原子间的力场来计算节点间的位置关系。算法通过考虑原子间引力和斥力的互相作用,计算节点的速度和加速度。依照类似原子的运动规律,系统最终进入一种动态的平衡状态。FR算法还采用了网格变量方法进行了优化。将布点屈原分成若干网格,计算斥力的时候只考虑节点与相邻的网格的节点间的作用。若以K表示节点周围空白的区域的理想半径,d表示节点间的距离,则斥力计算公式为:image其中,image

布点算法之Stress majorization

.stress majorization算法主要通过计算整个系统的总能量(Stress),Stress的定义如下image其中第二项为

image

第三项:image等号成立的条件是:X=Z。

Stress(X)最小的时候X满足,image,通常情况下,Stress最小的判断:image,迭代的deadline通常取值,10-4.

这个Stress majorization只对连通图有效,对于非连通图,需要自己处理。可以在最短路径矩阵中定义非连通图之间的最短路径。包括孤立点。

© 著作权归作者所有

阿山
粉丝 3
博文 28
码字总数 12844
作品 0
海淀
程序员
私信 提问
增加用户流量及产品知名度方案:

增加用户流量及产品知名度方案:(有些是本来就有得想法,目前还未完成的,有些是新想法,大家有想法可以直接评论) 方案一: 各院校布点做宣传活动,宁波先实行。如,布点,放个抽奖箱,扫了...

丁姑娘
2014/11/14
3
0
NMRAS dependency

NMRAS依赖项整理 标签(空格分隔): 遗留问题 1. 二维反演(NiumagInvertMethod.dll) // IR-CPMG function invt1t2(PDL1S: PDouble; NTI: integer; PPeakTime: PDouble; NECH: integer; P......

体全息
2017/12/08
1
0
中国安防为何世界最强?中科院AI+安防报告,解密8大趋势和8大限制【附下载】| 智东西内参...

来源:智东西 传统的安防企业、新兴的 AI 初创企业,开始积极从技术各个维度拥抱人工智能,在模式识别基础理论、图像处理、计算机视觉以及语音信息处理展开了集中研究与持续创新,探索模式识...

人工智能学家
2018/11/19
0
0
在球面上随机生成分布点的算法(fortran)

转载自:http://sobereva.com/311 参考算法网址(未看,待研究):http://mathworld.wolfram.com/SpherePointPicking.html Marsaglia方法:在[0,1)区间内随机取两个值x1和x2,若这两个值的平...

妍小屋
2018/06/29
0
0
SSH后台网站项目

基坑监测智能化管理云平台 需求1: 主页布局 功能1:地图功能 三级拓扑:1进入主页后在主页上标识所有建筑工地的位置、 拓扑2:选择建筑工地后在地图上标识该建筑工地下所有的基坑位置 拓扑3...

crazyWalker
2016/10/31
39
0

没有更多内容

加载失败,请刷新页面

加载更多

Nginx 快速安装详解

一、Nginx Nginx (engine x) 是一个高性能的HTTP和反向代理web服务器,同时也提供了IMAP/POP3/SMTP服务。Nginx是由伊戈尔·赛索耶夫为俄罗斯访问量第二的Rambler.ru站点(俄文:Рамбле...

网络小虾米
14分钟前
4
0
技术分享 | slave_relay_log_info 表认知的一些展开

作者:胡呈清 slave_relay_log_info 表是这样的: mysql> select * from mysql.slave_relay_log_info\G *************************** 1. row *************************** Number_of_lin......

爱可生
16分钟前
3
0
nginx配置http访问自动跳转到https

server {listen 80;server_name www.域名.com;rewrite ^(.*) https://$server_name$1 permanent;}server {listen 443;server_name www.域名.com;root /home/www;ssl on;......

很好亦平凡ms
16分钟前
2
0
SpreadJS:一款中国研发的类Excel开发工具,功能涵盖Excel的 95% 以上

Excel 作为一款深受用户喜爱的电子表格工具,借助其直观的界面、出色的计算性能、数据分析和图表,已经成为数据统计领域不可或缺的软件之一。 基于Excel对数据处理与分析的卓越表现,把Excel...

葡萄城技术团队
16分钟前
2
0
用javafx框架tornadofx做了个天气预报的程序

class WeatherApp : App(WeatherView::class)class WeatherView : View("十五天天气预报") { val weatherVM: WeatherViewModel by inject() val controller: WeatherController by......

oschina4cyy
20分钟前
3
1

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部