劉 光 曹

(國網(wǎng)信息通信產(chǎn)業(yè)集團廈門億力吉奧信息科技有限公司 福建 廈門 361008)

?

受約束應力優(yōu)化自動布圖原理方法闡述

劉 光 曹

(國網(wǎng)信息通信產(chǎn)業(yè)集團廈門億力吉奧信息科技有限公司 福建 廈門 361008)

在電路原理圖或電網(wǎng)圖紙的布局應用中，自動布圖要解決各種棘手的影響展示效果的問題，包括元件重疊、端口連線交叉、及正交化約束等。為此，Dwyer及其研究組在應力優(yōu)化自動布圖的基礎(chǔ)上，提出了一系列處理這類問題的行之有效的方法。對此加以歸納總結(jié)并探討了值得進一步發(fā)展的方向。

布圖 應力優(yōu)化 重疊 端口 正交

0 引 言

在電子原理圖、軟件工程UML圖、電網(wǎng)全網(wǎng)圖等的計算機輔助設(shè)計和可視化展現(xiàn)中，存在一個共性的問題是如何美觀地擺放眾多圖形元件和連線，從而展現(xiàn)節(jié)點之間的連接關(guān)系。在這類問題的研究上，經(jīng)過了多年的發(fā)展，涌現(xiàn)出各種類型的自動布圖算法[1-2]，較為著名的有平面化布圖[3-4]、樹形布圖[5-6]、層次化布圖[7-8]、力導向布圖等[9-12]。其中，基于力導向的布圖算法，廣泛適用于以點-邊為基本元素構(gòu)成的圖中。其基本原理是建立兩兩節(jié)點之間的相互作用模型函數(shù)，通過數(shù)值計算逐步迭代的方法來優(yōu)化目標函數(shù)，在這過程中確定節(jié)點的移動方向和移動距離，以得到優(yōu)化的布局。其優(yōu)點是由于計算了兩兩節(jié)點相互作用，具有全局性，使得元件擺放呈現(xiàn)出疏密有致的布局效果。在眾多的力導向模型中，受關(guān)注最多的模型有兩種。一種是Fruchterman和Reingold的用引力和斥力表達的模型[11]，其節(jié)點之間的引力fa與距離d平方成正比，節(jié)點之間的斥力fr與距離d成反比：

(1)

k作為常數(shù)，也是連線的兩個節(jié)點引力等于斥力時的平衡距離。Fruchterman-Reingold模型的求解過程相對容易，節(jié)點沿合力方向移動，按模擬退火的方式限制移動量，時間復雜度為O(|V|2+|E|)。若忽略遠距離節(jié)點的斥力，時間復雜度可以提高到O(|V|+|E|)。不利的一點是求解過程可能限于局部最優(yōu)，而非全局最優(yōu)。另一種是Kamada等提出的一種勢能模型，參考了節(jié)點間的最短路徑的拓撲距離[10]。如圖1所示，節(jié)點A與節(jié)點B的最短路徑拓撲距離最近lAB=1，而節(jié)點A與節(jié)點F的最短路徑拓撲距離最遠lAB=3。因此，在理想的布局中，節(jié)點A與節(jié)點B擺放的幾何距離|XA-XB|也就比較近，盡可能接近它們的拓撲距離lAB=1；節(jié)點A與節(jié)點F的幾何距離|XA-XF|要遠些，導致A和F盡可能相互遠離。其他節(jié)點間的相互作用以此類推，就得到圖1的理想布局。

圖1 Kamada和Kawai勢能模型布局示例

Kamada和Kawai的勢能模型表達式的如下：

(2)

上述Kamada-Kawai模型函數(shù)的實際優(yōu)化求解計算較為復雜。Kamada和Kawai采用牛頓-拉夫森迭代法，每次移動一個節(jié)點，從失衡梯度最嚴重的元件開始，逐步優(yōu)化。后來，Gansner等在此基礎(chǔ)上改進計算方法，引入多維尺度分析的應力優(yōu)化[13-14]的推導，采用共軛梯度迭代方法，提升收斂速度并加強穩(wěn)定性[12]。進一步地，Dwyer在Gansner的應力優(yōu)化迭代收斂推導基礎(chǔ)上，將優(yōu)化求解式(2)轉(zhuǎn)化成優(yōu)化求解二階矩陣如下:

(3)

式中各參數(shù)(A、Z(a)、AZ等)的獲取見文獻[15,19]。

1 受約束應力優(yōu)化布局

在電路原理圖或電網(wǎng)圖紙的應用中，自動布圖要克服許多約束。Dwyer及其研究組在處理這些約束方面做了大量的工作，包括分離約束，有向圖的排列，節(jié)點限制在容器輪廓內(nèi)部等等[15-19]。

約束限制下采用梯度投影法尋求優(yōu)化布局的主體步驟為[15-16,18]：

1) 計算最速下降梯度g=▽f(x)=Ax+b；

2) 計算能確保目標函數(shù)下降的步長s=(gTg)/(gTAg)；

3) 所有元件根據(jù)梯度下降移動x=x-s·g；

4) 移動所有不滿足約束的元件，使之滿足約束；

5) 從步驟1)開始重復，直到收斂或達到最多允許的迭代次數(shù)。

這里以解決元件重疊為例[17]，介紹上述步驟4)處理約束的方法。首先是生成約束，沿著X和Y方向掃描，生成鄰近元件間不重疊所要求的坐標約束，以|xv-xu|≥(1/2)(wv+wu)的形式表示，wv和wu是鄰近兩元件各自的寬度。除了最常見的防止元件重疊的約束外，該方法還可以用于處理更一般的其他形式的不等式約束或等式約束，類似|p-q|=d和|p-q|≥d等。處理時，例如圖2兩個元件p和q發(fā)生重疊，不滿足|p-q|≥d，d為沿著pq方向兩元件中心不重疊所要求的最小距離。為消除重疊，元件向相反方向移開來滿足約束，移動遵從重心不變的原理:

mprp=mqrq

(4)

其中mp和mq是它們的權(quán)重，加入權(quán)重滿足一個模塊元件由多個元件拼成的情況，多個元件的權(quán)重可以疊加起來組成模塊的權(quán)重。實際應用中，可以把元件的面積或其他有真實含義的量作為權(quán)重。消除重疊時，大塊的元件移動量小，小塊的元件移動量大。進而，元件p的移動量為：

(5)

元件q的移動量類似。pq是沿著p指向q的單位向量。

圖2 兩元件重疊示意圖

對于多個元件重疊，以及相互關(guān)聯(lián)的復雜情況，有兩種方法處理。一種方法相對簡單，每次取兩個違反約束的元件相互移開。由于處理一個約束后移動元件時可能又牽連到另一個約束，比如又引起新的重疊或者還存在其他重疊，故反復循環(huán)處理所有重疊，以促進所有約束都得到滿足[18]。另一種方法可以減少這種循環(huán)次數(shù)，其核心思想是把剛消除重疊的兩個元件綁定在一起當作一個模塊，后續(xù)讓這個模塊內(nèi)綁的元件一起移動，相對位置保持不變，以避免破壞先前處理好的約束；然后繼續(xù)消除該模塊與其他元件或模塊的重疊，這些模塊和元件也全部加以綁定以保持相對位置，這樣擴大了綁定范圍來保存解決好的約束[17]。

2 端口連線交叉處理

在LabView等軟件的數(shù)據(jù)流原理圖上，所有邊要連接每個元件上固定的端口，端口的排列順序會導致連邊產(chǎn)生交叉，例如圖3(a)中端口PB1在端口PB2上方而導致連邊交叉。在解決涉及元件的端口問題方面，Schulze 等給出一種基于層次化布局的方法[20]，Rüegg等給出了基于端口約束的方法[21]。相比而言，后者的方法更容易擴展到非層次化的、無向圖的應用中。因此，這里著重介紹后者的原理。在解決這一問題中，即Rüegg的方法中，把端口也當作節(jié)點，并添加了端口節(jié)點相對位置的約束，然后采用應力優(yōu)化布局來減少此類交叉。如圖3(b)中，約束端口節(jié)點的相對位置，約束限制PB1必須在PB2的上方：

{(xPB1,yPB1,xPB2,yPB2)|xPB1=xPB2,

yPB1=yPB2+ΔPB1,PB2}

(6)

這樣應力優(yōu)化布局后，由于不交叉的連線距離更短，導致圖3(b)中與PB1連接的端口PD0自然移動到端口PC0的上方；繼而帶動元件D移到元件C的上方，就不會產(chǎn)生交叉。

圖3 端口連線交叉的Labview電路示意圖

3 正交化布局

通常正交網(wǎng)格布局效果的美觀度較好，但是應力優(yōu)化布局后元件位置參差不齊。為實現(xiàn)正交化布局，Dwyer設(shè)計了一種自適應約束對齊ACA(Adaptive Constrained Alignment)算法[22]，其主體步驟如下：

1) 按照當前所有的約束，進行受約束的應力優(yōu)化布局；

2) 找出調(diào)整成水平(或豎直)排列代價最小的一條邊；

3) 在所有約束中，增加一條步驟2產(chǎn)生的新的水平(或豎直)排列約束；

4) 從步驟1)開始重復受約束的應力優(yōu)化布局，直到?jīng)]有新的約束。

第2步的代價計算包括兩個因素。一個因素是把非水平的邊調(diào)成水平所產(chǎn)生的代價，為減少這一代價傾向于把最接近水平的邊調(diào)整成水平。豎直方向調(diào)整類似。另一個因素是對一串連邊在中間節(jié)點處形成的折角進行懲罰，通過減少折角讓多邊形盡可能塑成矩形，以提高正交性。上述正交化循環(huán)過程結(jié)束后，再通過網(wǎng)格近似，實現(xiàn)網(wǎng)格化。

為了進一步提高布局效果的美觀度，2015年Kieffer等給出了一套仿人工正交布局算法HOLA(Human-like Orthogonal Layout Algorithm)[23]。他們先請用戶對一些人為布局的效果進行評價排序，總結(jié)出以下美學標準：(R1)樹宜放在環(huán)外而非放在環(huán)內(nèi)；(R2)美化彎折；(R3)充分利用繪圖空間；(R4)橫平豎直網(wǎng)格化；(R5)對稱性；(R6)不宜交叉；(R7)減少彎折；(R8)邊長均勻；(R9)節(jié)點受力均勻。考慮這些美學標準，仿人工正交布局算法采用以下步驟：

1) 先把樹狀分支都剪裁掉，只剩純粹的環(huán)連接而成的內(nèi)核。

2) 再進行內(nèi)核的布局，如圖4(a)，包括：a)對內(nèi)核采用應力優(yōu)化布局(符合R3,R5,R6,R8)；b)用最少的角度調(diào)整逐步實現(xiàn)正交化(符合R2,R4,R9)；c)正交化布線(符合R6,R7,R8)。

3) 再對被剪裁的樹進行布局，如圖4(b)，包括：a)對稱地布局每棵樹(符合R5)；b)把樹加入到內(nèi)核中，擴張內(nèi)核布局的相應行列(符合R1)。

4) 調(diào)整改進：a)對齊排列；b)鄰近節(jié)點受力優(yōu)化(符合R3,R8)；c)旋轉(zhuǎn)使得寬度大于高度，且讓多數(shù)的樹形朝下；d)最后正交化布線。

圖4 仿人工正交布局

可以看出，仿人工正交布局最主要的是模仿人的思路，先擺好圖中最難擺好的環(huán)(即內(nèi)核)，再加入樹狀分支進行調(diào)整。以上方法經(jīng)過測試與用戶評價，仿人工正交布局的美觀度與評測過程中最佳的人工布局美觀度可以相媲美。

4 結(jié) 語

本文總結(jié)了約束限制條件下布局的基本步驟，并以解決元件重疊為例進行說明。在受約束布局的基礎(chǔ)上，對元件的多個端口相對位置進行約束，就能克服多個端口間連線交叉的問題。然后，闡述了正交化布局的方法，在循環(huán)地使用應力優(yōu)化布局的過程中，對接近水平(或垂直)的邊，逐步添加正交化約束。在此基礎(chǔ)上，仿人工正交布局算法模仿人的思維方法，先把圖分解成樹狀分支和純粹由環(huán)組成的內(nèi)核，然后對內(nèi)核的環(huán)進行正交布局，再把樹狀分支擴充到內(nèi)核上，取得了很好的效果。

這些布局方法也有一些可以擴展或改進的空間，例如：

1) 布局算法步驟都是采用串行處理，如果能夠進行并行優(yōu)化，就可以利用GPU和云計算的強大計算能力，提高計算速度，完成更大規(guī)模的布局。實際上布局步驟進入細化微調(diào)階段以后，位置越遠的節(jié)點間的相關(guān)性越小，開展并行計算的可行性也就越高。

2) 仿人工正交布局(HOLA)是人為地總結(jié)一些美學經(jīng)驗或規(guī)則，再按照給定的方法步驟開展布局。現(xiàn)今人工智能、機器學習領(lǐng)域發(fā)展迅猛，在不久的將來，我們或許可以看到計算機通過自主地學習大量已有的人工布圖，再進行智能的繪圖。

自動布圖在計算機輔助設(shè)計領(lǐng)域有著廣闊的應用前景，隨著應用的拓展和深入，處理各種復雜規(guī)則和約束的能力日臻成熟，將為設(shè)計和開發(fā)人員帶來許多便利。

[1] Cruz I F,Tamassia R.Graph Drawing Tutorial[EB/OL].[1998-7-19].http://cs.brown.edu/～rt/papers/gd-tutorial/gd-constraints.pdf.

[2] Tamassia R.Handbook of Graph Drawing and Visualization[M].Crc Press,2013.

[3] DeFraysseix H,Pach J,Pollack R.How to Draw a Planar Graph on a Grid[J].Combinatorica,1990,10(1):41-51.

[4] Chrobak M,Payne T H.A Linear-time Algorithm for Drawing a Planar Graph on a Grid[J].Information Processing Letters,1995,54(4):241-246.

[5] Chan T M,Goodrich M T,Kosaraju S R,et al.Optimizing Area and Aspect Ratio in Straight-line Orthogonal Tree Drawings[J].Computational Geometry,2002,23(2):153-162.

[6] Garg A,Goodrich M T,Tamassia R.Planar Upward Tree Drawings with Optimal Area[J].International Journal of Computational Geometry and Applications,1996,6(3):333-356.

[7] Sugiyama K,Tagawa S,Toda M.Methods for Visual Understanding of Hierarchical System Structures[J].IEEE Transactions on Systems Man and Cybernetics,1981,11(2):109-125.

[8] Elsayed M A,Omran N F,Radwan A AA.Study of Proper Hierarchical Graphs on a Grid[J].International Journal of Advanced Computer Science and Application,2012,3(12):104-109.

[9] Eades P A.A Heuristic for Graph Drawing[J].Congressus Numerantium,1984,42(42):149-160.

[10] Kamada T,Kawai S.An Algorithm for Drawing General Undirected Graphs[J].Information Processing Letters,1989,31(1):7-15.

[11] Fruchterman T M J,Reingold E M.Graph drawing by Force-directed Placement[J].Software-Practice and Experience,1991,21(11):1129-1164.

[12] Gansner E R,Koren Y,North S.Graph Drawing by Stress Majorization[C]//Graph Drawing.Springer Berlin Heidelberg,2004:239-250.

[13] Leeuw J D.Convergence of the Majorization Method for Multidimensional Scaling[J].Journal of Classification,1988,5(2):163-180.

[14] Borg I,Groenen P.Modern Multidimensional Scaling:Theory and Applications[J].Journal of Educational Measurement,2003,40(3):277-280.

[15] Dwyer T,Koren Y,Marriott K.Stress Majorization with Orthogonal Ordering Constraints[C]//Graph Drawing.Springer Berlin Heidelberg,2005:141-152.

[16] Dwyer T,Koren Y,Marriott K.IPSEP-COLA:an Incremental Procedure for Separation Constraint Layout of Graphs[J].IEEE Transactions on Visualization and Computer Graphics,2006,12(5):821-828.

[17] Dwyer T,Marriott K,Peter J Stuckey.Fast Node Overlap Removal[C]//Graph Drawing.Springer Berlin Heidelberg,2005:153-164.

[18] Dwyer T.Scalable,Versatile and Simple Constrained Graph Layout[J].Computer Graphics Forum,2009,28(3):991-998.

[19] Dwyer T,Koren Y,Marriott K.Constrained Graph Layout by Stress Majorization and Gradient Projection[J].Discrete Mathematics,2009,309(7):1895-1908.

[20] Schulze C D,Sp?nemann M,Von Hanxleden R.Drawing Layered Graphs with Port Constraints[J].Journal of Visual Languages and Computing,2014,25(2):89-106.

[21] Rüegg U,Kieffer S,Dwyer T,et al.Stress-minimizing Orthogonal Layout of Data Flow Diagrams with Ports[C]//Graph Drawing.Springer Berlin Heidelberg,2014:319-330.

[22] Kieffer S,Dwyer T,Marriott K,et al.Incremental Grid-like Layout Using Soft and Hard Constraints[C]//Graph Drawing.Springer International Publishing,2013:448-459.

[23] Kieffer S,Dwyer T,Marriott K,et al.Hola:Human-like Orthogonal Network Layout[J].IEEE Transactions on Visualization and Computer Graphics,2016,22(1):349-358.

PRINCIPLES AND METHODS OF CONSTRAINED STRESS MAJORIZATION AUTOMATIC LAYOUT

Liu Guangcao

(XiamenGreatPowerGeoInformationTechnologyCo.,Ltd.,StateGridInformationandTelecommunicationGroup,Xiamen361008,Fujian,China)

In the application of circuit schematic or grid layout, automatic layout should overcome some stubborn problems. These problems which include elements overlapping and port connection crossing and orthogonalization constraints often influence display effect. So far, Dwyer and his research group present a series of effective methods to deal with these problems based on the stress majorization. We try to sum up these methods, and propose some effective improvements.

Graph drawing Stress majorization Overlap Port Orthogonal

2016-08-27。國家電網(wǎng)公司科技項目(SGITG-KJ-JSKF[2015]0012)。劉光曹，高工，主研領(lǐng)域：電力信息化。

TP391.7

A

10.3969/j.issn.1000-386x.2017.07.010