Ford-Fulkerson方法
有流网络\(G=(V,E)\)，其容量\(c\)(默认整数)、流\(f\)、源点\(s\)与汇点\(t\)。\(G\)与\(f\)给定\(G_f\)与\(c_f\)。则有步骤：
1) 遍历\((u,v) \in E\)，初始化流变量\((u,v).f=0\)；
2) 若当前\(G_f\)中存在某个增广路\(p\)则继续迭代，否则停机；
3) 求出增广路容量\(c_f(p)=min\{c_f(u,v)|(u,v) \in p\}\)；
4) 遍历\((u,v) \in p\)，若\((u,v)\in E\)，\((u,v).f+=c_f(p)\)，否则\((v,u).f-=c_f(p)\)，返回(2)；
其之所以不称为算法是因为(2)未有细节，算法与代价无法确定，但可验证其正确性。设每次(2)结束后发现某个\(G_f\)的增广路\(p\)，\(f\)更新为\((f\uparrow f_p)\)，一定有\(|(f\uparrow f_p)|>|f|\)，\(G_f\)与\(c_f\)被\((f\uparrow f_p)\)更新，此时\(p\)一定不是新的\(G_f\)的增广路，回到(2)。循环直到流值达到最大流值，此时(2)无法找到增广路，由最大流最小割定理当前\(f\)即最大流。
Ford-Fulkerson方法满足称为“完整性定理”的性质，即其求得的整数容量流网络的最大流\(f\)，不仅\(|f|\)为整数(之前文章有讨论)，任意\(f(u,v)\)都为整数，该性质根据上述流程可以比较容易的看出来。
Ford-Fulkerson算法(一般增广路算法)
FF方法的最基本实现，其在流网络数据结构上额外维护残存网络，实现(2)是在当前残存网络\(G_f=(V,E_f)\)的\(s\)上用BFS或DFS发现增广路，由于\(E_f\)被残存容量\(c_f\)(即当前流\(f\))给定，故BFS或DFS途中发现\(t\)即完成对增广路的确定。根据之前文章\(|E_f|\leq 2|E|\)与\(|E|\geq |V|-1\)，该步骤有代价上界\(O(|V|+|E_f|)=O(|V|+|E|)=O(|E|)\)。
分析算法代价，每次发现增广路有代价上界\(O(|E|)\)，转为正整数容量后问题的最大流为\(f^*\)，每次发现增广路\(p\)后，\(|f|\)自增到某个正整数(因为\(c_f\)为整数)，若认为每次发现增广路\(|f|\)自增1，则外循环有次数上界\(|f^*|\)，内循环是遍历当前\(p\)的边，当前\(p\)的边数显然不大于\(|E|\)，故总代价有上界\(O((|E|+|E|)|f^*|)=O(|E||f^*|)\)，上图给出了这种上界情况，左一是起始情况，每次当前\(p\)都只使当前\(|f|\)自增1，且这种对称结构使每次内循环\(p\)与\(|E|\)的边数同阶。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 | class NetworkFlow: def __init__(self,s,t): self.s = s self.t = t self.c = {} self.f = {} self.cf = {} def add_edge(self,u,v,c): if None==self.c.get(u): self.c[u] = {} self.f[u] = {} self.cf[u] = {} self.c[u][v] = c self.f[u][v] = 0 self.cf[u][v] = c if None==self.c.get(v): self.cf[v] = {} self.cf[v][u] = 0 def has_edge(self,u,v): return self.c.get(u)!=None and self.c[u].get(v)!=None and self.c[u][v] > 0 def residual_has_edge(self,u,v): return self.cf.get(u)!=None and self.cf[u].get(v)!=None and self.cf[u][v] > 0 def dfs(self,u,visited,pi): if None!=self.cf.get(u): for v in self.cf[u].keys(): if v not in visited and self.residual_has_edge(u,v): pi[v] = u if v == self.t: return visited.add(v) self.dfs(v,visited,pi) def dfs_path(self): pi = {} self.dfs(self.s,{self.s},pi) v = self.t path = [] while pi.get(v)!=None : u = pi[v] path.append((u,v)) v = u path.reverse() return path def updata_f(self,path): cp = float('inf') for u,v in path: cp = min(cp,self.cf[u][v]) for u,v in path: if self.has_edge(u,v): self.f[u][v] += cp else: self.f[v][u] -= cp def updata_gf(self): for u in self.cf.keys(): for v in self.cf[u].keys(): if self.has_edge(u,v): self.cf[u][v] = self.c[u][v] - self.f[u][v] elif self.has_edge(v,u): self.cf[u][v] = self.f[v][u] else: self.cf[u][v] = 0 def ford_fulkerson(self): while True: path = self.dfs_path() if not path: break self.updata_f(path) self.updata_gf() def max_flow_value(self): u = self.s val = 0 if self.c.get(u)!=None: for v in self.c[u].keys(): val += self.f[u][v] return val |
Edmonds-Karp算法(最短增广路算法/SAP算法)
FF方法的更优实现，其从\(s\)找增广路的策略为令\(e\in E\)有相同权重1，再求\(s\)的单源最短路，最后利用记录的前驱\(t.\pi\)确定增广路。该方法每次都找“最短”增广路，BFS可在\(O(|V|+|E|)=O(|E|)\)代价解决这种等边权单源最短路问题。表面上看依然只能确定其有\(O(|E||f^*|)\)的上界，实际上该策略能给出\(O(|V||E|^2)\)的上界。下面证明这点：
a) 路径长度递增：对残存网络\(G_f\)，每个\(v\in V-\{s,t\}\)每次求出的最短路值\(\delta_f(s,v)\)不递减；
证明思路是反证法，假设\(G\)上的流量从\(f\)递增为\(f’\)是所有流量递增中第1次使1个或1个以上\(v\in V-\{s,t\}\)的最短路值减小的递增，设\(v\)是这些距离减少的顶点中，在递增后\(\delta_{f’}(s,v)\)值最小的某一个，故\(\delta_{f’}(s,v)<\delta_{f}(s,v)\)。设路径\(p=s…u-v\)为残存网络\(G_{f’}\)中从\(s\)到\(v\)的最短路(可能存在\(u=s\)的情况)，故有\(\delta_{f’}(s,u)=\delta_{f’}(s,v)-1\)。根据假设\(u\)的距离是不能减少的(否则一开始就会取代\(v\))，所以\(\delta_{f’}(s,u)\geq \delta_{f}(s,u)\)。这使得\((u,v)\)不能属于递增发生前的残存网络\(G_{f}\)，否则会导致\(\delta_{f’}(s,v)\geq \delta_{f}(s,v)\)，所以只剩下\((u,v)\notin E_f\)但\((u,v)\in E_{f’}\)的情况，这种情况本身又可分为两种情况，一种是\(f(u,v)=c(u,v)\)但\(0\leq f'(u,v) < c(u,v)\)，另一种是\(f(v,u)=0\)但\(0<f'(v,u)\leq c(v,u)\)。这两种情况都意味着\(E_f\)存在边\((v,u)\)，然后增广路必然经过\((v,u)\)，否则增广路既不经过\((v,u)\)也不能经过\((u,v)\)(这条边不存在)，那么根据之前对递增流的定义，应保证满足\(f(v,u)=f'(v,u)\)，但已经违反了这点。由于该策略找到的增广路为残存网络\(G_f\)中从\(s\)到\(t\)的其中一个最短路，该最短路包含边\((v,u)\)，所以有\(\delta_f(s,v)=\delta_f(s,u)-1\leq \delta_{f’}(s,u)-1 = \delta_{f’}(s,v)-2\)，引发矛盾，题设中的节点\(v\)并不存在。
b) 流量递增次数上界：流量递增的次数为\(O(VE)\)；
增广路容量最小边为关键边，增广路用于递增流量后，关键边不出现在递增后的新残存网络。证\(E\)的每个边至多成为\(O(|V|)\)次关键边，\((u,v)\)首次作为\(G_f\)的增广路的关键边时\(\delta_f(s,v) = \delta_f(s,u)+1\)，仅当之后某个\(G_{f’}\)的增广路含\((v,u)\)时(\(\delta_{f’}(s,u)=\delta_{f’}(s,v)+1\))，之后的增广路才会再次出现\((u,v)\)。综上\(\delta_{f’}(s,u)=\delta_{f’}(s,v)+1 \geq \delta_{f}(s,v) + 1= \delta_{f}(s,u)+2\)，故每个边成为关键边后若再次成为关键边，其最短路严格递增。增广路作为路径至多含\(O(|V|)\)条边。递增\(O(|V||E|)\)次后，至少出现\(O(|V||E|)\)次关键边，故这之后将无法再有关键边(增广路)。
c) Edmonds-Karp算法的代价为\(O(|V||E|^2)\)；
每次递增后还需要BFS利用\(O(|E|)\)时间求得等权重单源最短路。
实现时直接把Ford-Fulkerson算法中的DFS换成BFS即得Edmonds-Karp算法。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 | from collections import deque class NetworkFlow: def __init__(self,s,t): self.s = s self.t = t self.c = {} self.f = {} self.cf = {} def add_edge(self,u,v,c): if None==self.c.get(u): self.c[u] = {} self.f[u] = {} self.cf[u] = {} self.c[u][v] = c self.f[u][v] = 0 self.cf[u][v] = c if None==self.c.get(v): self.cf[v] = {} self.cf[v][u] = 0 def has_edge(self,u,v): return self.c.get(u)!=None and self.c[u].get(v)!=None and self.c[u][v] > 0 def residual_has_edge(self,u,v): return self.cf.get(u)!=None and self.cf[u].get(v)!=None and self.cf[u][v] > 0 def bfs_path(self): queue = deque([self.s]) visited = set() pi = {} while len(queue)>0: u = queue.popleft() visited.add(u) for v in self.cf[u].keys(): if v not in visited and self.residual_has_edge(u,v): pi[v] = u if v == self.t: path = [] while pi.get(v)!=None : u = pi[v] path.append((u,v)) v = u path.reverse() return path queue.append(v) def updata_f(self,path): cp = float('inf') for u,v in path: cp = min(cp,self.cf[u][v]) for u,v in path: if self.has_edge(u,v): self.f[u][v] += cp else: self.f[v][u] -= cp def updata_gf(self): for u in self.cf.keys(): for v in self.cf[u].keys(): if self.has_edge(u,v): self.cf[u][v] = self.c[u][v] - self.f[u][v] elif self.has_edge(v,u): self.cf[u][v] = self.f[v][u] else: self.cf[u][v] = 0 def edmonds_karp(self): while True: path = self.bfs_path() if not path: break self.updata_f(path) self.updata_gf() def max_flow_value(self): u = self.s val = 0 for v in self.c[u].keys(): val += self.f[u][v] return val |
Dinic方法
FF方法是在残存网络不断找增广路，Dinic方法在残存网络不断建立层次图并在层次图不断找增广路。Dinic方法可被“归约”进FF方法，所以有时也认为Dinic方法是FF方法的“实现”。下面定义Dinic方法中最重要的层次图。
层次图：设\(G_f\)中\(v.\pi\)为\(s\)到\(v\)的最短路值(边权为1)，\(G_f\)的层次图\(G’_f\)的边集为\(\{ (u,v) \in E_f | v.\pi = u.\pi + 1 \}\)，顶点集为边的顶点。可想象将层次图“叠加”于残存网络，二者随增广路更新“动态变化”，这可把问题直观化。
把层次图顶点划入集合\(S_0,S_1,…\)，其中\(S_i\)为\(G_f\)上距离\(s\)最短路值为\(i\)的所有顶点。利用该集合可将\(G_f\)重新“画”成分层的图(如上图)。其中黑边为\(G_f\)同属于\(G’_f\)的边，红边为\(G_f\)的其他边。给出边的相关性质：
1) 不同\(S_i\)间无重复元素，\(i\)是从0开始递增的连续整数，其值有上界\(|V|-1\)；
2) \(G_f\)仅包含黑边红边，黑边从\(S_i\)达\(S_{i+1}\)，红边从\(S_i\)达\(S_j(j\leq i)\)；
\(G_f\)存在\(S_i\)到\(S_j(j\geq i+2)\)的边与\(G’_f\)定义矛盾。\(S_i\)到\(S_j(j=i+1)\)的边符合\(G’_f\)定义，\(S_i\)到\(S_j(j\leq i)\)的边不符合\(G’_f\)定义但可存在于\(G_f\)。
3) 若\(G’_f\)中存在从\(u\)到达\(v\)的路径，那么所有不同路径的长度相等；
否则会导致同个顶点有不同的两个最短路值(\(\pi\))的矛盾。
4) 若\(G’_f\)与\(G_f\)中都存在从\(u\)到达\(v\)的路径，则\(G’_f\)中的路径的长度最短；
由于所有黑边路径都按\(S_i,S_{i+2},S_{i+3}…\)推进，那么只要其中存在一条红边就会被“拉回”一次，然后再被黑边“推进”，只会比黑边路径长。
Dinic方法的思路很大程度依赖于上述的“分层图像”，这里给出“无具体实现”的Dinic方法的流程：
1) 利用\(G\)与\(f\)建立残存网络\(G_f\)，利用\(G_f\)建立层次图\(G’_f\)；
2) 在\(G’_f\)上第0次找增广路，若找到增广路\(p\)，用\(p\)更新\(f\)与\(G_f\)，但不重新建立\(G’_f\)，而是从\(G’_g\)删除原\(p\)失去的边。若未找到增广路则当前的\(f\)为最大流，算法退出；
3) 在\(G’_f\)上第1次找增广路，若找到增广路\(p\)，用\(p\)更新\(f\)与\(G_f\)，但不重新建立\(G’_f\)，而是从\(G’_g\)删除原\(p\)失去的边。若未找到增广路则去步骤(1)重建层次图……..在\(G’_f\)上第i次找增广路，若找到增广路\(p\)，用\(p\)更新\(f\)与\(G_f\)，但不重新建立\(G’_f\)，而是从\(G’_g\)删除原\(p\)失去的边。若未找到增广路则去步骤(1)重建层次图；
a) 对于步骤(1)刚刚新建的\(G_f\)与\(G’_f\)，\(G_f\)存在增广路的充要条件为\(G’_f\)存在增广路。
b) 步骤(3)每次循环时若可从当前\(G’_f\)找到增广路，则其长度与在相应步骤(2)找到的增广路长度\(k\)相等。
\(G’_f\)在任意次删边后都是最初未删边时的子图，若其存在长度不等于\(k\)的增广路会破坏未删边时的\(G’_f\)的定义(最短路性质)。
c) 步骤(3)每次循环时若可从当前\(G’_f\)找到增广路\(p\)，则可从当前\(G_f\)中找到\(p\)。否则当前\(G_f\)无增广路或仅有长度大于\(k\)的增广路。
步骤(3)在每次循环中更新\(G_f\)只会使其发生两类变化，第一类是\(G_f\)至少失去一条原\(p\)上的边，第二类是\(G_f\)上会加入若干原\(p\)上的边的反向边。从上述集合与分层图像的角度看来，\(G_f\)至少失去一条\(S_i\)到\(S_{i+1}\)的边，增加若干\(S_{i+1}\)到\(S_i\)的边，这里\(0\leq i \leq k-1\)。
对于第一种情况，步骤(3)在每次循环利用增广路\(p\)更新\(G_f\)只会使其有两类变化，一类是\(G_f\)至少失去一条原\(p\)上的边，二类是\(G_f\)上会加入若干原\(p\)上的边的反向边。从上述集合与分层图像的角度看来，\(G_f\)至少失去一条\(S_i\)到\(S_{i+1}\)的边，增加若干\(S_{i+1}\)到\(S_i\)的边，这里\(0\leq i \leq k-1\)。\(G_f\)更新后的新增边与\(G’_f\)无关，消失边在\(G’_f\)中也被删除。故每次“更新\(G_f\)删边\(G’_f\)”后，\(G’_f\)都为\(G_f\)的子图，\(G’_f\)的路径必为\(G_f\)的路径。
对于第二种情况，无论哪次到达步骤(3)的哪次循环，\(G_f\)与\(G’_f\)都经历了步骤(1)的“初始化”与(2)的至少1次的“更新删边”，并确定了\(G’_f\)上的增广路长度\(k\)。若当前\(G_f\)存在增广路\(p\)，从分层图像视角看来，\(p\)不存在\(S_i\)到\(S_j(j\geq i+2)\)的边，因为在\(G_f\)与\(G’_f\)刚被建立时，存在这样的边将违反\(S_i\)的定义，且之后无论如何更新\(G_f\)都只能在\(S_i\)与\(S_j(j=i+1)\)这样的集合对中加边或减边。故\(p\)只能存在\(S_i\)到\(S_j(j\leq i+1)\)的边，这显然使得\(p\)的长度无法小于\(k\)。若\(p\)的长度等于\(k\)，那么其仅存在\(S_i\)到\(S_j(j=i+1)\)的边，即\(S_0,S_1…S_k\)，这条路径由于与\(G’_f\)刚初始化后找到的第一个增广路的长度\(k\)相同，根据\(G’_f\)的定义，其一定也存在于刚初始化时的\(G’_f\)上。此时\(p\)存在于当前\(G_f\)上，由于每次更新都无法新增\(S_i\)到\(S_{i+1}\)的边，故之前从未使\(G_f\)删除过\(p\)上的边，因而也就从未在\(G’_f\)删除过\(p\)上的边，这与\(G’_f\)上无法找到\(p\)矛盾，说明\(p\)的长度不能等于\(k\)。当增广路长度大于\(k\)时则不排除可能存在\(…S_i,S_i,S_{i+1}..\)或\(…S_i,S_{i+1},S_i..\)等形式的增广路。
该流程虽未指明每次如何在\(G’_f\)找增广路，但可以简单讨论其正确性与某些部分的代价上界：
d) 算法中的步骤(1)至多被到达\(O(|V|)\)次。
最坏情况首次到达增广路长度为1，之后每次到达长度+1。由于增广路是路径故其至多有\(|V|-1\)条边，这样就得到上界\(O(|V|)\)。
e) 可以将Dinic方法归约为Ford-Fulkerson方法，这说明Dinic算法是正确的。
利用上述(a)(c)可把流程转化为完全是关于残存网络\(G_f\)的：每次(2)中是否找到增广路则等价于\(G_f\)是否有增广路，步骤(3)等价于“重复找\(G_f\)长度与\(p\)相同的增广路”。这样Dinic方法等价于“若在\(G_f\)找到1个或更多长度相同的增广路，则依次用于更新\(G_f\)，然后继续寻找…直到无法找到1个增广路”，而一般的FF方法是“若在\(G_f\)找到1个增广路，则用于更新\(G_f\)，然后继续寻找…直到无法找到1个增广路”。所以Dinic方法可以看作是为FF方法提供了更具体的“找增广路-更新残存网络”的流程，这也说明了Dinic方法的正确性。
Dinic算法(连续最短增广路算法)
不同于CLRS的白灰黑DFS，也不同于白灰DFS，接下来的DFS是“不染色”的，无论何时每个顶点都是白色，即每个顶点的子DFS都要对所有出边直达的顶点执行子DFS。下面讨论从层次图源点DFS得到的生成树的性质：
a) 第\(i\)层的节点来自\(S_i\)；
b) 同层可能出现重复节点，重复节点的子树相同；
c) 树边包含所有层次图的边；
d) 从\(s\)执行的DFS，DFS树的生成次序等于DFS树前序遍历的次序；
对上述Dinic方法步骤(2)(3)的最简单实现是“从\(G’_f\)的\(s\)开始DFS，发现增广路，更新\(G_f\)删边\(G’_f\)，然后从\(G’_f\)的\(s\)开始全新的DFS…直到某次DFS无增广路”，其DFS树的变化如上图第一张。这种实现的代价很大，但是其每次能否DFS到增广路完全等价于Dinic方法中的“能否找到增广路”，故其正确性是显然的，但代价太大。下面给出另一种实现，如果能证明这种实现每次所找到的增广路与上一种实现相同，那么就能证明这种实现是正确的：
1) 从未删边的\(G’_f\)的\(s\)执行DFS；
2) 若子DFS发现当前顶点\(v\neq t\)且没有出边，则回溯的将\(G’_f\)中父DFS到达\(v\)的边\((u,v)\)删除；
3) 若子DFS发现当前顶点\(v=t\)，利用该增广路更新\(G_f\)与删边\(G’_f\)，并从\(s\)开始新的DFS；
4) 直到最终某次DFS没有发现增广路，算法结束；
上图第一张是第一种实现，每次发现增广路并更新后的DFS生成树与其变化(蓝色叉表示用增广路更新后失去的边)。由于所有图边都在DFS树上，并且多个树边可能对应于同个图边，故删除1条图边可能导致删除多个树边。由于这种DFS的不染色特性，删除图边除了需要删除对应树边外，新的DFS树的结构是不会有变化的，对于染色DFS如果删除图边可能导致DFS树中的某个节点出现在新DFS树的其他子树上。
上图第二张是第二种实现，DFS回溯时删的边用红叉表示，这样删边同样是不会影响DFS树的“骨架”，但是这会导致删除后续DFS将到达的边。被本轮DFS删去的边不可能是本轮或之后的DFS中的增广路的边，否则被删去的边的子DFS必然会发现增广路。这两种实现的DFS次序是相同的，只不过后者将会“剪掉”没有用的边。
分析第二种实现的代价，根据层次图与该DFS性质，在所有DFS轮次中，红叉边仅到达\(O(1)\)次，增广路长度有上界\(O(|V|)\)，故增广路更新流量失边的最坏情况为每达\(O(|V|)\)次边仅失1条边。综上每到达\(O(|V|)\)条边至少失去1条边，最坏情况是若到达\(O(|V||E|)\)次边，则失去全部图边。结合层次图建图次数上界有总代价\(O(|E||V|^2)\)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 | from collections import deque class NetworkFlow: def __init__(self,s,t): self.s = s self.t = t self.c = {} self.f = {} def add_edge(self,u,v,c): if None == self.c.get(u): self.c[u] = {} self.f[u] = {} self.c[u][v] = c self.f[u][v] = 0 def get_cap(self,u,v): return self.c[u][v] if u in self.c and v in self.c[u] else 0 def get_residual_cap(self,u,v): if u in self.c and v in self.c[u] and self.c[u][v]>0: return self.c[u][v] - self.f[u][v] if v in self.c and u in self.c[v] and self.c[v][u]>0: return self.f[v][u] return 0 def make_residual_edges(self): edges = {} for u in self.c.keys(): for v in self.c[u].keys(): x = self.get_residual_cap(u,v) if x > 0: if u not in edges: edges[u] = {} edges[u][v] = x x = self.get_residual_cap(v,u) if x > 0: if v not in edges: edges[v] = {} edges[v][u] = x return edges def make_level_edges(self): res = self.make_residual_edges() q = deque([self.s]) vis = {self.s} level = {} while len(q)>0: u = q.popleft() if u in res: for v in res[u].keys(): if not v in vis: if u not in level: level[u] = set() level[u].add(v) vis.add(v) q.append(v) return level def dfs_level(self,level,u,path): path.append(u) if u == self.t: return True if u in level: for v in list(level[u]): if self.dfs_level(level,v,path): return True level[u].remove(v) path.pop() return False def update_flow_level(self,path,level): pf = float('inf') for i in range(len(path)-1): u,v = path[i],path[i+1] pf = min( pf, self.get_residual_cap(u,v) ) for i in range(len(path)-1): u,v = path[i],path[i+1] if self.get_cap(u,v) > 0: self.f[u][v] += pf else: self.f[v][u] -= pf if self.get_residual_cap(u,v) == 0: level[u].remove(v) def dinic(self): while True: j = 0 level = self.make_level_edges() while True: path = [] if self.dfs_level(level,self.s,path): self.update_flow_level(path,level) j += 1 else: break if j == 0: break def max_flow_value(self): u = self.s val = 0 for v in self.c[u].keys(): val += self.f[u][v] return val |