邊旭 王明興 黎俊茂 陳曉晴

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

關(guān)鍵詞：流程圖 布局 算法

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

1現(xiàn)狀分析

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

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

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

1.1相關(guān)研究

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

已有的層次化流程圖布局算法，它們的流程圖分析算法（P3步驟）過于復(fù)雜，無法滿足工業(yè)高效、簡潔的需求。本方法發(fā)明了一種全新的流程圖布局的分析優(yōu)化方法，高效、簡潔地實現(xiàn)了蘊含的復(fù)雜邏輯關(guān)系的工作流節(jié)點的層次化布局，滿足了大數(shù)據(jù)工業(yè)應(yīng)用的工作流程圖布局要求。

1.2 本文實現(xiàn)方法和效果

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

2算法實現(xiàn)

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

2.1邏輯節(jié)點（Node）

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

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

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

父節(jié)點：當前節(jié)點的前一個邏輯節(jié)點（inNode）；

入度：一個邏輯節(jié)點的父節(jié)點的個數(shù)；

初始邏輯節(jié)點：入度為0的邏輯節(jié)點是初始節(jié)點。

2.2連線（Link）

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

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

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

2.3等級（Level）

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

2.4深度優(yōu)先遍歷

是數(shù)據(jù)遍歷的基本方法之一，在本方法中指按照邏輯關(guān)系所蘊含的順序，從邏輯的起始節(jié)點到結(jié)束節(jié)點遍歷的方法，并且，盡可能遍歷到?jīng)]有子節(jié)點的邏輯節(jié)點為止。并且，不同于其他深度遍歷方法，我們的深度優(yōu)先遍歷，會重復(fù)遍歷節(jié)點。

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

3一組邏輯節(jié)點等級劃分方法

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

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

方法的輸入是從數(shù)據(jù)中提取的一組邏輯節(jié)點（Nodes）和它們的邏輯關(guān)系（Links），如例1。

P1：

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

根據(jù)表1，我們可以定位，初始節(jié)點是A、B、C節(jié)點。

P2和P3：循環(huán)遍歷設(shè)定邏輯節(jié)點的等級（Layer算法）

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

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

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

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

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

P4：優(yōu)化邏輯節(jié)點的等級

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

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

經(jīng)過調(diào)整，我們得到最終的優(yōu)化后的各個邏輯節(jié)點的等級如表3。

4結(jié)語

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

參考文獻

[1]專利：處理圖形對象的方法、設(shè)備及系統(tǒng)，國際商業(yè)機器公司，申請?zhí)枺?00910132268.X.

[2]專利：實現(xiàn)流程圖自動調(diào)整布局的方法及裝置，恒生電子股份有限公司，申請?zhí)枺?00910246003.2.

[3]K.Sugiyama，S.Tagawa，and M.Toda. Methods for visual understanding of hierarchical system structures.SMC-11（2）：109–125，F(xiàn)ebruary1981.