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: