流程圖布局算法實現

邊旭 王明興 黎俊茂 陳曉晴

摘要：在工作流工具系統中，用戶會依據復雜的業務邏輯來建立不同的工作流程圖，來描繪不同操作的流程。在這種情況下，用戶手工創建的流程圖因含有實際的業務邏輯，通常復雜、混亂。為了滿足工業工具的實際需要，需要發明一種高效、準確的流程圖自動布局方法，快速合理布局復雜的流程圖，準確體現數據的流向和清晰展現節點中蘊含的邏輯關系。

關鍵詞：流程圖 布局 算法

中圖分類號：TP391 文獻標識碼：A 文章編號：1007-9416（2016）05-0000-00

1現狀分析

隨著互聯網的快速發展和社會各領域信息化水平的提高，數據量正以史無前例的速度井噴。在大數據時代，處理海量數據的抽取和加工的工作流工具系統有著非常重要的工業用途。在工作流工具系統中，用戶會依據復雜的業務邏輯來建立不同的工作流程圖，來描繪不同操作的流程。在這種情況下，用戶手工創建的流程圖因含有實際的業務邏輯，通常復雜、混亂。為了滿足工業工具的實際需要，需要發明一種高效、準確的流程圖自動布局方法，快速合理布局復雜的流程圖，準確體現數據的流向和清晰展現節點中蘊含的邏輯關系。

流程圖布局算法有多種，國際商業機器公司[1]和恒生電子股份有限公司[2]都提出應用于工業的突出主線的流程圖自動布局方法。另一方面，層次化的流程圖布局算法也得到了廣泛關注，多種布局算法[3]根據拓撲順序（概念見圖1）對流程圖進行層次化布局。

本方法的輸入是一組邏輯關系數據。P1：從已知數據中抽取出節點信息和它們的邏輯關聯；P2：分析節點的邏輯關系，為節點們劃分等級；P3：優化級別相同的節點們的排列方式，達到合理布局，并計算節點們的坐標值；P4：根據坐標值，建立繪制流程圖。

1.1相關研究

學術界，存在多種流程圖層次化布局算法，它們都遵循了圖1的流程。不同的是，在P3步驟，不同的方法，采用了不同的解決方法。其中最具代表性的是Sugiyama[3]的算法，它通過用矩陣來表示流程圖的節點關系，來分析優化節點的布局，讓流程圖的交叉線最小，連線距離最短。Sugiyama算法的流程圖如圖2。

已有的層次化流程圖布局算法，它們的流程圖分析算法（P3步驟）過于復雜，無法滿足工業高效、簡潔的需求。本方法發明了一種全新的流程圖布局的分析優化方法，高效、簡潔地實現了蘊含的復雜邏輯關系的工作流節點的層次化布局，滿足了大數據工業應用的工作流程圖布局要求。

1.2 本文實現方法和效果

本發明實施了在大數據處理的工作流的應用場景下，一種準確、高效的流程圖布局分析優化算法。在大數據工作的工作流工具里，每個工作節點間存在復雜的邏輯關系，而用戶很難將節點合理的分布在工作流頁面里。在這種情況下，需要一個高效、準確的流程圖布局分析優化算法，快速合理布局層次化的復雜流程圖。

2算法實現

基本概念定義：邏輯關系。邏輯關系的含義非常豐富，在我們的方法里，它特指事件（抽象為節點）間建立的帶有順序性、業務邏輯性的關聯關系。例如：一個邏輯關系，表明事件A和B關聯，且只有A事件發生，B事件才有可能發生。

2.1邏輯節點（Node）

每一個事件，我們都把它抽象為一個節點。當節點間包含邏輯關系，我們稱這樣的節點叫邏輯節點。

每個節點里都包含以下信息：節點的名稱（NodeName），子節點的列表（List outNodes），父節點的列表（List inNodes），出度（outNum），入度（inNum），層次（Level）。

子節點：當前節點的下一個邏輯節點（outNode）；

父節點：當前節點的前一個邏輯節點（inNode）；

入度：一個邏輯節點的父節點的個數；

初始邏輯節點：入度為0的邏輯節點是初始節點。

2.2連線（Link）

描述兩個節點間的邏輯關系，每條連線里包含它的起始節點（startNode）和結束節點（endNode）.

下面給出一個例子來描述上面定義：

例1：一組邏輯關系{，抽象后，我們得到8個節點{A、B、C、D、E、F、G、H}和9條連線{（A，D）、（A，E）、（B，F）、（B，E）、（B，H）、（C，G）、（D，G）、（D，H）、（E，H）}。

2.3等級（Level）

一個邏輯節點在所給邏輯關系中的級別，它包含了這個邏輯節點在邏輯關系中的順序特性。等級越低的邏輯節點在邏輯關系中，代表越先發生的事件，往往是前驅事件。

2.4深度優先遍歷

是數據遍歷的基本方法之一，在本方法中指按照邏輯關系所蘊含的順序，從邏輯的起始節點到結束節點遍歷的方法，并且，盡可能遍歷到沒有子節點的邏輯節點為止。并且，不同于其他深度遍歷方法，我們的深度優先遍歷，會重復遍歷節點。

例如：在上面的例子中，起始節點是A、B、C，按照深度遍歷。起始點A下面的遍歷，依次通過的連線為（A，D）、（D，G）、（D，H）、（A，E）、（E，H）， 因此遍歷節點順序為，同理，B的遍歷節點順序為C的遍歷節點順序為。

3一組邏輯節點等級劃分方法

給定一組邏輯關系，本方法提取每個事件元素作為一個節點，通過分析已知的邏輯關系， 給這些邏輯節點劃分等級，設置等級值（level）。

方法實施核心過程詳細介紹如下：

方法的輸入是從數據中提取的一組邏輯節點（Nodes）和它們的邏輯關系（Links），如例1。

P1：

根據給定的邏輯關系，其蘊含了節點之間的邏輯順序，我們根據這些信息，首先計算每個節點的入度。根據入度的定義，例1中各個邏輯節點的入度的值見下表1。

根據表1，我們可以定位，初始節點是A、B、C節點。

P2和P3：循環遍歷設定邏輯節點的等級（Layer算法）

當我們定位了邏輯關系中所有的初始節點，我們依次對每個初始節點進行深度優先遍歷，在這個遍歷過程中，我們要依次設置各個節點的等級。因此，P2和P3步驟是循環進行的，每次遍歷一個節點，都要對其的等級進行設定。

在Layer算法的遍歷中，我們遵循以下三個原則：

（1）起始邏輯節點的等級是1；（2）依次遍歷初始節點，沿著其連線深度遍歷，每個當前邏輯節點的等級等于父節點的等級加1；（3）當一個節點有不止一個父節點的時候，它的等級由等級最高的那個父節點決定。

Layer算法的詳細流程：例如例1：依次遍歷A、B、C三個初始邏輯節點，依據上面的遍歷和等級定義原則，各節點的等級如表2。

其中，節點H有三個父節點B、D、E，因此它的等級由等級較高的D和E決定，為3。

P4：優化邏輯節點的等級

例1中，我們注意到初始節點C，有且僅有一個子節點G；即，邏輯節點C只和一個邏輯節點G在邏輯上具有關聯性，它們是息息相關的。然而，在Layer方法計算得到表2中，節點C和G的等級差異為2，無法正確體現邏輯節點間緊密相關的關系。對這類情況，P4步驟對節點的等級進行了優化。

根據上述的流程，我們當且僅當，優化初始節點和它最近級別的子節點的等級差距大于1的時候，對初始節點的等級進行優化。例1中，雖然初始節點B和它的子節點H的等級差距為2，方法并不會對邏輯節點B進行優化，因為它的其他子節點E和F的等級為1，和它非常接近。

經過調整，我們得到最終的優化后的各個邏輯節點的等級如表3。

4結語

在分析研究現有流程圖布局的基礎之上，本文提出了一種新的流程圖布局的算法。并將該算法應用在了實際布局上，效果較已有方法更好。

參考文獻

[1]專利：處理圖形對象的方法、設備及系統，國際商業機器公司，申請號：200910132268.X.

[2]專利：實現流程圖自動調整布局的方法及裝置，恒生電子股份有限公司，申請號：200910246003.2.

[3]K.Sugiyama，S.Tagawa，and M.Toda. Methods for visual understanding of hierarchical system structures.SMC-11（2）：109–125，February1981.