In a flow network, an s-t cut is a cut that requires the source ‘s’ and the sink ‘t’ to be in different subsets, and it consists of edges going from the source’s side to the sink’s side. The capacity of an s-t cut is defined by the sum of capacity of each edge in the cut-set. (Source: Wiki)
The problem discussed here is to find minimum capacity s-t cut of the given network. Expected output is all edges of the minimum cut.
For example, in the following flow network, example s-t cuts are {{0 ,1}, {0, 2}}, {{0, 2}, {1, 2}, {1, 3}}, etc. The minimum s-t cut is {{1, 3}, {4, 3}, {4 5}} which has capacity as 12+7+4 = 23.
[ad type=”banner”]Minimum Cut and Maximum Flow
Like Maximum Bipartite Matching, this is another problem which can solved using Ford-Fulkerson Algorithm. This is based on max-flow min-cut theorem.
The max-flow min-cut theorem states that in a flow network, the amount of maximum flow is equal to capacity of the minimum cut. See CLRS book for proof of this theorem.
From Ford-Fulkerson, we get capacity of minimum cut. How to print all edges that form the minimum cut? The idea is to use residual graph.
Following are steps to print all edges of minimum cut.
1) Run Ford-Fulkerson algorithm and consider the final residual graph.
2) Find the set of vertices that are reachable from source in the residual graph.
3) All edges which are from a reachable vertex to non-reachable vertex are minimum cut edges. Print all such edges.
Following is C++ implementation of the above approach.
C++ Programming:
[pastacode lang=”cpp” manual=”%2F%2F%20C%2B%2B%20program%20for%20finding%20minimum%20cut%20using%20Ford-Fulkerson%0A%23include%20%3Ciostream%3E%0A%23include%20%3Climits.h%3E%0A%23include%20%3Cstring.h%3E%0A%23include%20%3Cqueue%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20Number%20of%20vertices%20in%20given%20graph%0A%23define%20V%206%0A%20%0A%2F*%20Returns%20true%20if%20there%20is%20a%20path%20from%20source%20’s’%20to%20sink%20’t’%20in%0A%20%20residual%20graph.%20Also%20fills%20parent%5B%5D%20to%20store%20the%20path%20*%2F%0Aint%20bfs(int%20rGraph%5BV%5D%5BV%5D%2C%20int%20s%2C%20int%20t%2C%20int%20parent%5B%5D)%0A%7B%0A%20%20%20%20%2F%2F%20Create%20a%20visited%20array%20and%20mark%20all%20vertices%20as%20not%20visited%0A%20%20%20%20bool%20visited%5BV%5D%3B%0A%20%20%20%20memset(visited%2C%200%2C%20sizeof(visited))%3B%0A%20%0A%20%20%20%20%2F%2F%20Create%20a%20queue%2C%20enqueue%20source%20vertex%20and%20mark%20source%20vertex%0A%20%20%20%20%2F%2F%20as%20visited%0A%20%20%20%20queue%20%3Cint%3E%20q%3B%0A%20%20%20%20q.push(s)%3B%0A%20%20%20%20visited%5Bs%5D%20%3D%20true%3B%0A%20%20%20%20parent%5Bs%5D%20%3D%20-1%3B%0A%20%0A%20%20%20%20%2F%2F%20Standard%20BFS%20Loop%0A%20%20%20%20while%20(!q.empty())%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20u%20%3D%20q.front()%3B%0A%20%20%20%20%20%20%20%20q.pop()%3B%0A%20%0A%20%20%20%20%20%20%20%20for%20(int%20v%3D0%3B%20v%3CV%3B%20v%2B%2B)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(visited%5Bv%5D%3D%3Dfalse%20%26%26%20rGraph%5Bu%5D%5Bv%5D%20%3E%200)%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20q.push(v)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20parent%5Bv%5D%20%3D%20u%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20visited%5Bv%5D%20%3D%20true%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20If%20we%20reached%20sink%20in%20BFS%20starting%20from%20source%2C%20then%20return%0A%20%20%20%20%2F%2F%20true%2C%20else%20false%0A%20%20%20%20return%20(visited%5Bt%5D%20%3D%3D%20true)%3B%0A%7D%0A%20%0A%2F%2F%20A%20DFS%20based%20function%20to%20find%20all%20reachable%20vertices%20from%20s.%20%20The%20function%0A%2F%2F%20marks%20visited%5Bi%5D%20as%20true%20if%20i%20is%20reachable%20from%20s.%20%20The%20initial%20values%20in%0A%2F%2F%20visited%5B%5D%20must%20be%20false.%20We%20can%20also%20use%20BFS%20to%20find%20reachable%20vertices%0Avoid%20dfs(int%20rGraph%5BV%5D%5BV%5D%2C%20int%20s%2C%20bool%20visited%5B%5D)%0A%7B%0A%20%20%20%20visited%5Bs%5D%20%3D%20true%3B%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20V%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20if%20(rGraph%5Bs%5D%5Bi%5D%20%26%26%20!visited%5Bi%5D)%0A%20%20%20%20%20%20%20%20%20%20%20dfs(rGraph%2C%20i%2C%20visited)%3B%0A%7D%0A%20%0A%2F%2F%20Prints%20the%20minimum%20s-t%20cut%0Avoid%20minCut(int%20graph%5BV%5D%5BV%5D%2C%20int%20s%2C%20int%20t)%0A%7B%0A%20%20%20%20int%20u%2C%20v%3B%0A%20%0A%20%20%20%20%2F%2F%20Create%20a%20residual%20graph%20and%20fill%20the%20residual%20graph%20with%0A%20%20%20%20%2F%2F%20given%20capacities%20in%20the%20original%20graph%20as%20residual%20capacities%0A%20%20%20%20%2F%2F%20in%20residual%20graph%0A%20%20%20%20int%20rGraph%5BV%5D%5BV%5D%3B%20%2F%2F%20rGraph%5Bi%5D%5Bj%5D%20indicates%20residual%20capacity%20of%20edge%20i-j%0A%20%20%20%20for%20(u%20%3D%200%3B%20u%20%3C%20V%3B%20u%2B%2B)%0A%20%20%20%20%20%20%20%20for%20(v%20%3D%200%3B%20v%20%3C%20V%3B%20v%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20rGraph%5Bu%5D%5Bv%5D%20%3D%20graph%5Bu%5D%5Bv%5D%3B%0A%20%0A%20%20%20%20int%20parent%5BV%5D%3B%20%20%2F%2F%20This%20array%20is%20filled%20by%20BFS%20and%20to%20store%20path%0A%20%0A%20%20%20%20%2F%2F%20Augment%20the%20flow%20while%20tere%20is%20path%20from%20source%20to%20sink%0A%20%20%20%20while%20(bfs(rGraph%2C%20s%2C%20t%2C%20parent))%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Find%20minimum%20residual%20capacity%20of%20the%20edhes%20along%20the%0A%20%20%20%20%20%20%20%20%2F%2F%20path%20filled%20by%20BFS.%20Or%20we%20can%20say%20find%20the%20maximum%20flow%0A%20%20%20%20%20%20%20%20%2F%2F%20through%20the%20path%20found.%0A%20%20%20%20%20%20%20%20int%20path_flow%20%3D%20INT_MAX%3B%0A%20%20%20%20%20%20%20%20for%20(v%3Dt%3B%20v!%3Ds%3B%20v%3Dparent%5Bv%5D)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20u%20%3D%20parent%5Bv%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20path_flow%20%3D%20min(path_flow%2C%20rGraph%5Bu%5D%5Bv%5D)%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20update%20residual%20capacities%20of%20the%20edges%20and%20reverse%20edges%0A%20%20%20%20%20%20%20%20%2F%2F%20along%20the%20path%0A%20%20%20%20%20%20%20%20for%20(v%3Dt%3B%20v%20!%3D%20s%3B%20v%3Dparent%5Bv%5D)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20u%20%3D%20parent%5Bv%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20rGraph%5Bu%5D%5Bv%5D%20-%3D%20path_flow%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20rGraph%5Bv%5D%5Bu%5D%20%2B%3D%20path_flow%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Flow%20is%20maximum%20now%2C%20find%20vertices%20reachable%20from%20s%0A%20%20%20%20bool%20visited%5BV%5D%3B%0A%20%20%20%20memset(visited%2C%20false%2C%20sizeof(visited))%3B%0A%20%20%20%20dfs(rGraph%2C%20s%2C%20visited)%3B%0A%20%0A%20%20%20%20%2F%2F%20Print%20all%20edges%20that%20are%20from%20a%20reachable%20vertex%20to%0A%20%20%20%20%2F%2F%20non-reachable%20vertex%20in%20the%20original%20graph%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20V%3B%20i%2B%2B)%0A%20%20%20%20%20%20for%20(int%20j%20%3D%200%3B%20j%20%3C%20V%3B%20j%2B%2B)%0A%20%20%20%20%20%20%20%20%20if%20(visited%5Bi%5D%20%26%26%20!visited%5Bj%5D%20%26%26%20graph%5Bi%5D%5Bj%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20cout%20%3C%3C%20i%20%3C%3C%20%22%20-%20%22%20%3C%3C%20j%20%3C%3C%20endl%3B%0A%20%0A%20%20%20%20return%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20functions%0Aint%20main()%0A%7B%0A%20%20%20%20%2F%2F%20Let%20us%20create%20a%20graph%20shown%20in%20the%20above%20example%0A%20%20%20%20int%20graph%5BV%5D%5BV%5D%20%3D%20%7B%20%7B0%2C%2016%2C%2013%2C%200%2C%200%2C%200%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B0%2C%200%2C%2010%2C%2012%2C%200%2C%200%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B0%2C%204%2C%200%2C%200%2C%2014%2C%200%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B0%2C%200%2C%209%2C%200%2C%200%2C%2020%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B0%2C%200%2C%200%2C%207%2C%200%2C%204%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B0%2C%200%2C%200%2C%200%2C%200%2C%200%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D%3B%0A%20%0A%20%20%20%20minCut(graph%2C%200%2C%205)%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D” message=”” highlight=”” provider=”manual”/] [ad type=”banner”]Output:
1 - 3 4 - 3 4 - 5