国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

流程圖布局算法實(shí)現(xiàn)

2016-05-14 04:04邊旭王明興黎俊茂陳曉晴
關(guān)鍵詞:流程圖布局算法

邊旭 王明興 黎俊茂 陳曉晴

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

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

中圖分類號(hào):TP391 文獻(xiàn)標(biāo)識(shí)碼:A 文章編號(hào):1007-9416(2016)05-0000-00

1現(xiàn)狀分析

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

流程圖布局算法有多種,國(guó)際商業(yè)機(jī)器公司[1]和恒生電子股份有限公司[2]都提出應(yīng)用于工業(yè)的突出主線的流程圖自動(dòng)布局方法。另一方面,層次化的流程圖布局算法也得到了廣泛關(guān)注,多種布局算法[3]根據(jù)拓?fù)漤樞颍ǜ拍钜妶D1)對(duì)流程圖進(jìn)行層次化布局。

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

1.1相關(guān)研究

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

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

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

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

2算法實(shí)現(xiàn)

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

2.1邏輯節(jié)點(diǎn)(Node)

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

每個(gè)節(jié)點(diǎn)里都包含以下信息:節(jié)點(diǎn)的名稱(NodeName),子節(jié)點(diǎn)的列表(List outNodes),父節(jié)點(diǎn)的列表(List inNodes),出度(outNum),入度(inNum),層次(Level)。

子節(jié)點(diǎn):當(dāng)前節(jié)點(diǎn)的下一個(gè)邏輯節(jié)點(diǎn)(outNode);

父節(jié)點(diǎn):當(dāng)前節(jié)點(diǎn)的前一個(gè)邏輯節(jié)點(diǎn)(inNode);

入度:一個(gè)邏輯節(jié)點(diǎn)的父節(jié)點(diǎn)的個(gè)數(shù);

初始邏輯節(jié)點(diǎn):入度為0的邏輯節(jié)點(diǎn)是初始節(jié)點(diǎn)。

2.2連線(Link)

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

下面給出一個(gè)例子來(lái)描述上面定義:

例1:一組邏輯關(guān)系{,抽象后,我們得到8個(gè)節(jié)點(diǎn){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等級(jí)(Level)

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

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

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

例如:在上面的例子中,起始節(jié)點(diǎn)是A、B、C,按照深度遍歷。起始點(diǎn)A下面的遍歷,依次通過(guò)的連線為(A,D)、(D,G)、(D,H)、(A,E)、(E,H), 因此遍歷節(jié)點(diǎn)順序?yàn)?,同理,B的遍歷節(jié)點(diǎn)順序?yàn)镃的遍歷節(jié)點(diǎn)順序?yàn)椤?/p>

3一組邏輯節(jié)點(diǎn)等級(jí)劃分方法

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

方法實(shí)施核心過(guò)程詳細(xì)介紹如下:

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

P1:

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

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

P2和P3:循環(huán)遍歷設(shè)定邏輯節(jié)點(diǎn)的等級(jí)(Layer算法)

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

在Layer算法的遍歷中,我們遵循以下三個(gè)原則:

(1)起始邏輯節(jié)點(diǎn)的等級(jí)是1;(2)依次遍歷初始節(jié)點(diǎn),沿著其連線深度遍歷,每個(gè)當(dāng)前邏輯節(jié)點(diǎn)的等級(jí)等于父節(jié)點(diǎn)的等級(jí)加1;(3)當(dāng)一個(gè)節(jié)點(diǎn)有不止一個(gè)父節(jié)點(diǎn)的時(shí)候,它的等級(jí)由等級(jí)最高的那個(gè)父節(jié)點(diǎn)決定。

Layer算法的詳細(xì)流程:例如例1:依次遍歷A、B、C三個(gè)初始邏輯節(jié)點(diǎn),依據(jù)上面的遍歷和等級(jí)定義原則,各節(jié)點(diǎn)的等級(jí)如表2。

其中,節(jié)點(diǎn)H有三個(gè)父節(jié)點(diǎn)B、D、E,因此它的等級(jí)由等級(jí)較高的D和E決定,為3。

P4:優(yōu)化邏輯節(jié)點(diǎn)的等級(jí)

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

根據(jù)上述的流程,我們當(dāng)且僅當(dāng),優(yōu)化初始節(jié)點(diǎn)和它最近級(jí)別的子節(jié)點(diǎn)的等級(jí)差距大于1的時(shí)候,對(duì)初始節(jié)點(diǎn)的等級(jí)進(jìn)行優(yōu)化。例1中,雖然初始節(jié)點(diǎn)B和它的子節(jié)點(diǎn)H的等級(jí)差距為2,方法并不會(huì)對(duì)邏輯節(jié)點(diǎn)B進(jìn)行優(yōu)化,因?yàn)樗钠渌庸?jié)點(diǎn)E和F的等級(jí)為1,和它非常接近。

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

4結(jié)語(yǔ)

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

參考文獻(xiàn)

[1]專利:處理圖形對(duì)象的方法、設(shè)備及系統(tǒng),國(guó)際商業(yè)機(jī)器公司,申請(qǐng)?zhí)枺?00910132268.X.

[2]專利:實(shí)現(xiàn)流程圖自動(dòng)調(diào)整布局的方法及裝置,恒生電子股份有限公司,申請(qǐng)?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.

猜你喜歡
流程圖布局算法
基于MapReduce的改進(jìn)Eclat算法
Travellng thg World Full—time for Rree
進(jìn)位加法的兩種算法
VR布局
專利申請(qǐng)審批流程圖
專利申請(qǐng)審批流程圖
一種改進(jìn)的整周模糊度去相關(guān)算法
2015 我們這樣布局在探索中尋找突破
Face++:布局刷臉生態(tài)
寧??h村級(jí)權(quán)力清單36條