[發明專利]有向無環圖的獲取方法、裝置、電子設備和存儲介質

在審

• 申請號: 201910945920.3
• 申請日: 2019-09-30
• 公開（公告）號: CN110727834A
• 公開（公告）日: 2020-01-24
• 發明（設計）人: 王翰琦;王志清;崔軒
• 申請（專利權）人: 北京百度網訊科技有限公司
• 主分類號: G06F16/901
• 分類號: G06F16/901;H04L29/06
• 代理公司: 11205 北京同立鈞成知識產權代理有限公司
• 代理人: 張娜;臧建明

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

服務器接收終端設備的有向無環圖DAG請求，所述DAG請求指示所述服務器返回執行標簽的任務的各節點的層級關系；

所述服務器根據標簽的DAG信息，建立鄰接表，所述鄰接表表征所述各節點的出入度關系、鄰接關系；

所述服務器根據所述各節點的出入度關系、鄰接關系，建立所述各節點的層級關系，所述層級關系與所述各節點的空間相對位置相關；

所述服務器將所述各節點的層級關系和所述鄰接關系發送給終端設備，以使所述終端設備根據所述層級關系和所述鄰接關系渲染所述標簽的DAG。

2.根據權利要求1所述的方法，其特征在于，所述服務器根據所述各節點的出入度關系、鄰接關系，建立所述各節點的層級關系，包括：

所述服務器根據所述各節點的出入度關系，獲取所述各節點的入度數；

所述服務器根據所述各節點的入度數和所述鄰接關系，建立所述各節點的層級關系。

3.根據權利要求2所述的方法，其特征在于，所述服務器根據所述各節點的入度數和所述鄰接關系，建立所述各節點的層級關系，包括：

所述服務器建立隊列容器；

所述服務器將入度數為0的第一節點添加至所述隊列容器的第一層級；

所述服務器根據所述鄰接關系，獲取以所述第一節點為首節點的節點隊列；

所述服務器根據所述節點隊列中除所述第一節點之外的節點的入度數，建立所述各節點的層級關系。

4.根據權利要求3所述的方法，其特征在于，所述服務器根據所述節點隊列中除所述第一節點之外的節點的入度數，建立所述各節點的層級關系，包括：

A，所述服務器將所述節點隊列中以第i-1節點為首節點的節點的入度數均減1后，判斷是否有入度數為0的第i節點；若是，執行B，若否，執行C，i為大于或等于2的整數；

B，所述服務器將所述第i節點添加至所述隊列容器的第i層級，且判斷所述節點隊列中是否還有節點；若是，執行C，若否，執行D；

C，所述服務器將i加1，返回執行A；

D，所述服務器根據所述隊列容器中各層級對應的節點，建立所述各節點的層級關系。

5.根據權利要求4所述的方法，其特征在于，所述服務器根據所述隊列容器中各層級對應的節點，建立所述各節點的層級關系，包括：

所述服務器根據所述隊列容器中各層級對應的節點，建立結果列表，所述結果列表用于表征所述各節點的層級關系；

所述服務器所述將所述各節點的層級關系和所述鄰接關系發送給終端設備，以使所述終端設備根據所述層級關系和所述鄰接關系渲染所述各節點的DAG，包括：

所述服務器將所述結果列表和所述鄰接關系發送給終端設備，以使所述終端設備根據所述結果列表和所述鄰接關系渲染所述標簽的DAG。

6.一種有向無環圖的獲取方法，其特征在于，包括：

終端設備接收服務器發送的各節點的層級關系和鄰接關系，所述各節點用于執行標簽的任務，所述層級關系與所述各節點的空間相對位置相關；

所述終端設備根據所述各節點的層級關系和鄰接關系，渲染所述標簽的DAG。

7.根據權利要求6所述的方法，其特征在于，所述方法還包括：

所述終端設備接收所述服務器發送的結果列表和所述鄰接關系，所述結果列表用于表征所述各節點的層級關系；

所述終端設備根據所述結果列表和所述鄰接關系，渲染所述標簽的DAG。

8.根據權利要求6或7所述的方法，其特征在于，所述終端設備根據所述各節點的層級關系和所述鄰接關系，渲染所述標簽的DAG，包括：

所述終端設備根據所述各節點的層級關系和所述鄰接關系，獲取所述各節點的空間相對位置；

所述終端設備根據所述各節點的空間相對位置和所述鄰接關系，渲染所述標簽的DAG。