基于并行圖計算框架大規模圖最大流加速算法

張如青，魏 蔚，張永新

(河南工業大學信息科學與工程學院，河南 鄭州 450000)

1 引言

隨著計算機技術水平的發展，很多實際問題可以用解決最大流的方法進行處理，如在城市交通方面利用最大流算法求解城市交通網絡最大通行能力[1]；利用城市排水系統構建出有向網絡模型，使用最大流算法計算出排水管網的排水量[2]；在大規模資源調度方面，將資源調度問題轉換成最小費用最大流圖的構造和求解問題[3]，最大流在網絡規劃和圖像分割等領域有著廣泛的應用[4][5]。然而，這些算法在計算最大流時存在大量冗余工作，導致求解最大流問題效率較低。將原始圖中的強連通分量縮減到頂點以及基于底層并行架構實現最大流的計算作為可以有效減少冗余計算的方法，引起了很多研究者的關注。

文獻[6]采用粒計算思想在網絡中縮減最大集的方法計算出近似的最大流量。文獻[7]通過合并由簡單邊連接的節點來構造縮減圖進而計算出最大流值，加快了求解最大流的速度，但不能對現有算法實現并行，也不能減少圖分割占用的內存。文獻[8]根據圖中的邊將原圖隨機劃分成多個子圖，合并各個子圖的最大流值求出近似的最大流量。采用Ford-Fulkerson并行求解最大流算法，利用優化提高MapReduce的有效性和并行性，將最大流計算時間縮短至10分鐘左右。文獻[10]采用分布式算法解決Edmonds-Karp最大流問題，在算法各步驟采取不同的計算模型，利用Spark框架中內置的pregel接口提升算法并行度，但算法的通信成本較大。

針對上述問題，提出基于單機圖計算框架 GraphChi[11]處理大規模圖的最大流加速算法。該算法通過割點構建原始圖的覆蓋圖，給定源點和匯點后確定覆蓋圖中唯一路徑以及路徑上的各個子圖，利用GraphChi框架的并行性進行多子圖的并行計算，各子圖最大流的最小值即為原始圖中的最大流值。實驗結果證明，在GraphChi框架上并行求解各子圖最大流算法能明顯加速大規模圖中最大流的計算，有效降低了時間復雜度和空間復雜度。

2 理論模型

2.1 最大流計算理論模型

給定一個圖G=(V，E)，其中V是頂點集合，E是頂點間邊的集合。對于頂點對(s，t)，找到網絡中一個可行流(s，t)使得從頂點s的出邊流入到頂點t的流量最大，則可行流(s，t)稱為最大流，這個問題稱為最大流問題。根據上述，建立的最大流數學模型可以表示為

(1)

式中，δ+(s)表示源點s的出邊所連接的點的集合，v表示s的出邊連接的點，f(s，v)表示從s到出邊頂點v的流量。(s，t)表示從源點s到各出邊點流量的最大值之和，其值可根據每條邊的流量和容量之間的約束關系來確定。

源點s和匯點t之間約束可行流的數學模型可以表示為

(2)

δ-(v)={w∈V|(w，v)∈E}，

δ+(v)={w∈V|(v，w)∈E}

(3)

式中，δ-(t)表示t的入邊所連接的點的集合，f(v，t)表示從v到t的流量，fe表示圖中每條邊e的流量，每條邊上非負數ce為邊的容量，δ-(v)表示v的入邊所連接的點的集合，δ+(v)表示v的出邊所連接的點的集合，f(w，v)表示從w到v的流量，f(v，w)表示從v到w的流量，v∈V-{s，t}表示除源點s和匯點t以外的頂點。其中，(w，v)∈E表示w與出邊點v之間的邊屬于邊集合E，(v，w)∈E表示v與出邊點w之間的邊屬于邊集合E。

由式(2)可知，從源點s到各出邊點的總流量等于匯點t的各入邊點到t的總流量；每條邊的流量非負且最大不超過容量；除了s和t之外，從任何頂點w到所有出邊點v的總流量等于所有入邊點v到頂點w的總流量。

通過上述論述，根據最大流理論建立的數學模型和約束可行流的限制條件可以實現最大流的計算。

2.2 BDT理論模型

為有效處理大規模圖的最大流問題，基于BDT(BD-tractable)理論提出通過割點構建覆蓋圖加速最大流計算的算法。為了與傳統上研究決策問題的復雜性類保持一致[12][13]，定義布爾查詢類Ζ，并用Ζ作為術語S的鍵值對〈D，Q〉，其中Q是Ζ的一個查詢，D是在Ζ中已被定義的數據庫，且Q(D)為真。即當且僅當Q(D)為真，S才可以作為如〈D，Q〉∈S形式的二元關系。因此可以認為S是Ζ的一種術語。

定義1(復雜性類BDT0)：如果在數據集上存在PTIME-可計算的預處理函數∏，并且存在對于Q∈Z和所有數據集D的語言對S′，認定類Ζ查詢是BDT0。用BDT0表示所有BDT查詢類的集合。

在PTIME函數∏(·)中預處理D并離線生成二階結構D′=∏(D)，之后對于在D上定義的所有查詢Q∈Z，Q(D)可以通過在復雜類ΝC(Nick’sclass)中在線評估Q(D′)，即并行多項式時間來應答。

定義2(復雜性類BDT)：如果存在三個ΝC可計算函數π1(·)，π2(·)和ρ(·，·)，那么對于Ζ鍵值對〈D，Q〉上的術語S，可以認為類Ζ的查詢是BDT。比如，如果有

D′=π1(D，Q)，

Q′=π2(D，Q)，

〈D，Q〉=ρ(D′，Q′)，

(4)

則查詢類Z′是BDT，具體可表示為

Z′={Q′|Q′=π2(D，Q)，〈D，Q〉∈S}

(5)

顯然，當D=π1(D，Q)，Q=π2(D，Q)，且ρ是恒等函數時，BDT0才是BDT的一個子集。除非P=NC，BDT0才是BDT的真子集，即查詢類屬于BDT而不屬于BDT0。雖然一些查詢類Ζ不屬于BDT，但可以通過重新分解的方法將查詢類Ζ轉換為BDT可查詢類。重新分解和劃分Ζ的數據和查詢部分并識別要預處理的數據集，以便在預處理之后以并行多項式時間響應查詢。這樣為進行最大流計算提供理論依據。

2.3 基于BDT的查詢優化

假設需要在大數據集D上應答類Ζ的查詢。提出將D簡化為具有可管理大小的數據集D′(或者一定數量的片段D′)，仍可以通過只訪問小數據集D′的方法來計算準確的答案Q(D)，而不是直接對原始的大D進行操作。

這個想法很簡單。但要實施它，需要解決幾個基本問題。首先考慮到D存在的一個小子集D′，可以通過只訪問D′中的數據來應答D中的Q。接著提出識別D′的有效方法。為簡化討論，只考慮關系查詢。設R是關系模式(即R=(R1，…，Rn)，其中Ri是關系模式)，D是R的數據庫實例，Q是查詢類Ζ如關系代數或連接查詢的查詢，M是非負整數。 設|D|是D的大小，以D關系數組中的大小來衡量。

定義3：假設Q在D中是M規模獨立的，即如果存在一個子集DQ∈D，則

|DQ|≤M，Q(DQ)=Q(D).

(6)

也就是說，為了在D中應答Q，不管D的大小，只需要從D中取最多M個元組就可以應答Q。把DQ作為在D中應答Q的核心，注意DQ可能不是唯一的。因此，希望找到一個最小核心。如果R中的所有實例D，對于D而言Q都是M規模獨立的，那么R對于Q也是M規模獨立的。即總能找到用于在D中應答Q的最多M個元組的核心數據集DQ。

上述理論指出，對于大圖查詢，只要能符合理論規范并找到核心數據集，就能有效加速計算。對于最大流的計算，由于每次計算不一定要涉及所有節點，因此針對每次特定計算尋找核心數據集DQ從而可以簡化計算。

3 算法

3.1 通過割點構建原始圖的覆蓋圖

根據原始圖中割點構建的覆蓋圖如圖1，原始圖中的割點映射為覆蓋圖中的虛線頂點。

圖1 覆蓋圖構建示意圖

算法使用DFS從原圖的根節點進行遍歷。在算法的開始，遍歷當前頂點x的每一個鄰居頂點z，若鄰居頂點z未被訪問，則depth值加1，接著從z開始DFS遍歷，隨著頂點的不斷遍歷，low值更新為通過非父親頂點能夠追溯到depth值最小的頂點。當遍歷到葉子結點后回溯，若鄰居頂點z已被訪問且lowz≥depthx，則x為割點，將x映射到覆蓋圖中頂點X。若棧頂元素不是x或z，則棧頂元素出棧并把棧頂元素頂點對中不是x的頂點加入到覆蓋圖X頂點映射的子圖中。找到全部割點后根據原圖中割點之間的關系在覆蓋圖中建立相應的聯系。將子圖和覆蓋圖的數據保存，以便在給定源點和匯點后確定所在的子圖和覆蓋圖中對應的頂點。

算法1是算法的核心部分，描述了根據原圖中割點構建覆蓋圖的詳細過程。

輸入：所有頂點，頂點之間的邊，權值

輸出：覆蓋圖以及子圖

1)當前頂點x設置為正在訪問， 初始化每個頂點low[i]=INF，depth[i]=-1，parent[i]=-1;

2)for x的每一個鄰居節點z do

3) if z正在被訪問或已經被訪問

4) if depthz==depthx-1， continue;

5) if depthz>depthx， continue;

6) end

7) if z未被訪問

8) depthz=depthx+1;

9) 將邊(x，z)入棧

10) 在頂點z上調用當前過程

11) end

12) if z正在被訪問

13) tmp=depthz;

14) end

15) if z已經被訪問

16) tmp=lowz;

17) end

18) if lowx>t

19) lowx=t;

20) end

21) if z已被訪問且lowz≥depthx

22) if 割點標識isCutx==false

23) 設置當前頂點isCutx=true;

24) 將x加入覆蓋圖中并設為X，建立x與X之間的映射關系

25) end

26) do

27) 邊(u，q)出棧， 將u，q分別映射為U，Q

28) if u≠x， 將u加入子圖IGu

29) if q≠x， 將q加入子圖IGq

30) if u是割點， 在覆蓋圖中頂點U和X之間建立邊

31) if q是割點， 在覆蓋圖中頂點Q和X之間建立邊

32) while !(u==x&&q==z)

33) end

34)end

3.2 基于GraphChi框架并行計算最大流

基于GraphChi框架并行求解最大流示意圖如圖2，頂點EBADFG連成的路徑是給定源點和匯點后在覆蓋圖上確定的唯一路徑，每個頂點對應原圖中一個子圖。

圖2 基于GraphChi框架求解最大流示意圖

給定原圖中頂點對(s，t)，由算法1找到s和t分別在子圖IGu和IGv中，且分別對應覆蓋圖中頂點U和V。若s和t在同一個子圖中，則直接計算s和t之間的最大流。若s和t不在同一個子圖，則在覆蓋圖中遍歷從U能夠到達V的路徑，確定路徑后找到路徑上的子圖。由U對應原圖中割點u，V對應原圖中割點v，將路徑上的子圖提交到GraphChi框架上并行計算出s與u之間的最大流值、各子圖中割點之間的最大流值以及v與t之間的最大流值。將各子圖最大流的最小值作為原圖的最大流值。

算法2描述了給定原圖中頂點對(s，t)，確定覆蓋圖中的路徑和在GraphChi框架上計算路徑上各子圖最大流的詳細過程。

輸入：給定原始圖中的源點s和匯點t

輸出：最大流值

1)確定s在子圖IGu中， t在子圖IGv中

2)覆蓋圖中頂點U對應原圖中割點u， 覆蓋圖中頂點V對應原圖中割點v

3)while true

4) if U==V

5) 對(s，t)進行最大流計算

6) end

7) if U!=V

8) 確定U與V之間唯一路徑上經過的頂點W1，W2，W3….Wn

9) 在GraphChi框架上并行計算s與u之間的最大流， W1，W2，W3….Wn對應原圖中各子圖的最大流， 以及v與t之間的最大流

10) end

11) 找到路徑上各子圖最大流值的最小值即為原始圖的最大流值

12)end

4 實驗結果與分析

針對圖數據結構復雜多變、耦合性強，雖已有很多分布式圖計算系統可進行最大流的計算，但這些圖計算系統無法將整個圖一次完全載入到內存中，而基于磁盤的單機圖計算系統GraphChi很好的解決了這個問題。GraphChi是基于單機多核框架上實現的大規模圖處理系統，使用并行滑動窗口減少磁盤的隨機讀寫，從而減少處理過程中的磁盤訪問時間。因此，將大規模圖通過割點構建覆蓋圖并分割成子圖，在確定路徑后利用GraphChi框架的特性計算出各子圖的最大流，可顯著縮短最大流的計算時間。

為了對基于GraphChi框架的大規模圖最大流加速算法進行評估，本實驗在Graphchi框架上進行，使用CPU為i5-4200 @ 1.6GHz，內存為8G，Windows10操作系統。實驗數據取自美國路網[14]中5個不同地區的數據集。

根據上述實驗環境及數據集，實驗不同算法進行最大流計算的執行時間，實驗過程中在每個數據集上隨機抽取50組頂點對(s，t)進行最大流的計算。基于GraphChi框架大規模圖最大流加速算法由于在每個數據集上的覆蓋圖和子圖只需生成一次，因此該算法在數據集上的平均執行時間是這50組(s，t)在一個數據集上生成覆蓋圖和子圖的總時間，查找s和t所在子圖和確定覆蓋圖中路徑的時間，以及在GraphChi框架上并行計算各子圖最大流時間的和的平均值。Ford-Fulkerson算法以50組頂點對計算最大流時間的平均值作為該算法在各數據集上的平均執行時間。兩種算法在5個數據集上的平均執行時間，實驗結果如圖3所示。

圖3 不同算法在各數據集上執行時間對比

由圖3可以看出，對于同一個數據集在GraphChi框架上計算最大流算法的執行時間明顯少于Ford-Fulkerson算法的執行時間。兩種算法在頂點數為321270的數據集的執行時間相對于其它數據集的執行時間明顯縮短，這是因為在這個數據集上隨機抽取的源點和匯點經過的子圖都相對較小，而最大流的計算與源點到匯點所經過的子圖大小有關，源點與匯點間的子圖越小計算的時間越短。從頂點數為321270的數據集開始，GraphChi框架上計算最大流算法的執行時間緩慢增長，而Ford-Fulkerson算法的執行時間則急劇增長。這是因為并行算法在每個數據集上的覆蓋圖和子圖只生成一次，且只需要計算必要的子圖，因此在各數據集上計算最大流可顯著縮短最大流的執行時間。說明在GraphChi框架上計算最大流算法有效地提高了最大流的計算速度。

算法的優劣主要從算法的執行時間和所需要占用的存儲空間兩個方面衡量，因此除了對比兩種算法在各數據集上計算最大流的執行時間外，還可以比較兩種算法在不同數據集上內存消耗方面的差異。根據實驗環境和5個不同地區的數據集，在每個數據集上隨機取50組源點和匯點進行最大流的計算，其中兩種算法的內存開銷通過操作系統API查看，并行算法在每個數據集上計算最大流消耗內存的平均值是50組頂點對生成覆蓋圖和子圖的內存、查找路徑所占用的內存以及在GraphChi上計算最大流消耗的內存之和的平均值。而Ford-Fulkerson算法在相同數據集上消耗內存的平均值是對50組頂點對計算最大流時消耗的總內存的平均值。實驗結果如圖4所示。

圖4 不同算法在各數據集上內存開銷對比

通過圖4可以看出，前四個數據集在GraphChi框架上計算最大流算法消耗的內存少于Ford-Fulkerson算法消耗的內存，隨著數據集頂點數的增加兩種算法的內存開銷也逐漸增大，在頂點數為1207945的數據集上并行算法比Ford-Fulkerson算法消耗的內存多，這是因為GraphChi框架需要對子圖進行多次迭代導致并行算法消耗的內存顯著增加。當數據集較小時，基于GraphChi框架計算最大流消耗的內存少于Ford-Fulkerson算法消耗的內存，但是由于在GraphChi框架需要對子圖進行多次迭代導致并行算法在數據集較大時內存開銷會顯著增加、空間復雜度增高，因此當數據集較大時基于GraphChi框架計算最大流消耗的內存會高于Ford-Fulkerson算法消耗的內存。

5 結論

針對最大流算法計算復雜度較高的問題，提出一種利用大規模圖的割點構建覆蓋圖并在GraphChi框架上進行多子圖并行計算的加速算法。實驗采用在每個數據集上隨機抽取50組源點和匯點進行最大流計算的平均執行時間以及內存開銷作為評價標準，實驗結果表明，在GraphChi框架上計算最大流算法相較于Ford-Fulkerson算法能有效縮短最大流的計算時間，提高最大流的計算速度，當數據集較小時空間復雜度較低。下一步的研究工作重點是如何平衡各子圖規模，進一步提高并行計算的速度，降低最大流的空間復雜度。