基于迷宮算法思想的梯形圖向AOV圖的轉(zhuǎn)換

王吉停，張得禮，周來水

(南京航空航天大學(xué)機電學(xué)院，江蘇 南京，210016)

軟PLC的編程語言遵循IEC61131—3標(biāo)準(zhǔn)，該標(biāo)準(zhǔn)定義了5種PLC編程語言，其中梯形圖沿襲了傳統(tǒng)控制圖的表達(dá)方式，具有直觀明了、易于掌握等特點[1]，但其對于PLC來說是不可執(zhí)行代碼，無法直接運行，而指令表是一種用于嵌入式平臺且能直接轉(zhuǎn)化為二進制代碼的匯編語言，因此，在PLC軟件開發(fā)過程中，實現(xiàn)梯形圖向指令表程序的轉(zhuǎn)換有利于軟件的整合和解讀，通過對指令表的編譯或解釋執(zhí)行便可實現(xiàn)PLC程序的邏輯控制。目前關(guān)于梯形圖向指令表轉(zhuǎn)換的研究中，大多都用到了中間數(shù)據(jù)結(jié)構(gòu)AOV圖[2-7]。AOV圖能很好地反映梯形圖各元件之間的連接關(guān)系，與梯形圖有良好的對應(yīng)關(guān)系，相比直接將梯形圖轉(zhuǎn)化為指令表的方法來說，AOV圖能提高轉(zhuǎn)化效率。

梯形圖向AOV圖轉(zhuǎn)換算法的難點在于梯形圖中各元件直接前驅(qū)和直接后繼元件的確定。文獻(xiàn)[3]和文獻(xiàn)[6]中是通過元件坐標(biāo)來判斷當(dāng)前頂點的直接前驅(qū)和直接后繼頂點，最終實現(xiàn)向AOV圖轉(zhuǎn)換的，但該方法不適合處理串并聯(lián)關(guān)系復(fù)雜的程序，而且可擴展性不好。文獻(xiàn)[4]中提到基于迷宮算法思想的梯形圖向AOV圖轉(zhuǎn)換的算法，但沒有具體闡述。本文利用迷宮算法思想來確定梯形圖各元件的直接前驅(qū)和直接后繼元件，并給出了具體的實現(xiàn)方法。

1 AOV圖數(shù)據(jù)結(jié)構(gòu)

用頂點表示活動, 用弧〈i,j〉表示活動i必須在活動j開始之前完成。這種有向圖叫作用頂點表示活動的AOV 圖。對〈i,j〉弧而言,i是j的直接前驅(qū),j是i的直接后繼。采用十字鏈表[8]存儲結(jié)構(gòu)對AOV圖進行存儲，易于計算頂點的出度和入度。

一個梯形圖程序是由多個梯級網(wǎng)絡(luò)組成的，每個梯級網(wǎng)絡(luò)又由各種圖符構(gòu)成，包括功能單元圖符、連接單元圖符以及空單元。各個梯級網(wǎng)絡(luò)內(nèi)的梯形圖本質(zhì)上對應(yīng)著一個有向圖, 其中各功能單元圖符可以抽象為有向圖中的頂點, 連接單元圖符可以抽象為有向圖中的弧。

為簡化轉(zhuǎn)換算法，將梯形圖中的圖符元件對應(yīng)的AOV圖頂點分為以下4種類型：

(1)源頂點SNode。將左側(cè)起始線作為一類特殊的元件保存在相應(yīng)的對象中，作為AOV圖的起始標(biāo)志，存儲在Xlist[0]中，其入度為0，出度大小由程序需要決定。

(2)尾頂點TNode。將右側(cè)終止線也作為一類特殊的元件保存在相應(yīng)的對象中，作為AOV圖的結(jié)束標(biāo)志，存儲在頂點數(shù)組的最后位置處，出度為0，入度大小由程序結(jié)構(gòu)決定。

(3)豎直元件頂點VNode。豎直線連接元件作為各行之間連接關(guān)系的標(biāo)志，本程序?qū)⒕哂兄苯舆B接關(guān)系并且列值相等、行值最小的豎直線元件作為一類頂點VNode，其出度和入度均不小于1。

(4)功能元件(水平線元件除外)作為另一類頂點FNode，其入度和出度均為1。

2 梯形圖向AOV圖轉(zhuǎn)換算法描述

梯形圖向AOV圖轉(zhuǎn)換分為3個階段。第一階段：確定AOV圖的所有頂點。對當(dāng)前梯形圖按從左向右、從上向下的順序進行掃描，得到所有的頂點，并存儲在頂點數(shù)組Xlist中。在掃描過程中，豎直連接線元件也作為AOV圖頂點存儲在頂點數(shù)組中，這樣可以避免文獻(xiàn)[6]中提到的“虛頂點”問題；水平連接元件不作任何處理。第二階段：AOV圖各頂點的直接前驅(qū)和直接后繼頂點的掃描。本階段的實現(xiàn)最為關(guān)鍵也最為復(fù)雜，本文利用迷宮算法思想[8]來實現(xiàn)各頂點直接前驅(qū)和直接后繼頂點的掃描，在掃描過程中只掃描當(dāng)前頂點的直接后繼頂點，掃描到直接后繼頂點的同時，將當(dāng)前頂點作為其直接后繼頂點的直接前驅(qū)頂點存儲，這樣省去了直接前驅(qū)頂點的掃描過程，避免了重復(fù)掃描，使算法復(fù)雜度降低。第三階段：AOV圖十字鏈表存儲結(jié)構(gòu)的創(chuàng)建。通過第一、第二階段的處理，已經(jīng)提取出AOV圖的所有頂點及各頂點的直接前驅(qū)和直接后繼連接關(guān)系信息，作一個for 循環(huán), 遍歷各個頂點, 并定位頂點data后繼鏈表中存儲的元素，即得到它們在圖中的頂點編號，然后建立相應(yīng)的弧， 當(dāng)后繼鏈表中指向空時, 就完成了該頂點弧的建立,再作下一個循環(huán), 直至所有頂點都遍歷完畢，這時圖就建立起來了。

3 轉(zhuǎn)換算法的實現(xiàn)

在轉(zhuǎn)換算法執(zhí)行前，定義了以下處理算法：

(1)元件直接前驅(qū)后繼信息的存儲算法Rule_Save(A，B)：將B加入A的直接后繼鏈表中，A加入B的直接前驅(qū)鏈表中。

(2)直接后繼頂點為豎直線頂點的處理算法Rule_Vline：直接后繼頂點為豎直線頂點時，元件右連接屬性向上或向下連接標(biāo)志為真，得到當(dāng)前位置處的豎直線，從而得到與該豎直線有直接連接關(guān)系并且列值相等、行值最小的豎直線C，返回C；若沒有豎直線與當(dāng)前豎直線相連，則返回當(dāng)前位置處的豎直線。

(3)水平線處理算法Rule_Hline：判斷當(dāng)前水平線的右連接屬性，如果只有向右連接屬性，則繼續(xù)向右搜索，直至掃描到功能元件(FNode)或具有其他連接屬性的水平線為止。若為功能元件F，則將功能元件F返回；若為具有其他連接屬性的水平線，則通過調(diào)用算法Rule_Vline得到元件C，返回C。

(4)水平向右處理算法Rule_Right：得到與當(dāng)前元件A同一行的右邊相鄰的元件B。若B為功能元件(FNode)，返回B； 若B為水平線，則通過調(diào)用水平線處理算法Rule_Hline，得到當(dāng)前元件A的直接后繼元件B，再返回B。

轉(zhuǎn)換算法的流程圖如圖1所示。首先，順序遍歷頂點數(shù)組Xlist得到一個頂點，并判斷頂點的類型，然后根據(jù)頂點的類型進行相應(yīng)的掃描處理，直至遍歷完頂點數(shù)組中的所有頂點為止，具體步驟如下：

步驟1：順序遍歷頂點數(shù)組Xlist得到一個頂點A，若A不存在，則轉(zhuǎn)換算法結(jié)束；若A存在，則轉(zhuǎn)步驟2執(zhí)行。

步驟2：判斷當(dāng)前頂點A的類型，利用迷宮算法思想對A進行掃描處理，得到A的直接后繼頂點。不同類型頂點的處理規(guī)則如下：

(1)若當(dāng)前頂點A為功能元件頂點FNode，由前可知，A的出度和入度均為1，可以判斷A的直接前驅(qū)和直接后繼頂點均只有1個，則每當(dāng)確定了A的一個直接后繼頂點后，就停止對A的掃描處理，轉(zhuǎn)向步驟1。

算法中涉及到的功能元件頂點所有可能的右連接屬性如圖2所示。其掃描過程如下：

圖2 功能元件的右連接屬性Fig.2 Right connection properties of functional elements

圖1 轉(zhuǎn)換算法流程圖

① 根據(jù)當(dāng)前頂點A的右連接屬性(向上→向下→向右)，找到所有可能的搜索方向，將搜索路徑存入向量S中，搜索路徑包括頂點名稱和搜索方向。

② 順序遍歷向量S中的所有路徑，若搜索路徑存在，則沿搜索路徑進行搜索，否則轉(zhuǎn)步驟③。搜索是一個匹配的過程，即PLC的假想“電流”在該路徑的方向上要能流通。根據(jù)搜索方向的不同，分以下兩種情況：(a)如果當(dāng)前的搜索方向向上或向下，則停止對當(dāng)前頂點A的掃描，通過調(diào)用算法Rule_Vline得到元件B，再調(diào)用算法Rule_Save(A，B)，轉(zhuǎn)步驟1執(zhí)行；(b)如果當(dāng)前的搜索方向向右，則通過調(diào)用水平向右處理算法Rule_Right，得到當(dāng)前頂點A的直接后繼頂點B，停止對當(dāng)前頂點A的掃描，再調(diào)用算法Rule_Save(A,B)，轉(zhuǎn)步驟1執(zhí)行。

③ 清空向量S，轉(zhuǎn)步驟1執(zhí)行。

(2)若當(dāng)前頂點A為豎直線元件頂點VNode，由于算法的搜索過程是從左向右的，所以只考慮元件的右連接屬性，又由前描述可知，AOV圖中存儲的豎直線頂點是具有直接連接關(guān)系并且列值相等、行值最小的豎直線。所以豎直線頂點的搜索方向只有向右和向下，其入度和出度均可能大于1。該種類型的結(jié)點在本算法中是處理過程最復(fù)雜的部分，也是最關(guān)鍵的部分。算法中涉及到的豎直線元件所有可能的右連接屬性如圖3所示。其掃描過程如下：

圖3 豎直線的右連接屬性Fig.3 Right connection properties of vertical line

① 建立向量L，用來保存當(dāng)前豎直線頂點的直接后繼頂點。設(shè)置Bool型變量fSpecial為真(true)，用來進行特殊情況處理。根據(jù)A的右連接屬性(向右→向下)，找到所有可能的搜索方向，將搜索路徑存入向量S中。如果向量S不為空，執(zhí)行步驟②，否則執(zhí)行步驟③。

② 順序遍歷向量S中的所有路徑，若搜索路徑存在，則沿搜索路徑進行搜索，若不存在，則轉(zhuǎn)步驟③執(zhí)行。根據(jù)搜索方向的不同，分以下兩種情況：(a)如果當(dāng)前的搜索方向向右，則調(diào)用水平向右處理算法Rule_Right，得到A的直接后繼頂點B，將B保存在向量L中，停止當(dāng)前方向的掃描；如果當(dāng)前豎直線的向下連接標(biāo)志Right_down為假(false)并且向下向右連接標(biāo)志right_down_right為真，就得到與該豎直線右下右(right_down_right)處連接的元件。若該元件為功能元件B，則將B保存在向量L中，停止當(dāng)前方向的掃描處理；若該元件為水平線，通過調(diào)用水平線處理算法Rule_Hline得到A的直接后繼頂點C，將C保存在向量L中，停止當(dāng)前方向的掃描處理；(b)如果當(dāng)前的搜索方向向下，得到與該豎直線A相連的下一行的豎直線A1，則執(zhí)行步驟①，對A1進行掃描處理。如果豎直線元件A1右下右連接屬性為真并且A1向右(right)連接屬性為假，則設(shè)置Bool型變量fSpecial為假。

③ 如果當(dāng)前豎直線A的右連接屬性為假，A的右下右連接屬性為真并且Bool型變量fSpecial為真，就得到與豎直線右下右處連接的元件。若該元件為功能元件B，則將B保存在向量L中，停止當(dāng)前方向的掃描處理；若該處元件為水平線，則通過調(diào)用水平線處理算法Rule_Hline得到A的直接后繼頂點C，將C保存在向量L中，停止當(dāng)前方向的掃描處理。

④ 當(dāng)所有可能的路徑都掃描完后，順序遍歷向量L，得到頂點B，調(diào)用Rule_Save(A，B)，直至遍歷向量L中的最后一個元件為止，清空向量L，轉(zhuǎn)步驟1執(zhí)行。

(3)若當(dāng)前頂點A為源頂點SNode，由前可知源頂點只有后繼連接關(guān)系，其入度為0，掃描過程如下：遍歷當(dāng)前梯級元件鏈表中所有元件，找出所有列值為0的元件，存入向量L中。遍歷向量L得到一個元件B。若B為功能元件，調(diào)用Rule_Save(A，B)；若B為水平線，則調(diào)用水平線處理算法Rule_Hline得到A的直接后繼頂點B，再調(diào)用Rule_Save(A，B)。繼續(xù)遍歷向量L，直至處理完向量L中的所有元件，轉(zhuǎn)步驟1執(zhí)行。

(4)若當(dāng)前頂點A為尾頂點TNode，則其出度為0，掃描過程如下：遍歷頂點數(shù)組XList中的所有元件，將類型為輸出頂點的元件存入向量S中。遍歷S得到一個元件B，調(diào)用Rule_Save(A,B)。繼續(xù)遍歷下一元件，直至向量S中的所有元件都處理完為止。

4 轉(zhuǎn)換實例

圖4所示為用自主研發(fā)的軟PLC上位機軟件設(shè)計的具有復(fù)雜串并聯(lián)關(guān)系的梯形圖程序。圖5對應(yīng)的是AOV圖頂點的掃描過程，圖中V**代表豎直線元件。按照從左向右、從上到下的順序進行掃描，在掃描過程中，豎直線頂點優(yōu)先，即在掃描過程中，每當(dāng)碰到有豎直線連接元件的情形，優(yōu)先處理該列有連接關(guān)系的全部豎直線連接元件，并且定義它們所對應(yīng)的AOV圖頂點編號相同，如圖5中編號為2或7的頂點。

用轉(zhuǎn)換算法對圖5中AOV圖頂點進行處理。如實頂點3(I0.2)，按實頂點的掃描規(guī)則進行掃描，得到頂點4(I0.3)為頂點3的直接后繼頂點，同時將頂點3作為頂點4的直接前驅(qū)頂點。又如豎直線頂點7，按豎直線頂點的掃描規(guī)則進行處理，找到頂點7有3個直接后繼頂點，分別為頂點8(I1.5)、頂點16(I1.6)和頂點22(I2.0)。同時將頂點7分別作為每個后繼頂點的直接前驅(qū)頂點。當(dāng)所有頂點都處理完畢后，即生成如圖6所示的AOV圖。

圖4 梯形圖程序

圖5 AOV圖頂點掃描過程

圖6 轉(zhuǎn)換生成的AOV圖

5 與現(xiàn)有轉(zhuǎn)換算法的比較

當(dāng)前有關(guān)梯形圖向AOV圖轉(zhuǎn)換算法的研究很少，但其主流轉(zhuǎn)換策略均分為頂點掃描、統(tǒng)計頂點的直接前驅(qū)和直接后繼信息以及AOV圖的創(chuàng)建3個過程。本文提出的轉(zhuǎn)換算法與現(xiàn)有轉(zhuǎn)換算

法的流程是一樣的，都分三步進行，但具體轉(zhuǎn)換的策略不一樣。與現(xiàn)有轉(zhuǎn)換算法相比，本文提出的轉(zhuǎn)換算法具有以下優(yōu)點：

(1)本文提出的轉(zhuǎn)換算法將豎直連接線元件(并連線)也作為AOV圖頂點進行存儲，掃描過程簡單，省去了現(xiàn)有轉(zhuǎn)換算法中有關(guān)虛頂點判斷的復(fù)雜處理過程，同時節(jié)省了頂點掃描的時間。

(2)現(xiàn)有算法中由于頂點直接前驅(qū)和直接后繼信息的掃描是分開進行的，這就導(dǎo)致每個功能元件頂點至少要處理兩次，虛頂點處理的次數(shù)要根據(jù)并聯(lián)關(guān)系的深度確定，其總的時間復(fù)雜度為O(2i+δj)，而本文算法中每個頂點在前驅(qū)后繼信息的掃描過程中只處理一次，總的時間復(fù)雜度為O(i+j)，因此本文提出的轉(zhuǎn)換算法時間復(fù)雜度要小于現(xiàn)有轉(zhuǎn)換算法的時間復(fù)雜度，尤其是在處理并聯(lián)關(guān)系比較復(fù)雜(δ值很大)的梯形圖程序時，這種區(qū)別更加明顯。

6 結(jié)語

本文提出的基于迷宮算法思想實現(xiàn)梯形圖向AOV圖轉(zhuǎn)換的策略，可以簡潔高效地實現(xiàn)梯形圖各元件直接前驅(qū)及直接后繼頂點的掃描，進而實現(xiàn)梯形圖向AOV圖的轉(zhuǎn)換。該策略已經(jīng)成功應(yīng)用于自主研發(fā)的軟PLC上位機軟件系統(tǒng)中。為了驗證此轉(zhuǎn)換算法的正確性，已進行了很多嚴(yán)格的測試。實例表明，該算法能夠高效、正確地將梯形圖轉(zhuǎn)換為AOV圖。

[1] 馬小軍. 可編程控制器及其應(yīng)用[M].南京：東南大學(xué)出版社，2007：44-97.

[2] Yan Yi,Zhang Hangping.Compiling ladder diagram into instruction list to comply with IEC 61131-3[J].Computers in Industry,2010,61(5):448-462.

[3] Ge Fen, Wu Ning. A transformation algorithm between ladder diagram and instruction list based on AOV digraph and binary tree[C]∥Hong Kong:2006 IEEE Region 10 Conference,2006:1-4.

[4] 石銳,周雷,楊正益. 軟PLC梯形圖到語句表轉(zhuǎn)換新策略的研究[J]. 計算機工程與應(yīng)用, 2010,46(18):244-248.

[5] 鄒莉. 軟PLC梯形圖向指令表轉(zhuǎn)換新算法的研究與實現(xiàn)[J]. 聊城大學(xué)學(xué)報：自然科學(xué)版， 2013,26(1):105-110.

[6] 馮光，夏清國，裴元方. PLC梯形圖向AOV圖的一種轉(zhuǎn)換方法[J]. 航空計算技術(shù)，2009，39(2)：109-112.

[7] 陽俊將，黃道平，劉少君. 關(guān)于PLC梯形圖到指令表轉(zhuǎn)換算法的研究[J]. 信息技術(shù), 2012(6): 75-78.

[8] 嚴(yán)蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu)[M]. 北京：清華大學(xué)出版社，1997:50-166.