C++ Program to Implement Max-Flow_Min-Cut_Theorem

«
»
This C++ Program demonstrates implementation of Max-Flow_Min-Cut_Theorem.

Here is source code of the C++ Program to demonstrate Max-Flow_Min-Cut_Theorem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C++ Program to Implement Max-Flow Min-Cut Theorem
  3.  */
  4. #include <iostream>
  5. #include <climits>
  6. #include <cstdlib>
  7. #include <cstring>
  8. #include <queue>
  9. #define V 6
  10. using namespace std;
  11.  
  12. /*
  13.  * Returns true if there is a path from source 's' to sink 't' in
  14.  * residual graph. Also fills parent[] to store the path
  15.  */
  16. int bfs(int rGraph[V][V], int s, int t, int parent[])
  17. {
  18.     bool visited[V];
  19.     memset(visited, 0, sizeof(visited));
  20.     queue <int> q;
  21.     q.push(s);
  22.     visited[s] = true;
  23.     parent[s] = -1;
  24.     while (!q.empty())
  25.     {
  26.         int u = q.front();
  27.         q.pop();
  28.         for (int v = 0; v < V; v++)
  29.         {
  30.             if (visited[v] == false && rGraph[u][v] > 0)
  31.             {
  32.                 q.push(v);
  33.                 parent[v] = u;
  34.                 visited[v] = true;
  35.             }
  36.         }
  37.     }
  38.     return (visited[t] == true);
  39. }
  40.  
  41. /*
  42.  *  A DFS based function to find all reachable vertices from s.
  43.  */
  44. void dfs(int rGraph[V][V], int s, bool visited[])
  45. {
  46.     visited[s] = true;
  47.     for (int i = 0; i < V; i++)
  48.     {
  49.         if (rGraph[s][i] && !visited[i])
  50.            dfs(rGraph, i, visited);
  51.     }
  52. }
  53.  
  54. /*
  55.  * Prints the minimum s-t cut
  56.  */
  57. void minCut(int graph[V][V], int s, int t)
  58. {
  59.     int u, v;
  60.     int rGraph[V][V];
  61.     for (u = 0; u < V; u++)
  62.     {
  63.         for (v = 0; v < V; v++)
  64.              rGraph[u][v] = graph[u][v];
  65.     }
  66.     int parent[V];
  67.     while (bfs(rGraph, s, t, parent))
  68.     {
  69.         int path_flow = 65536;
  70.         for (v = t; v != s; v = parent[v])
  71.         {
  72.             u = parent[v];
  73.             path_flow = min(path_flow, rGraph[u][v]);
  74.         }
  75.         for (v = t; v != s; v = parent[v])
  76.         {
  77.             u = parent[v];
  78.             rGraph[u][v] -= path_flow;
  79.             rGraph[v][u] += path_flow;
  80.         }
  81.     }
  82.     bool visited[V];
  83.     memset(visited, 0, sizeof(visited));
  84.     dfs(rGraph, s, visited);
  85.     for (int i = 0; i < V; i++)
  86.     {
  87.         for (int j = 0; j < V; j++)
  88.         {
  89.             if (visited[i] && !visited[j] && graph[i][j])
  90.                 cout << i << " - " << j << endl;
  91.         }
  92.     }
  93.     return;
  94. }
  95. /*
  96.  * Main Contains Menu
  97.  */ 
  98.  
  99. int main()
  100. {
  101.     int graph[V][V] = { {0, 16, 13, 0, 0, 0},
  102.                         {0, 0, 10, 12, 0, 0},
  103.                         {0, 4, 0, 0, 14, 0},
  104.                         {0, 0, 9, 0, 0, 20},
  105.                         {0, 0, 0, 7, 0, 4},
  106.                         {0, 0, 0, 0, 0, 0}
  107.                       };
  108.  
  109.     minCut(graph, 0, 5);
  110.     return 0;
  111. }

advertisement
$ g++ maxflow_mincut.cpp
$ a.out
1 - 3
4 - 3
4 - 5
 
 
------------------
(program exited with code: 0)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn