| 权长相合的带权无向图画图算法 |
| |
| 引用本文： | 张伟,曾瑞弼,胡明晓. 权长相合的带权无向图画图算法[J]. 计算机应用, 2012, 32(4): 1116-1118. DOI: 10.3724/SP.J.1087.2012.01116 |
| |
| 作者姓名： | 张伟 曾瑞弼 胡明晓 |
| |
| 作者单位： | 温州大学 物理与电子信息工程学院，浙江 温州 325035 |
| |
| 基金项目： | 温州市科技局科技计划项目(H20090049);浙江省大学生科技创新活动计划项目(2011R424011) |
| |
| 摘 要： | 针对带权无向图的输出需用边长反映权值大小的问题，提出了一种基于遗传算法的带权无向图画图算法，通过对顶点坐标的编码进行交叉和变异来得到理想的节点坐标，变异算子结合了非一致性变异和单点邻域变异，并在适应度函数中运用顶点平均距离、边交叉数、多度顶点相关边夹角均匀度、边的权值长度比一致程度四个美学标准。实验结果表明，该算法画出的图形连线无交叉,分支清晰，权值—长度相合，能得到清晰、美观且能直观反映权值的可视化输出结果，可应用于带权无向图的可视化输出系统的设计。
|
| 关 键 词： | 带权图 无向图 遗传算法 画图 权长相合 |
| 收稿时间： | 2011-09-09 |
| 修稿时间： | 2011-11-15 |
Weight-length consistent graph drawing algorithm for weighted undirected graphs |
| |
| ZHANG Wei,ZENG Rui-bi,HU Ming-xiao. Weight-length consistent graph drawing algorithm for weighted undirected graphs[J]. Journal of Computer Applications, 2012, 32(4): 1116-1118. DOI: 10.3724/SP.J.1087.2012.01116 |
| |
| Authors: | ZHANG Wei ZENG Rui-bi HU Ming-xiao |
| |
| Affiliation: | College of Physics and Electronic Information Engineering,Wenzhou University, Wenzhou Zhejiang 325035, China |
| |
| Abstract: | 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. |
| |
| Keywords: | weighted graph undirected graph genetic algorithm graph drawing weight-length consistency |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《计算机应用》浏览原始摘要信息 |
|
点击此处可从《计算机应用》下载全文 |
