动态网络中最大流快速增量求解

张柏礼 王媛瑗 洪 亮 田 伟 吕建华, 2

(1东南大学计算机科学与工程学院, 南京 211189)(2东南大学计算机网络和信息集成教育部重点实验室, 南京 211189)(3中国能源研究会电力安全与应急技术中心, 北京 100045)(4南京弘毅电气自动化有限公司, 南京 210039)

动态网络中最大流快速增量求解

张柏礼1,2王媛瑗1洪 亮3田 伟4吕建华1, 2

(1东南大学计算机科学与工程学院, 南京 211189)(2东南大学计算机网络和信息集成教育部重点实验室, 南京 211189)(3中国能源研究会电力安全与应急技术中心, 北京 100045)(4南京弘毅电气自动化有限公司, 南京 210039)

利用损毁网络与原网络的结构包含性,提出了一种基于增广路径选择树的最大流增量算法MFIA-ART．算法在原网络最大流的求解过程中,对简单路径集等相关的中间结果给予缓存,构成增广路径候选集,当网络拓扑改变时直接在其中查找有效的增广路径,无需对新的残余网络进行复杂计算. 同时为了避免遍历包含饱和边的简单路径,进一步利用增广路径选择树ART来组织所有可能的增广路径集,从而可以通过一条从根节点到某个叶节点的路径找到所有需要的增广路径,获得最大流量．其遍历的深度为ART树的高度H,远小于所有增广路径的数量,因而显著地提高了求解最大流的效率．实验结果表明,MFIA-ART相对于采用经典的Dinic算法重新计算最大流的方法,在时间性能方面有数量级的提高,尤其适合应用于简单路径数量较少的稀疏性网络．

最大流;增量算法;增广路径选择树;简单路径

最大流描述了流网络中源点和汇点之间能够传递的最大流量,是衡量网络性能的关键指标之一,广泛应用于交通运输网络、电力传输网络、排水网络等系统中．同时最大流也是重要的决策部署依据,例如交通运输部门需要根据车辆通行情况合理地新修或扩建道路网络,也需要根据当前路况进行车辆通行数量的控制和疏导,从而保证交通运输网络的畅通．针对最大流的研究已有50多年的历史[1],研究人员不断地提出各种有效的方法用于提高求解最大流算法的效率以及解决其他相关问题．如早期Dantzig[2-3]提出的网络单纯形法及Ford等[4]提出的增载轨法,2种方法都属于伪多项式时间算法．Edmonds等[5]提出了多项式时间算法．Goldberg等[6]提出二分长度阻塞流算法,首次将时间复杂度因子由nm降为min{n2/3,m1/2}m,其中,n为网络中边的数量,m为网络中的顶点数．然而算法包含大量网络转换,过程复杂，具体实现比较困难．近年来,一些研究人员针对特定的网络提出了相应的最大流解决方案,如张宪超等[7-8]针对节点和边都有容量限制的无向平面网络,提出了利用最小割求解最大流问题的方案,使得问题在O(nlogn)的时间内获得解决．另一方面为了快速获得网络最大流,近似算法成为研究热点．如文献[9-11]针对无向图提出了各种有效的近似算法,文献[12]基于熵空间理论提出了针对有向图的相邻节点集压缩的最大流近似方法,文献[13]则利用遗传算法实现近似计算．在最大流理论具体应用过程中,为了满足实际的需求,研究人员拓展了原有最大流的研究领域,提出了最小费用最大流[14-15]、二部图最佳匹配[16-17]、网络容量可靠性[18-19]及最可靠最大流[20]等其他相关问题,并提出了相应的求解算法．

随着应用的深入,不难发现实际网络具有很强的动态性,即网络的承载容量和网络拓扑结构会随机发生变化．张玲[21]着重研究了网络中容量随时间变化的动态网络中某一时刻的最大流问题,提出了利用熵空间思想将动态网络分解成静态网络的组合,然后通过分析静态网络得到动态网络性质的解决方案．拓扑结构随时发生改变的动态网络往往对最大流这一重要性能指标的计算提出了实时性的要求．对于小规模的网络,利用传统最大流计算方法进行重新计算或许能满足要求,但对于庞大的实际网络,则因最大流算法的计算复杂性较高,一般难以满足实时性的需求．而增量计算凭借其高效快速的特性被广泛地应用于各种对计算实时性要求较高的解决方案中[22-24]．为此,本文基于增量计算这一思想,研究进一步提升最大流算法的效率．鉴于动态变化后的网络Gd(现阶段主要以损毁后网络为研究对象)和原网络G具有结构包含性,因此可以在原网络计算过程中对简单路径集之类的中间结果予以缓存,当网络拓扑改变时直接在缓存路径集中寻找有效的增广路径,而不再需要在Gd中重新找出所有的简单路径．同时,为了避免遍历包含饱和边的失效路径,本文又提出了利用增广路径选择树ART(augmented routing tree)来保存网络中所有可能的增广路径集,可以通过一次根节点到叶子的遍历,在O(H)时间内获得增广路径集(H为ART树的高度),最终获得Gd的最大流,从而显著提升算法效率．

1 最大流增量算法

1.1 算法的基本思路

当前最大流算法的设计思路一般都来源于Ford等[4]提出的最大流计算方法,即不断地从残余网络中寻找一条增广路径,累加增广流量并更新残余网络,直到网络中不存在新的增广路径就可以得到网络最大流．标号法是一种寻找增广路径的常用方法,3种经典的最大流算法(Dinic算法、最短路径组合算法SAP及改进的路径组合算法ISAP)都使用标号法寻求增广路径．其中,SAP算法通过广度优先遍历对残余网络进行分层,然后从源点s逐步寻找层数递增的节点,直到到达汇点t就可获得一条增广路径,但每获得一条增广路径就需要一次广度优先遍历进行重新编号,导致算法效率不高．为此,ISAP通过相邻节点的标号及边的流量是否饱和直接获得节点新的标号,在更新残余网络的同时更新节点标号,提高了算法的计算效率,但仍然没有降低算法的时间复杂度．通过对这些算法的研究,可以发现寻找增广路径是最大流算法中最复杂的过程,也是最耗时的阶段,因此如能采取有效手段缩短增广路径寻找过程,即可提高最大流算法的计算效率．

增广路径来源于网络中的简单路径,当网络中的某些边损毁后,新网络的简单路径包含于原网络中,因此,本文首先通过缓存原网络的简单路径集,当网络损毁时,直接在缓存的简单路径中寻找有效的增广路径,这样可以减少增广路径的寻找时间,提高算法的效率;然后,进一步提出增广路径选择树对路径饱和后下一条有效的增广路径进行预先索引,从而可以避免原始的顺序查找以及对包含饱和边的失效路径的无效遍历,实现对有效增广路径的快速查找．

1.2ART树及其构造算法

ART的相关特征如下:

2) 根节点的Pvalue指向简单路径中长度最短的路径．

3) 从根节点到叶子节点的每条路径上,节点所指向简单路径的长度递增．

4)Esaturated[]记录了从根节点到当前节点路径上的饱和边,下一次遍历的节点所指向的简单路径不能包含Esaturated[]中的任意一条边,否则该简单路径就是无效的饱和路径．

5) 如果路径p中包含边ei,则Snext[i]指向ei饱和后需要遍历的树节点,否则Snext[i]为空．

ART树可以通过递归的方式创建,具体创建过程见算法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保存了网络中所有的简单路径,同时按照长度递增排列;enum为网络中边的数量．根据定义可知ART中从根节点到叶子节点包含的路径集是一组可能的增广路径集,因此ART保存了网络中所有可能的增广路径集．图1为一个有5个顶点9条边的网络图,图中ei/c代表边的标号及其容量，vi为节点．表1给出了图1对应的所有简单路径信息,图2为表1对应的ART,其中包含的边没有分支表示子节点为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算法

增广路径选择树保存了网络中所有可能的增广路径集,因此可以根据当前路径的饱和边选择树分支,通过一次从根节点到叶子节点的遍历过程在O(H)的时间内获取网络所有增广路径得到的增广流量,从而计算出网络的最大流．基于增广路径选择树的最大流增量算法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首先进入根节点,通过GetPathAugFlow获取当前路径的增广流量faug,然后使用UpdateEdgeCap更新相关边的剩余容量,同时返回饱和边esaturated.通过esaturated获取下一步需要遍历的子节点,重复以上步骤直至到达叶子节点,即可获取网络最大流．以图2为例,首先获取路径P1的增广流量为3,饱和边为e4,通过e4选择孩子节点进入路径P2,获取增广流量为5，饱和边为e1；然后依次进入左侧子节点P3、右侧子节点P4,以及中间子节点P6,从而获取所有的增广路径及增广流量．如果ART的高度为H,那么算法可以通过遍历ART在O(H)的时间内找到所有的增广路径(H一般远小于所有简单路径的数量),避免了Dinic算法中多次重复地从残余网络中查找增广路径的过程,也不必在所有缓存的简单路径查找新的增广路径．

3 实验

3.1 实验环境及数据集

为了检验MFIA-ART算法的正确性及性能,本文进行了一系列实验.实验平台为一台Intel Core的PC机(CPU i7-3700,3.4 GHz,内存8 GB,64位Windows 7操作系统),算法采用C/C++编写,实现环境为Visual Studio 2010．实验以经典的Dinic最大流算法为比较对象,分别从算法的时间消耗及空间消耗2方面进行比较．为了进一步分析算法的适用性,本文又分别从图的规模、图的稠密度分别对比了Dinic算法和MFIA-ART算法的时间消耗变化情况．本文中所有数据集均采用了文献[25]中使用的NETGEN有向图生成器生成,具体的图数据包含以下2类:

1) 通过NETGEN有向图生成器生成了V6E10,V8E14,V10E18,V12E22,V14E26,V16E34,V18E40,V20E56八组有向图,其中,VnEm表示由n个顶点m边组成的图集合,每个集合有10～20个图数据．图中每条边的容量由生成器随机生成．本文采用了与文献[20]相同的源点、汇点选取方法,即选取图中2点间简单路径数最大的2个节点作为图的源点s和汇点t．

3.2 算法性能比较

本文首先通过不同规模的图数据对比了Dinic算法和MFIA-ART算法的时间消耗及空间消耗,然后从不同的稠密度角度对比2种算法的时间性能．

实验1 选取第1类数据集作为实验对象,比较了不同图规模下2种算法的性能．

图3(a)比较了经典的Dinic算法及MFIA-ART算法的时间开销与图规模的关系．从图中可以看出,本文提出的算法性能优势明显,在时间性能方面比Dinic算法有数量级的提升．根据图中数据可以发现,2种算法的时间消耗整体上随图规模的增加而呈现上升趋势,这是由于图的增广路径会随着图规模的扩大而增多,但MFIA-ART算法时间消耗增长较为缓慢,因为MFIA-ART算法只需要遍历最多H就可以找到所有增广路径计算最大流．

由图3(b)可以看出,Dinic算法的空间使用量增长缓慢,MFIA-ART算法存储了所有可能的简单路径,故相对于Dinic算法需要使用更多的空间,且空间使用量增长较快,这是因为随着图规模的增加,简单路径增加,ART树的宽度会迅速增长．

(a) 时间开销与图规模关系

(b) 内存开销与图规模的关系

实验2 选取第2类数据集作为实验对象,比较2种算法在不同稠密度下的时间消耗情况．

图4为2种算法在图顶点数固定、稠密度从0.2～0.6递增情况下的时间消耗．分析图中数据可知,2种算法的时间消耗整体上随着图稠密度增加而呈现上升趋势．稠密度的增加意味着图的边数的增加,因此图中源点、汇点之间的简单路径及增广路径数会增多,算法的时间开销都会增长，反之，在稀疏网络中，算法具有更好的时间性能.

图4 算法时间开销与稠密度的关系

4 结语

借鉴了以空间换时间的思想,利用损毁网络与原网络的结构包含性,提出了基于增广路径选择树的最大流增量算法MFIA-ART．利用树结构对网络所有可能的增广路径进行组织,从而使算法可以在O(H)的时间内找到所有能够增广的路径,提高了算法的效率．实验表明，相对于经典的Dinic算法,MFIA-ART算法在时间性能方面有数量级的提高．然而MFIA-ART算法的空间使用量会随着图规模的增大迅速增长,可以发现ART树中有许多具有节点内容相同但子节点指针不同的特性,因此后期研究将考虑合并ART树中内容相同的节点，简化树形结构，从而使MFIA-ART既有较高的时间效率也有可接受的空间使用量,扩展算法的使用范围．

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]张宪超, 万颖瑜, 陈国良. 一类实际网络中的最小截算法[J]. 软件学报, 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]张宪超, 江贺, 陈国良. 节点和边都有容量的有向平面网络中的最小截和最大流[J]. 计算机学报, 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].计算机学报, 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]张铃. 动态网络上最大流概念及其性质的研究[J]. 模式识别与人工智能, 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．

国家自然科学基金资助项目(61300200，61232007，61073059).

张柏礼,王媛瑗,洪亮,等.动态网络中最大流快速增量求解[J].东南大学学报(自然科学版),2017,47(3):450-455.

10.3969/j.issn.1001-0505.2017.03.006.

TP301.6;TP393

A

1001-0505(2017)03-0450-06