[發明專利]一種有向圖識別方法及系統和服務器

在審

• 申請號: 201910293860.1
• 申請日: 2019-04-12
• 公開（公告）號: CN111814002A
• 公開（公告）日: 2020-10-23
• 發明（設計）人: 趙凱
• 申請（專利權）人: 阿里巴巴集團控股有限公司
• 主分類號: G06F16/901
• 分類號: G06F16/901
• 代理公司: 北京安信方達知識產權代理有限公司 11262
• 代理人: 李丹;栗若木

1.一種有向圖識別方法，包括：

確定有向圖中每個節點的入度數/出度數；

逐個對有向圖中入度數/出度數為0的節點的直接下游節點/直接上游節點的入度數/出度數進行處理，直至所有節點處理完成；

如果有向圖中存在入度數/出度數不為0的節點，表明所述有向圖為有向有環圖。

2.根據權利要求1所述的有向圖識別方法，其中，所述逐個對有向圖中入度數/出度數為0的節點的直接下游節點/直接上游節點的入度數/出度數進行處理，直至所有節點處理完成，包括：

將所述有向圖中入度數為0的節點存儲在待處理隊列中，從根節點開始，刪除該節點，將該節點的直接下游節點的入度數進行減1處理，如果該節點的直接下游節點的入度數減1后為0，則將該下游節點存儲在所述待處理節點隊列中，以此循環，直至所有節點處理完成，如果該節點的直接下游節點的入度數減1后不為0，則保留該節點的直接下游節點和對應的處理后的入度數；

或者，

將所述有向圖中出度數為0的節點存儲在待處理隊列中，從最外層枝葉節點開始，刪除該節點，將該節點的直接上游節點的入度數進行減1處理，如果該節點的直接上游節點的入度數減1后為0，則將該上游節點存儲在所述待處理節點隊列中，以此循環，直至所有節點處理完成，如果該節點的直接上游節點的入度數減1后不為0，則保留該節點的直接上游節點和對應的處理后的入度數。

3.根據權利要求1所述的有向圖識別方法，所述方法之前還包括：根據有向圖包括的邊將有向圖劃分為多個子有向圖；

所述確定有向圖中每個節點的入度數/出度數，包括：采用分布式方式確定每個子有向圖中各節點的入度數/出度數；

所述逐個對有向圖中入度數/出度數為0的節點的直接下游節點/直接上游節點的入度數/出度數進行處理，包括：

對于每個子有向圖，確定在子有向圖中入度數/出度數為0的節點在有向圖中的入度數/出度數，對于在有向圖中的入度數/出度數為0的節點，對該節點的直接下游節點/直接上游節點的入度數/出度數進行處理。

4.根據權利要求3所述的有向圖識別方法，其中，所述將有向圖劃分為多個子有向圖，包括：

按照預先設置的子有向圖包括的邊的數量，隨機將所述有向圖中的節點劃分到不同的所述子有向圖中。

5.根據權利要求3所述的有向圖識別方法，其中，所述將有向圖劃分為多個子有向圖，包括：

根據所述有向圖中節點的節點標識，計算子有向圖中包括的節點數量；

根據計算出的節點數量和子有向圖對應的處理設備的編號，獲取子有向圖包括的節點的節點標識范圍。

6.根據權利要求5所述的有向圖識別方法，其中，

所述子有向圖中包括的節點數量N＝(MAX(ID)-MIN(ID))/C，其中，C表示所述處理設備的數量，MAX(ID)為所述有向圖中節點標識的最大值，MIN(ID)為所述有向圖中節點標識的最小值；

所述子有向圖包括的節點的節點標識范圍IDS＝I*N～I*(N+1)，其中，I為所述處理設備在對應的編號。