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

關(guān)鍵詞：流程圖自動(dòng)生成;源代碼逆向分析;流程圖自動(dòng)布局;Sugiyama布局算法; 軟件逆向工程

中圖分類號(hào)： TP391.4文獻(xiàn)標(biāo)志碼：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 引言

隨著軟件規(guī)模的與日俱增，大規(guī)模的系統(tǒng)軟件開發(fā)不能完全照搬瀑布模型的流程，更多地采用迭代和增量的開發(fā)模型。設(shè)計(jì)模型會(huì)影響程序代碼的編寫，程序代碼的實(shí)現(xiàn)細(xì)節(jié)也會(huì)同樣影響設(shè)計(jì)模型的架構(gòu)。從設(shè)計(jì)轉(zhuǎn)換到實(shí)現(xiàn)成為正向工程，從實(shí)現(xiàn)反推設(shè)計(jì)稱為逆向工程[1-2]。

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

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

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

1 流程圖自動(dòng)生成的基本流程

流程圖自動(dòng)生成過程分為以下幾個(gè)大的步驟：

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

2）然后根據(jù)Scope樹，提取順序、分支、循環(huán)結(jié)構(gòu)，生成流程圖的節(jié)點(diǎn)和邊的圖形場(chǎng)景，節(jié)點(diǎn)的位置（x，y）都初始化為0，邊無彎曲點(diǎn)。

3）根據(jù)Sugiyama自動(dòng)布局算法，對(duì)流程圖的節(jié)點(diǎn)和邊進(jìn)行自動(dòng)布局，算出節(jié)點(diǎn)的位置以及邊的彎曲點(diǎn)。

4）根據(jù)算出的節(jié)點(diǎn)位置和邊的彎曲點(diǎn)信息，重新調(diào)整流程圖的場(chǎng)景。

2 源代碼逆向分析算法

2.1 基本定義

源代碼逆向分析算法主要由源代碼Token鏈表創(chuàng)建、Scope樹創(chuàng)建以及流程圖場(chǎng)景結(jié)構(gòu)創(chuàng)建三部分組成。源代碼的相關(guān)定義描述如下：

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

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

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

2.2 Token鏈表創(chuàng)建算法

Token鏈表創(chuàng)建算法就是將C劃分為多個(gè)Ti的算法，其算法流程描述如下：

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

輸出 Token鏈表。

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

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

3）如果文件讀取未結(jié)束，則判斷當(dāng)前字符是否為字母、數(shù)字、下劃線，如果是，讀取下一個(gè)字符，并執(zhí)行步驟2）;否則結(jié)束記錄Token，并繼續(xù)。

4）如果當(dāng)前字符不為空格，則創(chuàng)建Token，并加入鏈表繼續(xù)。

5）讀取下一個(gè)字符，并開始記錄Token，繼續(xù)步驟2）。

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

2.3 Scope樹創(chuàng)建算法

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

輸入 Token鏈表。

輸出 Scope樹。

1）初始化token變量為鏈表頭，初始化parentScope變量、Scope樹的根節(jié)點(diǎn)scopeRoot，創(chuàng)建Scope棧stack。

2）當(dāng)前訪問token如果為空，則算法結(jié)束，否則繼續(xù)。

3）訪問當(dāng)前Scope棧頂?shù)膶?duì)象，記為s，如果s（Tend）等于當(dāng)前token，則表示當(dāng)前Scope已經(jīng)組裝完成，彈出棧頂，如果棧已空，則Scope樹的根節(jié)點(diǎn)，就是當(dāng)前彈出的棧頂Scope;如果不相等，則繼續(xù)執(zhí)行步驟5）。

4）當(dāng)前token的文字信息是否等于class、struct、namespace、if、else、for、while、do、switch、try、catch、enum等字符串，如果不相等，則繼續(xù)執(zhí)行步驟5）;否則表示一個(gè)新的Scope，創(chuàng)建對(duì)象，記為s。s（Type）為當(dāng)前token的文字信息類別;s（Thead）為當(dāng)前token;s（Tstart）為當(dāng)前token的下一個(gè)token所關(guān)聯(lián)的下一個(gè)token（token.next.link.next）;s（Tend）為s（Tstart）的下一個(gè)token。如果棧頂?shù)腟cope不為空，則表示棧頂?shù)腟cope為當(dāng)前創(chuàng)建Scope的父節(jié)點(diǎn)，從而創(chuàng)建父子關(guān)系。最后將該Scope壓入棧。

5）設(shè)置當(dāng)前token為下一個(gè)token，繼續(xù)執(zhí)行步驟2）。

一段C代碼：“if（ab<=10）c=3;”，通過Token鏈表創(chuàng)建算法形成如圖1的Token鏈表，再通過Scope樹創(chuàng)建算法執(zhí)行后，Scope結(jié)構(gòu)如圖3所示，如果存在嵌套的代碼，則會(huì)形成一棵Scope樹。最終通過以上兩個(gè)算法運(yùn)算后，就可以將源代碼轉(zhuǎn)換為一個(gè)可以訪問任意內(nèi)容的樹形加鏈表的結(jié)構(gòu)，為流程圖的場(chǎng)景的創(chuàng)建提供基本支撐。

2.4 流程圖結(jié)構(gòu)創(chuàng)建

流程圖的基本結(jié)構(gòu)分為順序結(jié)構(gòu)、分支結(jié)構(gòu)、循環(huán)結(jié)構(gòu)。而C/C++代碼的一個(gè)函數(shù)由if-else、switch、for、while、do-while的Scope樹組成，這些結(jié)構(gòu)的代碼與流程圖的片段對(duì)應(yīng)關(guān)系如表1所示。

流程圖結(jié)構(gòu)創(chuàng)建算法的基本思想為：識(shí)別一個(gè)函數(shù)類型的Scope后，再深度優(yōu)先遍歷該函數(shù)Scope下的Scope子節(jié)點(diǎn)，再根據(jù)不同的Scope子節(jié)點(diǎn)類型創(chuàng)建對(duì)應(yīng)的流程圖圖元，便可以生成基于函數(shù)級(jí)別的流程圖的節(jié)點(diǎn)和邊信息。

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

3 流程圖自動(dòng)布局算法

3.1 可讀流程圖的定義

一個(gè)可讀的流程圖是一個(gè)層次圖，應(yīng)滿足以下標(biāo)準(zhǔn)[5]：邊的方向盡量一致，圖要緊湊，布局具有對(duì)稱性，盡量避免長(zhǎng)邊、減少邊的彎曲，減少連線的交叉，保持節(jié)點(diǎn)的均衡。

可讀性流程圖的定義 一個(gè)有向圖G=（V，E，n），其中，V為流程圖的節(jié)點(diǎn)集合，E為流程圖的邊集合，n為流程圖的高度，并滿足以下性質(zhì)：

1） V被劃分為n個(gè)非空子集合， 即V=∪ni=1Li，Li∩Lj=（ i≠j），Li為流程圖的第i層，記第i層的節(jié)點(diǎn)數(shù)為|Li|。

2）對(duì)每條邊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的邊為長(zhǎng)邊。

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

為了生成可讀流程圖，本文采用Sugiyama布局算法對(duì)流程圖的邊和節(jié)點(diǎn)進(jìn)行自動(dòng)布局，標(biāo)準(zhǔn)的Sugiyama算法由分層指定、交叉減少、坐標(biāo)指定三個(gè)步驟組成[6]。

3.2 層次指定

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

1）把所有出度為0的流程圖節(jié)點(diǎn)放置在最底層即L1層。

2）將剩下的每個(gè)流程圖節(jié)點(diǎn)u放置的層數(shù)記為L(zhǎng)（u），使用以式（1）計(jì)算每個(gè)流程圖節(jié)點(diǎn)的層數(shù)。

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

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

3.3 交叉減少

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

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

本文采用的是重心啟發(fā)算法，其基本思想是根據(jù)節(jié)點(diǎn)相關(guān)聯(lián)的邊在鄰層中的平均重心次序值來重排節(jié)點(diǎn)，其中節(jié)點(diǎn)的重心次序值的計(jì)算方法為式（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）是節(jié)點(diǎn)v在第i層第j個(gè)節(jié)點(diǎn)的重心次序值;u是節(jié)點(diǎn)v的鄰層關(guān)聯(lián)節(jié)點(diǎn);πi（u）表示節(jié)點(diǎn)u在第i層中排列次序;Li表示第i層的節(jié)點(diǎn)集合，|Li|是第i層節(jié)點(diǎn)的總數(shù)。

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

輸入 節(jié)點(diǎn)排列次序。

輸出 節(jié)點(diǎn)重排次序。

1）計(jì)算整個(gè)流程圖的交叉計(jì)數(shù)（CrossNum），記為CNold。

2）遍歷Li（1≤i≤n）根據(jù)式（2）計(jì)算第i層各個(gè)節(jié)點(diǎn)相對(duì)于i-1和i+1層各個(gè)節(jié)點(diǎn)的b（vij）值，并根據(jù)該值從小到大對(duì)第i層節(jié)點(diǎn)進(jìn)行排序。

3）計(jì)算整個(gè)流程圖的交叉計(jì)數(shù)，記為CNnew，判斷CNnew是否小于CNold，如果小于則繼續(xù)執(zhí)行步驟2），否則認(rèn)為該算法計(jì)算結(jié)束。

3.4 坐標(biāo)指定

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

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

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

設(shè)節(jié)點(diǎn)u到節(jié)點(diǎn)v的一個(gè)路徑為p（u，v），p（u，v）=（u，d1，d1，…， dk，v），di（1≤i≤k）表示虛擬節(jié)點(diǎn)。

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

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

min∑ki=1|xdi-ai|

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

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

3.5 坐標(biāo)指定算法的補(bǔ)充改進(jìn)

流程圖中的循環(huán)結(jié)構(gòu)存在反向邊，在Sugiyama布局算法中，將這些邊統(tǒng)一作為正向邊進(jìn)行處理，圖5是未考慮循環(huán)結(jié)構(gòu)反向邊的布局結(jié)果。這樣的布局不利于理解循環(huán)過程，為了解決該問題，需要對(duì)該反向邊進(jìn)行特殊處理，應(yīng)用改進(jìn)后的坐標(biāo)定位算法后的流程圖的效果如圖6所示。

循環(huán)結(jié)構(gòu)的反向邊的源節(jié)點(diǎn)記為vs（x，y，w，h），目的節(jié)點(diǎn)記為vd（x，y，w，h），其中x和y表示一個(gè)矩形左上方的點(diǎn)，w為節(jié)點(diǎn)的寬，h為節(jié)點(diǎn)的高，重新計(jì)算反向邊的彎曲點(diǎn)序列的算法流程描述如下。

1）刪除反向流程邊生產(chǎn)的彎曲點(diǎn)。

2）重新計(jì)算反向流程邊的點(diǎn)序列，Δx>5，如果vs（x）+vs（w）2>vd（x）+vd（w）2時(shí)，則反向邊的點(diǎn)序列計(jì)算方法如式（5），當(dāng)vs（x）+vs（w）>vd（x）+vd（w）時(shí)，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時(shí)，則反向邊的點(diǎn)序列計(jì)算方法如式（6），當(dāng)vs（x）≤vd（x）時(shí)，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）重新將以上點(diǎn)序列加入反向邊中，重新繪制反向邊。

4 實(shí)驗(yàn)結(jié)果

通過完成軟件輔助設(shè)計(jì)平臺(tái)軟件的C/C++代碼逆向?qū)肷闪鞒虉D的功能，實(shí)現(xiàn)了流程圖自動(dòng)生成算法。該軟件采用QT4作為界面開發(fā)庫(kù)，通過QT的場(chǎng)景視圖框架繪制流程圖，采用VS2010開發(fā)工具進(jìn)行開發(fā)。支持在線編輯和導(dǎo)入代碼生成流程圖。圖7（a）為不帶注釋的代碼生成流程圖的示例截圖，圖7（b）為帶注釋的代碼生成流程圖的示例截圖。軟件最終通過自動(dòng)截取生成流程圖的圖片，然后調(diào)用Word的API插入到Word文檔中，實(shí)現(xiàn)了軟件設(shè)計(jì)說明文檔的自動(dòng)生成。該實(shí)驗(yàn)結(jié)果說明了該算法能高效根據(jù)C/C++源代碼自動(dòng)逆向生成流程圖，節(jié)約了大量的人力成本，保證了代碼和文檔的一致性。

5 結(jié)語

本文提出了一種流程圖自動(dòng)生成的算法，首先提取了代碼的Token列表，構(gòu)建了Scope樹，生成流程圖場(chǎng)景，同時(shí)通過規(guī)范代碼注釋格式，使得生成的流程圖更具可理解性。最終對(duì)通過Sugiyama布局算法完成流程圖的可讀性布局，并對(duì)其中的坐標(biāo)指定步驟進(jìn)行了補(bǔ)充改進(jìn)。

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

參考文獻(xiàn) （References）

[1]王鑫，裘佺，孫洪濤.Halo：基于Eclipse的逆向工程工具[J].計(jì)算機(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]王鑫，袁曉潔.實(shí)現(xiàn)UML二元關(guān)系的規(guī)范化方法[J].計(jì)算機(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]趙國(guó)慶，楊南應(yīng)，賈振洋，等.概念圖的布局算法研究[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]胡開寶，張毅坤，趙明.隨程序規(guī)模動(dòng)態(tài)調(diào)整的通道優(yōu)化布線算法[J].計(jì)算機(jī)應(yīng)用，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]陳建新，唐海.有向無環(huán)圖分層算法研究[J].華中師范大學(xué)學(xué)報(bào)：自然科學(xué)版，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]張毅坤，朱偉，王凱，等.一種基于繼承次序與相關(guān)度的布圖算法[J].計(jì)算機(jī)應(yīng)用，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]孫軍歡.專用系統(tǒng)人機(jī)界面技術(shù)研究[D].哈爾濱：哈爾濱工程大學(xué)，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]孫昌愛，劉超，金茂忠.一種有效的軟件結(jié)構(gòu)圖的布圖算法[J].北京航空航天大學(xué)學(xué)報(bào)，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。

作者簡(jiǎn)介：梁白鷗（1982—），男，四川成都人，高級(jí)工程師，碩士，主要研究方向：軟件輔助設(shè)計(jì)、航空通信系統(tǒng)軟件架構(gòu)。

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