一種基于有向無環(huán)圖的依賴管理機(jī)制及實(shí)現(xiàn)*

顏 雨，李洋昕，張?jiān)伹?/p>

（1.海軍裝備部，四川 成都 610036；2.中國(guó)電子科技集團(tuán)公司第三十研究所，四川 成都 610041）

0 引言

控制類軟件通常需要維護(hù)大量的狀態(tài)信息，根據(jù)輸入數(shù)據(jù)推動(dòng)內(nèi)部狀態(tài)機(jī)運(yùn)轉(zhuǎn)，從而輸出控制信息。這些內(nèi)部狀態(tài)信息之間通常包含復(fù)雜的依賴關(guān)系，一個(gè)輸入條件的改變會(huì)引起內(nèi)部一系列的連鎖反應(yīng)。如果這些狀態(tài)以及狀態(tài)之間的關(guān)系都采用硬編碼，狀態(tài)依賴關(guān)系處理會(huì)分散在軟件代碼各處，正確性完全依賴于實(shí)現(xiàn)人員，易出現(xiàn)偏差，且后期軟件的維護(hù)工作會(huì)非常困難。當(dāng)依賴關(guān)系稍有變動(dòng)，軟件就需要做較大改動(dòng)，易有所遺漏。

圖論以圖為研究對(duì)象。研究的圖是由若干抽象的點(diǎn)以及若干連接兩點(diǎn)的線所組成。在實(shí)際應(yīng)用中，通常可以用點(diǎn)代表事物，連線代表兩個(gè)事物之間的關(guān)系，以此研究處理多個(gè)事物間的復(fù)雜關(guān)系[1]。

本文針對(duì)大量狀態(tài)之間的復(fù)雜依賴關(guān)系問題，基于圖論中的有向無環(huán)圖相關(guān)理論，把軟件中的每一個(gè)狀態(tài)信息抽象成一個(gè)點(diǎn)，兩個(gè)狀態(tài)之間的依賴關(guān)系抽象成這兩個(gè)點(diǎn)之間的有向線段，把復(fù)雜狀態(tài)依賴問題抽象成對(duì)有向無環(huán)圖問題的求解[2]。

1 需求分析

控制軟件的主要功能是根據(jù)系統(tǒng)輸入信息以及系統(tǒng)當(dāng)前的狀態(tài)做出控制決策。系統(tǒng)輸入信息包括設(shè)備時(shí)鐘或定時(shí)器、系統(tǒng)數(shù)據(jù)輸入、系統(tǒng)傳感器輸入以及用戶輸入等。系統(tǒng)狀態(tài)包括系統(tǒng)內(nèi)部數(shù)據(jù)狀態(tài)、系統(tǒng)軟件運(yùn)行狀態(tài)等。控制軟件在處理系統(tǒng)外部輸入時(shí)，需先要根據(jù)預(yù)定的邏輯推動(dòng)內(nèi)部狀態(tài)機(jī)運(yùn)轉(zhuǎn)，修改系統(tǒng)內(nèi)部狀態(tài)[3]。控制軟件內(nèi)部通常會(huì)包含多個(gè)狀態(tài)機(jī)，分別處理不同子系統(tǒng)的邏輯。多個(gè)狀態(tài)機(jī)之間彼此推動(dòng)運(yùn)轉(zhuǎn)，直到達(dá)成一個(gè)穩(wěn)定狀態(tài)。在狀態(tài)機(jī)運(yùn)轉(zhuǎn)的同時(shí)，根據(jù)狀態(tài)機(jī)設(shè)定執(zhí)行預(yù)定操作，輸出控制決策。同樣的，對(duì)于外部輸入，當(dāng)系統(tǒng)狀態(tài)不同時(shí)，系統(tǒng)做出的控制決策也不盡相同。

控制軟件通常需要面對(duì)一個(gè)復(fù)雜系統(tǒng)，軟件內(nèi)部需要維護(hù)大量的狀態(tài)信息，以便精確與實(shí)際環(huán)境相對(duì)應(yīng)。數(shù)量眾多的狀態(tài)之間相互依賴，關(guān)系盤根錯(cuò)節(jié)，增加了控制軟件的復(fù)雜度，嚴(yán)重威脅軟件的可靠性。目前，比較常用的簡(jiǎn)化問題的方法是把全部狀態(tài)集合劃分成若干個(gè)較小的子集合。每個(gè)子集合規(guī)模不大，內(nèi)部狀態(tài)關(guān)系相對(duì)清晰[4]。跨越子集合的狀態(tài)依賴關(guān)系歸結(jié)為子集合之間的依賴關(guān)系。這樣實(shí)際上就把原始問題劃分成了兩個(gè)層次，一是子集合內(nèi)部問題，二是子集合之間的問題，降低了問題規(guī)模，間接提高了軟件實(shí)現(xiàn)的正確性。

雖然通過上述方法可以降低軟件實(shí)現(xiàn)難度，但是并沒有解決軟件正確性全部交由實(shí)現(xiàn)人員保證的問題，且仍然存在軟件可維護(hù)性基礎(chǔ)較差、無法靈活面對(duì)需求變更的問題。本文應(yīng)用圖論中的有向無環(huán)圖理論，設(shè)計(jì)并實(shí)現(xiàn)了一套依賴管理機(jī)制，把系統(tǒng)內(nèi)狀態(tài)信息抽象成點(diǎn)，狀態(tài)信息之間的依賴關(guān)系抽象成有向邊，每個(gè)狀態(tài)點(diǎn)僅需要關(guān)注有依賴關(guān)系的少數(shù)狀態(tài)點(diǎn)，簡(jiǎn)化了問題規(guī)模，通過有向無環(huán)圖的相關(guān)算法自動(dòng)解決狀態(tài)信息之間的依賴傳遞問題。

2 算法設(shè)計(jì)

首先需要構(gòu)建生成系統(tǒng)狀態(tài)信息組成的有向圖，初始化有向圖各頂點(diǎn)的基本狀態(tài)，然后可以接收處理外部輸入，修改內(nèi)部狀態(tài)，通過遍歷有向圖傳播內(nèi)部狀態(tài)變動(dòng)，輸出控制指令。

2.1 初始化

2.1.1 建立有向圖存儲(chǔ)

有向圖的建立主要是生成頂點(diǎn)和有向邊信息。信息可以從配置文件加載，也可以把構(gòu)建過程固化在軟件代碼中。有向圖在算法中采用雙重鄰接表的結(jié)構(gòu)存儲(chǔ)。普通鄰接表為圖中的各個(gè)頂點(diǎn)獨(dú)自建立一個(gè)鏈表，鏈表中存放所有直接可達(dá)的頂點(diǎn)，即是以該頂點(diǎn)為起始點(diǎn)的有向邊的終止頂點(diǎn)。雙重鄰接表在鄰接表的基礎(chǔ)上為每個(gè)頂點(diǎn)增設(shè)了一個(gè)鏈表，存放所有逆向直接可達(dá)的頂點(diǎn)，即是以該頂點(diǎn)為終止頂點(diǎn)的有向邊的起始頂點(diǎn)。雙重鄰接表實(shí)質(zhì)上分別以起始頂點(diǎn)和終止頂點(diǎn)為線索，把有向邊保存了兩次，方便從正向和逆向遍歷有向圖。

每個(gè)頂點(diǎn)在實(shí)現(xiàn)上使用state_vertex 類來保存。類定義如下：

需要說明的是，state 成員表示頂點(diǎn)的當(dāng)前狀態(tài)，initted 成員表示節(jié)點(diǎn)頂點(diǎn)狀態(tài)是否經(jīng)過初始化，edges_in 存儲(chǔ)逆向直接可達(dá)頂點(diǎn)，edges_out 存儲(chǔ)直接可達(dá)頂點(diǎn)。

2.1.2 加載狀態(tài)

完成有向圖存儲(chǔ)的建立后，需要加載各個(gè)頂點(diǎn)的初始狀態(tài)。由于各個(gè)頂點(diǎn)代表的實(shí)際狀態(tài)有很多類型，部分頂點(diǎn)有外部真實(shí)狀態(tài)相對(duì)應(yīng)，可以在初始化時(shí)確定狀態(tài)值。部分頂點(diǎn)只代表了軟件的一個(gè)中間狀態(tài)，需要根據(jù)其他頂點(diǎn)的狀態(tài)動(dòng)態(tài)計(jì)算實(shí)際的狀態(tài)值。頂點(diǎn)狀態(tài)初始化的第一步是獨(dú)立計(jì)算各個(gè)頂點(diǎn)的狀態(tài)值。

對(duì)于無法獨(dú)立確定狀態(tài)值的頂點(diǎn)，采用默認(rèn)的load_state 方法設(shè)置初始狀態(tài)值。load_state 方法定義如下：

需要說明的是，設(shè)置initted 成員為false，表示該頂點(diǎn)的狀態(tài)值沒有最終確定。對(duì)于可以獨(dú)立確定狀態(tài)值的頂點(diǎn)，則需要根據(jù)具體情況重載該方法，為state 成員設(shè)置合適的取值，并將initted 成員設(shè)置為true，表示該頂點(diǎn)的狀態(tài)值已經(jīng)最終確定。

2.1.3 進(jìn)入穩(wěn)定狀態(tài)

完成狀態(tài)加載后，由于部分中間狀態(tài)還沒有確定，需要計(jì)算確定這部分頂點(diǎn)的狀態(tài)值后，有向圖才能進(jìn)入穩(wěn)定狀態(tài)發(fā)揮功效。中間狀態(tài)節(jié)點(diǎn)的狀態(tài)值由該頂點(diǎn)的逆向直接可達(dá)頂點(diǎn)的狀態(tài)值共同決定。check_depends 方法用于完成這一功能。該方法遍歷了指定頂點(diǎn)的edges_in 列表，檢查是否列表中的所有頂點(diǎn)狀態(tài)值都是true，如果是則返回true，否則返回false。如果其中有頂點(diǎn)的initted 成員是false，則拋出異常。check_depends 允許頂點(diǎn)重新定義，采用更加個(gè)性化的狀態(tài)值計(jì)算方法，定義如下：

由于中間狀態(tài)頂點(diǎn)可能存在嵌套依賴的現(xiàn)象，一次遍歷不一定能計(jì)算出所有中間狀態(tài)頂點(diǎn)的狀態(tài)值，因此需要采用多輪遍歷。如果某一次遍歷成功得到狀態(tài)值的頂點(diǎn)數(shù)為0，則表示出現(xiàn)了無法確定初始值的中間狀態(tài)頂點(diǎn)。這表示有向圖的設(shè)計(jì)有問題，需要重新安排各個(gè)頂點(diǎn)的類型與連通關(guān)系等。完整的有向圖初始化函數(shù)實(shí)現(xiàn)如下：

2.1.4 示 例

下面以一個(gè)遠(yuǎn)程訪問流程控制為例，簡(jiǎn)述有向圖的初始化過程。遠(yuǎn)程訪問過程需要用戶設(shè)置目標(biāo)服務(wù)器的IP 地址和端口，以及用于身份認(rèn)證的用戶名和密碼信息。根據(jù)軟件控制流程，建立如圖1所示的有向圖。

“IP 地址”“端口號(hào)”“用戶名”和“密碼”4個(gè)頂點(diǎn)與配置信息內(nèi)容高度相關(guān)，初始化時(shí)根據(jù)配置項(xiàng)是否加載成功設(shè)置狀態(tài)。“連接信息”是“IP地址”和“端口號(hào)”狀態(tài)的匯總，便于軟件衡量是否具備建立連接的基礎(chǔ)，屬于中間狀態(tài)，需要等待其他頂點(diǎn)狀態(tài)加載完成后，通過自身的check_depends 方法計(jì)算狀態(tài)值。“登錄信息”同樣屬于中間狀態(tài)，需要通過自身的check_depends 方法計(jì)算狀態(tài)值。“連接狀態(tài)”和“登錄狀態(tài)”是軟件的動(dòng)態(tài)狀態(tài)，需要自定義加載狀態(tài)方法，設(shè)置初始狀態(tài)為false。

圖1 有向圖初始化

2.2 處理外部輸入

有向圖進(jìn)入穩(wěn)定狀態(tài)后，可以開始處理外部輸入。外部輸入信號(hào)經(jīng)過處理后最終會(huì)造成某個(gè)頂點(diǎn)的狀態(tài)值產(chǎn)生變化。該頂點(diǎn)處理完自身狀態(tài)變動(dòng)后，將沿著有向邊向直接可達(dá)的頂點(diǎn)發(fā)起通知信號(hào)。收到該信號(hào)的頂點(diǎn)由于輸入依賴的狀態(tài)值有變化，需要重新計(jì)算并更新自身的狀態(tài)值，并繼續(xù)沿著有向邊傳播通知信號(hào)，直到整個(gè)有向圖達(dá)成一個(gè)新的平衡。

外部信號(hào)通過調(diào)用頂點(diǎn)的set_state 方法改變頂點(diǎn)的狀態(tài)值，其中使用到的change_state 是一個(gè)可重載的方法，默認(rèn)實(shí)現(xiàn)是直接返回新狀態(tài)值，通過重載可以實(shí)現(xiàn)對(duì)輸入信號(hào)的個(gè)性化處理。

頂點(diǎn)之間傳遞通知信號(hào)，使用當(dāng)前頂點(diǎn)的broadcast 方法在broadcast 方法中遍歷需要接收信號(hào)的頂點(diǎn)，并調(diào)用其activate 方法，實(shí)現(xiàn)信號(hào)的傳遞。

基于如圖2 所示的有向圖，當(dāng)頂點(diǎn)A 的狀態(tài)改變時(shí)，會(huì)發(fā)生以下一系列方法調(diào)用：

（1）設(shè)置A 的狀態(tài)：A.set_state；

（2）A 自身狀態(tài)變更：A.change_state；

（3）A 向外通告狀態(tài)變化：A.broadcast；

（4）B 被激活：B.activate；

（5）B 檢查自身依賴滿足情況：B.check_depends；

（6）B 自身狀態(tài)變更：B.change_state；

（7）B 向外通告狀態(tài)變化：B.broadcast；

（8）C 被激活：C.activate；

（9）C 檢查自身依賴滿足情況：C.check_depends；

（10）C 自身狀態(tài)變更：C.change_state；

（11）C 向外通告狀態(tài)變化：C.broadcast。

頂點(diǎn)可以重載change_state 方法，自由控制頂點(diǎn)的狀態(tài)轉(zhuǎn)換過程。

圖2 有向圖頂點(diǎn)關(guān)系示例1

2.2.1 拓?fù)渑判?/p>

如果通知信號(hào)不加區(qū)分的向所有直接可達(dá)頂點(diǎn)發(fā)送，部分頂點(diǎn)會(huì)重復(fù)收到通知消息，產(chǎn)生不必要的處理。為了避免這種情況，需要對(duì)頂點(diǎn)進(jìn)行拓?fù)渑判颍_保所有需要接收通知信號(hào)的頂點(diǎn)能夠按順序處理，且不會(huì)重復(fù)收到消息。

這里的拓?fù)渑判蛑会槍?duì)完整有向圖的一個(gè)子區(qū)域從最初受影響的頂點(diǎn)開始，范圍包括其他所有可達(dá)的頂點(diǎn)，此外的頂點(diǎn)不參與拓?fù)渑判颉Ｓ捎谕負(fù)渑判虻膶?duì)象是有向圖的部分子圖，常用的每次刪除入度為0 的拓?fù)渑判蛩惴ú⒉贿m合，這里借助深度優(yōu)先的遍歷方法實(shí)現(xiàn)部分區(qū)域的拓?fù)渑判颍a實(shí)現(xiàn)如下：

基于如圖3 所示的有向圖，頂點(diǎn)A 狀態(tài)改變，將會(huì)依次通告B、D、C。B 會(huì)通告D，D 會(huì)向C發(fā)起第二次通告。這樣就有重復(fù)的通告過程。通過以頂點(diǎn)A 為起始頂點(diǎn)做拓?fù)渑判颍判蚪Y(jié)果為A →B →D →C。當(dāng)A 狀態(tài)改變時(shí)，只需要依次向B、D、C 發(fā)起通告即可，降低了通告過程的復(fù)雜度。

圖3 有向圖頂點(diǎn)關(guān)系示例2

2.2.2 激發(fā)處理

頂點(diǎn)通過重載change_state 方法，可以自定義狀態(tài)值改變時(shí)執(zhí)行的操作。此時(shí)，可以根據(jù)操作結(jié)果選擇保持當(dāng)前狀態(tài)值或者改變狀態(tài)值。在change_state 方法中，還可以根據(jù)當(dāng)前狀態(tài)對(duì)外部做出控制指令，實(shí)現(xiàn)控制軟件對(duì)外部的控制輸出。

2.2.3 剪 枝

在單向圖傳遞通知信號(hào)時(shí)，部分頂點(diǎn)可能會(huì)選擇不改變當(dāng)前狀態(tài)值，后序遍歷的頂點(diǎn)可能會(huì)出現(xiàn)所有逆向直接可達(dá)頂點(diǎn)的狀態(tài)值都沒有改變。此時(shí)，為了優(yōu)化控制軟件的運(yùn)行速度，可以選擇不再向后發(fā)送通知信號(hào)，減少觸發(fā)操作，提高處理效率[5]。

2.3 逆向遍歷

根據(jù)外部輸入，沿著有向邊傳遞通知信號(hào)，屬于有向圖的正向遍歷。還可以對(duì)有向圖進(jìn)行逆向遍歷，確定某個(gè)頂點(diǎn)的目標(biāo)狀態(tài)值逆向回溯有向邊，主動(dòng)創(chuàng)造達(dá)成目標(biāo)狀態(tài)的條件，或者檢查達(dá)成目標(biāo)還有哪些中間條件需要得到滿足。

2.4 優(yōu) 化

有向圖的遍歷還有一定的優(yōu)化空間，最直接的就是以空間換取時(shí)間，保留每個(gè)頂點(diǎn)的拓?fù)渑判蚪Y(jié)果，后續(xù)該頂點(diǎn)狀態(tài)改變時(shí)，就不再需要進(jìn)行拓?fù)渑判蜻^程，減少了計(jì)算步驟。

3 結(jié)語

本文使用有向圖理論解決大量復(fù)雜依賴關(guān)系管理的問題，將狀態(tài)信息抽象成頂點(diǎn)，將狀態(tài)信息之間的依賴關(guān)系抽象成有向邊，通過求解對(duì)應(yīng)有向圖的問題，實(shí)現(xiàn)了狀態(tài)信息之間的自動(dòng)推導(dǎo)管理。這種方法相比硬編碼依賴關(guān)系更加可靠，且可以實(shí)現(xiàn)狀態(tài)信息和依賴關(guān)系的動(dòng)態(tài)加載，實(shí)現(xiàn)了邏輯關(guān)系與軟件實(shí)現(xiàn)的相分離。