一种无向图视觉清敞化显示算法

一种无向图视觉清敞化显示算法

1视觉清析显示算法图形是一种广泛使用的数据结构。它可以直观地表示各种复杂的关系模型。其中，表示系统中的对象，表示对象之间的关系。将图清晰、美观地显示在二维或三维的一个有限区域对理解和分析模型具有十分重要的意义。在许多应用领域,需要描述一组对象间的关系。比如在软件工程中,各个模块间存在依赖关系,各个数据类间存在访问关系。在系统分析时,就要考虑子系统的划分及其包含的模块和数据类。如果把这些模块或数据类看成顶点,依赖关系或访问关系看成二元关系,如何理顺模块或数据类就是一个图的清晰化显示问题。此外,关系数据表间的联系、组织成员间的合作关系、知识点依赖图、路由器分布图等,只要需要图形化显示的,都涉及到图的清晰化显示问题。因此,图的视觉清晰化显示算法具有相当大的实际意义,是一项值得研究的应用基础研究项目。该算法的研究一旦取得实质性的成果,就可以将它植入软件工程、识别系统等应用技术或系统中去,使这些技术或系统更加自动化、智能化、高效率、实用化和人性化。其中,无向关系图的画图算法是其中一类重要的算法,很多学者对此做过深入的研究。EadesP用弹力模型绘制一般无向图,该方法将一个图看成是一个顶点为钢环、边为弹簧的机械系统,弹簧达到极小能量状态时对应图的一个美观画法。然而,这种方法由于容易陷入局部最优解而得到的结果很差。Davidson和Harel提出用模拟退火算法画一般无向图,产生的效果可与弹力模型法产生的效果相比。但是,该算法在绘制顶点数较多且无弦的图时得到的并不是通常情况下的大圈,而是一个卷曲的圈,即得到的是一个凹多边形而不是凸多边形;同时,模拟退火算法也容易限入局部最优解而得到较差的画法。黄竞伟、康立山等提出了一种基于遗传算法的无向图画图算法,该算法将画图问题转化为函数优化问题,但遗传算法属于概率算法,算法执行结果具有不确定性,同时想要得到好的输出结果,需要经过相当长的时间演化,因此算法收敛性较差。Papadopoulos和Voglis采用自底向上的模块分解树的方法绘制无向图,使得绘图结果达到一定的美学标准,但模块之间的连线相交问题仍然不能解决。张清国、叶俊民等也提出了一种基于遗传算法的无向绘制图算法。张磊、孙松等提出将无向图显示在环上,根据每个顶点的加权值确定其所占有的扇形区域,并将每个顶点布局在其扇区的中心线上。然而,这种方法不适用于带有环的无向图。Hong和Nagamochi研究了用星形和凸多边形相结合的方式绘制可平面图,并分析了可平面化的充分条件,但并未对无向图画图算法作深入研究。相比之下,本文算法能很好地克服上述算法中的不足。2提出无向关系图清糊化的要求并构建相应的二元关系无向关系图的绘制算法有直线法、折线法、正交法、平面化法等。本文提出的无向关系图视觉清晰化显示算法是基于直线画法实现的。无向关系图清晰化显示问题的形式化描述是:给定顶点集A={Pi,i=1,…,N},以及A上的反自反对称二元关系R={<Pi,Pj>|i≠j,1≤i≤N,1≤j≤N}和二维区域Ω=[0,X]×[0,Y],寻找N个顶点的位置P=(P1,…,PN)∈ΩN,使得二元关系图在一定的视觉清晰度目标函数Q(P)的意义下达到最优或近似最优。2.1清朗化显示算法清晰度是从人的视觉感官上看图的美学标准,至今没有统一的解析表达式,预计将来也难以产生能被普遍接受的标准。一个视觉清晰化显示算法就是在这样一个无定论的标准之上绘制的画图算法,即使有一个清晰度的客观标准Q(P),由于问题的搜索空间是ΩN,具有2N个自由度,搜索空间巨大,清晰化显示算法也难以解析地表达。对于无向关系图,通常能够被接受的清晰度标准有:(1)以连通分支为基本单位分配显示区域;(2)顶点间的最小距离越大越好;(3)边的交叉越少越好;(4)边的长度越均匀越好;(5)多度顶点的各相关边的夹角越均匀越好;(6)尽量占满显示区域。2.2无向连通一带子团内各子团交叉连接为了更好地说明无向关系图视觉清晰化显示算法,先定义几个术语。(1)团:一个连通无向图删除所有割边后,每一个连通子图称为团。团内不再有割边。在一般无向连通图中,如果将团缩为一个顶点,那么该无向连通图将缩为一棵树。(2)子团:一个团删除所有割点后,每一个连通子图称为子团。子团内不再有割点。从团和子团的定义中可以发现,没有割点的团也是子团,子团是一种特殊的团,子团与子团间通过割点连接构成团。本文算法除了遵循通常的清晰度标准之外,还在下述清晰度标准上达到最优或近似最优:(1)团内各子团分布越均匀越好;(2)团间连接各子团的交叉边越少越好;(3)团内连接各子团的边长越均匀越好;(4)子团内顶点分布越均匀越好;(5)子团内交叉边越少越好;(6)子团内边长越均匀越好。2.3dfsu低v的位点由于在本文中要用到求割点与割边,先将该算法说明如下。该算法是TarjanR提出的。对图深度优先搜索,定义DFS(u)为u在搜索树(以下简称为树)中被遍历到的次序号。定义Low(u)为u或u的子树中能通过非父子边追溯到的最早的顶点,即DFS序号最小的顶点。根据定义,则有:一个顶点u是割点,当且仅当满足以下条件:(1)u为树根,且u有多于一个子树。(2)u不为树根,且满足存在(u,v)为树枝边,使得DFS(u)≤Low(v)。一条无向边(u,v)是割边,当且仅当(u,v)为树枝边,且满足DFS(u)<Low(v)。3清晰显示算法3.1离开孤立点遍历全图,将图G中顶点度数为零的顶点从原图中分离出来,将这些孤立点删除,或者显示在一个独立的边缘区域,原图由G变为G′。3.2全面展开方向展开在左上坐标为(x1,y1)、右下坐标为(x2,y2)的矩形区域内将G′分离出连通分支。(1)遍历图G′,检查出G′的连通分支数n,每个连通分支记为G′i(i=0,…,n-1)。(2)将区域以横向展开方向,以该连通分支顶点数占全部顶点的比例将矩形区域划分为n份,如图1所示。设G′i所显示的区域为左上坐标为(x1,i,y1,i)、右下坐标为(x2,i,y2,i),则有:x1,0=x1x1,i=x1+1Νi-1∑k=0Νk(x2-x1)‚i=1,⋯,n-1x2,i=x1,i+1‚i=0,⋯,n-2x2,n-1=x2y1,i=y1,y2,i=y2‚i=0,⋯,n-1x1,0=x1x1,i=x1+1N∑k=0i−1Nk(x2−x1)‚i=1,⋯,n−1x2,i=x1,i+1‚i=0,⋯,n−2x2,n−1=x2y1,i=y1,y2,i=y2‚i=0,⋯,n−1其中,Nk为第k个连通分支的顶点数,N为G′的总顶点数。3.3trool稳定性检验对每个连通分支G′i基于树型结构显示。(1)遍历G′i,找出G′i中所有的割边。(2)根据割边可以构造出一棵树,记为G′i,T,该树中的每个顶点对应于G′i中的一个团,将该团记为G′i,j,如图2所示。(3)记G′i,j的显示区域为:左上坐标为(x1,i,j,y1,i,j),右下标为(x2,i,j,y2,i,j),将G′i以G′i,T结构分层显示。其中G′i,T中的每个顶点对应G′i中的一个团,将G′i,0对应树G′i,T中的根结点,该根结点记为Vi,Troot。(4)以Vi,Troot为根结点遍历G′i,T,检测出G′i,T的总层数以及每层包含的顶点数。(5)记第k层的左上坐标为(x1,i,αk,y1,i,αk),右下坐标为(x2,i,αk,y2,i,αk)。记Mi,k为G′i在第k层中的顶点数,则:x1,i,αk=x1,iy1,i,αk=y2,i,αk-1x2,i,αk=x2,iy2,i,αk=y1,i,αk+Μi,kΝi×(y2,i-y1,i)x1,i,αk=x1,iy1,i,αk=y2,i,αk−1x2,i,αk=x2,iy2,i,αk=y1,i,αk+Mi,kNi×(y2,i−y1,i)其中,y1,i,α0=y1,iy2,i,α0=y1,i,α0+Μi,0Νi×(y2,i-y1,i)y1,i,α0=y1,iy2,i,α0=y1,i,α0+Mi,0Ni×(y2,i−y1,i)(6)记第k层第l团的左上坐标为(x1,i,αk,βl,y1,i,αk,βl),右下坐标为(x2,i,αk,βl,y2,i,αk,βl),记Mi,k,l为第k层第l团的顶点数,则:x1,i,αk,βl=x2,i,αk,βl-1y1,i,αk,βl=y1,i,αk,βk-1x2,i,αk,βl=x1,i,αk,βl+Μi,k,lΜi,k×(x2,i,αk-x1,i,αk)y2,i,αk,βl=y2,i,αk,βl-1x1,i,αk,βl=x2,i,αk,βl−1y1,i,αk,βl=y1,i,αk,βk−1x2,i,αk,βl=x1,i,αk,βl+Mi,k,lMi,k×(x2,i,αk−x1,i,αk)y2,i,αk,βl=y2,i,αk,βl−1其中,x1,i,αk,β0=x1,i,αky1,i,αk,β0=y1,i,αkx2,i,αk,β0=x1,i,αk,β0+Μi,k,0Μi,k×(x2,i,αk-x1,i,αk)y2,i,αk,β0=y2,i,αk3.4求各起品种多且连接点值的估计,把vk作对于团G′i,j中每个属于割边所连接的顶点vk,设vk与团外的边连接数为C,其中与上层团的连接数为CU,与下层团的连接数为CD,根据CU和CD的大小关系分别做如下处理:(1)如果CU>CD,将vk定位在vk所在团显示区域的(x1,i,j+x2,i,j-x1,i,jn×m,y1,i,j+p)处,p≥0且是一个相对较小的值。其中,n为该团中同样具有CU>CD性质的割边连接点的个数,m为vk在这些割边连接点中的序号。(2)如果CU=CD,将vk定位在vk所在团显示区域的(x1,i,j+x2,i,j-x1,i,jn×m,y1,i,j+y2,i,j2)处。其中,n为该团中同样具有CU=CD性质的割边连接点的个数,m为vk在这些割边连接点中的序号。(3)如果CU<CD,将vk定位在vk所在团显示区域的(x1,i,j+x2,i,j-x1,i,jn×m,y2,i,j-p)处,p≥0且是一个相对较小的值。其中,n为该团中同样具有CU<CD性质的割边连接点的个数,m为vk在这些割边连接点中的序号。3.5连通分支内团分布(1)遍历该团G′i,j,找出该团中所有的割点,以割点为分界点,团G′i,j可以被划分为若干个子团G′i,j,k。(2)选取团G′i,j中与上层团有联系的一个顶点所在子团为根结点,子团与子团间存在虚连线,则团G′i,j可以映射为一根树G′i,j,T。其中,G′i,j,T中的一个顶点对应于G′i,j中的一个子团,如图3所示。(3)根据G′i,j,T,可以用处理连通分支内团的分布的方法来处理团内子团的分布。(4)在G′i,j中将虚线连接的顶点向虚线方向缩回到其归属的顶点。3.6区域的最大内径将子团内不在割边上的顶点均匀分布在所在子团显示区域的最大圆环上。由于子团间的连接点为割点,首先将割点定位在相邻子团的方向,其余点的定位按照均匀分布的原则分布在一个显示区域的内切圆周上。4实验结果分析用VC6.0编程实现视觉清晰化算法,实验结果表明,经过本算法后的无向关系图清晰度明显提高,尤其对具有稀疏关系性质的无向关系图效果更加明显。实验结果如图4～图7所示。图4显示了一个简单封闭回路关系(如图4a所示)在本文算法下的输出结果,如图4b所示,均匀美观,但文献算法的输出有时会出现凹形结