{"id":26453,"date":"2017-12-20T21:11:27","date_gmt":"2017-12-20T15:41:27","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26453"},"modified":"2017-12-20T21:11:27","modified_gmt":"2017-12-20T15:41:27","slug":"cpp-algorithm-find-minimum-s-t-cut-flow-network","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/cpp-algorithm-find-minimum-s-t-cut-flow-network\/","title":{"rendered":"Cpp Algorithm – Find minimum s-t cut in a flow network"},"content":{"rendered":"

In a flow network, an s-t cut is a cut that requires the source \u2018s\u2019 and the sink \u2018t\u2019 to be in different subsets, and it consists of edges going from the source\u2019s side to the sink\u2019s side. <\/span>The capacity of an s-t cut is defined by the sum of capacity of each edge in the cut-set. (Source: Wiki<\/a>)
\nThe problem discussed here is to find minimum capacity s-t cut of the given network. Expected output is all edges of the minimum cut.<\/p>\n

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.<\/p>\n[ad type=\u201dbanner\u201d]\n

Minimum Cut and Maximum Flow<\/strong>
\nLike Maximum Bipartite Matching<\/a>, this is another problem which can solved using Ford-Fulkerson Algorithm<\/a>. This is based on max-flow min-cut theorem.<\/p>\n

The max-flow min-cut theorem<\/a> states that in a flow network, the amount of maximum flow is equal to capacity of the minimum cut. See CLRS book<\/a> for proof of this theorem.<\/p>\n

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<\/a>.<\/p>\n

Following are steps to print all edges of minimum cut.<\/p>\n

1)<\/strong> Run Ford-Fulkerson algorithm and consider the final residual graph<\/a>.<\/p>\n

2)<\/strong> Find the set of vertices that are reachable from source in the residual graph.<\/p>\n

3)<\/strong> All edges which are from a reachable vertex to non-reachable vertex are minimum cut edges. Print all such edges.<\/p>\n

Following is C++ implementation of the above approach.<\/p>\n

C++ Programming:<\/strong><\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%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\u2019s\u2019%20to%20sink%20\u2019t\u2019%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\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n[ad type=\u201dbanner\u201d]\n

Output:<\/strong><\/p>\n

1 - 3\r\n4 - 3\r\n4 - 5<\/pre>\n","protected":false},"excerpt":{"rendered":"
Cpp Algorithm – Find minimum s-t cut in a flow network –  Graph Algorithm – In a flow network, an s-t cut is a cut that requires the source \u2018s\u2019 <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[82509,73906,78429],"tags":[78844,78840,78843,78837,78845,78841,78846,78847,78842,78838,78839,78848],"class_list":["post-26453","post","type-post","status-publish","format-standard","hentry","category-binary-search-tree-2","category-graph-algorithms","category-maximum-flow","tag-explain-max-flow-min-cut-theorem-with-example","tag-ford-fulkerson-algorithm-for-maximum-flow-problem","tag-how-to-find-min-cut-of-a-graph","tag-max-flow-min-cut-algorithm","tag-max-flow-min-cut-geeksforgeeks","tag-max-flow-min-cut-theorem-in-graph-theory","tag-max-flow-min-cut-theorem-pdf","tag-max-flow-min-cut-theorem-ppt","tag-min-cut-algorithm-example","tag-minimum-cut-algorithm","tag-randomized-min-cut-algorithm","tag-s-t-cut"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26453","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26453"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26453\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26453"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26453"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26453"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}