圖布局FR算法探究和實(shí)現(xiàn)

《圖布局FR算法探究和實(shí)現(xiàn)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫(kù)。

1、圖布局FR算法探究和實(shí)現(xiàn)摘要：近年來(lái)，對(duì)信息技術(shù)可視化的研究越來(lái)越廣泛，信息技術(shù)可視化也在各個(gè)領(lǐng)域中得到越來(lái)越廣泛的應(yīng)用。圖布局是用圖結(jié)構(gòu)解決現(xiàn)實(shí)世界中信息可視化問(wèn)題的一種重要技術(shù)。該文介紹圖布局FR算法的基本模型，研究FR算法實(shí)現(xiàn)方法，及FR算法的優(yōu)化。關(guān)鍵詞：圖布局；FR算法中圖分類號(hào)：TP391文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2013)12-2864-021概述近年來(lái)對(duì)信息技術(shù)可視化的研究越來(lái)越廣泛，信息技術(shù)可視化也在各個(gè)領(lǐng)域中得到越來(lái)越廣泛的應(yīng)用。信息可視化充分利用了人類視覺感知系統(tǒng)，將信息以圖形化方式進(jìn)行展示，直觀快速地解釋信息的意義。繪圖

2、技術(shù)是信息可視化與應(yīng)用數(shù)學(xué)的一個(gè)交叉領(lǐng)域，主要研究從圖到幾何空間的映射關(guān)系。繪圖技術(shù)的內(nèi)容極其豐富，主要是根據(jù)不同的實(shí)際應(yīng)用需求，滿足繪圖的基本要求。從圖布局的觀點(diǎn)來(lái)看，在圖的繪制中，主要解決的是圖中節(jié)點(diǎn)的布局問(wèn)題。2FR算法的基本模型1984年,Eades首次提出了用彈力模型實(shí)現(xiàn)圖布局算法。彈力模型即力學(xué)中常用的虎克定律：在彈性限度內(nèi)，物體的形變跟引起形變的外力成正比。Eades將圖中的邊看成力學(xué)中的彈簧，利用彈力關(guān)系決定圖點(diǎn)的布局。彈簧模型提出后，許多學(xué)者在此基礎(chǔ)上進(jìn)行了深入的研究。最典型的算法有Fruchtennan和Reingold提出的FR算法。FR算

3、法在經(jīng)典彈簧算法的基礎(chǔ)上進(jìn)行了改進(jìn)，引入了力導(dǎo)引模型。力導(dǎo)引模型建立在粒子物理理論的基礎(chǔ)上，將無(wú)向圖中的節(jié)點(diǎn)模擬成原子，通過(guò)模擬原子間的力場(chǎng)來(lái)計(jì)算節(jié)點(diǎn)間的位置關(guān)系。算法通過(guò)考慮原子間引力和斥力的互相作用，經(jīng)過(guò)不斷的迭代計(jì)算，系統(tǒng)最終進(jìn)入一種動(dòng)態(tài)平衡狀態(tài)。FR算法也沒有太嚴(yán)格地遵照物理規(guī)則來(lái)進(jìn)行模擬，而是進(jìn)行了一些簡(jiǎn)化。FR算法在所有的實(shí)體之間計(jì)算排斥力,而吸引力只在相互連接的實(shí)體之間進(jìn)行計(jì)算。FR算法的每次迭代主要分為三個(gè)部分:首先是計(jì)算節(jié)點(diǎn)之間相互的排斥力，然后是計(jì)算圖中有邊連接的節(jié)點(diǎn)之間相互的吸引力，最后綜合吸引力和排斥力，并通過(guò)最大位移來(lái)限制移動(dòng)的距離。對(duì)

4、于一個(gè)高度為H,寬度為W的顯示區(qū)域，其中任意節(jié)點(diǎn)V有兩個(gè)布局參數(shù)（分量）：節(jié)點(diǎn)的位置pos和所受合力產(chǎn)生的位置偏移量diSPoFR的基本定義如下：顯示區(qū)域：［area=WXH］其中：［W］和［H］是顯不區(qū)域的寬和高；平衡距離：FR算法的偽代碼如下：for(i=1；i其中：p(E)指出狀態(tài)E的能量值的概率分布，作為溫度T和Boltzmann常數(shù)k的函數(shù)。一方面，對(duì)每一個(gè)溫度，各個(gè)能量E有非零的概率，因此，系統(tǒng)能以較高的溫度改變它的狀態(tài)。另一方面，在降低溫度時(shí)，系統(tǒng)趨向于非常低的能量狀態(tài)，當(dāng)全局能量最小時(shí)，達(dá)到溫度零。在本算法中，采用了線性算法。首先設(shè)置一個(gè)初始溫度

5、,即節(jié)點(diǎn)允許的最大位移量。如果初始溫度足夠高，節(jié)點(diǎn)可以任意地移動(dòng)。因此，將節(jié)點(diǎn)初始最大位移量設(shè)置為繪圖矩形區(qū)域長(zhǎng)邊的1/2,其后是溫度減少的過(guò)程，典型的是一個(gè)多項(xiàng)式算法。本文使用線性數(shù)，溫度下降過(guò)程的表達(dá)式為：，［V］稱為冷卻系數(shù)，在0.6到0.95之間，一般使用用］Y=0.8］o按照式上述公式，模擬退火算法的迭代次數(shù)由初始溫度、冷卻系數(shù)、迭代終止下界決定。初始溫度T0一般設(shè)置為顯示區(qū)域邊長(zhǎng)的1/2,每次迭代后，溫度T的值乘以冷卻系數(shù)，因冷卻系數(shù)小于1,溫度T的值遞減，直至溫度Tn到達(dá)迭代終止下界。迭代終止下界是一個(gè)很小的值，即節(jié)點(diǎn)的最小位移量。我們用FR算法對(duì)

6、100個(gè)節(jié)點(diǎn)的圖進(jìn)行了布局計(jì)算。迭代300次后的執(zhí)行效果見圖（b）?？梢钥吹?，布局效果并不太好。模擬退火算法的迭代次數(shù)由初始溫度、冷卻系數(shù)和迭代終止下界決定。在計(jì)算中，初始溫度T0設(shè)置為顯示區(qū)域邊長(zhǎng)的1/2,冷卻系數(shù)為0.9,迭代終止下界為1。因此迭代了315次。顯然比前面不用模擬退火算法循環(huán)300次的效果要好了許多。由運(yùn)行測(cè)試與分析，模擬退火算法在FR算法中起著比較重要的作用，它能有效地防止節(jié)點(diǎn)位移的振蕩，因此，在按循環(huán)次數(shù)迭代時(shí)，也引入了模擬退火算法來(lái)限制節(jié)點(diǎn)位移的最大偏移量，按循環(huán)次數(shù)使節(jié)點(diǎn)位移最大偏移量遞減。4結(jié)束語(yǔ)本文主要研究圖的布局算法與實(shí)現(xiàn)方法。闡

7、述了FR算法的原理，給出了算法的偽代碼。并應(yīng)用模擬退火算法對(duì)FR算法進(jìn)行優(yōu)化，分析及其執(zhí)行效果，為后繼數(shù)據(jù)分析工作建立一個(gè)堅(jiān)實(shí)的基礎(chǔ)。