基于Sugiyama的流程圖自動生成算法

摘 要：為了解決流程圖繪制效率低下的問題，更好地保證軟件模型、文檔與代碼的一致性，提出了一種流程圖自動生成算法。首先，通過逆向分析C/C++源代碼，提取代碼的Token列表，生成Scope樹，從而生成流程圖。同時，提出了一種規范代碼函數體注釋的方法，提高流程圖的可理解性。最后，應用Sugiyama布局算法，并對坐標指定步驟進行補充改進，對流程圖進行了自動布局，最終生成可讀流程圖。實際應用過程中，所提算法有效地提高了軟件設計文檔的編寫效率，保證了軟件模型、文檔與代碼的一致性。

關鍵詞：流程圖自動生成;源代碼逆向分析;流程圖自動布局;Sugiyama布局算法; 軟件逆向工程

中圖分類號： TP391.4文獻標志碼：A

Flowchart automatic generation algorithm base on Sugiyama

LIANG Baiou*

（Southwest China Institute of Electronic Technology， Chengdu Sichuan 610036， China）

Abstract： In order to solve the problem of low efficiency of flowchart drawing and better guarantee the consistency of software model， document and code， an algorithm for automatic generation of flowchart was proposed. Firstly， by analyzing the C/C++ source code in reverse， the Token list of the code was extracted， and the Scope tree was created to realize the flowchart generation. At the same time， a method for regulating the annotation of code functions was proposed， improving the comprehensibility of the flowchart. Finally， the readable flowchart was generated after the automatic layout of flowchart by applying the Sugiyama layout algorithm and completing and improving the coordinate designation step. In the actual application process， with the use of the proposed algorithm， the efficiency of writing software design documents is effectively improved and the consistency of the software model， document and code is guaranteed.

Key words： flowchart automatic generation; source code reverse analysis; flowchart automatic layout; Sugiyama layout algorithm; software reverse engineering

0 引言

隨著軟件規模的與日俱增，大規模的系統軟件開發不能完全照搬瀑布模型的流程，更多地采用迭代和增量的開發模型。設計模型會影響程序代碼的編寫，程序代碼的實現細節也會同樣影響設計模型的架構。從設計轉換到實現成為正向工程，從實現反推設計稱為逆向工程[1-2]。

軟件設計的正向工程，一般需要進行軟件的概要設計和詳細設計，在詳細設計中通常需要采用流程圖或活動圖來描述軟件的邏輯處理流程。在常規的軟件建模工具中，用戶會根據業務具體邏輯來手工繪制流程圖，這一過程因為業務的復雜性以及繪圖的繁瑣性，常常需要耗費大量的時間和人力成本，另一方面，需求的變更很可能導致已經設計好的流程圖完全作廢，開發人員為了趕進度，直接跳過設計步驟，直接編寫代碼，最終導致設計模型和通用程序設計語言（如C++和Java）之間存在著語法和語義不一致現象[3]。

因此，軟件建模工具不僅需要支持軟件設計的正向工程，更需要解決軟件設計的逆向工程。通過調研國內外的軟件建模工具，大多數建模工具如Enterprise Architect、starUML、Rational Rose、Rational Rhapsody等工具都支持根據代碼生成軟件的類圖，但是幾乎都不支持根據源代碼生成函數級別的流程圖。

為了保證文檔與代碼的一致性，以及降低手動繪制流程圖的繁瑣性，本文提出了一種根據C/C++軟件源代碼自動生成函數級別流程圖的解決方案。該解決方案主要涉及C/C++源代碼的逆向分析技術，提取其中的流程關鍵字和注釋信息;然后根據提取的信息生成流程圖的圖形元素節點，以及圖形元素節點的連線;最后采用Sugiyama布局算法[4]，對流程圖進行自動布局，提高了流程圖的可讀性。

1 流程圖自動生成的基本流程

流程圖自動生成過程分為以下幾個大的步驟：

1）首先通過分析C/C++源代碼的語義，提取Token列表，構建Scope樹。

2）然后根據Scope樹，提取順序、分支、循環結構，生成流程圖的節點和邊的圖形場景，節點的位置（x，y）都初始化為0，邊無彎曲點。

3）根據Sugiyama自動布局算法，對流程圖的節點和邊進行自動布局，算出節點的位置以及邊的彎曲點。

4）根據算出的節點位置和邊的彎曲點信息，重新調整流程圖的場景。

2 源代碼逆向分析算法

2.1 基本定義

源代碼逆向分析算法主要由源代碼Token鏈表創建、Scope樹創建以及流程圖場景結構創建三部分組成。源代碼的相關定義描述如下：

1）Token記為T，是源代碼最小且不可分割的部分，不能存在空格、制表符和回車換行符。T=（Text， Tnext， Tlink），其中Tnext表示該Token在源代碼中的緊接著的下一個Token，Tlink表示該Token有關聯的Token，以（）、{}、[]作為關聯判斷字符。

2）源代碼記為C，可由Token來表示。C=∪ni=1Ti，（Ti∩Tj=， i≠j），其中Ti表示一個Token。

Scope記為S，表示一段有意義的代碼范圍。S=（Type，Thead，Tstart，Tend，Sparent，Schildren， Detail）。其中：Type表示該Scope的類型，如（類、函數、結構體、命名空間、函數、if、else、for、while、do、switch、try、catch、枚舉等）;Thead表示該Scope頭的Token，以class、struct、namespace、函數名、if、else、for、while、do、switch、try、catch、enum等字符串開始;Tstart表示該Scope體的開始Token，固定為{字符;Tend表示該Scope的結束Token，固定為}字符;Sparent表示該Scope的父Scope，Schildren表示該Scope的一個或多個子Scope;Detail表示該Scope的一些特殊的詳細信息，一般以Type來區分。

2.2 Token鏈表創建算法

Token鏈表創建算法就是將C劃分為多個Ti的算法，其算法流程描述如下：

輸入 C/C++源代碼文件;

輸出 Token鏈表。

1）打開并讀取文件，將代碼標準化，即將所有制表符、回車換行都替換為空格，并開始記錄Token。

2）判斷文件是否讀取結束，如果結束，則結束記錄Token。然后遍歷Token鏈表，在for、while、switch、do、if、else的Token后面判斷是否存在{的Token，如果不存在，則添加“{”的Token，并找到最近的“;”Token，在其之后增加“}”的Token。最后遍歷Token鏈表根據（）、{}、[]的Token信息建立Token的Tlink節點信息。

3）如果文件讀取未結束，則判斷當前字符是否為字母、數字、下劃線，如果是，讀取下一個字符，并執行步驟2）;否則結束記錄Token，并繼續。

4）如果當前字符不為空格，則創建Token，并加入鏈表繼續。

5）讀取下一個字符，并開始記錄Token，繼續步驟2）。

一段C代碼：“if（ab<=10）c=3;”，通過執行Token鏈表創建算法后，最終得到的Token鏈表如圖1所示。

2.3 Scope樹創建算法

Scope樹創建算法就是將Ti組合成S樹的算法，其算法流程如圖2所示，具體步驟描述如下。

輸入 Token鏈表。

輸出 Scope樹。

1）初始化token變量為鏈表頭，初始化parentScope變量、Scope樹的根節點scopeRoot，創建Scope棧stack。

2）當前訪問token如果為空，則算法結束，否則繼續。

3）訪問當前Scope棧頂的對象，記為s，如果s（Tend）等于當前token，則表示當前Scope已經組裝完成，彈出棧頂，如果棧已空，則Scope樹的根節點，就是當前彈出的棧頂Scope;如果不相等，則繼續執行步驟5）。

4）當前token的文字信息是否等于class、struct、namespace、if、else、for、while、do、switch、try、catch、enum等字符串，如果不相等，則繼續執行步驟5）;否則表示一個新的Scope，創建對象，記為s。s（Type）為當前token的文字信息類別;s（Thead）為當前token;s（Tstart）為當前token的下一個token所關聯的下一個token（token.next.link.next）;s（Tend）為s（Tstart）的下一個token。如果棧頂的Scope不為空，則表示棧頂的Scope為當前創建Scope的父節點，從而創建父子關系。最后將該Scope壓入棧。

5）設置當前token為下一個token，繼續執行步驟2）。

一段C代碼：“if（ab<=10）c=3;”，通過Token鏈表創建算法形成如圖1的Token鏈表，再通過Scope樹創建算法執行后，Scope結構如圖3所示，如果存在嵌套的代碼，則會形成一棵Scope樹。最終通過以上兩個算法運算后，就可以將源代碼轉換為一個可以訪問任意內容的樹形加鏈表的結構，為流程圖的場景的創建提供基本支撐。

2.4 流程圖結構創建

流程圖的基本結構分為順序結構、分支結構、循環結構。而C/C++代碼的一個函數由if-else、switch、for、while、do-while的Scope樹組成，這些結構的代碼與流程圖的片段對應關系如表1所示。

流程圖結構創建算法的基本思想為：識別一個函數類型的Scope后，再深度優先遍歷該函數Scope下的Scope子節點，再根據不同的Scope子節點類型創建對應的流程圖圖元，便可以生成基于函數級別的流程圖的節點和邊信息。

創建的菱形或矩形框中的文字，默認情況下為具體的代碼，為了增強流程圖的可理解性，本文采用添加特殊注釋的方法來提升流程圖的可讀性。不同的Scope類型，采用不同的注釋方式。例如以下代碼，生成的流程圖如圖4所示。

3 流程圖自動布局算法

3.1 可讀流程圖的定義

一個可讀的流程圖是一個層次圖，應滿足以下標準[5]：邊的方向盡量一致，圖要緊湊，布局具有對稱性，盡量避免長邊、減少邊的彎曲，減少連線的交叉，保持節點的均衡。

可讀性流程圖的定義 一個有向圖G=（V，E，n），其中，V為流程圖的節點集合，E為流程圖的邊集合，n為流程圖的高度，并滿足以下性質：

1） V被劃分為n個非空子集合， 即V=∪ni=1Li，Li∩Lj=（ i≠j），Li為流程圖的第i層，記第i層的節點數為|Li|。

2）對每條邊e（u，v）∈E，若u∈Li，v∈Lj，則有i > j。

3）如果邊e（u，v）∈E，u∈Li，v∈Lj， i>j， 那么邊e（u，v）的跨度span（i， j）=i-j，稱跨度大于1的邊為長邊。

4） Li層的寬度為W（Li）=∑v∈Liv（w），其中v（w）為節點的寬度。圖的總寬度為Wmax=max1≤i≤n W（Li）。

為了生成可讀流程圖，本文采用Sugiyama布局算法對流程圖的邊和節點進行自動布局，標準的Sugiyama算法由分層指定、交叉減少、坐標指定三個步驟組成[6]。

3.2 層次指定

層次指定主要完成將流程圖的節點指定到特定的層中，目前分層算法主要有最長路徑算法LPL（Longest Path Layering algorithm）、最小寬度算法（The Coffman-Graham algorithm）、虛擬節點最小化算法（The ILP algorithm of Gansneretal）等[7-8]。本文采用最長路徑算法進行層次指定，該算法描述如下：

1）把所有出度為0的流程圖節點放置在最底層即L1層。

2）將剩下的每個流程圖節點u放置的層數記為L（u），使用以式（1）計算每個流程圖節點的層數。

L（u）=max{i|v∈N+（u）且L（v）=i}+1（1）

其中N+（u）={v∈V|（u，v）∈E}。

3.3 交叉減少

交叉減少主要完成重排層內節點和彎曲點（虛擬節點），減少邊的交叉數量。流程圖布局中，邊交叉最小化是主要目的，邊交叉度越小流程圖的布局越清晰，更便于理解。針對整幅圖的交叉減少算法稱為K-層交叉減少算法，可被分解為2層交叉減少算法。邊交叉數目取決于每層中節點的排列順序，減少邊交叉的問題是一個NP完全問題， 即便是兩層稀疏圖[9]，目前多數算法都是試圖減少邊的交叉，但都不能完全消除其中的交叉。逐層清理（layer-by-layer-sweep）[10]是循環應用2層交叉減少算法從而減少整圖邊交叉數的一般方法。

目前常用的2層交叉算法主要有分支切割啟發式算法（Branch and cut heuristic）、中值啟發式算法（Median heuristic）、貪婪插入啟發式算法（Greedy-insert heuristic）、貪婪交換啟發式算法（Greedy-switch heuristic）、排列啟發式算法（Permutation heuristic）和重心啟發式算法（Barycenter heuristic）等[10-11]。其中排列啟發式算法效果最佳，但它是以O（N?。r間復雜度為代價（N是圖的節點數）。

本文采用的是重心啟發算法，其基本思想是根據節點相關聯的邊在鄰層中的平均重心次序值來重排節點，其中節點的重心次序值的計算方法為式（2）：

b（vij）=∑j∈Li+1πi+1（u）/|Li+1|， i=1

∑j∈Li-1πi-1（u）+∑j∈Li+1πi+1（u）|Li-1∪Li+1|，1

∑j∈Li-1πi-1（u）/|Li-1|， i=n （2）

其中：b（vij）是節點v在第i層第j個節點的重心次序值;u是節點v的鄰層關聯節點;πi（u）表示節點u在第i層中排列次序;Li表示第i層的節點集合，|Li|是第i層節點的總數。

基于重心啟發式的交叉減少算法的步驟描述如下：

輸入 節點排列次序。

輸出 節點重排次序。

1）計算整個流程圖的交叉計數（CrossNum），記為CNold。

2）遍歷Li（1≤i≤n）根據式（2）計算第i層各個節點相對于i-1和i+1層各個節點的b（vij）值，并根據該值從小到大對第i層節點進行排序。

3）計算整個流程圖的交叉計數，記為CNnew，判斷CNnew是否小于CNold，如果小于則繼續執行步驟2），否則認為該算法計算結束。

3.4 坐標指定

坐標指定主要完成所有節點和彎曲點（虛擬節點）的坐標計算，同時試圖減少虛擬節點而引起的過多彎曲點[12]，使圖形布局盡可能地緊湊，跨層邊應盡可能地拉直，從而保證了圖形的易讀性和美觀性。節點的y坐標的計算比較簡單，相同層的y坐標相等，可通過層與層之間的最短距離以及節點本身的高度來計算;而節點的x坐標計算是該步驟的核心。

盡可能減少虛擬節點，常用的算法有促進分層（Promote Layering）算法[12]、路由算法[13]和LP（Linear Program）算法[14-15]。其中促進分層算法通過提升節點層的方法來減少虛擬節點個數;路由算法的基本思想是繞開圖形之間的障礙， 通過折線選擇一條最短路徑進行節點的連接;LP算法通過保證跨層邊盡量拉直，節點間盡量緊湊，從而實現圖形布局的易讀性和美觀性。

本文采用LP算法進行求解，該算法通過式（3）的計算保證了圖形布局盡可能緊湊，式（4）的計算保證了跨層邊盡可能拉直。

設節點u到節點v的一個路徑為p（u，v），p（u，v）=（u，d1，d1，…， dk，v），di（1≤i≤k）表示虛擬節點。

min∑（u，v）∈E|xu-xv|

xw-xz≥ρ（w，z） （3）

min∑ki=1|xdi-ai|

xw-xz≥ρ（w，z） （4）

其中：xi表示節點i的x坐標;ai表示p（u，v）為直線時di的x坐標，計算方法為ai=xu+ik+1（xv-xu）;w和z節點為同層的相鄰節點，其中w在z的右邊; ρ（w，z）為w和z節點的最小距離，計算方法為ρ（w，z）=（Widthw+Widthz）/2+Δx，其中Δx為節點之間的最小間距。

3.5 坐標指定算法的補充改進

流程圖中的循環結構存在反向邊，在Sugiyama布局算法中，將這些邊統一作為正向邊進行處理，圖5是未考慮循環結構反向邊的布局結果。這樣的布局不利于理解循環過程，為了解決該問題，需要對該反向邊進行特殊處理，應用改進后的坐標定位算法后的流程圖的效果如圖6所示。

循環結構的反向邊的源節點記為vs（x，y，w，h），目的節點記為vd（x，y，w，h），其中x和y表示一個矩形左上方的點，w為節點的寬，h為節點的高，重新計算反向邊的彎曲點序列的算法流程描述如下。

1）刪除反向流程邊生產的彎曲點。

2）重新計算反向流程邊的點序列，Δx>5，如果vs（x）+vs（w）2>vd（x）+vd（w）2時，則反向邊的點序列計算方法如式（5），當vs（x）+vs（w）>vd（x）+vd（w）時，i=s;否則i=d。

（x1，y1）=（vs（x）+vs（w），vs（y）+vs（h）2）

（x2，y2）=（vi（x）+vi（w）+Δx，vs（y）+vs（h）2）

（x3，y3）=（vi（x）+vi（w）+Δx，vd（y）+vd（h）2）

（x4，y4）=（vd（x）+vd（w），vd（y）+vd（h）2） （5）

如果vs（x）+vs（w）2≤vd（x）+vd（w）2時，則反向邊的點序列計算方法如式（6），當vs（x）≤vd（x）時，i=s;否則i=d。

（x1，y1）=（vs（x），vs（y）+vs（h）2）

（x2，y2）=（vi（x）-Δx，vs（y）+vs（h）2）

（x3，y3）=（vi（x）-Δx，vd（y）+vd（h）2）

（x4，y4）=（vd（x），vd（y）+vd（h）2） （6）

3）重新將以上點序列加入反向邊中，重新繪制反向邊。

4 實驗結果

通過完成軟件輔助設計平臺軟件的C/C++代碼逆向導入生成流程圖的功能，實現了流程圖自動生成算法。該軟件采用QT4作為界面開發庫，通過QT的場景視圖框架繪制流程圖，采用VS2010開發工具進行開發。支持在線編輯和導入代碼生成流程圖。圖7（a）為不帶注釋的代碼生成流程圖的示例截圖，圖7（b）為帶注釋的代碼生成流程圖的示例截圖。軟件最終通過自動截取生成流程圖的圖片，然后調用Word的API插入到Word文檔中，實現了軟件設計說明文檔的自動生成。該實驗結果說明了該算法能高效根據C/C++源代碼自動逆向生成流程圖，節約了大量的人力成本，保證了代碼和文檔的一致性。

5 結語

本文提出了一種流程圖自動生成的算法，首先提取了代碼的Token列表，構建了Scope樹，生成流程圖場景，同時通過規范代碼注釋格式，使得生成的流程圖更具可理解性。最終對通過Sugiyama布局算法完成流程圖的可讀性布局，并對其中的坐標指定步驟進行了補充改進。

流程圖的自動生成算法在一定程度上解決了代碼逆向工程中的部分問題，提高了文檔生產率，且本文中的布局算法能很好地應用于UML的組件依賴圖、活動圖的自動布局上，但在對類圖、狀態圖、用例圖等圖形的自動布局的應用效果還不夠好，今后將繼續研究相關的自動布局算法。

參考文獻 （References）

[1]王鑫，裘佺，孫洪濤.Halo：基于Eclipse的逆向工程工具[J].計算機工程，2012，38（1）：45-47.（WANG X， QIU Q， SUN H T. Halo： reverse engineering tool based on Eclipse [J]. Computer Engineering， 2012， 38（1）： 45-47.）

[2]BYRNE E J. Software reverse engineering： a case study [J]. Software： Practice and Experience， 1991， 21（12）： 1349-1364.

[3]王鑫，袁曉潔.實現UML二元關系的規范化方法[J].計算機工程，2006，32（21）：79-81.（WANG X， YUAN X J. Normalization method to implement UML binary relationships [J]. Computer Engineering， 2006， 32（21）： 79-81.）

[4]趙國慶，楊南應，賈振洋，等.概念圖的布局算法研究[J].開放教育研究，2005，11（5）：32-37.（ZHAO G Q， YANG N Y， JIA Z Y， et al. Research on algorithm for drawing concept maps [J]. Open Education Research， 2005， 11（5）： 32-37.）

[5]TAMASSIA R. Handbook of Graph Drawing and Visualization [M]. Boca Raton： Chapman and Hall/CRC， 2016： 43-44.

[6]MAZETTI V， SRENSSON H. Visualization of state machines using the Sugiyama framework [D]. Gteborg： Chalmers University of Technology， University of Gothenburg， 2012： 6-11.

[7]胡開寶，張毅坤，趙明.隨程序規模動態調整的通道優化布線算法[J].計算機應用，2013，33（4）：1136-1138，1145.（HU K B， ZHANG Y K， ZHAO M. Optimized channel routing algorithms for dynamically adjusting channel with the program size [J]. Journal of Computer Applications， 2013， 33（4）： 1136-1138， 1145.）

[8]陳建新，唐海.有向無環圖分層算法研究[J].華中師范大學學報：自然科學版，2008，42（3）：359-363.（CHEN J X， TANG H. Research on layered algorithm of directed acyclic graph [J]. Journal of Central China Normal University （Nature Sciences）， 2008， 42（3）： 359-363.）

[9]張毅坤，朱偉，王凱，等.一種基于繼承次序與相關度的布圖算法[J].計算機應用，2009，29（5）：1373-1375.（ZHANG Y K， ZHU W， WANG K， et al. Hierarchical layout algorithm based on order of succession and degree of association [J]. Journal of Computer Applications， 2009， 29（5）： 1373-1375.）

[10]孫軍歡.專用系統人機界面技術研究[D].哈爾濱：哈爾濱工程大學，2009：25-26.（SUN J H. Research on man-machine interface technology of specialized system [D]. Harbin： Harbin Engineering University， 2009： 25-26.）

[11]BACHMAIER C. A radial adaptation of the sugiyama framework for visualizing hierarchical information [J]. IEEE Transactions on Visualization & Computer Graphics， 2007， 13（3）： 583-594.

[12]NIKOLOV N S， TARASSOV A. Graph layering by promotion of nodes [J]. Discrete Applied Mathematics， 2006， 154（5）： 848-860.

[13]孫昌愛，劉超，金茂忠.一種有效的軟件結構圖的布圖算法[J].北京航空航天大學學報，2000，26（6）：705-709.（SUN C A， LIU C， JIN M Z. Effective wove algorithm for software structure graph [J]. Journal of Beijing University of Aeronautics and Astronautics， 2000， 26（6）： 705-709.）

[14]GANSNER E R， KOUTSOFIOS E， NORTH S C， et al. A technique for drawing directed graphs [J]. IEEE Transactions on Software Engineering， 1993， 19（3）： 214-230.

[15]SIX J M， TOLLIS I G. A framework and algorithms for circular drawings of graphs [J]. Journal of Discrete Algorithms， 2006， 4（1）： 25-50.

LIANG Baiou， born in 1982， M. S.， senior engineer. His research interests include software aided design， software architecture of aeronautical communication system.

收稿日期：2019-05-30;修回日期：2019-07-18;錄用日期：2019-07-22。

作者簡介：梁白鷗（1982—），男，四川成都人，高級工程師，碩士，主要研究方向：軟件輔助設計、航空通信系統軟件架構。

文章編號：1001-9081（2019）12-3639-05 DOI：10.11772/j.issn.1001-9081.2019050909