基于迷宮算法思想的梯形圖向AOV圖的轉換

王吉停，張得禮，周來水

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

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

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

1 AOV圖數據結構

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

一個梯形圖程序是由多個梯級網絡組成的，每個梯級網絡又由各種圖符構成，包括功能單元圖符、連接單元圖符以及空單元。各個梯級網絡內的梯形圖本質上對應著一個有向圖, 其中各功能單元圖符可以抽象為有向圖中的頂點, 連接單元圖符可以抽象為有向圖中的弧。

為簡化轉換算法，將梯形圖中的圖符元件對應的AOV圖頂點分為以下4種類型：

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

(2)尾頂點TNode。將右側終止線也作為一類特殊的元件保存在相應的對象中，作為AOV圖的結束標志，存儲在頂點數組的最后位置處，出度為0，入度大小由程序結構決定。

(3)豎直元件頂點VNode。豎直線連接元件作為各行之間連接關系的標志，本程序將具有直接連接關系并且列值相等、行值最小的豎直線元件作為一類頂點VNode，其出度和入度均不小于1。

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

2 梯形圖向AOV圖轉換算法描述

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

3 轉換算法的實現

在轉換算法執行前，定義了以下處理算法：

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

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

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

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

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

步驟1：順序遍歷頂點數組Xlist得到一個頂點A，若A不存在，則轉換算法結束；若A存在，則轉步驟2執行。

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

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

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

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

圖1 轉換算法流程圖

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

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

③ 清空向量S，轉步驟1執行。

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

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

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

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

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

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

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

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

4 轉換實例

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

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

圖4 梯形圖程序

圖5 AOV圖頂點掃描過程

圖6 轉換生成的AOV圖

5 與現有轉換算法的比較

當前有關梯形圖向AOV圖轉換算法的研究很少，但其主流轉換策略均分為頂點掃描、統計頂點的直接前驅和直接后繼信息以及AOV圖的創建3個過程。本文提出的轉換算法與現有轉換算

法的流程是一樣的，都分三步進行，但具體轉換的策略不一樣。與現有轉換算法相比，本文提出的轉換算法具有以下優點：

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

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

6 結語

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

[1] 馬小軍. 可編程控制器及其應用[M].南京：東南大學出版社，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梯形圖到語句表轉換新策略的研究[J]. 計算機工程與應用, 2010,46(18):244-248.

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

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

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

[8] 嚴蔚敏，吳偉民. 數據結構[M]. 北京：清華大學出版社，1997:50-166.