受約束應力優化自動布圖原理方法闡述

劉 光 曹

(國網信息通信產業集團廈門億力吉奧信息科技有限公司 福建 廈門 361008)

?

受約束應力優化自動布圖原理方法闡述

劉 光 曹

(國網信息通信產業集團廈門億力吉奧信息科技有限公司 福建 廈門 361008)

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

布圖 應力優化 重疊 端口 正交

0 引 言

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

(1)

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

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

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

(2)

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

(3)

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

1 受約束應力優化布局

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

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

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

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

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

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

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

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

mprp=mqrq

(4)

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

(5)

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

圖2 兩元件重疊示意圖

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

2 端口連線交叉處理

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

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

yPB1=yPB2+ΔPB1,PB2}

(6)

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

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

3 正交化布局

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

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

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

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

4) 從步驟1)開始重復受約束的應力優化布局，直到沒有新的約束。

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

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

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

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

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

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

圖4 仿人工正交布局

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

4 結 語

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

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

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

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

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

[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。國家電網公司科技項目(SGITG-KJ-JSKF[2015]0012)。劉光曹，高工，主研領域：電力信息化。

TP391.7

A

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