Interactive Programming Education Platform

Logic Practice

In this guide, we will explore the Ford Fulkerson Algorithm in C++ and how it can be applied in practice.

What is the Ford Fulkerson Algorithm?

The Ford-Fulkerson algorithm is commonly utilized for resolving maximum flow challenges within a network. The objective of the maximum flow issue is to determine the highest volume of flow that can be transmitted from a specified source node to a target node in a graph with directed weights, all while adhering to the constraints of edge capacities. This method functions by progressively pinpointing an augmented path in the residual graph that links the source to the target. The residual graph is constructed by deducting the current flow of data from the capacity of each edge. Subsequently, the algorithm augments the flow along this path by the maximum feasible amount, which is equivalent to the minimum capacity among the path's edges.

Problem:

Examine a graph illustrating a flow network where each edge is assigned a specific capacity value. When provided with two vertices, namely the source 's' and the sink 't', ascertain the maximum achievable flow from s to t while abiding by the following restrictions:

✅ The flow through an edge is constrained by the capacity of that edge.
✅ With the exception of the source 's' and the sink 't', every vertex maintains an equal volume of incoming and outgoing flow.

The Ford-Fulkerson Algorithm

The following is a fundamental concept of the Ford-Fulkerson algorithm:

✅ Begin with an initial flow of 0.
✅ It also contains an additional passage from the source to the sink: Generate an expanded path using a path search technique such as: Breadth-first search or depth-first search. Calculate the flow rate that can be transferred along an extended path. This is the minimum remaining capacity at the end of the path. Increase the rate of flow along the augmenting path to the specified amount.
✅ Return the highest possible flow.
✅ Generate an expanded path using a path search technique such as: Breadth-first search or depth-first search.
✅ Calculate the flow rate that can be transferred along an extended path. This is the minimum remaining capacity at the end of the path.
✅ Increase the rate of flow along the augmenting path to the specified amount.

Implementation:

Initially, we will elaborate on the notion of a Residual Graph, a fundamental concept essential for comprehending the execution process.

The leftover graph in a flow network signifies additional potential flows. When a path exists in the residual graph from the source to the sink, additional flow can be incorporated. Each edge within the residual graph is accompanied by a parameter known as residual capacity, which is calculated as the original capacity of the edge minus the existing flow through it. This residual capacity denotes the current capacity of the edge.

Now, let's delve into the specifics of the implementation. The remaining capacity becomes null when there's no connection between two nodes in the residual graph. Initializing the residual graph to mirror the original one is feasible since no initial flow exists, and the residual capacity matches the original capacity initially. To identify an augmenting path, we can apply either a Breadth-First Search (BFS) or a Depth-First Search (DFS) on the residual graph. Utilizing BFS allows us to determine the presence of a viable path from the source to the sink and also produces a parent array. By traversing the found path using the parent array, we can ascertain a workable flow by computing the minimum residual capacity along the path. Subsequently, we incorporate the flow from the identified path into the overall flow.

We must ensure to update the remaining capacity within the residual graph. By deducting the flow along the path from all edges and transferring it to the reverse edges, we maintain the flow balance. It's essential to allocate flow along reverse edges to accommodate potential flow in the opposite direction.

Example:

Let's consider a scenario to demonstrate the Ford Fulkerson Algorithm in C++.

FileName: FordFulkerson.cpp

Example


// Program to implement the the Ford-Fulkerson Algorithm 
#include <iostream>
#include <limits.h>
#include <queue>
#include <string.h>
using namespace std;

// Declaring the count of the vertices
#define V 6

/* Returns true if a path exists between source and sink 't' in the residual graph. Additionally, it stores the route in the parent[].*/
bool bfsSearch(int rGraph[V][V], int s, int t, int parent[])
{
	//The initial visited array, which is marked as not listed
	bool visited[V];
	memset(visited, 0, sizeof(visited));

	// Create a queue, enqueue the source vertex, and mark the source
	// vertex as visited
	queue<int> q;
	q.push(s);
	visited[s] = true;
	parent[s] = -1;

	//The logic for the BFS
	while (!q.empty()) {
		int u = q.front();
		q.pop();

		for (int v = 0; v < V; v++) {
			if (visited[v] == false && rGraph[u][v] > 0) {
				// checking for the condition in BFS for any node; we
				//If it is true, then the parent value is set to return true
				if (v == t) {
					parent[v] = u;
					return true;
				}
				q.push(v);
				parent[v] = u;
				visited[v] = true;
			}
		}
	}

	//As the sink node is not reached so, it will return as a false
	return false;
}

// the function for finding the flow in a graph
int fordFulkersonAlgo(int graph[V][V], int s, int t)
{
	int u, v;
     //Create an augmenting path using any path-finding
     // approach, including breadth-first or depth-first search.
    //Determine the quantity of flow that can be s
    //hared down the augmenting path, as well as the 
    //path?s edges' minimal residual capability.
	int rGraph[V]
			[V]; //the capacity of the residual graph
                                         // initialled with 0
				// from i to j (if there is an edge. If
				// rGraph[i][j] is 0, then there is no edge)
	for (u = 0; u < V; u++)
		for (v = 0; v < V; v++)
			rGraph[u][v] = graph[u][v];

	int parent[V]; // the bfs array for storing path
				// store path

	int max_flow = 0; //setting up the initial flow as 0
	//checking if the flow exists is not
	while (bfsSearch(rGraph, s, t, parent)) {
		//The minimum residual capacity can be found, and
		// the path filled by BFS.
                     //Or finding the maximum flow of the path
		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 and reverse the edges 
		for (v = t; v != s; v = parent[v]) {
			u = parent[v];
			rGraph[u][v] -= path_flow;
			rGraph[v][u] += path_flow;
		}

		// adding up the flow path to the Toal flow
		max_flow += path_flow;
	}

	//The max flow is then returned
	return max_flow;
}

// Main section
int main()
{
	//The initial graph creation
	int graphS[V][V]
		= { { 0, 16, 13, 0, 12, 0 }, { 0, 0, 10, 22, 0, 0 },
			{ 0, 8, 0, 0, 14, 0 }, { 0, 0, 9, 0, 0, 20 },
			{ 0, 0, 0, 7, 0, 4 }, { 0, 0, 0, 1, 0, 0 } };

	cout << "The maximum possible flow is "
		<< fordFulkersonAlgo(graphS, 0, 5);

	return 0;
}

Output:

Output


The maximum possible flow is 24

Complexity Analysis:

Time Complexity:

The time complexity is O(|V| * E^2), with E representing the quantity of edges and V denoting the number of vertices.

Space complexity:

The space requirement is O(V) due to the creation of a queue.

The program mentioned above, which is applied in the Ford Fulkerson Algorithm, is commonly known as the Edmonds-Karp Algorithm. Edmonds-Karp suggests utilizing Breadth-First Search (BFS) in the Ford Fulkerson approach because BFS consistently selects the path with the minimum number of edges. By employing BFS, the worst-case time complexity decreases to O(VE^2). The implementation described above utilizes adjacency matrix representation. However, whereas BFS operates in O(V^2) time, the mentioned implementation necessitates O(EV^3) time.

Applications of Ford Fulkerson Algorithm:

The primary method for determining the maximum flow in a flow network is the Ford-Fulkerson algorithm. This algorithm is widely employed across various industries and disciplines. The Ford-Fulkerson approach finds frequent application in the following contexts and situations:

Network:

The Ford-Fulkerson algorithm is commonly employed for addressing network flow dilemmas. It defines the highest amount of flow that can be transmitted from a starting point to a destination in a flow network.

Transportation:

Enhancing transportation and logistics systems entails maximizing the movement of goods from suppliers to consumers using various transport modes such as roads, railways, or other connection channels.

Telecommunication:

The method can enhance data transfer within telecommunication networks, resulting in efficient interaction among numerous nodes.

Image segmentation:

In the field of artificial intelligence, the Ford-Fulkerson algorithm can partition images into segments based on attributes such as intensity or color.

Ford Fulkerson Algorithm In C++