[發明專利]一種有向圖中的環路檢測方法、裝置、設備和存儲介質

有效

• 申請號: 201911328366.0
• 申請日: 2019-12-20
• 公開（公告）號: CN110968429B
• 公開（公告）日: 2022-11-11
• 發明（設計）人: 盧文祥;李玉明;王云龍;周力;蔡歌;汪洋;袁鵬程;李剛
• 申請（專利權）人: 北京百度網訊科技有限公司
• 主分類號: G06F9/50
• 分類號: G06F9/50;G06F16/901
• 代理公司: 北京品源專利代理有限公司 11332
• 代理人: 孟金喆

1.一種有向圖中的環路檢測方法，其特征在于，包括：

分布式集群中的服務中心獲取待檢測的有向圖；

所述服務中心對所述有向圖的至少一個邊進行切割，得到多個子圖；

所述服務中心將多個子圖分發至分布式集群中的多個計算節點，以供每個計算節點檢測接收到的子圖中的環路和鏈路；

所述服務中心從多個計算節點獲取多個子圖中的環路和鏈路，并根據子圖之間的被切邊的信息，對獲取的環路和/或鏈路進行拼接，得到所述有向圖中的環路；

其中，每個被切邊的兩個切割點順序構成切邊序列，環路的各頂點順序構成環序列，鏈路的各頂點順序構成鏈序列；

對于第一切邊序列，所述服務中心根據子圖之間的被切邊的信息，對獲取的環路和/或鏈路進行拼接，得到所述有向圖中的環路，包括：

所述服務中心從獲取的環序列和鏈序列中，查找所述第一切邊序列的鄰接序列；

所述服務中心將所述鄰接序列與所述第一切邊序列拼接得到新的第一切邊序列；

如果新的第一切邊序列中不存在重復頂點，所述服務中心判斷新的第一切邊序列的首尾是否存在有向邊；

如果存在，所述服務中心將新的第一切邊序列檢測為所述有向圖中的環路；

如果不存在，所述服務中心從獲取的環序列和鏈序列中剔除所述鄰接序列，返回執行鄰接序列的查找操作，直到新的第一切邊序列包括所述有向圖中的全部頂點，或者未找到鄰接序列。

2.根據權利要求1所述的方法，其特征在于，所述服務中心從獲取的環序列和鏈序列中，查找所述第一切邊序列的鄰接序列，包括：

在首次查找所述第一切邊序列的鄰接序列時，所述服務中心從獲取的環序列和鏈序列中，按照前向序列拼接方向或者后向序列拼接方向查找所述第一切邊序列的鄰接序列；

在非首次查找所述第一切邊序列的鄰接序列時，所述服務中心獲取前次序列拼接方向，并按照前次序列拼接方向的反方向，查找所述第一切邊序列的鄰接序列。

3.根據權利要求1所述的方法，其特征在于，所述服務中心對所述有向圖的至少一個邊進行切割，得到多個子圖，包括：

所述服務中心過濾所述有向圖中入度或出度為0的頂點；

所述服務中心對過濾后的有向圖的至少一個邊進行切割，得到多個子圖，任兩個子圖之間的頂點數量之差在預設范圍內。

4.一種有向圖中的環路檢測方法，其特征在于，包括：

分布式集群中的計算節點從服務中心獲取至少一個子圖，所述至少一個子圖是服務中心對有向圖的至少一個邊進行切割得到的；

所述計算節點遍歷至少一個所述子圖中的各頂點，檢測每個子圖中的環路和鏈路；

所述計算節點將檢測出的環路和鏈路上傳至所述服務中心，以供所述服務中心獲取到多個計算節點上傳的環路和鏈路之后，根據子圖之間的被切邊的信息，對獲取的環路和/或鏈路進行拼接，得到所述有向圖中的環路；

其中，每個被切邊的兩個切割點順序構成切邊序列，環路的各頂點順序構成環序列，鏈路的各頂點順序構成鏈序列；

對于第一切邊序列，根據子圖之間的被切邊的信息，對獲取的環路和/或鏈路進行拼接，得到所述有向圖中的環路，包括：

從獲取的環序列和鏈序列中，查找所述第一切邊序列的鄰接序列；

將所述鄰接序列與所述第一切邊序列拼接得到新的第一切邊序列；

如果新的第一切邊序列中不存在重復頂點，判斷新的第一切邊序列的首尾是否存在有向邊；

如果存在，將新的第一切邊序列檢測為所述有向圖中的環路；

如果不存在，所述服務中心從獲取的環序列和鏈序列中剔除所述鄰接序列，返回執行鄰接序列的查找操作，直到新的第一切邊序列包括所述有向圖中的全部頂點，或者未找到鄰接序列。

5.根據權利要求4所述的方法，其特征在于，所述計算節點遍歷至少一個所述子圖中的各頂點，檢測每個子圖中的環路和鏈路，包括：

所述計算節點按照每個子圖中頂點的連接方向，依次訪問各頂點；

如果當前訪問頂點的后繼頂點已被訪問過，將本次訪問過的頂點及頂點間的有向邊檢測為環路；

如果當前訪問頂點的出度為0，將本次訪問過的頂點及頂點間的有向邊檢測為鏈路。