[發明專利]一種分布式計算有向圖圍長的方法

有效

• 申請號: 201711237056.9
• 申請日: 2017-11-30
• 公開（公告）號: CN108154530B
• 公開（公告）日: 2020-07-10
• 發明（設計）人: 華強勝;金海;錢立祥
• 申請（專利權）人: 華中科技大學
• 主分類號: G06T7/62
• 分類號: G06T7/62
• 代理公司: 華中科技大學專利中心 42201
• 代理人: 廖盈春;李智

本發明公開了一種分布式計算有向圖圍長的方法，屬于并行與分布式計算技術領域。本發明方法首先將有向圖G中所有權值為負的邊轉化為非負；之后圖G中每一個點執行有距離限制參數t的Bounded BFS算法；再根據Bounded BFS算法的結束條件，更新有向圖圍長g的下界α或上界β；之后根據β、α和Bounded BFS的結束條件，刪除圖G中權值之和大于α或β的路徑；最后通過α和β更新距離限制參數t，重復執行步驟S2?S5直到β?α小于等于1，得到圖G的圍長g＝β。本發明方法旨在設計一個線性時間的分布式計算有向圖圍長的方法，此方法的時間復雜度為O(nlognlogg)，可在有權圖下避免消息擁塞，有效的降低了算法的時間復雜度，保證了在大規模有向圖中可以快速的分布式計算圖的圍長。

技術領域

本發明屬于并行與分布式計算技術領域，更具體地，涉及一種分布式計算有向圖圍長的方法。

背景技術

有向圖G是一個由結點集合V和帶權值的有向邊的集合E組成的簡單圖。有向圖可以刻畫現實世界中實體之間的關系，例如在社交網絡中表示人與人之間的關系；在交通網絡或者航空網絡中描繪兩個點之間的可達性或者用于設計最優的路線；工作的分配，工程進度的安排或者課程表的制定都可以利用有向圖來進行建模。因此，有向圖算法的設計是計算機科學中的一項重要課題。

有向圖的圍長表示的是有向圖中最小的環的大小。它是圖算法的一個基本問題，被廣泛用社交網絡分析，數據可視化，生物信息學和三維表面重構等領域。在集中式算法中，計算圖的圍長在無權圖中可以很容易的解決：利用寬度優先搜索算法可以在O(mn)的時間內求出圍長，其中n和m分別為有向圖中點的個數和邊的條數。對于有權圖，集中式算法也可以利用求解最短路徑方法在O(n³)的時間內計算圍長。但是對于分布式算法來說，在有權圖和無權圖上求解圍長的難度差別很大。在無權圖中，可以利用分布式寬度優先搜索算法在O(n)的時間內快速的求出圍長的大小。而在有權圖中，現有文獻求解圍長均利用最短路徑方法。而目前最快的分布式求解有權圖最短路徑算法需要O(n²)的時間，這也意味著求解圍長的時間不低于 O(n²)。

在分布式算法中，最棘手的問題是如何處理擁塞。在目前分布式領域中，最常用的模型為擁塞模型(CONGEST Model)，它要求圖中每條邊在每一輪中最多傳遞一個消息。這給算法的設計帶來了巨大的挑戰，它要求我們設計合適的策略去傳遞和路由消息，保證圖中沒有擁塞發生。這個挑戰使得簡單的利用寬度優先搜索算法在有權有向圖下計算圍長需要很高的時間復雜度，而在這種方法下降低時間復雜度又會引入計算錯誤。因此，如何設計一個算法可以快速而正確的計算有向圖的圍長是一個重要且極具挑戰的問題。

發明內容

針對現有技術的以上缺陷或改進需求，本發明提供了一種分布式計算有向圖圍長的方法，其目的在于它有效的在分布式環境下將計算有向圖圍長問題轉化為計算非負權有向圖圍長的問題，簡化了算法的設計，另外設計了一種高效的分布式算法在線性時間內計算出非負權有向圖的圍長，由此可以快速而正確的計算有向圖的圍長。

為實現上述目的，本發明提供了一種分布式計算有向圖圍長的方法，所述方法包括：

S1，將有向圖G中所有權值為負的邊轉化為非負；

S2，圖G中每一個點執行有距離限制參數t的Bounded BFS算法；

S3，根據Bounded BFS算法的結束條件，更新有向圖圍長g的下界α或上界β；

S4，根據β、α和Bounded BFS的結束條件，刪除圖G中權值之和大于α或β的路徑；

S5，通過α和β更新距離限制參數t，重復執行步驟S2-S5直到β-α≤1 成立，得到圖G的圍長g＝β。

進一步地，所述步驟S1包括：

S1.1，計算有向圖G的最小平均值環λ；