图布局算法综述

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

1、OVERVIEWOFALGORITHMSFORGRAPHDRAWING图布局算法综述BostjanPajntarDepartmentofKnowledgeTechnologiesJozefStefanInstituteJamova39,1000Ljubljana,Slovenia（南斯拉夫）Tel:+38614773128E-mail:bostjan.pajntar@ijs.si摘要本文综述若干种图可视化算法，并详细描述了最常用的几个算法。本文的首要目的是帮助读者选择合适的算法去可视化关系数据。另一方面，也可以当作对图布局算法及其发展的历史回顾

2、1概要从前，信息只是一种commodity（?商品，不足大量）。然而随着互联网的发展，大规模的数据变得随处可见。问题从获取信息，变为抽取其中的有用倍息。使用统计分析与数据挖掘，我们能够抽取所需的信息。但是，由于显示是平面的，大部分这些数据挖掘的结杲难以为人们所阅读，由此就产牛-了对可视化的需求。因为一张图画常常可以蕴含一篇文章（的信息），对任何关系数据的描绘成为了一种非常常用的表示已获信息的途径。2关于图图论中的定义在不同文献中有所不同。针对我们的需求，图G的一个宽松的定义是一个三元组（V,E,X）-顶点集V・边集E・函数儿映射每条边的端点到一

3、个顶点一个循环是一条两端指向相同顶点的边。一条多重边表示两个顶点同时关联多条边（图1）。一个没冇循环和多重边的图称为简单图。如果边是冇向的，则图为冇向图（digraph）。Figure1:Graphwithoneloopandonemulti3图的大小（size,规模）关于图的大小并没有专门的术语。图的大小常常被定义为顶点的数冃，这并非是一个最好的定义。由于计算机运行速度L1益增长，图的大小会随着时间而改变（译者注：喑示图的大小跟计算机运行速度应该联系起来）。也许一种更好的定义就是将图的大小和计算复杂度（译者注：以下可以理解为单位时间计算机可处

4、理的顶点数n）联合起来。我们把图划分为小、中、大（large）、超大（huge）。・对于小图，基木上可以使用任何算法。冃前这种图的规模为n10（最大为150个顶点）-中图可以被多项式时间复杂度的算法所绘制。这种图的规模也是足够小，以被绘制在常用的屏幕上，其数量为n100o・大图不能被直接地绘制（由于屏幕象索不足）。然而，这种图仍然足以存放在内存中。■更大的图就称为超大图（内存都放不下整个图的数据）同时，我们也按稠密程序把图分为［5］：-稀疏：Ev=V（译者注：划为理由可能是根据树的性质E=V-1）・一般：V3V（译者注：

5、划为理由可能是根据平面图的充分条件E>=3V-6）这种命名法认为树是稀疏的，而四方体和多面体则为一般图。4图的嵌入（Embbeding,译者注：可认为是平面化planarization）图可视化的质量诚然是一种主观判断。它依赖于图，以及我们希望从中获取的信息。目前，关于人们如何从图屮阅读信息的研究比较少［7］,大多数准则是直观的选择出来的。首要的指导思想是：用户必须能够从图中获取他所感兴趣的信息，而口越简单越好。以下是关于好的图绘制的准则：■顶点必须均匀地分布在屏幕・边交叉必须只有少量・边长度必须均匀・图结构中的对称性必须表现出来-图必须被包含

6、在一，个画面中（原文为:Grafshouldbeboundinsideaframe,译文可能有误）这些准则常常描述了我们的需求。然而，也有例外。・平面绘制可能有更好的结果，如果边具有不同的长度（图3,4）。・对于大图，顶点必须被聚类；一种可视化的方法是所有同类的顶点被绘制为一点。・对于十分稠密的图，対边进行合并具有一定的意义。利用这个方法，可能将非平血图进行平面绘制。（以下是按次方法对一个96个顶点的完全图的绘制）Figure2:Fullgraphon96nodesindeleconfluemdraw力送.5算法可视化图具有许多种方法。常用的对

7、简单无向图的方法是物理类比的（译者注：将图类比为一定的物理模型，如具有引力斥力的弹簧和粒子）。然而，如果图具有其他的特征，我们可以使用其他的方法。5.1对于具有附加属性的图的算法5.1.1正交风格图可以被绘制在正交栅格上。这种方法常常用于有向图，如我们所见的图表（diagram）。每条边都可以曲折，但每部分都必须是水平或者垂直。由此每个边交叉都是正交的。这样有利于对图的阅读。5.1.2Sugiyama风格图布局的--种好方法是层次化布局。对于DAG（有向无循环图），我们可以根据拓扑顺序对图进行层次化。接着我们就可以得到一个流程图，其所有边都指向

8、同个方向。例如，有一条从A指向B的边，A就在B的上方或左方。这种方法的一个优点是所有图都可以转换为DAG。Sugiyama提出了一个很好的算法［11］