一種交叉數(shù)減少的布圖方法

一種交叉數(shù)減少的布圖方法

0布圖可視化的運(yùn)用應(yīng)符合傳統(tǒng)美學(xué)標(biāo)準(zhǔn)隨著軟件規(guī)模的增加和體系結(jié)構(gòu)的復(fù)雜性，程序代碼的分析、測試和維護(hù)變得困難。作為一門跨學(xué)科的學(xué)科，軟件可視化已成為研究的熱點(diǎn)。根據(jù)不同的要求，許多基于布圖算法的軟件可視化工具已經(jīng)生產(chǎn)。軟件可視化可以抽象為層次布圖問題，許多問題是財(cái)務(wù)問題，因此很多可視化工具“忽略了別人”。鑒于上述情況,權(quán)衡布圖中存在的問題約束,協(xié)調(diào)問題之間的沖突,保證層次布圖符合傳統(tǒng)美學(xué)標(biāo)準(zhǔn),從而確保軟件可視化的效果是關(guān)鍵。本文分析當(dāng)前流行的層次布圖模型,融合多種算法,達(dá)到了互補(bǔ)優(yōu)化的效果,并借鑒重心啟發(fā)算法進(jìn)行相應(yīng)改進(jìn),提出了繼承次序與相關(guān)度算法。1布圖算法的繼承層次布圖使用最廣的是Sugiyama算法,其他諸多布圖算法多是在其基礎(chǔ)上進(jìn)行某些方面的改進(jìn),本文布圖算法繼承了Sugiyama算法模式,基本流程如圖1所示。此框架流程在布線時(shí)提出了添加虛擬節(jié)點(diǎn)與通道路由布線兩種選擇,重點(diǎn)是交叉最小化方面的探索性改進(jìn)。2構(gòu)建“東南角”、集中和多元的“東南角”節(jié)點(diǎn)模型布局是由給定的節(jié)點(diǎn)信息及節(jié)點(diǎn)間依賴關(guān)系,生成結(jié)構(gòu)清晰、美觀的“半成品層次圖”,包括兩個(gè)步驟:1)節(jié)點(diǎn)分層,確定映射參數(shù)f;2)層內(nèi)順序調(diào)整,為減少層次圖連線交叉度Crossing(H)。2.1節(jié)點(diǎn)安裝及調(diào)度定義1層次圖H=(V,E,n,f),其中V是節(jié)點(diǎn)集,E是邊集,n是層次圖層數(shù),記為L1…Ln,f是節(jié)點(diǎn)到層次的映射,若f(v)=k(1≤k≤n),則節(jié)點(diǎn)v在第k層。借鑒“最長路徑分層算法”,通過尋找節(jié)點(diǎn)v到根節(jié)點(diǎn)最長路徑來確定其所在層,若節(jié)點(diǎn)沒有直接前趨節(jié)點(diǎn),將其放在最上層,其余節(jié)點(diǎn)放在其最大層次直接前趨節(jié)點(diǎn)所在層的下一層。這樣可保證布線時(shí)依賴關(guān)系箭頭盡可能指向同一方向。1)初始化:布圖節(jié)點(diǎn)置于集合V,依賴關(guān)系置于集合E;2)第一層節(jié)點(diǎn)布置:由E中依賴關(guān)系,找出其中沒有直接前趨的節(jié)點(diǎn)(根節(jié)點(diǎn)或非聯(lián)通節(jié)點(diǎn))布置在第一層,并從V中刪除這些節(jié)點(diǎn);3)“非閉環(huán)”且“非第一層”上節(jié)點(diǎn)布置:遍歷E,尋找上一層已布置節(jié)點(diǎn)的直接后繼集,置于該層,隨后進(jìn)行兩個(gè)循環(huán)判斷:①依據(jù)調(diào)用關(guān)系判斷該層內(nèi)節(jié)點(diǎn)之間有無調(diào)用關(guān)系,若有,將被調(diào)用節(jié)點(diǎn)放入集合P中,在布置該層下一層時(shí),優(yōu)先考慮P中節(jié)點(diǎn),這樣可保證調(diào)用者與被調(diào)用者在相鄰層,否則執(zhí)行第二個(gè)判斷;②在E中搜索是否存在剩余節(jié)點(diǎn)調(diào)用了該層中節(jié)點(diǎn),若存在,將被調(diào)用節(jié)點(diǎn)從該層中刪除,放回到V中,若不存在,從V中刪除該層中已布置節(jié)點(diǎn);4)按步驟1)～3)將V中節(jié)點(diǎn)進(jìn)行層次指定后,若還有節(jié)點(diǎn)未指定層次,則這些節(jié)點(diǎn)在閉環(huán)上,閉環(huán)節(jié)點(diǎn)按步驟5)處理;5)搜索E中閉環(huán)節(jié)點(diǎn)依賴關(guān)系,在已布置圖各層上尋找閉環(huán)節(jié)點(diǎn)的直接后繼節(jié)點(diǎn),若搜索到,將該閉環(huán)上節(jié)點(diǎn)置于其最小層次直接后繼節(jié)點(diǎn)的上一層,否則置于調(diào)用它的閉環(huán)節(jié)點(diǎn)的下一層。2.2重心啟發(fā)算法層次圖布局中,節(jié)點(diǎn)交叉最小化是重點(diǎn)問題,交叉度越小層次布圖越清晰,從而由一個(gè)節(jié)點(diǎn)出發(fā)找到與其相關(guān)的節(jié)點(diǎn)也更容易,但其又是NP完全問題,即便是兩層稀疏圖,其解決方法的基本思想是將n層次圖轉(zhuǎn)化為n-1個(gè)兩層圖來處理,固定i層(1≤i≤n)節(jié)點(diǎn)次序,調(diào)整i±1層上節(jié)點(diǎn)次序,再按照自頂向下或自底向上逐層清理,以期達(dá)到最佳交叉最小化效果,針對兩層圖交叉最小化問題,出現(xiàn)了分支切割啟發(fā)算法、中值啟發(fā)算法、貪婪交換啟發(fā)算法、排列啟發(fā)算法等。排序啟發(fā)算法效果最佳,但其是以O(shè)(N!)時(shí)間復(fù)雜度為代價(jià)(N是層次圖節(jié)點(diǎn)數(shù)),最常用的是重心啟發(fā)算法,其基本思想是根據(jù)節(jié)點(diǎn)相關(guān)聯(lián)的邊在鄰層中的平均順序值重排節(jié)點(diǎn),形式化為:bc(v)=?????????????????????????∑w∈Vi+1πi+1(w)|Vi+1|,∑w∈Vi?1πi?1(w)+∑w∈Vi+1πi+1(w)|Vi?1∪Vi+1|,∑w∈Vi?1πi?1(w)|Vi?1|,i=11<i<ni=n(1)bc(v)是節(jié)點(diǎn)v的重心次序;w是節(jié)點(diǎn)v的鄰層關(guān)聯(lián)節(jié)點(diǎn);πi(w)表示節(jié)點(diǎn)w在i層中排列次序;︱Vi︱是i層節(jié)點(diǎn)總數(shù)。定義2相關(guān)度是節(jié)點(diǎn)v的扇入、扇出系數(shù)之和,記作Div(v)。重心啟發(fā)算法是一種基于繼承鄰層關(guān)聯(lián)節(jié)點(diǎn)次序的算法,即節(jié)點(diǎn)v的鄰層關(guān)聯(lián)節(jié)點(diǎn)在其層內(nèi)處于一種什么樣的排序狀態(tài),那么節(jié)點(diǎn)v就相應(yīng)地“繼承”它們的排序狀態(tài),處于相似的一種排序狀態(tài)。這是一種簡單實(shí)用的算法,但沒有考慮節(jié)點(diǎn)v的相關(guān)度,假設(shè)將Div(v)值最大的節(jié)點(diǎn)置于中間位置,其余節(jié)點(diǎn)分別置于兩側(cè),則可減少交叉數(shù)。鑒于重心啟發(fā)算法的優(yōu)缺點(diǎn),本文提出一種交叉最小化啟發(fā)方法,即繼承次序與相關(guān)度算法,形式化為:Node_Sequence(v)是節(jié)點(diǎn)v在層內(nèi)的排列次序,bc(v)是其重心次序,a是層內(nèi)節(jié)點(diǎn)個(gè)數(shù),b為層內(nèi)節(jié)點(diǎn)按Div(v)的排列次序。從表達(dá)式兩個(gè)參數(shù)入手,對“繼承次序與相關(guān)度”算法進(jìn)行說明。1)重心次序參數(shù):重心啟發(fā)算法作為經(jīng)典交叉最小化算法,具有良好的輸出結(jié)果和線型時(shí)間復(fù)雜度O(nlogn)。2)相關(guān)度參數(shù):將節(jié)點(diǎn)相關(guān)度作為一個(gè)重要算子的原因是吸取了廣義張量平衡算法的思想,其中(a+1)/2是某層的“中間位置”,(-1)b·(a-b)是由div(v)來確定兩側(cè)位置的“位移參量”。3)將兩參數(shù)相加,并非簡單求和,而是結(jié)合考慮兩要素作為層次圖節(jié)點(diǎn)排序的依據(jù),這樣可以融合兩者優(yōu)點(diǎn),彌補(bǔ)缺陷。4)基于繼承次序與相關(guān)度的層次圖邊交叉最小化算法步驟如下:①獲取Crossing(H)的初始值,按照從頂至底,或者從底至頂掃描層次圖;②計(jì)算層中節(jié)點(diǎn)的bc(v)、Node_Sequence(v);③按照Node_Sequence(v)由小至大順序?qū)層進(jìn)行排序、bc(v)由小至大順序?qū)+1/i-1層進(jìn)行排序,交替循環(huán)執(zhí)行;④循環(huán)執(zhí)行步驟①～③,直至Crossing(H)不再減小。3層析成像的布局布線是根據(jù)節(jié)點(diǎn)間依賴關(guān)系,把布局生成的“半成品層次圖”通過連接線生成結(jié)構(gòu)嚴(yán)謹(jǐn)、布線清晰的層次圖。3.1無線傳感器網(wǎng)絡(luò)定義3跨度是層次間距離,記作Span(i,j)。連線節(jié)點(diǎn)有兩種分布情況:1)兩節(jié)點(diǎn)分屬兩層i,j且[Span(i,j)=1];2)兩節(jié)點(diǎn)分屬兩層i,j且[Span(i,j)>1],即鄰層與跨層。定義4虛擬節(jié)點(diǎn)是為特定目的而增加的節(jié)點(diǎn),記作Dummy(v)。以上分析可確定如下布線策略:1)鄰層連接:不用考慮連接線越過節(jié)點(diǎn),直接用連接線將依賴關(guān)系的兩節(jié)點(diǎn)連接;2)跨層連接:①通過路由算法,即由尋找“通道”的方法來布線;②通過添加虛擬節(jié)點(diǎn),例如Span(i,j)=k(k>1),則在兩節(jié)點(diǎn)間添加k-1個(gè)虛擬節(jié)點(diǎn),將跨層連接轉(zhuǎn)為鄰層連接,再用鄰層連接的布線方式來處理,而虛擬節(jié)點(diǎn)的添加會(huì)增加系統(tǒng)開銷,包括:內(nèi)存開銷、影響顯示清晰度等,因此必須盡可能減少虛擬節(jié)點(diǎn)個(gè)數(shù),本文采用PL算法。3.2上層節(jié)點(diǎn)的選擇PL算法通過提升層的方法來減少虛擬節(jié)點(diǎn)個(gè)數(shù),包括內(nèi)外兩層遞歸循環(huán),其功能是實(shí)現(xiàn)提升規(guī)則節(jié)點(diǎn),若上層有其直接前趨節(jié)點(diǎn),那么又根據(jù)分層算法中所敘述的依賴關(guān)系節(jié)點(diǎn)不能處于同一層,必須提升其直接前趨節(jié)點(diǎn),依次遞歸,達(dá)到減少虛擬節(jié)點(diǎn)總數(shù)的目的。定義5規(guī)則節(jié)點(diǎn)是層次圖中除虛擬節(jié)點(diǎn)之外的節(jié)點(diǎn),是具體模塊的表現(xiàn)形式。1duysdiffv的生成為了表達(dá)將節(jié)點(diǎn)v從k層提升到k+1層后虛擬節(jié)點(diǎn)總數(shù)的變化情況,引入節(jié)點(diǎn)v直接后繼集s(v),直接前趨集p(v),令u1,u2,…up1(0≤p1≤p)記作節(jié)點(diǎn)v的直接前趨節(jié)點(diǎn),提升節(jié)點(diǎn)v后虛擬節(jié)點(diǎn)的變化記作dummydiff(v),由上面分析可得:dummydiff(v)=s(v)?p(v)+∑i=1p1dummydiff(ui)(3)結(jié)合式(3)以及圖2對PL算法實(shí)例說明(矩形表示規(guī)則節(jié)點(diǎn);橢圓形表示虛擬節(jié)點(diǎn)):圖2(a)中有4個(gè)虛擬節(jié)點(diǎn),提升節(jié)點(diǎn)D,形成圖2(b),由式(3)可知,s(D)=0,p(D)=3,由于C、D存在依賴關(guān)系,必須提升節(jié)點(diǎn)C,所以dummydiff(D)=0-3+dummydiff(C);圖2(b)提升節(jié)點(diǎn)C,形成圖2(c),由式(3)可知,s(C)=2,p(C)=1,而提升C后沒有導(dǎo)致p(C)中一個(gè)或多個(gè)節(jié)點(diǎn)的提升,則dummydiff(C)=2-1=1,dummydiff(D)=0-3+dummydiff(C)=-2,即提升節(jié)點(diǎn)D、C后,虛擬節(jié)點(diǎn)總數(shù)減少了兩個(gè),由圖2(a)～(c)可看出,虛擬節(jié)點(diǎn)個(gè)數(shù)的確減少了兩個(gè)。22外歸算法循環(huán)掃描層次圖各規(guī)則節(jié)點(diǎn),采用內(nèi)遞歸算法,直至虛擬節(jié)點(diǎn)總數(shù)不再減少為止。3.3最短路徑鏈接路由層次圖通道路由布線出現(xiàn)了很多路由算法:如GEF(GraphicalEditorFramework),它是Eclipse中的重要圖形生成框架,該框架下的draw2D包中有一種路由算法——最短路徑鏈接路由(ShortestPathConnectionRouter)算法,可以有效解決層次圖跨度長邊的通道布線問題,其基本思想是繞開圖形之間障礙,折線選擇一條最短路徑進(jìn)行連接,效果如圖3所示;另外還有文獻(xiàn)提出的基于線性散列的通道布圖算法等,該問題非本文重點(diǎn),在此不再贅述。4節(jié)點(diǎn)位置物理定位布局得到了X、Y方向的相對布局位置,下一步是將圖元(如用矩形或橢圓來表示節(jié)點(diǎn))在具體顯示環(huán)境中得出窗口絕對坐標(biāo),若選擇圖元為矩形,在確定其寬、高參數(shù)后,要確定其窗口位置,只要確定其左上角節(jié)點(diǎn)坐標(biāo)(xtop_left,ytop_left)即可,計(jì)算步驟如下:1)假設(shè)節(jié)點(diǎn)用Rectangle(x,y)來表示,其中,x為矩形寬度,y為矩形高度,圖模型有m層,每層中最多有n個(gè)節(jié)點(diǎn),顯示窗口長為XWidth,高為YHeight,窗口左上角的坐標(biāo)為(0,0),行間距Layer_distance,記作L_d,列間距Node_distance,記作N_d;2)根據(jù)步驟1)中假設(shè)參數(shù),可得到i層(0<i≤m),j列(1≤j≤n)矩形圖元的左上角坐標(biāo)(假設(shè)i層節(jié)點(diǎn)數(shù)為count),那么可得到:???????????????xtop_left=Xwidth?(Count?1)?N_d?Count?x2+(j?1)?(x+N_d)ytop_left=Yheight?(m?1)?L_d?m?y2+(i?1)?(y+L_d)(4)3)由式(4)可得到層次圖H任意行任意列上節(jié)點(diǎn)v的左上角物理坐標(biāo),再對節(jié)點(diǎn)的寬x和高y進(jìn)行相關(guān)運(yùn)算,就可以得到其余三個(gè)角上的物理坐標(biāo),從而確定節(jié)點(diǎn)物理位置。此算法進(jìn)行絕對坐標(biāo)的計(jì)算,可以將相對布圖的層次圖居中、規(guī)整地顯示在實(shí)際計(jì)算機(jī)窗體上。5關(guān)度算法與重心啟發(fā)算法的比較通過圖4中兩層圖交叉度變化情況對“繼承次序與相關(guān)度算法”與重心啟發(fā)算法進(jìn)行比較說明。圖4(a)中有7個(gè)交叉點(diǎn),分別用重心啟發(fā)算法與“繼承次序與相關(guān)度”算法來處理,得到圖(b)、(c)。1bcz圖(a)中,先固定ABCDE,運(yùn)用式(1)可計(jì)算得到bc(X)=3,bc(Y)=3,bc(Z)=4,得到第二層順序是XYZ;固定XYZ,再運(yùn)用式(1)可得到bc(A)=1,bc(B)=1.5,bc(C)=2,bc(D)=1.5,bc(E)=2,得到第一層順序ABDCE,圖(b)中交叉度為6,相比圖(a)減少了1個(gè)交叉點(diǎn)。2繼承順序與相關(guān)度圖(a)中,先固定ABCDE,運(yùn)用式(2)可計(jì)算得到Node_Sequence(X)=5,Node_Sequence(Y)=3,Node_Sequence(Z)=7,得到第二層順序是YXZ;固定YXZ,再運(yùn)用式(1)可得bc(A)=2,bc(B)=1.5,bc(C)=2.5,bc(D)=1.5,bc(E)=2