ѧ
Journal of Software
2000 Vol.11 No.1 P.138-142



һµͼͼ㷨
ƾΰɽع
ժҪһͼĻͼתΪŻ,Ŵ㷨Ŀ꺯ŽĽֵ,ӶõͼԶͼ㷨һһ.·ص:ͬĻͼ㷨Ŀܶһ,ֻͬǷӳͼͼ۱׼Ŀ꺯.ŵ,㷨ͳһ򵥡ʵ֡޸,ڲл,ֱͨͼ.
ؼʡͼ,ͼ,׼,㷨,Ŵ㷨.
ͼšTP301
A New Graph Drawing Algorithm for Undirected Graphs
HUANG Jing-weiKANG Li-shanCHEN Yu-ping
(State Key Laboratory of Software EngineeringWuhan UniversityWuhan430072)
AbstractIn this paper, the authors transform the problem of undirected graph drawing to the problem of function optimization, then use genetic algorithms to find approximate optimal solutions of the objective function, and thus obtain a general structure of undirected graph drawing algorithms. The characters of the new method are: the structures of the different graph drawing algorithms are the same, the difference exists only in the objective functions which reflect aesthetic criteria. The advantages of the method are: unified algorithms, simplicity, easy modification and parallelism, and it can be used to draw non-connected graphs directly.
Key wordsUndirected graph, graph drawing, aesthetic criteria, algorithm, genetic algorithm.
ͼһӦ÷ǳ㷺ݽṹ,ʾָӵϵͳģ,жʾϵͳеԪ,߱ʾԪ֮Ĺϵ.ͼ롢۵ػ,ͷģͶʮҪ.ͨ,ʾϵͳģ͵ͼĶͱ൱,˹ͼ롢۵ػǲܵ,üԶؽͼ롢۵ػΪһʮҪĿ.֮,ͼ(graph drawing)ڵ·ߡ̡ͼѧӻѧжڶӦ.,ͼܵԽԽĹע,γ˼ѧеһµо.
1992,Ѿٰ߽(ÿһ)ͼѧֻ.ף1һƪйػͼ.ͨ,Ըֲͬ͵ͼвͬĻͼ㷨,Ʃлƽͼͼͼ㷨.ÿһͼ,ָͼԺ׼Ĳͬ,вͬ㷨.ͼͼ㷨,ʹõķеģͷ2ݺforce-directed method3.,Ҳ˿ʼӦŴ㷨оͼͼ㷨4.ڱ,оŴ㷨һͼĻͼ.һͼͼ㷨ټ.ף2,T.KamadaS.KawaiһͨͼһΪֻΪɵĶ̬ϵͳ,ͼһ𲽼ϵͳĹ.ף3,T.M.J.FruchtermanE.M.Reingoldһͨͼһѧϵͳ,㷨ĿҪʹѧϵͳﵽƽ.ǰо,ͬͼͼ㷨вͬ㷨,õ֪ʶҲͬ,һӦõĲͬѧ۵Ĳͬ,ʱҪ׼޸ӦͬҪ,ǰĻͼ㷨׼Ƕ㷨֮,޸,Ҫһ޸ĵĻͼ㷨ӦͬҪ.ڱ,ǽһͼĻͼ⿴һŻ,ȻŴ㷨5Ŀ꺯ŽĽֵ,ӶõͼԶͼ㷨һһ.ͬĻͼ㷨㷨ܶһ,ֻͬǷӳͼͼѧ׼Ŀ꺯.ŵ,㷨ͳһ򵥡޸Ĳڲʵ.ǰͼͼ㷨ͨͼ,ڻͨͼ,÷ֱÿһ֧ͨ,Ȼ󽫲֧ͬͨƴķ,ǵ㷨ֱͨͼ.
1ͼ
һͼG=(V,E)һߵļ϶,VΪļ,EΪߵļ.ͼGһֻǽGÿvVӳ䵽ƽϵһP(v),Gÿ(u,v)ӳƽϵһ˵ֱΪP(u)P(v)ļԼ.Gÿ߶ӳһֱ߶,ǳƻһֱ߻.Gÿ߶ӳһ,ƻһ߻.Gÿ߶ӳһƽСֱ߶,ƻһ.Gߵӳ񶼲ཻ,ƻһƽ滭.
ڱ,оͼֱ߻,,ͼ㷨Ŀǽͼĳ(Ʃ),㷨Ҫһ׼,ͼеÿһvָһ(x(v),y(v)),һÿ㶼ָһ,ͼһ׵,ֻбĶ֮仭һֱ߶μ.ڻһͼ,Ӧú͹۵Ĳͬ,вͬ׼.ձ׼
(1) ܽȵطֲ;
(2) ܱߵĽ;
(3) ʹ߳һ;
(4) ӳͼڶԳ.
ǵ㷨,ֻ׼(1)(3)õԵ,㷨ĽҲ׼(4).ע⵽,׼(3)Щ²Ǳ.ͼ,ֻ,ͼ1ͼ2ʾ.Ȼͼ1еĻûбߵĽ,ͼ2ͼ1ҪһЩ.

Fig.1Drawing without crossing edges
ͼ1޽ߵĻ

Fig.2Drawing with crossing edges
ͼ2нߵĻ
2ͼͼŴ㷨
Ŵ㷨ǽչѸٵһ㷨,һҪӦǺŻ.Ŵ㷨⻭ͼķǽͼתΪŻ,Ŀ꺯,ʹܹ֮ӳͼͼ۱׼Ŵ㷨⻭ͼĹؼ.,Ŀ꺯.
Ŀ꺯ƻ۲:
(1) κ㲻Ӧ̫,
(2) бĶӦ໥.
ĺΪĿ꺯.
(1)
PiΪViƽϵӳ,|pi-pj|ʾpipj֮ľ,Ϊ߳,nΪͼGĶ,SΪ,kΪʵõĲ.(1),ʹʽ(1)еĵ1ʽ;(2),ʹʽ(1)еĵ2ʽ,ͼתΪʽ(1)Сֵ.
x(v),y(v)ֱʾvƽϵӳP(v)xy,Ϊϣͼaxb,cyd,ǵĿ´ԼĿ꺯Сֵ.
(2)
ax(vi)b,cy(vi)d,i=1,2,...,n.
Ŵ㷨ʽ(2)˼:óΪȾɫһּݽṹʽ(2)ܵĽ(x1,y1),(x2,y2),...,(xn,yn)б,ȻһŴһıȺ,ȾɫȺ,ʹܹһЩؼϢ,ͨݻ,õʽ(2)СֵСֵ.
һŴ㷨Ļɱ롢ӦȺƶѡԡѡƲŴԼֹ׼6.ֱ6.
(1) 
봫ͳŴ㷨ͬ,ʽ(2)ÿܵĽ(x1,y1),(x2,y2),...,(xn,yn),һΪ2nʵ(x1,y1,x2,y2,...,xn,yn)ʾ,һҪôǿԱ,㷨ʱ.
(2) ӦȺ
ΪСֵ,ǿѡһCmaxf(x1,y1,x2,y2,...,xn,yn),ֱӴf(x1,y1,x2,y2,...,xn,yn)ӦȺF(x1,y1,x2,y2,...,xn,yn)=Cmax-f(x1,y1,x2,y2,...,xn,yn).
(3) ѡ
Ϊ˷ֹ췢,Sigma任ԸӦֵб任,ԸiӦֵf(i),ùʽ

f(i)任ExpVal(i),f(t)ΪtȺƽӦֵ,(t)ʾtȺı׼.ȻExpVal(i)ӦûӦֵѡ,ӦֵߵȾɫ.
(4) Ʋ
ǵ㷨,ȡN=20,Pc=0.75,Pm=0.015.ǷֱʾȺĴСӽ.ݻTһΪͼĶĺ,ʵӦпɸͼĶĴСȡֵͬ.
(5) Ŵ
ӽ,ǲõӽ,ѡΪ
A=a1,a2,...,a2n),B=b1,b2,...,b2n),
ѡӽλΪ3,õ¸ֱΪ
A=(a1,a2,a3,b4,...,b2n);B=(b1,b2,b3,a4,...,a2n).
ڱ,ǲµķһ±ӣ踸ΪA=a1,a2,...,ak,...,a2n),kѡб.kΪy,ȡֵΧΪc,d,õ¸Ϊ
A=a1,a2,...,ak,...,a2n),


,Random(2)01һ,(t,y)=y.(1-r(1-t/T)5),rΪ0,1֮һ,tΪǰݻ,TΪݻ.Ȼ,(t,y)ֵΪ0,y,ҵtTʱ,(t,y)0.,ݻ,ڽϴķΧ;ݻ,һ־ֲ΢.
(6) ֹ׼
㷨ɴֹ㷨.Ŵ㷨ͼͨûͼ㷨:


Draw_Graph(G,X,Y)̻xΪX=(x1,x2,...,xn),yΪY=(y1,y2,...,yn)ͼG.
3ʵ
Delphiʵ㷨.һЩͼĻ,ǵõף3ƵĽ.һЩϸӵͼ,ף3е㷨ͼĳЩʼ״ֲ̬СĽֵ,õϲĻ.ǵ㷨ȶԽϺ,ʵ,սͼĳʼ״̬.ǵ㷨ͨͼ,Ҳֱͨͼ,ֻ轫֧ͬͨͬм.ͼ3ǵ㷨ͼ.

Fig.3Experiment results
ͼ3ʵ
4
Ŵ㷨⻭ͼ.Ŵ㷨Ļ,ǵõһͨͼͼ㷨,ͬͼͼ㷨Ŀܶһ,ֻͬƵķӳͼͼѧ׼Ŀ꺯.,㷨ף2еĿ꺯,ɵõף2ƵĽ.ڻŴ㷨ͨͼͼ㷨ܵĻ,ͼͼ㷨ҪƳܹӳ۱׼Ŀ꺯.ݲͬӦԼͬ۱׼,ԶҪĿ꺯ǽһоķ.
оõȻѧ(No.69635030)863ƼĿ(863-306-ZT06-06-3)ͺʡƼĿ(No.98P0119).
ƾΰ(人ѧ̹صʵҡ人430072)
ɽ(人ѧ̹صʵҡ人430072)
ع(人ѧ̹صʵҡ人430072)
E-mail: jwhuang@public.wh.hb.cn
ο
1Battista G D, Eades P, Tamassia R et al. Algorithms for drawing graphs: an annotated bibliography. Computational Geometry: Theory and Applications, 1994,4(5):235282
2Kamada T, Kawai S. An algorithm for drawing general undirected graph. Information Letters, 1989,31(1):715
3Fruchterman T M J , Reingold E M. Graph drawing by force-directed placement. Software-Practice and Experience, 1991,21(11):11291164
4Kosak C, Marks J, Shieber S. Automating the layout of network diagrams with specified visual organization. IEEE Transactions on System, Man and Cybernetics, 1994,24(3):440454
5Michalewicz Z. Genetic Algorithms+Data Structures=Evolution Programs. 3rd edition, New York: Springer-Verlag, 1996
1998-09-25ո
1999-01-22޸
