[發明專利]一種GMF圖形編輯器創建有向圖的自動布局方法

有效

• 申請號: 201310443605.3
• 申請日: 2013-09-26
• 公開（公告）號: CN103500250B
• 公開（公告）日: 2017-04-12
• 發明（設計）人: 李紅;楊國青;陳坤;郭徐;雷健;吳朝暉
• 申請（專利權）人: 浙江大學
• 主分類號: G06F17/50
• 分類號: G06F17/50
• 代理公司: 杭州宇信知識產權代理事務所(普通合伙)33231
• 代理人: 張宇娟

技術領域

本發明涉及圖形布局技術，具體涉及一種GMF圖形編輯器創建有向圖的自動布局方法。

背景技術

圖形建模框架（Graphical?Modeling?Framework，簡稱GMF）是Eclipse平臺中用于圖形化編輯器開發的框架。開發者利用GMF提供的組件及其運行時環境，進行必要的圖形元素建模和相關配置，便可生成圖形化編輯器工程源代碼。因為圖形編輯器代碼編寫實現了高度自動化，使得圖形編輯器的設計與實現變得簡單而迅速。

圖形布局指按照要求設置圖元的大小、位置、圖元之間連線的路徑等信息。GMF圖形編輯器圖元具有嵌套組合的特點：大圖元由小圖元組成，小圖元又由小一級的圖元組成。大圖元的布局策略需要處理其內部子圖元的布局排放，而內部子圖元又能擁有自己的布局策略。一個好的布局算法既能保證圖形排版的美觀，又能增強圖形編輯器的易用性。

目前GMF框架中，已經由Randy?Hudson等人提供了一種有向圖布局算法的實現。但該算法執行過程中有一個限制條件，該有向圖必須是有連接關系的圖，否則每個結點計算出的水平位置相同，所有結點從上往下排成一列。而且，對于圖元之間連線多，圖元層次復雜等情況，該算法在布局時會導致圖元布局重疊、圖元之間連線穿過圖元等現象的發生。

發明內容

為解決上述問題，得到圖元連線簡潔、圖元間無重疊的圖形布局，本發明提出了一種GMF圖形編輯器創建有向圖的自動布局方法，其具體技術方案如下：

一種GMF圖形編輯器創建有向圖的自動布局方法，包括如下步驟：

S10：解析GMF圖形編輯器建立的有向圖數據，獲取圖元信息，將每個組件圖元擁有的有向連線起點的個數作為該圖元的出度，將其擁有的有向連線的終點的個數作為該圖元的入度；

S20：使用拓撲排序的方法對所有的組件圖元進行分層處理；

S30：設置連接圖元的位置：將同一個組件圖元中，所有是有向連線起點的連接點均放置在組件圖元的右側，是有向連線終點的連接點放置在組件圖元的左側，兩個連接點之間等間距放置；然后在此前提下，將與同一個組件圖元相連的連接圖元相鄰放置；

S40：設置每個組件圖元的位置：將同一層次的組件圖元設置在同一個水平位置上，以圖元間所有連線的曼哈頓距離最短為目標，進行目標規劃，以此設置每個層次中圖元的垂直位置；

S50：設置每個組件圖元的大小：將每個組件圖元的寬度設置為固定的值，然后根據該組件圖元左右兩側擁有的連接圖元的個數來設置組件圖元的長度；

S60：使用Mikami-Tabuchi布線算法布置圖元之間的連線的路徑，當連線出現重疊時，使用近鄰連線避讓策略消除重疊。

進一步的，步驟S20中對組件圖元進行拓撲排序的具體包括：

S201：完成對不構成連線環路、且不孤立的圖元的層次設置；將無直接前驅的圖元層次數設置為固定值，其他圖元的層次數為其所有直接前驅中層次數最大的加上1；

S202：對構成連接環路的圖元，將環路中層次數最低的任意一個圖元的層次數設置為當前的層次數加1,然后將這些圖元重新加入到排序中；如果仍然存在連接環路，則重復執行該步驟；

S203：對于孤立的圖元，將孤立的圖元的層次數依次設置為1,2,3…n，n為正整數；當某個孤立圖元的層次數達到n時，如果仍有孤立的圖元，則對剩余的圖元重新從1開始編號，直至結束。

進一步的，步驟S40包括：

S401：:將每個組件圖元長度、寬度設置為固定相同的值，令同一個層次中的圖元在本層次中根據垂直的距離均勻分布，并令其水平位置相同；

S402：使用每個圖元的重心代表該圖元的位置，計算所有存在連接的圖元之間的曼哈頓距離，其中：如果兩個連接圖元之間有多條連接，則在計算兩者距離時，每條連接的距離計算一次；最終得到當前布局情況下，各個圖元之間的距離的總和；

S403：調整每個層次中的組件圖元的垂直方向的位置，保證每個組件圖元水平方向不變，垂直方向均勻分布，重新按照步驟S402計算距離值；最終將距離值最小的圖形布局設置為最終布局。

進一步的，步驟S50還包括：

如果連接圖元具有大小，則將連接圖元大小固定，然后每個連接圖元相距等同的距離，分別計算組件圖元左右兩邊的長度，取兩者中長度較大的那個作為組件圖元的最終長度；

如果連接圖元沒有大小時，則將連接圖元之間的距離設置為相同的值，分別計算組件圖元左右兩邊的長度，取兩者中長度較大的那個作為組件圖元的最終長度。