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

有效

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

1.一種GMF圖形編輯器創建有向圖的自動布局方法，其特征在于，包括如下步驟：

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

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

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

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

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

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

2.根據權利要求1所述的GMF圖形編輯器創建有向圖的自動布局方法，其特性在于，步驟S20中對組件圖元進行拓撲排序的具體包括：

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

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

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

3.根據權利要求1或2所述的GMF圖形編輯器創建有向圖的自動布局方法，其特性在于，步驟S40包括：

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

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

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

4.根據權利要求3所述的GMF圖形編輯器創建有向圖的自動布局方法，其特性在于，步驟S50還包括：

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

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

5.根據權利要求1或4所述的GMF圖形編輯器創建有向圖的自動布局方法，其特性在于，所述近鄰連線避讓策略包括：首先檢測重疊路徑兩側某距離的地方是否有布線，如果沒有則隨機選擇一邊進行布線；否則增加檢測的距離，直至找到一個合適的路徑為止。