[發明專利]用于驗證有向無環圖的環的方法及裝置、電子設備、存儲介質

在審

• 申請號: 202110963189.4
• 申請日: 2021-08-20
• 公開（公告）號: CN113672369A
• 公開（公告）日: 2021-11-19
• 發明（設計）人: 王培梁
• 申請（專利權）人: 北京明略軟件系統有限公司
• 主分類號: G06F9/48
• 分類號: G06F9/48;G06F16/901;G06F16/903
• 代理公司: 北京康盛知識產權代理有限公司 11331
• 代理人: 陶俊潔

1.一種用于驗證有向無環圖的環的方法，其特征在于，包括：

獲取有向無環圖中的多個節點，各所述節點的入棧狀態均為未入棧；

從各所述節點中選取一個節點為起始節點，并對所述起始節點進行入棧操作；

獲取所述起始節點對應的多條路徑；所述路徑中的節點包括起始節點和待遍歷節點，所述路徑中各節點通過有向邊順序連接；所述待遍歷節點為起始節點外的其他節點；

從多條所述路徑中依次選取一條路徑確定為待遍歷路徑，對所述待遍歷路徑執行第一預設操作；所述第一預設操作為確定所述待遍歷路徑中的第一個待遍歷節點，并從所述第一個待遍歷節點開始根據所述待遍歷路徑的有向邊依次對所述待遍歷路徑中的節點執行第二預設操作，在所述待遍歷路徑中的節點均執行完第二預設操作且未確定出所述有向無環圖存在閉環的情況下，將所述待遍歷路徑中的待遍歷節點均出棧；所述第二預設操作為判斷節點的入棧狀態，在入棧狀態為未入棧的情況下對節點進行入棧操作，在入棧狀態為已入棧的情況下確定所述有向無環圖存在閉環；

在各所述路徑均執行完第一預設操作且未確定出所述有向無環圖存在閉環的情況下，則確定所述有向無環圖不存在閉環。

2.根據權利要求1所述的方法，其特征在于，確定所述待遍歷路徑中的第一個待遍歷節點，包括：

將所述待遍歷路徑中起始節點通過有向邊直接指向的待遍歷節點確定為所述待遍歷路徑中的第一個待遍歷節點。

3.根據權利要求1所述的方法，其特征在于，所述入棧操作，包括：

將節點對應的數據存入預設的棧中；所述數據用于表征節點。

4.根據權利要求3所述的方法，其特征在于，所述判斷節點的入棧狀態，包括：

依次遍歷所述棧中的數據，在所述棧中存在節點對應的數據的情況下，則確定節點的入棧狀態為已入棧；在所述棧中不存在節點對應的數據的情況下，則確定節點的入棧狀態為未入棧。

5.一種用于驗證有向無環圖的環的裝置，其特征在于，包括：

獲取模塊，被配置為獲取有向無環圖中的多個節點，各所述節點的入棧狀態均為未入棧；

起始節點確定模塊，被配置為從各所述節點中選取一個節點為起始節點，并對所述起始節點進行入棧操作；

路徑確定模塊，被配置為獲取所述起始節點對應的多條路徑；所述路徑中的節點包括起始節點和待遍歷節點，所述路徑中各節點通過有向邊順序連接；所述待遍歷節點為起始節點外的其他節點；

判斷模塊，被配置為從多條所述路徑中依次選取一條路徑確定為待遍歷路徑，對所述待遍歷路徑執行第一預設操作；所述第一預設操作為確定所述待遍歷路徑中的第一個待遍歷節點，并從所述第一個待遍歷節點開始根據所述待遍歷路徑的有向邊依次對所述待遍歷路徑中的節點執行第二預設操作，在所述待遍歷路徑中的節點均執行完第二預設操作且未確定出所述有向無環圖存在閉環的情況下，待遍歷路徑中的待遍歷節點均出棧；所述第二預設操作為判斷節點的入棧狀態，在入棧狀態為未入棧的情況下對節點進行入棧操作，在入棧狀態為已入棧的情況下確定所述有向無環圖存在閉環；

有向無環圖確定模塊，被配置為在各所述路徑均執行完第一預設操作且未確定出所述有向無環圖存在閉環的情況下，則確定所述有向無環圖不存在閉環。

6.根據權利要求5所述的裝置，其特征在于，判斷模塊被配置為按照以下方式確定所述待遍歷路徑中的第一個待遍歷節點：

將所述待遍歷路徑中起始節點通過有向邊直接指向的待遍歷節點確定為所述待遍歷路徑中的第一個待遍歷節點。

7.根據權利要求5所述的裝置，其特征在于，所述入棧操作，包括：

將節點對應的數據存入預設的棧中；所述數據用于表征節點。

8.一種用于驗證有向無環圖的環的裝置，包括處理器和存儲有程序指令的存儲器，其特征在于，所述處理器被配置為在運行所述程序指令時，執行如權利要求1至4任一項所述的用于驗證有向無環圖的環的方法。

9.一種電子設備，其特征在于，包括如權利要求8所述的用于驗證有向無環圖的環的裝置。

10.一種存儲介質，存儲有程序指令，其特征在于，所述程序指令在運行時，執行如權利要求1至4任一項所述的用于驗證有向無環圖的環的方法。