[發明專利]一種基于圖的多點路徑查詢方法和裝置

在審

• 申請號: 201910132053.1
• 申請日: 2019-02-22
• 公開（公告）號: CN111611442A
• 公開（公告）日: 2020-09-01
• 發明（設計）人: 郝彤
• 申請（專利權）人: 京東數字科技控股有限公司
• 主分類號: G06F16/901
• 分類號: G06F16/901;G06F16/903
• 代理公司: 北京德琦知識產權代理有限公司 11018
• 代理人: 杜志敏;宋志強

1.一種基于圖的多點路徑查詢方法，其特征在于，該方法包括：

接收到查詢請求時，獲取該請求攜帶的起始頂點的集合V、擴展的層次數L和返回的路徑數量N；

針對V中的每個起始頂點擴展M層，將每個起始頂點對應的擴展信息分別記錄到一個數組中；并將擴展過程中經過的頂點和邊使用鄰接表進行緩存；其中，M小于L；

將V中的兩兩起始頂點對應的擴展信息求交集之后，再將所有交集內的擴展信息求并集；

將并集中的擴展信息按照預設規則進行排列；并獲取并集中前N條擴展信息作為初步擴展信息；

根據緩存中的鄰接表將初步擴展信息對應的每個頂點再擴展L-M層，并獲取對應的擴展信息作為二次擴展信息；

合并初步擴展信息和二次擴展信息，過濾掉非起始頂點對應的擴展信息，并按照預設規則排列，作為待返回擴展信息；

獲取待返回擴展信息中的前N條擴展信息，并將所述獲取的前N條擴展信息中的路徑信息響應給發送查詢請求的設備。

2.根據權利要求1所述的方法，其特征在于，

所述預設規則為：

層數從小到大，頂點ID從小到大的順序；

或，隨機順序；

或，層數從小到大，頂點按照V中起始頂點的順序。

3.根據權利要求1所述的方法，其特征在于，

所述擴展信息，包括：層ID、頂點ID和路徑信息；其中，路徑信息為擴展過程中經過的邊的集合，一條邊使用頂點的開始頂點和結束頂點表示。

4.根據權利要求1所述的方法，其特征在于，

M為L/2，當L/2不為整數時，將L/2向上取整作為M。

5.根據權利要求1所述的方法，其特征在于，所述將V中的兩兩起始頂點對應的擴展信息求交集，包括：

若兩兩起始頂點對應的擴展信息中的路徑信息中存在相同的頂點ID，則確定該擴展信息為交集中的擴展信息。

6.根據權利要求1-5任一項所述的方法，其特征在于，所述方法進一步包括：

預先配置查詢起始頂點的數量范圍、擴展的層次數的范圍和返回的路徑數量的范圍；

當下述任一項不滿足配置的范圍時，向發送查詢請求的設備返回不能查詢的響應：

起始頂點的集合V中的頂點數量、擴展的層次數L和返回的路徑數量N。

7.一種基于圖的多點路徑查詢裝置，其特征在于，該裝置包括：接收單元、獲取單元、第一擴展單元、第二擴展單元和響應單元；

所述接收單元，用于接收查詢請求；

所述獲取單元，用于當所述接收單元接收到查詢請求時，獲取該請求攜帶的起始頂點的集合V、擴展的層次數L和返回的路徑數量N；

所述第一擴展單元，用于針對獲取單元中的V中的每個起始頂點擴展M層，將每個起始頂點對應的擴展信息分別記錄到一個數組中；并將擴展過程中經過的頂點和邊使用鄰接表進行緩存；將V中的兩兩起始頂點對應的擴展信息求交集之后，再將所有交集內的擴展信息求并集；將并集中的擴展信息按照預設規則進行排列；并獲取并集中前N條擴展信息作為初步擴展信息；其中，M小于L；

所述第二擴展單元，用于根據所述第一擴展單元在緩存中緩存的鄰接表將初步擴展信息對應的每個頂點再擴展L-M層，并獲取對應的擴展信息作為二次擴展信息；合并初步擴展信息和二次擴展信息，過濾掉非起始頂點對應的擴展信息，并按照預設規則排列，作為待返回擴展信息；獲取待返回擴展信息中的前N條擴展信息；

所述響應單元，用于將所述第二擴展單元獲取的前N條擴展信息中的路徑信息響應給發送查詢請求的設備。

8.根據權利要求7所述的裝置，其特征在于，

所述預設規則為：

層數從小到大，頂點ID從小到大的順序；

或，隨機順序；

或，層數從小到大，頂點按照V中起始頂點的順序。