動(dòng)態(tài)網(wǎng)絡(luò)中最大流快速增量求解

張柏禮 王媛瑗 洪 亮 田 偉 呂建華, 2

(1東南大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院, 南京 211189)(2東南大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)和信息集成教育部重點(diǎn)實(shí)驗(yàn)室, 南京 211189)(3中國能源研究會(huì)電力安全與應(yīng)急技術(shù)中心, 北京 100045)(4南京弘毅電氣自動(dòng)化有限公司, 南京 210039)

動(dòng)態(tài)網(wǎng)絡(luò)中最大流快速增量求解

張柏禮1,2王媛瑗1洪 亮3田 偉4呂建華1, 2

(1東南大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院, 南京 211189)(2東南大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)和信息集成教育部重點(diǎn)實(shí)驗(yàn)室, 南京 211189)(3中國能源研究會(huì)電力安全與應(yīng)急技術(shù)中心, 北京 100045)(4南京弘毅電氣自動(dòng)化有限公司, 南京 210039)

利用損毀網(wǎng)絡(luò)與原網(wǎng)絡(luò)的結(jié)構(gòu)包含性,提出了一種基于增廣路徑選擇樹的最大流增量算法MFIA-ART．算法在原網(wǎng)絡(luò)最大流的求解過程中,對(duì)簡單路徑集等相關(guān)的中間結(jié)果給予緩存,構(gòu)成增廣路徑候選集,當(dāng)網(wǎng)絡(luò)拓?fù)涓淖儠r(shí)直接在其中查找有效的增廣路徑,無需對(duì)新的殘余網(wǎng)絡(luò)進(jìn)行復(fù)雜計(jì)算. 同時(shí)為了避免遍歷包含飽和邊的簡單路徑,進(jìn)一步利用增廣路徑選擇樹ART來組織所有可能的增廣路徑集,從而可以通過一條從根節(jié)點(diǎn)到某個(gè)葉節(jié)點(diǎn)的路徑找到所有需要的增廣路徑,獲得最大流量．其遍歷的深度為ART樹的高度H,遠(yuǎn)小于所有增廣路徑的數(shù)量,因而顯著地提高了求解最大流的效率．實(shí)驗(yàn)結(jié)果表明,MFIA-ART相對(duì)于采用經(jīng)典的Dinic算法重新計(jì)算最大流的方法,在時(shí)間性能方面有數(shù)量級(jí)的提高,尤其適合應(yīng)用于簡單路徑數(shù)量較少的稀疏性網(wǎng)絡(luò)．

最大流;增量算法;增廣路徑選擇樹;簡單路徑

最大流描述了流網(wǎng)絡(luò)中源點(diǎn)和匯點(diǎn)之間能夠傳遞的最大流量,是衡量網(wǎng)絡(luò)性能的關(guān)鍵指標(biāo)之一,廣泛應(yīng)用于交通運(yùn)輸網(wǎng)絡(luò)、電力傳輸網(wǎng)絡(luò)、排水網(wǎng)絡(luò)等系統(tǒng)中．同時(shí)最大流也是重要的決策部署依據(jù),例如交通運(yùn)輸部門需要根據(jù)車輛通行情況合理地新修或擴(kuò)建道路網(wǎng)絡(luò),也需要根據(jù)當(dāng)前路況進(jìn)行車輛通行數(shù)量的控制和疏導(dǎo),從而保證交通運(yùn)輸網(wǎng)絡(luò)的暢通．針對(duì)最大流的研究已有50多年的歷史[1],研究人員不斷地提出各種有效的方法用于提高求解最大流算法的效率以及解決其他相關(guān)問題．如早期Dantzig[2-3]提出的網(wǎng)絡(luò)單純形法及Ford等[4]提出的增載軌法,2種方法都屬于偽多項(xiàng)式時(shí)間算法．Edmonds等[5]提出了多項(xiàng)式時(shí)間算法．Goldberg等[6]提出二分長度阻塞流算法,首次將時(shí)間復(fù)雜度因子由nm降為min{n2/3,m1/2}m,其中,n為網(wǎng)絡(luò)中邊的數(shù)量,m為網(wǎng)絡(luò)中的頂點(diǎn)數(shù)．然而算法包含大量網(wǎng)絡(luò)轉(zhuǎn)換,過程復(fù)雜，具體實(shí)現(xiàn)比較困難．近年來,一些研究人員針對(duì)特定的網(wǎng)絡(luò)提出了相應(yīng)的最大流解決方案,如張憲超等[7-8]針對(duì)節(jié)點(diǎn)和邊都有容量限制的無向平面網(wǎng)絡(luò),提出了利用最小割求解最大流問題的方案,使得問題在O(nlogn)的時(shí)間內(nèi)獲得解決．另一方面為了快速獲得網(wǎng)絡(luò)最大流,近似算法成為研究熱點(diǎn)．如文獻(xiàn)[9-11]針對(duì)無向圖提出了各種有效的近似算法,文獻(xiàn)[12]基于熵空間理論提出了針對(duì)有向圖的相鄰節(jié)點(diǎn)集壓縮的最大流近似方法,文獻(xiàn)[13]則利用遺傳算法實(shí)現(xiàn)近似計(jì)算．在最大流理論具體應(yīng)用過程中,為了滿足實(shí)際的需求,研究人員拓展了原有最大流的研究領(lǐng)域,提出了最小費(fèi)用最大流[14-15]、二部圖最佳匹配[16-17]、網(wǎng)絡(luò)容量可靠性[18-19]及最可靠最大流[20]等其他相關(guān)問題,并提出了相應(yīng)的求解算法．

隨著應(yīng)用的深入,不難發(fā)現(xiàn)實(shí)際網(wǎng)絡(luò)具有很強(qiáng)的動(dòng)態(tài)性,即網(wǎng)絡(luò)的承載容量和網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)會(huì)隨機(jī)發(fā)生變化．張玲[21]著重研究了網(wǎng)絡(luò)中容量隨時(shí)間變化的動(dòng)態(tài)網(wǎng)絡(luò)中某一時(shí)刻的最大流問題,提出了利用熵空間思想將動(dòng)態(tài)網(wǎng)絡(luò)分解成靜態(tài)網(wǎng)絡(luò)的組合,然后通過分析靜態(tài)網(wǎng)絡(luò)得到動(dòng)態(tài)網(wǎng)絡(luò)性質(zhì)的解決方案．拓?fù)浣Y(jié)構(gòu)隨時(shí)發(fā)生改變的動(dòng)態(tài)網(wǎng)絡(luò)往往對(duì)最大流這一重要性能指標(biāo)的計(jì)算提出了實(shí)時(shí)性的要求．對(duì)于小規(guī)模的網(wǎng)絡(luò),利用傳統(tǒng)最大流計(jì)算方法進(jìn)行重新計(jì)算或許能滿足要求,但對(duì)于龐大的實(shí)際網(wǎng)絡(luò),則因最大流算法的計(jì)算復(fù)雜性較高,一般難以滿足實(shí)時(shí)性的需求．而增量計(jì)算憑借其高效快速的特性被廣泛地應(yīng)用于各種對(duì)計(jì)算實(shí)時(shí)性要求較高的解決方案中[22-24]．為此,本文基于增量計(jì)算這一思想,研究進(jìn)一步提升最大流算法的效率．鑒于動(dòng)態(tài)變化后的網(wǎng)絡(luò)Gd(現(xiàn)階段主要以損毀后網(wǎng)絡(luò)為研究對(duì)象)和原網(wǎng)絡(luò)G具有結(jié)構(gòu)包含性,因此可以在原網(wǎng)絡(luò)計(jì)算過程中對(duì)簡單路徑集之類的中間結(jié)果予以緩存,當(dāng)網(wǎng)絡(luò)拓?fù)涓淖儠r(shí)直接在緩存路徑集中尋找有效的增廣路徑,而不再需要在Gd中重新找出所有的簡單路徑．同時(shí),為了避免遍歷包含飽和邊的失效路徑,本文又提出了利用增廣路徑選擇樹ART(augmented routing tree)來保存網(wǎng)絡(luò)中所有可能的增廣路徑集,可以通過一次根節(jié)點(diǎn)到葉子的遍歷,在O(H)時(shí)間內(nèi)獲得增廣路徑集(H為ART樹的高度),最終獲得Gd的最大流,從而顯著提升算法效率．

1 最大流增量算法

1.1 算法的基本思路

當(dāng)前最大流算法的設(shè)計(jì)思路一般都來源于Ford等[4]提出的最大流計(jì)算方法,即不斷地從殘余網(wǎng)絡(luò)中尋找一條增廣路徑,累加增廣流量并更新殘余網(wǎng)絡(luò),直到網(wǎng)絡(luò)中不存在新的增廣路徑就可以得到網(wǎng)絡(luò)最大流．標(biāo)號(hào)法是一種尋找增廣路徑的常用方法,3種經(jīng)典的最大流算法(Dinic算法、最短路徑組合算法SAP及改進(jìn)的路徑組合算法ISAP)都使用標(biāo)號(hào)法尋求增廣路徑．其中,SAP算法通過廣度優(yōu)先遍歷對(duì)殘余網(wǎng)絡(luò)進(jìn)行分層,然后從源點(diǎn)s逐步尋找層數(shù)遞增的節(jié)點(diǎn),直到到達(dá)匯點(diǎn)t就可獲得一條增廣路徑,但每獲得一條增廣路徑就需要一次廣度優(yōu)先遍歷進(jìn)行重新編號(hào),導(dǎo)致算法效率不高．為此,ISAP通過相鄰節(jié)點(diǎn)的標(biāo)號(hào)及邊的流量是否飽和直接獲得節(jié)點(diǎn)新的標(biāo)號(hào),在更新殘余網(wǎng)絡(luò)的同時(shí)更新節(jié)點(diǎn)標(biāo)號(hào),提高了算法的計(jì)算效率,但仍然沒有降低算法的時(shí)間復(fù)雜度．通過對(duì)這些算法的研究,可以發(fā)現(xiàn)尋找增廣路徑是最大流算法中最復(fù)雜的過程,也是最耗時(shí)的階段,因此如能采取有效手段縮短增廣路徑尋找過程,即可提高最大流算法的計(jì)算效率．

增廣路徑來源于網(wǎng)絡(luò)中的簡單路徑,當(dāng)網(wǎng)絡(luò)中的某些邊損毀后,新網(wǎng)絡(luò)的簡單路徑包含于原網(wǎng)絡(luò)中,因此,本文首先通過緩存原網(wǎng)絡(luò)的簡單路徑集,當(dāng)網(wǎng)絡(luò)損毀時(shí),直接在緩存的簡單路徑中尋找有效的增廣路徑,這樣可以減少增廣路徑的尋找時(shí)間,提高算法的效率;然后,進(jìn)一步提出增廣路徑選擇樹對(duì)路徑飽和后下一條有效的增廣路徑進(jìn)行預(yù)先索引,從而可以避免原始的順序查找以及對(duì)包含飽和邊的失效路徑的無效遍歷,實(shí)現(xiàn)對(duì)有效增廣路徑的快速查找．

1.2ART樹及其構(gòu)造算法

ART的相關(guān)特征如下:

2) 根節(jié)點(diǎn)的Pvalue指向簡單路徑中長度最短的路徑．

3) 從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的每條路徑上,節(jié)點(diǎn)所指向簡單路徑的長度遞增．

4)Esaturated[]記錄了從根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)路徑上的飽和邊,下一次遍歷的節(jié)點(diǎn)所指向的簡單路徑不能包含Esaturated[]中的任意一條邊,否則該簡單路徑就是無效的飽和路徑．

5) 如果路徑p中包含邊ei,則Snext[i]指向ei飽和后需要遍歷的樹節(jié)點(diǎn),否則Snext[i]為空．

ART樹可以通過遞歸的方式創(chuàng)建,具體創(chuàng)建過程見算法1.

算法1 CreateART

輸出: the root of ART *r.

if(plist==NULL) return NULL;

inti=0;

if the simple path contains the saturated edges

returnCreateART(plist->next,enum,Esaturated,n);

else

create a tree noder,r->pvalue=plist;

for(i=1;i<=enum;i++)

if this path contain edgei

Esaturated[n++]=i;

r->SNext[i]=CreateART(

plist->next,enum,Esaturated,n);

n--;

else

r->Snext[i]=NULL;

returnr;

算法1中,plist保存了網(wǎng)絡(luò)中所有的簡單路徑,同時(shí)按照長度遞增排列;enum為網(wǎng)絡(luò)中邊的數(shù)量．根據(jù)定義可知ART中從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)包含的路徑集是一組可能的增廣路徑集,因此ART保存了網(wǎng)絡(luò)中所有可能的增廣路徑集．圖1為一個(gè)有5個(gè)頂點(diǎn)9條邊的網(wǎng)絡(luò)圖,圖中ei/c代表邊的標(biāo)號(hào)及其容量，vi為節(jié)點(diǎn)．表1給出了圖1對(duì)應(yīng)的所有簡單路徑信息,圖2為表1對(duì)應(yīng)的ART,其中包含的邊沒有分支表示子節(jié)點(diǎn)為NULL．

簡單路徑向量P1(0,0,0,1,0,0,0,0,0)P2(1,0,0,0,0,0,0,0,1)P3(0,0,1,0,0,0,0,1,0)P4(0,1,0,0,1,0,0,0,1)P5(0,1,0,0,0,1,0,1,0)P6(0,0,1,0,0,0,1,0,1)P7(0,1,0,0,0,1,1,0,1)

圖2V5E9的增廣路徑選擇樹

2 MFIA-ART算法

增廣路徑選擇樹保存了網(wǎng)絡(luò)中所有可能的增廣路徑集,因此可以根據(jù)當(dāng)前路徑的飽和邊選擇樹分支,通過一次從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的遍歷過程在O(H)的時(shí)間內(nèi)獲取網(wǎng)絡(luò)所有增廣路徑得到的增廣流量,從而計(jì)算出網(wǎng)絡(luò)的最大流．基于增廣路徑選擇樹的最大流增量算法MFIA-ART(maximum flow incremental algorithm based on augmented routing tree)，具體過程見算法2.

算法2 MFIA-ART

輸入:r,enum, edge-capacity *Ce, fail-edgeei.

輸出: max flow of network wheneiis fail.

Intfmax=0,faug=0,esaturated=0;

set the fail edge’s capacityCe[i]=0;

PathTreeNode *p=r;

While(p){

faug=GetPathAugFlow(Ce,p->pvalue,enum);

esaturated=UpdateEdgeCap(Ce,faug,p->pvalue);

fmax+=faug;

p=p->Snext[esaturated];}

Returnfmax

算法2首先進(jìn)入根節(jié)點(diǎn),通過GetPathAugFlow獲取當(dāng)前路徑的增廣流量faug,然后使用UpdateEdgeCap更新相關(guān)邊的剩余容量,同時(shí)返回飽和邊esaturated.通過esaturated獲取下一步需要遍歷的子節(jié)點(diǎn),重復(fù)以上步驟直至到達(dá)葉子節(jié)點(diǎn),即可獲取網(wǎng)絡(luò)最大流．以圖2為例,首先獲取路徑P1的增廣流量為3,飽和邊為e4,通過e4選擇孩子節(jié)點(diǎn)進(jìn)入路徑P2,獲取增廣流量為5，飽和邊為e1；然后依次進(jìn)入左側(cè)子節(jié)點(diǎn)P3、右側(cè)子節(jié)點(diǎn)P4,以及中間子節(jié)點(diǎn)P6,從而獲取所有的增廣路徑及增廣流量．如果ART的高度為H,那么算法可以通過遍歷ART在O(H)的時(shí)間內(nèi)找到所有的增廣路徑(H一般遠(yuǎn)小于所有簡單路徑的數(shù)量),避免了Dinic算法中多次重復(fù)地從殘余網(wǎng)絡(luò)中查找增廣路徑的過程,也不必在所有緩存的簡單路徑查找新的增廣路徑．

3 實(shí)驗(yàn)

3.1 實(shí)驗(yàn)環(huán)境及數(shù)據(jù)集

為了檢驗(yàn)MFIA-ART算法的正確性及性能,本文進(jìn)行了一系列實(shí)驗(yàn).實(shí)驗(yàn)平臺(tái)為一臺(tái)Intel Core的PC機(jī)(CPU i7-3700,3.4 GHz,內(nèi)存8 GB,64位Windows 7操作系統(tǒng)),算法采用C/C++編寫,實(shí)現(xiàn)環(huán)境為Visual Studio 2010．實(shí)驗(yàn)以經(jīng)典的Dinic最大流算法為比較對(duì)象,分別從算法的時(shí)間消耗及空間消耗2方面進(jìn)行比較．為了進(jìn)一步分析算法的適用性,本文又分別從圖的規(guī)模、圖的稠密度分別對(duì)比了Dinic算法和MFIA-ART算法的時(shí)間消耗變化情況．本文中所有數(shù)據(jù)集均采用了文獻(xiàn)[25]中使用的NETGEN有向圖生成器生成,具體的圖數(shù)據(jù)包含以下2類:

1) 通過NETGEN有向圖生成器生成了V6E10,V8E14,V10E18,V12E22,V14E26,V16E34,V18E40,V20E56八組有向圖,其中,VnEm表示由n個(gè)頂點(diǎn)m邊組成的圖集合,每個(gè)集合有10～20個(gè)圖數(shù)據(jù)．圖中每條邊的容量由生成器隨機(jī)生成．本文采用了與文獻(xiàn)[20]相同的源點(diǎn)、匯點(diǎn)選取方法,即選取圖中2點(diǎn)間簡單路徑數(shù)最大的2個(gè)節(jié)點(diǎn)作為圖的源點(diǎn)s和匯點(diǎn)t．

3.2 算法性能比較

本文首先通過不同規(guī)模的圖數(shù)據(jù)對(duì)比了Dinic算法和MFIA-ART算法的時(shí)間消耗及空間消耗,然后從不同的稠密度角度對(duì)比2種算法的時(shí)間性能．

實(shí)驗(yàn)1 選取第1類數(shù)據(jù)集作為實(shí)驗(yàn)對(duì)象,比較了不同圖規(guī)模下2種算法的性能．

圖3(a)比較了經(jīng)典的Dinic算法及MFIA-ART算法的時(shí)間開銷與圖規(guī)模的關(guān)系．從圖中可以看出,本文提出的算法性能優(yōu)勢(shì)明顯,在時(shí)間性能方面比Dinic算法有數(shù)量級(jí)的提升．根據(jù)圖中數(shù)據(jù)可以發(fā)現(xiàn),2種算法的時(shí)間消耗整體上隨圖規(guī)模的增加而呈現(xiàn)上升趨勢(shì),這是由于圖的增廣路徑會(huì)隨著圖規(guī)模的擴(kuò)大而增多,但MFIA-ART算法時(shí)間消耗增長較為緩慢,因?yàn)镸FIA-ART算法只需要遍歷最多H就可以找到所有增廣路徑計(jì)算最大流．

由圖3(b)可以看出,Dinic算法的空間使用量增長緩慢,MFIA-ART算法存儲(chǔ)了所有可能的簡單路徑,故相對(duì)于Dinic算法需要使用更多的空間,且空間使用量增長較快,這是因?yàn)殡S著圖規(guī)模的增加,簡單路徑增加,ART樹的寬度會(huì)迅速增長．

(a) 時(shí)間開銷與圖規(guī)模關(guān)系

(b) 內(nèi)存開銷與圖規(guī)模的關(guān)系

實(shí)驗(yàn)2 選取第2類數(shù)據(jù)集作為實(shí)驗(yàn)對(duì)象,比較2種算法在不同稠密度下的時(shí)間消耗情況．

圖4為2種算法在圖頂點(diǎn)數(shù)固定、稠密度從0.2～0.6遞增情況下的時(shí)間消耗．分析圖中數(shù)據(jù)可知,2種算法的時(shí)間消耗整體上隨著圖稠密度增加而呈現(xiàn)上升趨勢(shì)．稠密度的增加意味著圖的邊數(shù)的增加,因此圖中源點(diǎn)、匯點(diǎn)之間的簡單路徑及增廣路徑數(shù)會(huì)增多,算法的時(shí)間開銷都會(huì)增長，反之，在稀疏網(wǎng)絡(luò)中，算法具有更好的時(shí)間性能.

圖4 算法時(shí)間開銷與稠密度的關(guān)系

4 結(jié)語

借鑒了以空間換時(shí)間的思想,利用損毀網(wǎng)絡(luò)與原網(wǎng)絡(luò)的結(jié)構(gòu)包含性,提出了基于增廣路徑選擇樹的最大流增量算法MFIA-ART．利用樹結(jié)構(gòu)對(duì)網(wǎng)絡(luò)所有可能的增廣路徑進(jìn)行組織,從而使算法可以在O(H)的時(shí)間內(nèi)找到所有能夠增廣的路徑,提高了算法的效率．實(shí)驗(yàn)表明，相對(duì)于經(jīng)典的Dinic算法,MFIA-ART算法在時(shí)間性能方面有數(shù)量級(jí)的提高．然而MFIA-ART算法的空間使用量會(huì)隨著圖規(guī)模的增大迅速增長,可以發(fā)現(xiàn)ART樹中有許多具有節(jié)點(diǎn)內(nèi)容相同但子節(jié)點(diǎn)指針不同的特性,因此后期研究將考慮合并ART樹中內(nèi)容相同的節(jié)點(diǎn)，簡化樹形結(jié)構(gòu)，從而使MFIA-ART既有較高的時(shí)間效率也有可接受的空間使用量,擴(kuò)展算法的使用范圍．

References)

[1]Goldberg A V. Recent developments in maximum flow algorithms (invited lecture)[C]//Proceedingsofthe6thScandinavianWorkshoponAlgorithmTheory.Heidelber: Springer-Verlags, 1988:1-10.

[2]Cormen T H, Leiserson C E, Rivest R L, et al.Introductiontoalgorithms[M]. 2nd ed. Cambridge: MIT Press, 2001:588-760.

[3]Ahuja R K, Magnanti T L, Orlin J B.Networkflows:Theory,algorithmsandapplications[M]. Upper Saddle River, NJ, USA: Prentice Hall Press, 2005:294-356.

[4]Ford L R, Fulkerson D R.Flowsinnetworks[M]. Princeton, USA: Princeton University Press, 1962:1-96.

[5]Edmonds J, Karp R M. Theoretical improvements in algorithm efficiency for networks flow problems[J].JournaloftheACM, 1972, 19(2):248-264. DOI:10.1145/321694.321699.

[6]Goldberg A V, Rao S. Beyond the flow decomposition barrier[J].JournaloftheACM, 1998, 45(5):783-797. DOI:10.1145/290179.290181.

[7]張憲超, 萬穎瑜, 陳國良. 一類實(shí)際網(wǎng)絡(luò)中的最小截算法[J]. 軟件學(xué)報(bào), 2003,14(5):885-890. Zhang Xianchao, Wan Yingyu, Chen Guoliang. Approaches to the minimum cut problem in a class of practical networks[J].JournalofSoftware, 2003, 14(5): 885-890.(in Chinese)

[8]張憲超, 江賀, 陳國良. 節(jié)點(diǎn)和邊都有容量的有向平面網(wǎng)絡(luò)中的最小截和最大流[J]. 計(jì)算機(jī)學(xué)報(bào), 2006,29(4):543-551. Zhang Xianchao, Jiang He, Chen Guoliang. Minimum cuts and maximum flows in directed planar networks with both node and edge capacities[J].ChineseJournalofComputers, 2006, 29(4):543-551. (in Chinese)

[9]Lee Y T, Rao S, Srivastava N. A new approach to computing maximum flows using electrical flows[C]//Proceedingsofthe45thAnnualACMSymposiumonTheoryofComputing. Palo Alto, CA, USA, 2013:755-764. DOI:10.1145/2488608.2488704.

[10]Daitch S I, Spielman D A. Faster approximate lossy generalized flow via interior point algorithms[C]//Proceedingsofthe40thAnnualACMSymposiumonTheoryofComputing. Victoria, BC, Canada, 2008:451-460. DOI:10.1145/1374376.1374441.

[11]Peng R. Approximate undirected maximum flows inO(Mpolylog(n)) time[C]//Proceedingsofthe27thAnnualACM-SIAMSymposiumonDiscreteAlgorithms. Arlington, VA, USA, 2016:1862-1867. DOI:10.1137/1.9781611974331.ch130.

[12]Zhao S, Xu X S, Hua B. Contraction network for solving maximum flow problem[C]//ProceedingsoftheACMSIGKDDWorkshoponMiningDataSemantics. Beijing, China, 2012:1-6. DOI:10.1145/2350190.2350198.

[13]Sharma M, Ghosh D. Speeding up the estimation of the expected value of maximum flow through reliable networks[J].IEEETransactionsonReliability, 2013, 62(1):105-115. DOI:10.1109/tr.2013.2241132.

[14]Hadji M, Zeghlache D. Minimum cost maximum flow algorithm for dynamic resource allocation in clouds[C]//IEEEInternationalConferenceonCloudComputing. Honolulu, Hawaii, USA, 2012:876-882. DOI:10.1109/cloud.2012.36.

[15]Szymanski T H. Achieving minimum-routing-cost maximum-flows in infrastructure wireless mesh networks[C]//IEEEWirelessCommunications&NetworkingConference. Paris, France, 2012:2031-2036. DOI:10.1109/wcnc.2012.6214124.

[16]Bora N, Arora S, Arora N. An efficient algorithm for calculating maximum bipartite matching in a graph[J].InternationalJournalofAdvancedComputerResearch, 2013, 3(10):193-199.

[17]Gu T L, Chang L, Xu Z B. A novel symbolic algorithm for mximum weighted matching in bipartite graphs[J].InternationalJournalofComunications,NetworkandSystemSciences, 2012, 4(2):111-121. DOI:10.4236/ijcns.2011.42014.

[18]Zhao P X, Zhang X. A survey on reliability evaluation of stochastic-flow networks in terms of minimal paths[C]//InternationalConferenceonInformationEngineering&ComputerScience. Wuhan, China, 2009:2010-2013. DOI:10.1109/iciecs.2009.5365424.

[19]Jane C C, Lin J S, Yuan J. Reliability evaluation of a limited-flow network in terms of minimal cutsets[J].IEEETransactionsonReliability, 1993, 42(3): 354-361, 368. DOI:10.1109/24.257817.

[20]蔡偉, 張柏禮, 呂建華. 不確定圖最可靠最大流算法研究[J].計(jì)算機(jī)學(xué)報(bào), 2012, 35(11):2371-2380. DOI:10.3724/SP.J.1016.2012.02371. Cai Wei, Zhang Baili, Lü Jianhua. Algorithms of the most reliable maximum flow on uncertain graph[J].ChineseJournalofComputers, 2012, 35(11): 2371-2380. DOI:10.3724/SP.J.1016.2012.02371.(in Chinese)

[21]張鈴. 動(dòng)態(tài)網(wǎng)絡(luò)上最大流概念及其性質(zhì)的研究[J]. 模式識(shí)別與人工智能, 2013,26(7):609-614. DOI:10.3969/j.issn.1003-6059.2013.07.001. Zhang Ling. The concept of max-flow and its properties in dynamic networks[J].PatternRecognitionandArtificialIntelligence, 2013, 26(7):609-614. DOI:10.3969/j.issn.1003-6059.2013.07.001.(in Chinese)

[22]Kas M, Wachs M, Carley K M, et al. Incremental algorithm for updating betweenness centrality in dynamically growing networks[C]//InternationalConferenceonAdvancesinSocialNetworksAnalysis&Mining. Niagara Falls, Canada, 2013:33-40. DOI:10.1145/2492517.2492533.

[23]Ben-Eliyahu-Zohary R. An incremental algorithm for generating all minimal models[J].ArtificialIntelligence, 2005, 169(1): 1-22. DOI:10.1016/j.artint.2005.06.003.

[24]Hsieh M C, Lee Y S, Yen S J. An efficient incremental algorithm for mining Web traversal patterns[C]//IEEEInternationalConferenceonE-business. Beijing, China, 2005:274-281.

[25]Klingman D, Napier A, Stutz J. NETNEN:A program for generating large scale capacitated assignment, transportation and minimal cost flow network problems[J].ManagementScience, 1974, 20(5):814-821. DOI:10.1287/mnsc.20.5.814.

[26]Johnson D B. Finding all the elementary circuits of a directed graph[J].SIAMJournalonComputing, 1975, 4(1):77-84. DOI:10.1137/0204007.

Fast incremental maximum flow algorithm in dynamic network

Zhang Baili1,2Wang Yuanyuan1Hong Liang3Tian Wei4Lü Jianhua1,2

(1School of Computer Science and Engineering, Southeast University, Nanjing 211189, China)(2Key Laboratory of Computer Network and Information Integration of Ministry of Education, Southeast University, Nanjing 211189, China)(3Electrical Power Industry Security and Emergency Response Technology Center, China Energy Research Society, Beijing 100045, China)(4Nanjing Hongyi Electric Automation Technology Co., Ltd., Nanjing 210039, China)

An maximum flow incremental algorithm based on augmented routing tree (MFIA-ART) was proposed to obtain augmenting paths directly without complex calculation. The algorithm cached the simple path information during calculating the original network maximum flow. When network topology changing, the augmenting path was obtained from the cache data, rather than through complex calculation in residual network. In addition, to avoid traversing invalid simple paths including saturated edges, an augmented routing tree was proposed to index all simple paths. Using the tree, the next augmenting paths could be sequentially found by traversing from root to leaf to achieve maximum flow. The time complexity is determined by the height of ART, it was far less than the augmenting path number thus improving the algorithm performance. Experimental results show that MFIA-ART in time performance has a greater advantage than Dinic algorithm, and it is especially suitable for sparse graph.

maximum flow; incremental algorithm; augmented routing tree; simple path

10.3969/j.issn.1001-0505.2017.03.006

2016-09-05. 作者簡介: 張柏禮(1970—)，男，博士，副教授，bailey＿zhang@163．com．

國家自然科學(xué)基金資助項(xiàng)目(61300200，61232007，61073059).

張柏禮,王媛瑗,洪亮,等.動(dòng)態(tài)網(wǎng)絡(luò)中最大流快速增量求解[J].東南大學(xué)學(xué)報(bào)(自然科學(xué)版),2017,47(3):450-455.

10.3969/j.issn.1001-0505.2017.03.006.

TP301.6;TP393

A

1001-0505(2017)03-0450-06