一種無向圖視覺清敞化顯示算法

一種無向圖視覺清敞化顯示算法

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