基于并行圖計(jì)算框架大規(guī)模圖最大流加速算法

張如青，魏 蔚，張永新

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

1 引言

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

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

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

2 理論模型

2.1 最大流計(jì)算理論模型

給定一個(gè)圖G=(V，E)，其中V是頂點(diǎn)集合，E是頂點(diǎn)間邊的集合。對(duì)于頂點(diǎn)對(duì)(s，t)，找到網(wǎng)絡(luò)中一個(gè)可行流(s，t)使得從頂點(diǎn)s的出邊流入到頂點(diǎn)t的流量最大，則可行流(s，t)稱為最大流，這個(gè)問(wèn)題稱為最大流問(wèn)題。根據(jù)上述，建立的最大流數(shù)學(xué)模型可以表示為

(1)

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

源點(diǎn)s和匯點(diǎn)t之間約束可行流的數(shù)學(xué)模型可以表示為

(2)

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

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

(3)

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

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

通過(guò)上述論述，根據(jù)最大流理論建立的數(shù)學(xué)模型和約束可行流的限制條件可以實(shí)現(xiàn)最大流的計(jì)算。

2.2 BDT理論模型

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

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

在PTIME函數(shù)∏(·)中預(yù)處理D并離線生成二階結(jié)構(gòu)D′=∏(D)，之后對(duì)于在D上定義的所有查詢Q∈Z，Q(D)可以通過(guò)在復(fù)雜類ΝC(Nick’sclass)中在線評(píng)估Q(D′)，即并行多項(xiàng)式時(shí)間來(lái)應(yīng)答。

定義2(復(fù)雜性類BDT)：如果存在三個(gè)ΝC可計(jì)算函數(shù)π1(·)，π2(·)和ρ(·，·)，那么對(duì)于Ζ鍵值對(duì)〈D，Q〉上的術(shù)語(yǔ)S，可以認(rèn)為類Ζ的查詢是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āng)D=π1(D，Q)，Q=π2(D，Q)，且ρ是恒等函數(shù)時(shí)，BDT0才是BDT的一個(gè)子集。除非P=NC，BDT0才是BDT的真子集，即查詢類屬于BDT而不屬于BDT0。雖然一些查詢類Ζ不屬于BDT，但可以通過(guò)重新分解的方法將查詢類Ζ轉(zhuǎn)換為BDT可查詢類。重新分解和劃分Ζ的數(shù)據(jù)和查詢部分并識(shí)別要預(yù)處理的數(shù)據(jù)集，以便在預(yù)處理之后以并行多項(xiàng)式時(shí)間響應(yīng)查詢。這樣為進(jìn)行最大流計(jì)算提供理論依據(jù)。

2.3 基于BDT的查詢優(yōu)化

假設(shè)需要在大數(shù)據(jù)集D上應(yīng)答類Ζ的查詢。提出將D簡(jiǎn)化為具有可管理大小的數(shù)據(jù)集D′(或者一定數(shù)量的片段D′)，仍可以通過(guò)只訪問(wèn)小數(shù)據(jù)集D′的方法來(lái)計(jì)算準(zhǔn)確的答案Q(D)，而不是直接對(duì)原始的大D進(jìn)行操作。

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

定義3：假設(shè)Q在D中是M規(guī)模獨(dú)立的，即如果存在一個(gè)子集DQ∈D，則

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

(6)

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

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

3 算法

3.1 通過(guò)割點(diǎn)構(gòu)建原始圖的覆蓋圖

根據(jù)原始圖中割點(diǎn)構(gòu)建的覆蓋圖如圖1，原始圖中的割點(diǎn)映射為覆蓋圖中的虛線頂點(diǎn)。

圖1 覆蓋圖構(gòu)建示意圖

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

算法1是算法的核心部分，描述了根據(jù)原圖中割點(diǎn)構(gòu)建覆蓋圖的詳細(xì)過(guò)程。

輸入：所有頂點(diǎn)，頂點(diǎn)之間的邊，權(quán)值

輸出：覆蓋圖以及子圖

1)當(dāng)前頂點(diǎn)x設(shè)置為正在訪問(wèn)， 初始化每個(gè)頂點(diǎn)low[i]=INF，depth[i]=-1，parent[i]=-1;

2)for x的每一個(gè)鄰居節(jié)點(diǎn)z do

3) if z正在被訪問(wèn)或已經(jīng)被訪問(wèn)

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

5) if depthz>depthx， continue;

6) end

7) if z未被訪問(wèn)

8) depthz=depthx+1;

9) 將邊(x，z)入棧

10) 在頂點(diǎn)z上調(diào)用當(dāng)前過(guò)程

11) end

12) if z正在被訪問(wèn)

13) tmp=depthz;

14) end

15) if z已經(jīng)被訪問(wèn)

16) tmp=lowz;

17) end

18) if lowx>t

19) lowx=t;

20) end

21) if z已被訪問(wèn)且lowz≥depthx

22) if 割點(diǎn)標(biāo)識(shí)isCutx==false

23) 設(shè)置當(dāng)前頂點(diǎn)isCutx=true;

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

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是割點(diǎn)， 在覆蓋圖中頂點(diǎn)U和X之間建立邊

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

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

33) end

34)end

3.2 基于GraphChi框架并行計(jì)算最大流

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

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

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

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

輸入：給定原始圖中的源點(diǎn)s和匯點(diǎn)t

輸出：最大流值

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

2)覆蓋圖中頂點(diǎn)U對(duì)應(yīng)原圖中割點(diǎn)u， 覆蓋圖中頂點(diǎn)V對(duì)應(yīng)原圖中割點(diǎn)v

3)while true

4) if U==V

5) 對(duì)(s，t)進(jìn)行最大流計(jì)算

6) end

7) if U!=V

8) 確定U與V之間唯一路徑上經(jīng)過(guò)的頂點(diǎn)W1，W2，W3….Wn

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

10) end

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

12)end

4 實(shí)驗(yàn)結(jié)果與分析

針對(duì)圖數(shù)據(jù)結(jié)構(gòu)復(fù)雜多變、耦合性強(qiáng)，雖已有很多分布式圖計(jì)算系統(tǒng)可進(jìn)行最大流的計(jì)算，但這些圖計(jì)算系統(tǒng)無(wú)法將整個(gè)圖一次完全載入到內(nèi)存中，而基于磁盤(pán)的單機(jī)圖計(jì)算系統(tǒng)GraphChi很好的解決了這個(gè)問(wèn)題。GraphChi是基于單機(jī)多核框架上實(shí)現(xiàn)的大規(guī)模圖處理系統(tǒng)，使用并行滑動(dòng)窗口減少磁盤(pán)的隨機(jī)讀寫(xiě)，從而減少處理過(guò)程中的磁盤(pán)訪問(wèn)時(shí)間。因此，將大規(guī)模圖通過(guò)割點(diǎn)構(gòu)建覆蓋圖并分割成子圖，在確定路徑后利用GraphChi框架的特性計(jì)算出各子圖的最大流，可顯著縮短最大流的計(jì)算時(shí)間。

為了對(duì)基于GraphChi框架的大規(guī)模圖最大流加速算法進(jìn)行評(píng)估，本實(shí)驗(yàn)在Graphchi框架上進(jìn)行，使用CPU為i5-4200 @ 1.6GHz，內(nèi)存為8G，Windows10操作系統(tǒng)。實(shí)驗(yàn)數(shù)據(jù)取自美國(guó)路網(wǎng)[14]中5個(gè)不同地區(qū)的數(shù)據(jù)集。

根據(jù)上述實(shí)驗(yàn)環(huán)境及數(shù)據(jù)集，實(shí)驗(yàn)不同算法進(jìn)行最大流計(jì)算的執(zhí)行時(shí)間，實(shí)驗(yàn)過(guò)程中在每個(gè)數(shù)據(jù)集上隨機(jī)抽取50組頂點(diǎn)對(duì)(s，t)進(jìn)行最大流的計(jì)算?；贕raphChi框架大規(guī)模圖最大流加速算法由于在每個(gè)數(shù)據(jù)集上的覆蓋圖和子圖只需生成一次，因此該算法在數(shù)據(jù)集上的平均執(zhí)行時(shí)間是這50組(s，t)在一個(gè)數(shù)據(jù)集上生成覆蓋圖和子圖的總時(shí)間，查找s和t所在子圖和確定覆蓋圖中路徑的時(shí)間，以及在GraphChi框架上并行計(jì)算各子圖最大流時(shí)間的和的平均值。Ford-Fulkerson算法以50組頂點(diǎn)對(duì)計(jì)算最大流時(shí)間的平均值作為該算法在各數(shù)據(jù)集上的平均執(zhí)行時(shí)間。兩種算法在5個(gè)數(shù)據(jù)集上的平均執(zhí)行時(shí)間，實(shí)驗(yàn)結(jié)果如圖3所示。

圖3 不同算法在各數(shù)據(jù)集上執(zhí)行時(shí)間對(duì)比

由圖3可以看出，對(duì)于同一個(gè)數(shù)據(jù)集在GraphChi框架上計(jì)算最大流算法的執(zhí)行時(shí)間明顯少于Ford-Fulkerson算法的執(zhí)行時(shí)間。兩種算法在頂點(diǎn)數(shù)為321270的數(shù)據(jù)集的執(zhí)行時(shí)間相對(duì)于其它數(shù)據(jù)集的執(zhí)行時(shí)間明顯縮短，這是因?yàn)樵谶@個(gè)數(shù)據(jù)集上隨機(jī)抽取的源點(diǎn)和匯點(diǎn)經(jīng)過(guò)的子圖都相對(duì)較小，而最大流的計(jì)算與源點(diǎn)到匯點(diǎn)所經(jīng)過(guò)的子圖大小有關(guān)，源點(diǎn)與匯點(diǎn)間的子圖越小計(jì)算的時(shí)間越短。從頂點(diǎn)數(shù)為321270的數(shù)據(jù)集開(kāi)始，GraphChi框架上計(jì)算最大流算法的執(zhí)行時(shí)間緩慢增長(zhǎng)，而Ford-Fulkerson算法的執(zhí)行時(shí)間則急劇增長(zhǎng)。這是因?yàn)椴⑿兴惴ㄔ诿總€(gè)數(shù)據(jù)集上的覆蓋圖和子圖只生成一次，且只需要計(jì)算必要的子圖，因此在各數(shù)據(jù)集上計(jì)算最大流可顯著縮短最大流的執(zhí)行時(shí)間。說(shuō)明在GraphChi框架上計(jì)算最大流算法有效地提高了最大流的計(jì)算速度。

算法的優(yōu)劣主要從算法的執(zhí)行時(shí)間和所需要占用的存儲(chǔ)空間兩個(gè)方面衡量，因此除了對(duì)比兩種算法在各數(shù)據(jù)集上計(jì)算最大流的執(zhí)行時(shí)間外，還可以比較兩種算法在不同數(shù)據(jù)集上內(nèi)存消耗方面的差異。根據(jù)實(shí)驗(yàn)環(huán)境和5個(gè)不同地區(qū)的數(shù)據(jù)集，在每個(gè)數(shù)據(jù)集上隨機(jī)取50組源點(diǎn)和匯點(diǎn)進(jìn)行最大流的計(jì)算，其中兩種算法的內(nèi)存開(kāi)銷通過(guò)操作系統(tǒng)API查看，并行算法在每個(gè)數(shù)據(jù)集上計(jì)算最大流消耗內(nèi)存的平均值是50組頂點(diǎn)對(duì)生成覆蓋圖和子圖的內(nèi)存、查找路徑所占用的內(nèi)存以及在GraphChi上計(jì)算最大流消耗的內(nèi)存之和的平均值。而Ford-Fulkerson算法在相同數(shù)據(jù)集上消耗內(nèi)存的平均值是對(duì)50組頂點(diǎn)對(duì)計(jì)算最大流時(shí)消耗的總內(nèi)存的平均值。實(shí)驗(yàn)結(jié)果如圖4所示。

圖4 不同算法在各數(shù)據(jù)集上內(nèi)存開(kāi)銷對(duì)比

通過(guò)圖4可以看出，前四個(gè)數(shù)據(jù)集在GraphChi框架上計(jì)算最大流算法消耗的內(nèi)存少于Ford-Fulkerson算法消耗的內(nèi)存，隨著數(shù)據(jù)集頂點(diǎn)數(shù)的增加兩種算法的內(nèi)存開(kāi)銷也逐漸增大，在頂點(diǎn)數(shù)為1207945的數(shù)據(jù)集上并行算法比Ford-Fulkerson算法消耗的內(nèi)存多，這是因?yàn)镚raphChi框架需要對(duì)子圖進(jìn)行多次迭代導(dǎo)致并行算法消耗的內(nèi)存顯著增加。當(dāng)數(shù)據(jù)集較小時(shí)，基于GraphChi框架計(jì)算最大流消耗的內(nèi)存少于Ford-Fulkerson算法消耗的內(nèi)存，但是由于在GraphChi框架需要對(duì)子圖進(jìn)行多次迭代導(dǎo)致并行算法在數(shù)據(jù)集較大時(shí)內(nèi)存開(kāi)銷會(huì)顯著增加、空間復(fù)雜度增高，因此當(dāng)數(shù)據(jù)集較大時(shí)基于GraphChi框架計(jì)算最大流消耗的內(nèi)存會(huì)高于Ford-Fulkerson算法消耗的內(nèi)存。

5 結(jié)論

針對(duì)最大流算法計(jì)算復(fù)雜度較高的問(wèn)題，提出一種利用大規(guī)模圖的割點(diǎn)構(gòu)建覆蓋圖并在GraphChi框架上進(jìn)行多子圖并行計(jì)算的加速算法。實(shí)驗(yàn)采用在每個(gè)數(shù)據(jù)集上隨機(jī)抽取50組源點(diǎn)和匯點(diǎn)進(jìn)行最大流計(jì)算的平均執(zhí)行時(shí)間以及內(nèi)存開(kāi)銷作為評(píng)價(jià)標(biāo)準(zhǔn)，實(shí)驗(yàn)結(jié)果表明，在GraphChi框架上計(jì)算最大流算法相較于Ford-Fulkerson算法能有效縮短最大流的計(jì)算時(shí)間，提高最大流的計(jì)算速度，當(dāng)數(shù)據(jù)集較小時(shí)空間復(fù)雜度較低。下一步的研究工作重點(diǎn)是如何平衡各子圖規(guī)模，進(jìn)一步提高并行計(jì)算的速度，降低最大流的空間復(fù)雜度。