Welcome to Code Forum!

Join a community that supports you and your coding journey from day one. We strive to be a friendly, supportive community that empowers everyone to be better developers. By registering with us, you'll be able to discuss, share and private message with other members of our community.

SignUp Now!
  • Guest, before posting your code please take these rules into consideration:
    • It is required to use our BBCode feature to display your code. While within the editor click < / > or >_ and place your code within the BB Code prompt. This helps others with finding a solution by making it easier to read and easier to copy.
    • You can also use markdown to share your code. When using markdown your code will be automatically converted to BBCode. For help with markdown check out the markdown guide.
    • Don't share a wall of code. All we want is the problem area, the code related to your issue.

    GIF shows where to locate </> in the thread and or post editor toolbar.
    To learn more about how to use our BBCode feature, review our "How to post your code into threads" here.

    Thank you, Code Forum.

C++ Implementation of Edmons-Karp algorithm c++

Dav1d

New Coder
I am trying to generate a random vertices and edges for my Edmon-karp algorithm, but I am unable to do it and I think that is useful formany of us, as there is no info on the internet how to generate automatically edges ant vertices. I am trying this method instead of inputting numbers by hand, but it doesn't work.For random generating numbers I always get the same numbers in each line. Example:line1[1,5,9]Line2[1,5,9] and so on...

C++:
#include<cstdio>
#include<queue>
#include<cstring>
#include <climits>
#include<vector>
#include<iostream>
#include<chrono>
#include<time.h>
#include<ctime>
using namespace std;
using namespace std::chrono;

int c[10][10];
int flowPassed[10][10];
vector<int> g[10];
int parList[10];
int currentPathC[10];
int bfs(int sNode, int eNode)//breadth first search
{
   memset(parList, -1, sizeof(parList));
   memset(currentPathC, 0, sizeof(currentPathC));
   queue<int> q;//declare queue vector
   q.push(sNode);
   parList[sNode] = -1;//initialize parlist’s source node
   currentPathC[sNode] = 999;//initialize currentpath’s source node
   while(!q.empty())// if q is not empty

   {
      int currNode = q.front();
      q.pop();
      for(int i=0; i<g[currNode].size(); i++)
      {
         int to = g[currNode];
         if(parList[to] == -1)
         {
            if(c[currNode][to] - flowPassed[currNode][to] > 0)
            {
               parList[to] = currNode;
               currentPathC[to] = min(currentPathC[currNode],
               c[currNode][to] - flowPassed[currNode][to]);
               if(to == eNode)
               {
                  return currentPathC[eNode];
               }
               q.push(to);
            }
         }
      }
   }
   return 0;
}
int edmondsKarp(int sNode, int eNode)
{
   int maxFlow = 0;
   while(true)
   {
      int flow = bfs(sNode, eNode);
      if (flow == 0)
      {
         break;
      }
      maxFlow += flow;
      int currNode = eNode;
      while(currNode != sNode)
      {
         int prevNode = parList[currNode];
         flowPassed[prevNode][currNode] += flow;
         flowPassed[currNode][prevNode] -= flow;
         currNode = prevNode;
      }
   }
    return maxFlow;
}
int main() {
   int nodCount, edCount;
   cout<<"enter the number of nodes and edges\n";
   cin>>nodCount>>edCount;
   int source, sink;
   cout<<"enter the source and sink\n";
   cin>>source>>sink;
   for(int ed = 0; ed < edCount; ed++)
   {
      int from, to = 0, cap;
       cout<<"enter the start and end vertex along with capacity\n"<<from<<','<<to<<','<<cap;
      srand(time(0));
      from = rand() %51;
      to = rand() %51;
      cap = rand() %51;
      //cin>>from>>to>>cap; //Typing by hand
      c[from][to] = cap;
      g[from].push_back(to);
      g[to].push_back(from);
   }
    auto Start = high_resolution_clock::now();
   int maxFlow = edmondsKarp(source, sink);
   auto Stop = high_resolution_clock::now();
   auto dur = duration_cast<milliseconds>(Stop - Start);
       int Time = dur.count();
    cout <<"Time (ms) :"<< Time<< " ms";
   cout<<endl<<endl<<"Max Flow is:"<<maxFlow<<endl;
}
 
Last edited by a moderator:
Back
Top Bottom