权长相合的带权无向图画图算法  

Weight-length consistent graph drawing algorithm for weighted undirected graphs

作　　者：张伟[1] 曾瑞弼[1] 胡明晓[1] 

机构地区：[1]温州大学物理与电子信息工程学院,浙江温州325035

出　　处：《计算机应用》2012年第4期1116-1118,1121,共4页journal of Computer Applications

基　　金：温州市科技局科技计划项目(H20090049);浙江省大学生科技创新活动计划项目(2011R424011)

摘　　要：针对带权无向图的输出需用边长反映权值大小的问题,提出了一种基于遗传算法的带权无向图画图算法,通过对顶点坐标的编码进行交叉和变异来得到理想的节点坐标,变异算子结合了非一致性变异和单点邻域变异,并在适应度函数中运用顶点平均距离、边交叉数、多度顶点相关边夹角均匀度、边的权值长度比一致程度四个美学标准。实验结果表明,该算法画出的图形连线无交叉,分支清晰,权值—长度相合,能得到清晰、美观且能直观反映权值的可视化输出结果,可应用于带权无向图的可视化输出系统的设计。Concerning the problem that the weighted undirected graph＇s output is needed to demonstrate weights with edge lengths,a new algorithm for weighted undirected graphs based on genetic algorithm was proposed.The algorithm obtained the ideal vertex coordinates by the crossover and mutation on the vertex coordinate coding.The mutation operator combined the inconsistent mutation with single neighbourhood mutation.In the fitness function,four evaluation criteria were employed： the average distance of the vertex,the edge crossing number,the uniformity of the angles around the multi-degree vertex,and the uniformity of the ratios of edge weight and edge length.The experimental results show that the drawn graph by the proposed algorithm is featured with edge-crossing-free,clear showing of branches and weight-length consistency.The visual output results of the algorithm are clear,visually optimized and especially faithful to weights.The algorithm is suitable to draw most kinds of weighted undirected graphs and can be used in undirected graph drawing methods and/or prototypes.

关 键 词：带权图 无向图 遗传算法 画图 权长相合 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]