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

《权长相合的带权无向图画图算法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、权长相合的带权无向图画图算法摘要:针对带权无向图的输出需用边长反映权值大小的问题，提出了一种基于遗传算法的带权无向图画图算法，通过对顶点坐标的编码进行交叉和变异来得到理想的节点坐标，变异算子结合了非一致性变异和单点邻域变异，并在适应度函数中运用顶点平均距离、边交叉数、多度顶点相关边夹角均匀度、边的权值长度比一致程度四个美学标准。实验结果表明，该算法画出的图形连线无交叉,分支清晰，权值—长度相合，能得到清晰、美观且能直观反映权值的可视化输出结果，可应用于带权无向图的可视化输出系统的设计。关键词:带权图；无向图；遗传

2、算法；画图；权长相合weight.lengthconsistentgraphdrawingalgorithmforweightedundirectedgraphszhangwei,zengrui.bi,huming.xiao*collegeofphysicsandelectronicinformationengineering,wenzhouuniversity,wenzhouzhejiang325035,chinaabstract:asfortheproblemthatweightedundirecte

3、dgraph’soutputisnecessarytodemonstrateweightswithedgelengths,anewalgorithmforweightedundirectedgraphsbasedongeneticalgorithmisproposed.thealgorithmobtainstheidealvertexcoordinatesbythecrossoverandmutationonthevertexcoordinatecodings.themutationoperatorcombine

4、stheinconsistentmutationwithsingleneighbourhoodmutation.inthefitnessfunction,fourevaluationcriteriaareemployed:theaveragedistanceofthevertex,theedgecrossingnumber,theuniformityoftheanglesaroundthemulti-degreevertex,andtheuniformityoftheratiosofedgeweightanded

5、gelength.theexperimentresultsshowthatthedrawngraphbytheproposedalgorithmisfeatheredwithedge-crossing-free,clearshowingofbranchesandweight-lengthconsistency.thevisualoutputresultsofthealgorithmareclear,visualoptimizedandespeciallyfaithfultoweights.thealgorithm

6、issuitabletodrawmostkindsofweightedundirectedgraphsandcanbeusedinundirectedgraphdrawingmethodsand/ordevices.concerningtheproblemthattheweightedundirectedgraphsoutputisneededtodemonstrateweightswithedgelengths,anewalgorithmforweightedundirectedgraphsbasedonge

7、neticalgorithmwasproposed.thealgorithmobtainedtheidealvertexcoordinatesbythecrossoverandmutationonthevertexcoordinatecoding.themutationoperatorcombinedtheinconsistentmutationwithsingleneighbourhoodmutation.inthefitnessfunction,fourevaluationcriteriawereemploy

8、ed:theaveragedistanceofthevertex,theedgecrossingnumber,theuniformityoftheanglesaroundthemulti.degreevertex,andtheuniformityoftheratiosofedgeweightandedgelength.theexperimentalresultsshowt