一種無(wú)向圖視覺(jué)清敞化顯示算法

一種無(wú)向圖視覺(jué)清敞化顯示算法

1視覺(jué)清析顯示算法圖形是一種廣泛使用的數(shù)據(jù)結(jié)構(gòu)。它可以直觀地表示各種復(fù)雜的關(guān)系模型。其中，表示系統(tǒng)中的對(duì)象，表示對(duì)象之間的關(guān)系。將圖清晰、美觀地顯示在二維或三維的一個(gè)有限區(qū)域?qū)斫夂头治瞿Ｐ途哂惺种匾囊饬x。在許多應(yīng)用領(lǐng)域,需要描述一組對(duì)象間的關(guān)系。比如在軟件工程中,各個(gè)模塊間存在依賴關(guān)系,各個(gè)數(shù)據(jù)類間存在訪問(wèn)關(guān)系。在系統(tǒng)分析時(shí),就要考慮子系統(tǒng)的劃分及其包含的模塊和數(shù)據(jù)類。如果把這些模塊或數(shù)據(jù)類看成頂點(diǎn),依賴關(guān)系或訪問(wèn)關(guān)系看成二元關(guān)系,如何理順模塊或數(shù)據(jù)類就是一個(gè)圖的清晰化顯示問(wèn)題。此外,關(guān)系數(shù)據(jù)表間的聯(lián)系、組織成員間的合作關(guān)系、知識(shí)點(diǎn)依賴圖、路由器分布圖等,只要需要圖形化顯示的,都涉及到圖的清晰化顯示問(wèn)題。因此,圖的視覺(jué)清晰化顯示算法具有相當(dāng)大的實(shí)際意義,是一項(xiàng)值得研究的應(yīng)用基礎(chǔ)研究項(xiàng)目。該算法的研究一旦取得實(shí)質(zhì)性的成果,就可以將它植入軟件工程、識(shí)別系統(tǒng)等應(yīng)用技術(shù)或系統(tǒng)中去,使這些技術(shù)或系統(tǒng)更加自動(dòng)化、智能化、高效率、實(shí)用化和人性化。其中,無(wú)向關(guān)系圖的畫圖算法是其中一類重要的算法,很多學(xué)者對(duì)此做過(guò)深入的研究。EadesP用彈力模型繪制一般無(wú)向圖,該方法將一個(gè)圖看成是一個(gè)頂點(diǎn)為鋼環(huán)、邊為彈簧的機(jī)械系統(tǒng),彈簧達(dá)到極小能量狀態(tài)時(shí)對(duì)應(yīng)圖的一個(gè)美觀畫法。然而,這種方法由于容易陷入局部最優(yōu)解而得到的結(jié)果很差。Davidson和Harel提出用模擬退火算法畫一般無(wú)向圖,產(chǎn)生的效果可與彈力模型法產(chǎn)生的效果相比。但是,該算法在繪制頂點(diǎn)數(shù)較多且無(wú)弦的圖時(shí)得到的并不是通常情況下的大圈,而是一個(gè)卷曲的圈,即得到的是一個(gè)凹多邊形而不是凸多邊形;同時(shí),模擬退火算法也容易限入局部最優(yōu)解而得到較差的畫法。黃競(jìng)偉、康立山等提出了一種基于遺傳算法的無(wú)向圖畫圖算法,該算法將畫圖問(wèn)題轉(zhuǎn)化為函數(shù)優(yōu)化問(wèn)題,但遺傳算法屬于概率算法,算法執(zhí)行結(jié)果具有不確定性,同時(shí)想要得到好的輸出結(jié)果,需要經(jīng)過(guò)相當(dāng)長(zhǎng)的時(shí)間演化,因此算法收斂性較差。Papadopoulos和Voglis采用自底向上的模塊分解樹的方法繪制無(wú)向圖,使得繪圖結(jié)果達(dá)到一定的美學(xué)標(biāo)準(zhǔn),但模塊之間的連線相交問(wèn)題仍然不能解決。張清國(guó)、葉俊民等也提出了一種基于遺傳算法的無(wú)向繪制圖算法。張磊、孫松等提出將無(wú)向圖顯示在環(huán)上,根據(jù)每個(gè)頂點(diǎn)的加權(quán)值確定其所占有的扇形區(qū)域,并將每個(gè)頂點(diǎn)布局在其扇區(qū)的中心線上。然而,這種方法不適用于帶有環(huán)的無(wú)向圖。Hong和Nagamochi研究了用星形和凸多邊形相結(jié)合的方式繪制可平面圖,并分析了可平面化的充分條件,但并未對(duì)無(wú)向圖畫圖算法作深入研究。相比之下,本文算法能很好地克服上述算法中的不足。2提出無(wú)向關(guān)系圖清糊化的要求并構(gòu)建相應(yīng)的二元關(guān)系無(wú)向關(guān)系圖的繪制算法有直線法、折線法、正交法、平面化法等。本文提出的無(wú)向關(guān)系圖視覺(jué)清晰化顯示算法是基于直線畫法實(shí)現(xiàn)的。無(wú)向關(guān)系圖清晰化顯示問(wèn)題的形式化描述是:給定頂點(diǎn)集A={Pi,i=1,…,N},以及A上的反自反對(duì)稱二元關(guān)系R={<Pi,Pj>|i≠j,1≤i≤N,1≤j≤N}和二維區(qū)域Ω=[0,X]×[0,Y],尋找N個(gè)頂點(diǎn)的位置P=(P1,…,PN)∈ΩN,使得二元關(guān)系圖在一定的視覺(jué)清晰度目標(biāo)函數(shù)Q(P)的意義下達(dá)到最優(yōu)或近似最優(yōu)。2.1清朗化顯示算法清晰度是從人的視覺(jué)感官上看圖的美學(xué)標(biāo)準(zhǔn),至今沒(méi)有統(tǒng)一的解析表達(dá)式,預(yù)計(jì)將來(lái)也難以產(chǎn)生能被普遍接受的標(biāo)準(zhǔn)。一個(gè)視覺(jué)清晰化顯示算法就是在這樣一個(gè)無(wú)定論的標(biāo)準(zhǔn)之上繪制的畫圖算法,即使有一個(gè)清晰度的客觀標(biāo)準(zhǔn)Q(P),由于問(wèn)題的搜索空間是ΩN,具有2N個(gè)自由度,搜索空間巨大,清晰化顯示算法也難以解析地表達(dá)。對(duì)于無(wú)向關(guān)系圖,通常能夠被接受的清晰度標(biāo)準(zhǔn)有:(1)以連通分支為基本單位分配顯示區(qū)域;(2)頂點(diǎn)間的最小距離越大越好;(3)邊的交叉越少越好;(4)邊的長(zhǎng)度越均勻越好;(5)多度頂點(diǎn)的各相關(guān)邊的夾角越均勻越好;(6)盡量占滿顯示區(qū)域。2.2無(wú)向連通一帶子團(tuán)內(nèi)各子團(tuán)交叉連接為了更好地說(shuō)明無(wú)向關(guān)系圖視覺(jué)清晰化顯示算法,先定義幾個(gè)術(shù)語(yǔ)。(1)團(tuán):一個(gè)連通無(wú)向圖刪除所有割邊后,每一個(gè)連通子圖稱為團(tuán)。團(tuán)內(nèi)不再有割邊。在一般無(wú)向連通圖中,如果將團(tuán)縮為一個(gè)頂點(diǎn),那么該無(wú)向連通圖將縮為一棵樹。(2)子團(tuán):一個(gè)團(tuán)刪除所有割點(diǎn)后,每一個(gè)連通子圖稱為子團(tuán)。子團(tuán)內(nèi)不再有割點(diǎn)。從團(tuán)和子團(tuán)的定義中可以發(fā)現(xiàn),沒(méi)有割點(diǎn)的團(tuán)也是子團(tuán),子團(tuán)是一種特殊的團(tuán),子團(tuán)與子團(tuán)間通過(guò)割點(diǎn)連接構(gòu)成團(tuán)。本文算法除了遵循通常的清晰度標(biāo)準(zhǔn)之外,還在下述清晰度標(biāo)準(zhǔn)上達(dá)到最優(yōu)或近似最優(yōu):(1)團(tuán)內(nèi)各子團(tuán)分布越均勻越好;(2)團(tuán)間連接各子團(tuán)的交叉邊越少越好;(3)團(tuán)內(nèi)連接各子團(tuán)的邊長(zhǎng)越均勻越好;(4)子團(tuán)內(nèi)頂點(diǎn)分布越均勻越好;(5)子團(tuán)內(nèi)交叉邊越少越好;(6)子團(tuán)內(nèi)邊長(zhǎng)越均勻越好。2.3dfsu低v的位點(diǎn)由于在本文中要用到求割點(diǎn)與割邊,先將該算法說(shuō)明如下。該算法是TarjanR提出的。對(duì)圖深度優(yōu)先搜索,定義DFS(u)為u在搜索樹(以下簡(jiǎn)稱為樹)中被遍歷到的次序號(hào)。定義Low(u)為u或u的子樹中能通過(guò)非父子邊追溯到的最早的頂點(diǎn),即DFS序號(hào)最小的頂點(diǎn)。根據(jù)定義,則有:一個(gè)頂點(diǎn)u是割點(diǎn),當(dāng)且僅當(dāng)滿足以下條件:(1)u為樹根,且u有多于一個(gè)子樹。(2)u不為樹根,且滿足存在(u,v)為樹枝邊,使得DFS(u)≤Low(v)。一條無(wú)向邊(u,v)是割邊,當(dāng)且僅當(dāng)(u,v)為樹枝邊,且滿足DFS(u)<Low(v)。3清晰顯示算法3.1離開(kāi)孤立點(diǎn)遍歷全圖,將圖G中頂點(diǎn)度數(shù)為零的頂點(diǎn)從原圖中分離出來(lái),將這些孤立點(diǎn)刪除,或者顯示在一個(gè)獨(dú)立的邊緣區(qū)域,原圖由G變?yōu)镚′。3.2全面展開(kāi)方向展開(kāi)在左上坐標(biāo)為(x1,y1)、右下坐標(biāo)為(x2,y2)的矩形區(qū)域內(nèi)將G′分離出連通分支。(1)遍歷圖G′,檢查出G′的連通分支數(shù)n,每個(gè)連通分支記為G′i(i=0,…,n-1)。(2)將區(qū)域以橫向展開(kāi)方向,以該連通分支頂點(diǎn)數(shù)占全部頂點(diǎn)的比例將矩形區(qū)域劃分為n份,如圖1所示。設(shè)G′i所顯示的區(qū)域?yàn)樽笊献鴺?biāo)為(x1,i,y1,i)、右下坐標(biāo)為(x2,i,y2,i),則有:x1,0=x1x1,i=x1+1Νi-1∑k=0Νk(x2-x1)?i=1,?,n-1x2,i=x1,i+1?i=0,?,n-2x2,n-1=x2y1,i=y1,y2,i=y2?i=0,?,n-1x1,0=x1x1,i=x1+1N∑k=0i?1Nk(x2?x1)?i=1,?,n?1x2,i=x1,i+1?i=0,?,n?2x2,n?1=x2y1,i=y1,y2,i=y2?i=0,?,n?1其中,Nk為第k個(gè)連通分支的頂點(diǎn)數(shù),N為G′的總頂點(diǎn)數(shù)。3.3trool穩(wěn)定性檢驗(yàn)對(duì)每個(gè)連通分支G′i基于樹型結(jié)構(gòu)顯示。(1)遍歷G′i,找出G′i中所有的割邊。(2)根據(jù)割邊可以構(gòu)造出一棵樹,記為G′i,T,該樹中的每個(gè)頂點(diǎn)對(duì)應(yīng)于G′i中的一個(gè)團(tuán),將該團(tuán)記為G′i,j,如圖2所示。(3)記G′i,j的顯示區(qū)域?yàn)?左上坐標(biāo)為(x1,i,j,y1,i,j),右下標(biāo)為(x2,i,j,y2,i,j),將G′i以G′i,T結(jié)構(gòu)分層顯示。其中G′i,T中的每個(gè)頂點(diǎn)對(duì)應(yīng)G′i中的一個(gè)團(tuán),將G′i,0對(duì)應(yīng)樹G′i,T中的根結(jié)點(diǎn),該根結(jié)點(diǎn)記為Vi,Troot。(4)以Vi,Troot為根結(jié)點(diǎn)遍歷G′i,T,檢測(cè)出G′i,T的總層數(shù)以及每層包含的頂點(diǎn)數(shù)。(5)記第k層的左上坐標(biāo)為(x1,i,αk,y1,i,αk),右下坐標(biāo)為(x2,i,αk,y2,i,αk)。記Mi,k為G′i在第k層中的頂點(diǎn)數(shù),則:x1,i,αk=x1,iy1,i,αk=y2,i,αk-1x2,i,αk=x2,iy2,i,αk=y1,i,αk+Μi,kΝi×(y2,i-y1,i)x1,i,αk=x1,iy1,i,αk=y2,i,αk?1x2,i,αk=x2,iy2,i,αk=y1,i,αk+Mi,kNi×(y2,i?y1,i)其中,y1,i,α0=y1,iy2,i,α0=y1,i,α0+Μi,0Νi×(y2,i-y1,i)y1,i,α0=y1,iy2,i,α0=y1,i,α0+Mi,0Ni×(y2,i?y1,i)(6)記第k層第l團(tuán)的左上坐標(biāo)為(x1,i,αk,βl,y1,i,αk,βl),右下坐標(biāo)為(x2,i,αk,βl,y2,i,αk,βl),記Mi,k,l為第k層第l團(tuán)的頂點(diǎn)數(shù),則:x1,i,αk,βl=x2,i,αk,βl-1y1,i,αk,βl=y1,i,αk,βk-1x2,i,αk,βl=x1,i,αk,βl+Μi,k,lΜi,k×(x2,i,αk-x1,i,αk)y2,i,αk,βl=y2,i,αk,βl-1x1,i,αk,βl=x2,i,αk,βl?1y1,i,αk,βl=y1,i,αk,βk?1x2,i,αk,βl=x1,i,αk,βl+Mi,k,lMi,k×(x2,i,αk?x1,i,αk)y2,i,αk,βl=y2,i,αk,βl?1其中,x1,i,αk,β0=x1,i,αky1,i,αk,β0=y1,i,αkx2,i,αk,β0=x1,i,αk,β0+Μi,k,0Μi,k×(x2,i,αk-x1,i,αk)y2,i,αk,β0=y2,i,αk3.4求各起品種多且連接點(diǎn)值的估計(jì),把vk作對(duì)于團(tuán)G′i,j中每個(gè)屬于割邊所連接的頂點(diǎn)vk,設(shè)vk與團(tuán)外的邊連接數(shù)為C,其中與上層團(tuán)的連接數(shù)為CU,與下層團(tuán)的連接數(shù)為CD,根據(jù)CU和CD的大小關(guān)系分別做如下處理:(1)如果CU>CD,將vk定位在vk所在團(tuán)顯示區(qū)域的(x1,i,j+x2,i,j-x1,i,jn×m,y1,i,j+p)處,p≥0且是一個(gè)相對(duì)較小的值。其中,n為該團(tuán)中同樣具有CU>CD性質(zhì)的割邊連接點(diǎn)的個(gè)數(shù),m為vk在這些割邊連接點(diǎn)中的序號(hào)。(2)如果CU=CD,將vk定位在vk所在團(tuán)顯示區(qū)域的(x1,i,j+x2,i,j-x1,i,jn×m,y1,i,j+y2,i,j2)處。其中,n為該團(tuán)中同樣具有CU=CD性質(zhì)的割邊連接點(diǎn)的個(gè)數(shù),m為vk在這些割邊連接點(diǎn)中的序號(hào)。(3)如果CU<CD,將vk定位在vk所在團(tuán)顯示區(qū)域的(x1,i,j+x2,i,j-x1,i,jn×m,y2,i,j-p)處,p≥0且是一個(gè)相對(duì)較小的值。其中,n為該團(tuán)中同樣具有CU<CD性質(zhì)的割邊連接點(diǎn)的個(gè)數(shù),m為vk在這些割邊連接點(diǎn)中的序號(hào)。3.5連通分支內(nèi)團(tuán)分布(1)遍歷該團(tuán)G′i,j,找出該團(tuán)中所有的割點(diǎn),以割點(diǎn)為分界點(diǎn),團(tuán)G′i,j可以被劃分為若干個(gè)子團(tuán)G′i,j,k。(2)選取團(tuán)G′i,j中與上層團(tuán)有聯(lián)系的一個(gè)頂點(diǎn)所在子團(tuán)為根結(jié)點(diǎn),子團(tuán)與子團(tuán)間存在虛連線,則團(tuán)G′i,j可以映射為一根樹G′i,j,T。其中,G′i,j,T中的一個(gè)頂點(diǎn)對(duì)應(yīng)于G′i,j中的一個(gè)子團(tuán),如圖3所示。(3)根據(jù)G′i,j,T,可以用處理連通分支內(nèi)團(tuán)的分布的方法來(lái)處理團(tuán)內(nèi)子團(tuán)的分布。(4)在G′i,j中將虛線連接的頂點(diǎn)向虛線方向縮回到其歸屬的頂點(diǎn)。3.6區(qū)域的最大內(nèi)徑將子團(tuán)內(nèi)不在割邊上的頂點(diǎn)均勻分布在所在子團(tuán)顯示區(qū)域的最大圓環(huán)上。由于子團(tuán)間的連接點(diǎn)為割點(diǎn),首先將割點(diǎn)定位在相鄰子團(tuán)的方向,其余點(diǎn)的定位按照均勻分布的原則分布在一個(gè)顯示區(qū)域的內(nèi)切圓周上。4實(shí)驗(yàn)結(jié)果分析用VC6.0編程實(shí)現(xiàn)視覺(jué)清晰化算法,實(shí)驗(yàn)結(jié)果表明,經(jīng)過(guò)本算法后的無(wú)向關(guān)系圖清晰度明顯提高,尤其對(duì)具有稀疏關(guān)系性質(zhì)的無(wú)向關(guān)系圖效果更加明顯。實(shí)驗(yàn)結(jié)果如圖4～圖7所示。圖4顯示了一個(gè)簡(jiǎn)單封閉回路關(guān)系(如圖4a所示)在本文算法下的輸出結(jié)果,如圖4b所示,均勻美觀,但文獻(xiàn)算法的輸出有時(shí)會(huì)出現(xiàn)凹形結(jié)