{"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=”banner”]\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

<\/div> 
\/\/ C++ program for finding minimum cut using Ford-Fulkerson#include <iostream>#include <limits.h>#include <string.h>#include <queue>using namespace std; \/\/ Number of vertices in given graph#define V 6 \/* Returns true if there is a path from source 's' to sink 't' in  residual graph. Also fills parent[] to store the path *\/int bfs(int rGraph[V][V], int s, int t, int parent[]){    \/\/ Create a visited array and mark all vertices as not visited    bool visited[V];    memset(visited, 0, sizeof(visited));     \/\/ Create a queue, enqueue source vertex and mark source vertex    \/\/ as visited    queue <int> q;    q.push(s);    visited[s] = true;    parent[s] = -1;     \/\/ Standard BFS Loop    while (!q.empty())    {        int u = q.front();        q.pop();         for (int v=0; v<V; v++)        {            if (visited[v]==false && rGraph[u][v] > 0)            {                q.push(v);                parent[v] = u;                visited[v] = true;            }        }    }     \/\/ If we reached sink in BFS starting from source, then return    \/\/ true, else false    return (visited[t] == true);} \/\/ A DFS based function to find all reachable vertices from s.  The function\/\/ marks visited[i] as true if i is reachable from s.  The initial values in\/\/ visited[] must be false. We can also use BFS to find reachable verticesvoid dfs(int rGraph[V][V], int s, bool visited[]){    visited[s] = true;    for (int i = 0; i < V; i++)       if (rGraph[s][i] && !visited[i])           dfs(rGraph, i, visited);} \/\/ Prints the minimum s-t cutvoid minCut(int graph[V][V], int s, int t){    int u, v;     \/\/ Create a residual graph and fill the residual graph with    \/\/ given capacities in the original graph as residual capacities    \/\/ in residual graph    int rGraph[V][V]; \/\/ rGraph[i][j] indicates residual capacity of edge i-j    for (u = 0; u < V; u++)        for (v = 0; v < V; v++)             rGraph[u][v] = graph[u][v];     int parent[V];  \/\/ This array is filled by BFS and to store path     \/\/ Augment the flow while tere is path from source to sink    while (bfs(rGraph, s, t, parent))    {        \/\/ Find minimum residual capacity of the edhes along the        \/\/ path filled by BFS. Or we can say find the maximum flow        \/\/ through the path found.        int path_flow = INT_MAX;        for (v=t; v!=s; v=parent[v])        {            u = parent[v];            path_flow = min(path_flow, rGraph[u][v]);        }         \/\/ update residual capacities of the edges and reverse edges        \/\/ along the path        for (v=t; v != s; v=parent[v])        {            u = parent[v];            rGraph[u][v] -= path_flow;            rGraph[v][u] += path_flow;        }    }     \/\/ Flow is maximum now, find vertices reachable from s    bool visited[V];    memset(visited, false, sizeof(visited));    dfs(rGraph, s, visited);     \/\/ Print all edges that are from a reachable vertex to    \/\/ non-reachable vertex in the original graph    for (int i = 0; i < V; i++)      for (int j = 0; j < V; j++)         if (visited[i] && !visited[j] && graph[i][j])              cout << i << " - " << j << endl;     return;} \/\/ Driver program to test above functionsint main(){    \/\/ Let us create a graph shown in the above example    int graph[V][V] = { {0, 16, 13, 0, 0, 0},                        {0, 0, 10, 12, 0, 0},                        {0, 4, 0, 0, 14, 0},                        {0, 0, 9, 0, 0, 20},                        {0, 0, 0, 7, 0, 4},                        {0, 0, 0, 0, 0, 0}                      };     minCut(graph, 0, 5);     return 0;}<\/code><\/pre> <\/div>\n[ad type=”banner”]\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}]}}