C++ Program to Implement The Edmonds-Karp Algorithm

«
»
This C++ program implements the Edmonds_Karp Algorithm which is used to compute the maximum flow between the sink and source vertex. It is the same as the Ford-Fulkersson Algorithm except that it uses breadth first search to reduce time complexity.

Here is the source code of the C++ program to display the maximum flow by giving the sink and source nodes as input along with the directed graph. This C++ program is successfully compiled and run on DevCpp, a C++ compiler.The program output is given below.

  1. /*
  2.  * C++ Program to Implement The Edmonds-Karp Algorithm
  3.  */
  4. #include<cstdio>
  5. #include<cstdio>
  6. #include<queue>
  7. #include<cstring>
  8. #include<vector>
  9. #include<iostream>
  10. #include<conio.h>
  11.  
  12. using namespace std; 
  13.  
  14. int capacities[10][10];
  15. int flowPassed[10][10];
  16. vector<int> graph[10];
  17. int parentsList[10];       
  18. int currentPathCapacity[10];  
  19.  
  20. int bfs(int startNode, int endNode)
  21. {
  22.     memset(parentsList, -1, sizeof(parentsList));
  23.     memset(currentPathCapacity, 0, sizeof(currentPathCapacity));
  24.  
  25.     queue<int> q;
  26.     q.push(startNode);
  27.  
  28.     parentsList[startNode] = -2;
  29.     currentPathCapacity[startNode] = 999;
  30.  
  31.     while(!q.empty())
  32.     {
  33.         int currentNode = q.front();
  34.         q.pop();
  35.  
  36.         for(int i=0; i<graph[currentNode].size(); i++)
  37.         {
  38.             int to = graph[currentNode][i];
  39.             if(parentsList[to] == -1)
  40.             {
  41.                 if(capacities[currentNode][to] - flowPassed[currentNode][to] > 0)
  42.                 {
  43.                     parentsList[to] = currentNode;
  44.                     currentPathCapacity[to] = min(currentPathCapacity[currentNode], 
  45.                     capacities[currentNode][to] - flowPassed[currentNode][to]);
  46.                     if(to == endNode)
  47.                     {
  48.                         return currentPathCapacity[endNode];
  49.                     }
  50.                     q.push(to);
  51.                 }
  52.             }
  53.         }
  54.     }
  55.     return 0;
  56. }
  57.  
  58. int edmondsKarp(int startNode, int endNode)
  59. {
  60.     int maxFlow = 0;
  61.       while(true)
  62.     {
  63.         int flow = bfs(startNode, endNode);
  64.         if (flow == 0) 
  65.         {
  66.             break;
  67.         }
  68.         maxFlow += flow;
  69.         int currentNode = endNode;
  70.         while(currentNode != startNode)
  71.         {
  72.             int previousNode = parentsList[currentNode];
  73.             flowPassed[previousNode][currentNode] += flow;
  74.             flowPassed[currentNode][previousNode] -= flow;
  75.             currentNode = previousNode;
  76.         }
  77.     }
  78.     return maxFlow;
  79. }
  80. int main()
  81. {
  82.     int nodesCount, edgesCount;
  83.     cout<<"enter the number of nodes and edges\n";
  84.     cin>>nodesCount>>edgesCount;
  85.  
  86.     int source, sink;
  87.     cout<<"enter the source and sink\n";
  88.     cin>>source>>sink;
  89.  
  90.     for(int edge = 0; edge < edgesCount; edge++)
  91.     {
  92.         cout<<"enter the start and end vertex alongwith capacity\n";
  93.         int from, to, capacity;
  94.         cin>>from>>to>>capacity;
  95.  
  96.         capacities[from][to] = capacity;
  97.         graph[from].push_back(to);
  98.  
  99.         graph[to].push_back(from);
  100.     }
  101.  
  102.     int maxFlow = edmondsKarp(source, sink);
  103.  
  104.     cout<<endl<<endl<<"Max Flow is:"<<maxFlow<<endl;
  105.  
  106.     getch();
  107. }

advertisement
Output
enter the number of nodes and edges
6
10
enter the source and sink
0
5
enter the start and end vertex alongwith capacity
0
1
16
enter the start and end vertex alongwith capacity
0
2
13
enter the start and end vertex alongwith capacity
1
2
10
enter the start and end vertex alongwith capacity
2
1
4
enter the start and end vertex alongwith capacity
1
3
12
enter the start and end vertex alongwith capacity
3
2
9
enter the start and end vertex alongwith capacity
2
4
14
enter the start and end vertex alongwith capacity
4
3
7
enter the start and end vertex alongwith capacity
4
5
4
enter the start and end vertex alongwith capacity
3
5
20
 
 
Max Flow is:23

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