Following is a C++ implementation of Ford-Fulkerson algorithm. To keep things si
ID: 3907238 • Letter: F
Question
Following is a C++ implementation of Ford-Fulkerson algorithm. To keep things simple, graph is represented as a 2D matrix.
// C++ program for implementation of Ford Fulkerson algorithm
#include <iostream>
#include <limits.h>
#include <string.h>
#include <queue>
using namespace std;
// Number of vertices in given graph
#define V 6
/* Returns true if there is a path from source 's' to sink 't' in
residual graph. Also fills parent[] to store the path */
bool bfs(int rGraph[V][V], int s, int t, int parent[])
{
// Create a visited array and mark all vertices as not visited
bool visited[V];
memset(visited, 0, sizeof(visited));
// Create a queue, enqueue source vertex and mark source vertex
// as visited
queue <int> q;
q.push(s);
visited[s] = true;
parent[s] = -1;
// Standard BFS Loop
while (!q.empty())
{
int u = q.front();
q.pop();
for (int v=0; v<V; v++)
{
if (visited[v]==false && rGraph[u][v] > 0)
{
q.push(v);
parent[v] = u;
visited[v] = true;
}
}
}
// If we reached sink in BFS starting from source, then return
// true, else false
return (visited[t] == true);
}
// Returns the maximum flow from s to t in the given graph
int fordFulkerson(int graph[V][V], int s, int t)
{
int u, v;
// Create a residual graph and fill the residual graph with
// given capacities in the original graph as residual capacities
// in residual graph
int rGraph[V][V]; // Residual graph where rGraph[i][j] indicates
// residual capacity of edge from i to j (if there
// is an edge. If rGraph[i][j] is 0, then there is not)
for (u = 0; u < V; u++)
for (v = 0; v < V; v++)
rGraph[u][v] = graph[u][v];
int parent[V]; // This array is filled by BFS and to store path
int max_flow = 0; // There is no flow initially
// Augment the flow while there is a path from source to sink
while (bfs(rGraph, s, t, parent))
{
// Find minimum residual capacity of the edges along the
// path filled by BFS. Or we can say find the maximum flow
// through the path found.
int path_flow = INT_MAX;
for (v=t; v!=s; v=parent[v])
{
u = parent[v];
path_flow = min(path_flow, rGraph[u][v]);
}
// update residual capacities of the edges and reverse edges
// along the path
for (v=t; v != s; v=parent[v])
{
u = parent[v];
rGraph[u][v] -= path_flow;
rGraph[v][u] += path_flow;
}
// Add path flow to overall flow
max_flow += path_flow;
}
// Return the overall flow
return max_flow;
}
// Driver program to test above functions
int main()
{
// Let us create a graph shown in the above example
int graph[V][V] = { {0, 16, 13, 0, 0, 0},
{0, 0, 10, 12, 0, 0},
{0, 4, 0, 0, 14, 0},
{0, 0, 9, 0, 0, 20},
{0, 0, 0, 7, 0, 4},
{0, 0, 0, 0, 0, 0}
};
cout << "The maximum possible flow is " << fordFulkerson(graph, 0, 5);
return 0;
}
Questions: In the method bool bfs(int rGraph[V][V], int s, int t, int parent[]), why do we have the array parent[]? What is the array parent[] used for?
Why is a visited[V] array needed for this algorithm?
What is memset(visited, 0, sizeof(visited))?
Why are we setting parent[s] = -1? Why are setting visited[s] = true?
Why are using a standard BFS Loop? What does int u = q.front() do? Why are we using the pop method q.pop()?
Inside of the for (int v=0; v<V; v++) loop, we have an if statement if (visited[v]==false && rGraph[u][v] > 0) where we use
q.push(v);
parent[v] = u;
visited[v] = true;
Why we using the above three lines inside of the if statement?
Why do we have a strange looking for loop statement for (v=t; v!=s; v=parent[v])??
Basically, you need to add more code comments to explain what the above source code is trying to do.
// C++ program for implementation of Ford Fulkerson algorithm
#include <iostream>
#include <limits.h>
#include <string.h>
#include <queue>
using namespace std;
// Number of vertices in given graph
#define V 6
/* Returns true if there is a path from source 's' to sink 't' in
residual graph. Also fills parent[] to store the path */
bool bfs(int rGraph[V][V], int s, int t, int parent[])
{
// Create a visited array and mark all vertices as not visited
bool visited[V];
memset(visited, 0, sizeof(visited));
// Create a queue, enqueue source vertex and mark source vertex
// as visited
queue <int> q;
q.push(s);
visited[s] = true;
parent[s] = -1;
// Standard BFS Loop
while (!q.empty())
{
int u = q.front();
q.pop();
for (int v=0; v<V; v++)
{
if (visited[v]==false && rGraph[u][v] > 0)
{
q.push(v);
parent[v] = u;
visited[v] = true;
}
}
}
// If we reached sink in BFS starting from source, then return
// true, else false
return (visited[t] == true);
}
// Returns the maximum flow from s to t in the given graph
int fordFulkerson(int graph[V][V], int s, int t)
{
int u, v;
// Create a residual graph and fill the residual graph with
// given capacities in the original graph as residual capacities
// in residual graph
int rGraph[V][V]; // Residual graph where rGraph[i][j] indicates
// residual capacity of edge from i to j (if there
// is an edge. If rGraph[i][j] is 0, then there is not)
for (u = 0; u < V; u++)
for (v = 0; v < V; v++)
rGraph[u][v] = graph[u][v];
int parent[V]; // This array is filled by BFS and to store path
int max_flow = 0; // There is no flow initially
// Augment the flow while there is a path from source to sink
while (bfs(rGraph, s, t, parent))
{
// Find minimum residual capacity of the edges along the
// path filled by BFS. Or we can say find the maximum flow
// through the path found.
int path_flow = INT_MAX;
for (v=t; v!=s; v=parent[v])
{
u = parent[v];
path_flow = min(path_flow, rGraph[u][v]);
}
// update residual capacities of the edges and reverse edges
// along the path
for (v=t; v != s; v=parent[v])
{
u = parent[v];
rGraph[u][v] -= path_flow;
rGraph[v][u] += path_flow;
}
// Add path flow to overall flow
max_flow += path_flow;
}
// Return the overall flow
return max_flow;
}
// Driver program to test above functions
int main()
{
// Let us create a graph shown in the above example
int graph[V][V] = { {0, 16, 13, 0, 0, 0},
{0, 0, 10, 12, 0, 0},
{0, 4, 0, 0, 14, 0},
{0, 0, 9, 0, 0, 20},
{0, 0, 0, 7, 0, 4},
{0, 0, 0, 0, 0, 0}
};
cout << "The maximum possible flow is " << fordFulkerson(graph, 0, 5);
return 0;
}
Questions: In the method bool bfs(int rGraph[V][V], int s, int t, int parent[]), why do we have the array parent[]? What is the array parent[] used for?
Why is a visited[V] array needed for this algorithm?
What is memset(visited, 0, sizeof(visited))?
Why are we setting parent[s] = -1? Why are setting visited[s] = true?
Why are using a standard BFS Loop? What does int u = q.front() do? Why are we using the pop method q.pop()?
Inside of the for (int v=0; v<V; v++) loop, we have an if statement if (visited[v]==false && rGraph[u][v] > 0) where we use
q.push(v);
parent[v] = u;
visited[v] = true;
Why we using the above three lines inside of the if statement?
Why do we have a strange looking for loop statement for (v=t; v!=s; v=parent[v])??
Basically, you need to add more code comments to explain what the above source code is trying to do.
Explanation / Answer
In the method bool bfs(int rGraph[V][V], int s, int t, int parent[]), why do we have the array parent[]? What is the array parent[] used for?
Array parent [] is used for to store the path.
Why is a visited[V] array needed for this algorithm?
It stores the nodes which are visited
What is memset(visited, 0, sizeof(visited))?
It creates a queue which stores the nodes which are visited and also the size of the vertex which are visited.
Why are we setting parent[s] = -1? Why are setting visited[s] = true?
Initiial values are set to -1.When the nodes are visited that particular node is made true.
Why are using a standard BFS Loop? What does int u = q.front() do? Why are we using the pop method q.pop()?
BFS loop is used to parse the array.From front the values are inserted and the pop method is used to move the nodes.