[發明專利]一種單機核外屬性圖計算方法

在審

• 申請號: 202110334310.7
• 申請日: 2021-03-29
• 公開（公告）號: CN113065035A
• 公開（公告）日: 2021-07-02
• 發明（設計）人: 鐘鳴;鄭盈儀;荊澤華
• 申請（專利權）人: 武漢大學
• 主分類號: G06F16/901
• 分類號: G06F16/901;G06F16/906
• 代理公司: 武漢科皓知識產權代理事務所(特殊普通合伙) 42222
• 代理人: 許蓮英

1.一種單機核外屬性圖計算方法，其特征在于，包括以下步驟：

步驟1：構建屬性圖，所述屬性圖由多個頂點、多條邊、頂點對應的多個屬性，以及邊對應的多個屬性構成；

步驟2：將屬性圖的多個頂點通過外層不對稱網格分圖策略算法進行分簇，得到頂點簇以及每對頂點簇對應的邊集合；

步驟3：將步驟2中通過外層不對稱網格分圖策略算法得到的P_s×P_t個邊集合Block再次細化分簇，對每個Block通過內層不對稱網格分圖策略算法得到粒度更小的頂點簇以及每對細粒度頂點簇對應的細粒度邊集合；

步驟4：對每個經過步驟3處理的Block(x,y)所得到的細粒度邊集合Block(x_a,y_b)按源頂點簇優先的順序重組，會得到一個細粒度邊集合有序的一維數組Block’(x,y)；

步驟5：對所有一維數組Block’(x,y)(x∈[1,P_s]，y∈[1,P_t])按目的頂點簇優先的順序重組，得到一個一維數組Block’(x,y)間有序的屬性圖二維數組Grid；

步驟6：通過步驟5得到的屬性圖二維數組Grid構建出1個拓撲數組Column(E)和q個邊的屬性的數組Column(A_E(b))，b∈[1,q]；

步驟7：對頂點的屬性數據A_V構建出m個頂點的屬性一維數組Column(A_V(a))，a∈[1,m]；

步驟8：根據用戶給定的屬性條件限制，依次順序遍歷需要的在步驟7得到的頂點屬性數組，在內存中得到一個頂點標記數組，再依次順序遍歷需要的在步驟6得到的邊屬性數組并結合頂點標記數組，最終得到在內存中的頂點標記數組和邊標記數組；

步驟9：根據用戶給定的計算任務，順序讀步驟6得到的拓撲數組，對讀入的每條邊通過步驟8得到的頂點標記數組和邊標記數組判斷該邊是否需要進行計算，若需要則按用戶定義的計算任務處理；遍歷完拓撲數組中的每條邊后，根據用戶定義的計算任務判斷是否滿足計算任務結束條件，是則結束，用戶發起新的計算任務時直接進入步驟8，否則重復步驟9。