[权长相合的带权无向图画图算法] dijkstra算法过程图解

　　摘要:针对带权无向图的输出需用边长反映权值大小的问题，提出了一种基于遗传算法的带权无向图画图算法，通过对顶点坐标的编码进行交叉和变异来得到理想的节点坐标，变异算子结合了非一致性变异和单点邻域变异，并在适应度函数中运用顶点平均距离、边交叉数、多度顶点相关边夹角均匀度、边的权值长度比一致程度四个美学标准。实验结果表明，该算法画出的图形连线无交叉,分支清晰，权值―长度相合，能得到清晰、美观且能直观反映权值的可视化输出结果，可应用于带权无向图的可视化输出系统的设计。
　　
　　关键词:带权图；无向图；遗传算法；画图；权长相合
　　中图分类号: TP391.41文献标志码:A
　　�
　　Weight.length consistent graph drawing algorithm for weighted undirected graphs
　　
　　�
　　ZHANG Wei, ZENG Rui.bi, HU Ming.xiao��*
　　College of Physics and Electronic Information Engineering,Wenzhou University, Wenzhou Zhejiang 325035, China
　　
　　Abstract:
　　As for the problem that weighted undirected graph’s output is necessary to demonstrate weights with edge lengths, a new algorithm for weighted undirected graphs based on genetic algorithm is proposed. The algorithm obtains the ideal vertex coordinates by the crossover and mutation on the vertex coordinate codings. The mutation operator combines the inconsistent mutation with single neighbourhood mutation. In the fitness function, four evaluation criteria are 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 experiment results show that the drawn graph by the proposed algorithm is feathered with edge-crossing-free, clear showing of branches and weight-length consistency. The visual output results of the algorithm are clear, visual 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 devices.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.
　　
　　�Key words:
　　weighted graph; undirected graph; genetic algorithm; graph drawing; weight.length consistency
　　
　　�
　　0 引言�
　　无向图是描述对象之间逻辑关系的抽象表示，是图论的基本研究对象。无向图经常需要在二维平面上作可视化输出，图的可视化输出在组织关系图、模块关系图、抄袭圈图示、网络分析等需要逻辑定位的应用领域有着广泛的应用。如果用连接两个顶点的直线段表示边，则图的输出效果完全取决于顶点的位置。如何确定顶点的位置，使图输出的视觉效果最佳，即所谓优化画图问题。关于带权图的可视化输出，除了逻辑关系的清晰展示之外，还要反映出逻辑关系的强弱，关系强的节点距离近，关系弱的节点距离远，边的权值（或其倒数）与边长之比尽量保持一个固定的比值，即要求权长相合。�
　　对于无向图已有不少文献报道其画图算法�［1］，譬如基于弹性模型的算法�［2］、力导引方法�［3］、基于连通分支与割边识别的方法�［4］、基于遗传算法的方法�［5-7］，以及发明专利�［8-9］，其中遗传算法的方法通过顶点编码和评价函数的设计实现了无向图的顶点优化定位，但只针对不带权的无向图。文献［8］提出将顶点做类似聚类分析的方法，解决了现有无向关系图分割方法中存在的不能够保证图形的自连通性问题，但是没有涉及具体的顶点定位。文献［9］的方法克服了顶点重叠问题，然而，它不适用于带有环的无向图，也没考虑权值。�
　　本文介绍一种带权无向图画图算法，它采用遗传算法进行顶点坐标的优化。算法目标是使带权无向图的输出连线清晰、分支清晰、分布均匀，而且权长相合。�
　　
　　1 算法描述�
　　1.1 带权无向图的清晰度准则�
　　清晰程度是人视觉感官上看图的一种体会，如易辨、匀称、平衡，其准确值无法用一个统一的解析表达式度量。一个清晰度上优化的画图显示算法是在如此无定论的标准之上设计的画图算法，即使有一个清晰度准则的客观标准，但由于解空间的自由度是�2|V|（V�为顶点集），搜索空间巨大，画图算法也难以解析地表达。故本文以下列准则为带权无向图的清晰度准则。�
　　
　　1）顶点间的平均距离大，充满画图区域。�
　　2）边的交叉数少，最好消除交叉。�
　　3）多度顶点的各相关边的夹角均匀。�
　　4）权长相合度高（边的权值或其倒数与长度的比值一致程度高）。�
　　
　　1.2 遗传算法�
　　遗传算法（Genetic Algorithm，GA）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法的基本要素包括：初始化、个体评价、选择运算、交叉运算、变异运算、终止条件判断等，其中评价函数（亦称适应度函数）的设计是影响算法效果的重要因素，本文的评价函数是清晰度准则的体现。�

推荐访问:相合 图画 算法 带权无