Part1: Write a program in C/C++ to find the maximum flow in the given Flow Network...

Part1: Write a program in C/C++ to find the maximum flow in the given Flow Network using (i)Ford -Fulkerson algorithm and (ii) Edmond-Karps algorithm Go through the related text and implement each of these algorithms using the efficient data structure. Show the results of different steps of these algorithms for an instance of the flow network with total number of nodesV=6 (please note down that in a flow network there are two special nodes source and sink) and total number of edges E =12 Part2: Analyze the complexity of these algorithms (Run each of the two algorithms for a set of ten randomly generated Flow Network instances (with V=6, E=12) and compute the time taken by the selected implementation in each run. Compute average time taken by each of these two algorithms. Reference: Introduction to Algorithms by Cormen, Lieserson, Rivest (First Edition)

Solutions

Expert Solution

Part 1:

Example graph has been shown below and below two programs has been run by taking reference of below graph:

i) C++ code for Ford-Fulkerson Algorithm:

#include<iostream>
#include<queue>
#include <chrono>
#define NODE 6
using namespace std;
using namespace std::chrono;

typedef struct node {
int val;
int state; //status
int pred; //predecessor
}node;

int minimum(int a, int b) {
return (a<b)?a:b;
}

int resGraph[NODE][NODE];

int graph[NODE][NODE] = {
{0, 10, 0, 10, 11, 0},
{0, 0, 4, 2, 8, 0},
{0, 0, 0, 5, 0, 10},
{0, 0, 10, 0, 9, 0},
{0, 0, 6, 0, 0, 10},
{0, 0, 0, 0, 0, 0}
};

int bfs(node *vert, node start, node sink) {
node u;
int i, j;
queue<node> que;

for(i = 0; i<NODE; i++) {
vert[i].state = 0; //not visited
}

vert[start.val].state = 1; //visited
vert[start.val].pred = -1; //no parent node
que.push(start); //insert starting node

while(!que.empty()) {
//delete from queue and print
u = que.front();
que.pop();

for(i = 0; i<NODE; i++) {
if(resGraph[u.val][i] > 0 && vert[i].state == 0) {
que.push(vert[i]);
vert[i].pred = u.val;
vert[i].state = 1;
}
}
}
return (vert[sink.val].state == 1);
}

int fordFulkerson(node *vert, node source, node sink) {
int maxFlow = 0;
int u, v;

for(int i = 0; i<NODE; i++) {
for(int j = 0; j<NODE; j++) {
resGraph[i][j] = graph[i][j]; //initially residual graph is main graph
}
}

while(bfs(vert, source, sink)) { //find augmented path using bfs algorithm
int pathFlow = 999;//as infinity
for(v = sink.val; v != source.val; v=vert[v].pred) {
u = vert[v].pred;
pathFlow = minimum(pathFlow, resGraph[u][v]);
}

for(v = sink.val; v != source.val; v=vert[v].pred) {
u = vert[v].pred;
resGraph[u][v] -= pathFlow; //update residual capacity of edges
resGraph[v][u] += pathFlow; //update residual capacity of reverse edges
}

maxFlow += pathFlow;
}
return maxFlow; //the overall max flow
}

int main() {
node vertices[NODE];
node source, sink;

for(int i = 0; i<NODE; i++) {
vertices[i].val = i;
}

source.val = 0;
sink.val = 5;
auto start = high_resolution_clock::now();
int maxFlow = fordFulkerson(vertices, source, sink);
auto stop = high_resolution_clock::now();
auto duration = duration_cast<microseconds>(stop - start);
cout << "Maximum flow is: " << maxFlow << endl;
cout << "Time taken by function: "
<< duration.count() << " microseconds" << endl;
}

Output:

ii) C++ code for Edmond-Karps algorithm:

#include<cstdio>
#include<cstdio>
#include<queue>
#include<cstring>
#include<vector>
#include<iostream>
#include<conio.h>
#include <chrono>

using namespace std;
using namespace std::chrono;

int capacities[15][15];

int flowPassed[15][15];

vector < int >graph[15];

int parentsList[15];

int currentPathCapacity[15];

int
bfs (int startNode, int endNode)
{

memset (parentsList, -1, sizeof (parentsList));

memset (currentPathCapacity, 0, sizeof (currentPathCapacity));


queue < int >q;

q.push (startNode);


parentsList[startNode] = -2;

currentPathCapacity[startNode] = 999;


while (!q.empty ())

{

int currentNode = q.front ();

q.pop ();


for (int i = 0; i < graph[currentNode].size (); i++)

   {

int to = graph[currentNode][i];

if (parentsList[to] == -1)

   {

if (capacities[currentNode][to] - flowPassed[currentNode][to] >
       0)

       {

parentsList[to] = currentNode;

currentPathCapacity[to] =
       min (currentPathCapacity[currentNode],

capacities[currentNode][to] -
           flowPassed[currentNode][to]);

if (to == endNode)

       {

return currentPathCapacity[endNode];

}

q.push (to);

}

}

}

}

return 0;

}

int
edmondsKarp (int startNode, int endNode)
{

int maxFlow = 0;

while (true)

{

int flow = bfs (startNode, endNode);

if (flow == 0)

   {

break;

}

maxFlow += flow;

int currentNode = endNode;

while (currentNode != startNode)

   {

int previousNode = parentsList[currentNode];

flowPassed[previousNode][currentNode] += flow;

flowPassed[currentNode][previousNode] -= flow;

currentNode = previousNode;

}
}
return maxFlow;

}

int
main ()
{

int nodesCount, edgesCount;

cout << "enter the number of nodes and edges\n";

cin >> nodesCount >> edgesCount;


int source, sink;

cout << "enter the source and sink\n";

cin >> source >> sink;


for (int edge = 1; edge <= edgesCount; edge++)

{

cout << "enter the start and end vertex alongwith capacity\n";

int from, to, capacity;

cin >> from >> to >> capacity;


capacities[from][to] = capacity;

graph[from].push_back (to);


graph[to].push_back (from);

}

auto start = high_resolution_clock::now();

int maxFlow = edmondsKarp (source, sink);

auto stop = high_resolution_clock::now();

cout << endl << endl << "Max Flow is:" << maxFlow << endl;

auto duration = duration_cast<microseconds>(stop - start);

cout << "Time taken by function: "
<< duration.count() << " microseconds" << endl;

getch ();

}

Output:

Part 2:

Random instance 1:

Ford-Fulkerson Algorithm: 17 ms

Edmond-Karps algorithm: 34 ms

Random instance 2: