Algorithm
The Ford-Fulkerson algorithm is a max-flow algorithm used in network flow problems. It was introduced by L.R. Ford Jr. and D.R. Fulkerson in 1956. The algorithm is designed to find the maximum flow in a flow network, which is a directed graph where each edge has a capacity and represents a conduit through which a certain quantity (the flow) can be transported.
Here's a basic overview of the Ford-Fulkerson algorithm:
-
Initialization: Start with an initial feasible flow, which is usually set to zero.
-
Augmenting Paths: While there exists an augmenting path in the residual graph (a graph that represents the remaining capacity on each edge after the current flow is considered), augment the flow along this path. An augmenting path is a path from the source to the sink in which the capacity of each edge is greater than the flow through that edge.
-
Update Residual Graph: Update the residual graph by subtracting the augmented flow from forward edges and adding it to backward edges.
-
Repeat: Repeat steps 2 and 3 until no more augmenting paths can be found.
The Ford-Fulkerson algorithm doesn't specify how to choose the augmenting paths, and different choices can lead to different results. One popular method is the Edmonds-Karp algorithm, which always chooses the shortest augmenting path in terms of the number of edges.
It's important to note that the Ford-Fulkerson algorithm may not terminate in a finite amount of time if capacities are real numbers. To guarantee termination, a proper choice of augmenting paths or other modifications, such as the use of the capacity scaling technique, may be necessary.
Code Examples
#1 Ford-Fulkerson implement in Python
Code -
Python Programming
from collections import defaultdict, deque
class Graph:
def __init__(self, graph):
self.graph = graph
self.rows = len(graph)
self.cols = len(graph[0])
def add_edge(self, u, v, capacity):
self.graph[u][v] = capacity
def bfs(self, s, t, parent):
visited = [False] * self.rows
queue = deque()
queue.append(s)
visited[s] = True
while queue:
u = queue.popleft()
for ind, val in enumerate(self.graph[u]):
if visited[ind] == False and val > 0:
queue.append(ind)
visited[ind] = True
parent[ind] = u
return visited[t]
def ford_fulkerson(self, source, sink):
parent = [-1] * self.rows
max_flow = 0
while self.bfs(source, sink, parent):
path_flow = float("inf")
s = sink
while s != source:
path_flow = min(path_flow, self.graph[parent[s]][s])
s = parent[s]
max_flow += path_flow
v = sink
while v != source:
u = parent[v]
self.graph[u][v] -= path_flow
self.graph[v][u] += path_flow
v = parent[v]
return max_flow
# Example Usage:
graph = [[0, 10, 5, 15, 0],
[0, 0, 4, 0, 0],
[0, 0, 0, 0, 10],
[0, 0, 0, 0, 10],
[0, 0, 0, 0, 0]]
g = Graph(graph)
source = 0
sink = 4
print("Max Flow:", g.ford_fulkerson(source, sink))
#2 Ford-Fulkerson implement in Java
Code -
Java Programming
import java.util.*;
class FordFulkerson {
private static final int INF = Integer.MAX_VALUE;
// Returns the maximum flow in the given graph
static int fordFulkerson(int graph[][], int source, int sink) {
int V = graph.length;
int rGraph[][] = new int[V][V]; // Residual graph
for (int u = 0; u < V; u++)
for (int v = 0; v < V; v++)
rGraph[u][v] = graph[u][v];
int parent[] = new int[V]; // Parent array to store augmenting path
int maxFlow = 0; // Initialize result
// Augument the flow while tere is augmenting path
while (bfs(rGraph, source, sink, parent)) {
int pathFlow = INF;
for (int v = sink; v != source; v = parent[v]) {
int u = parent[v];
pathFlow = Math.min(pathFlow, rGraph[u][v]);
}
// update residual capacities of the edges and reverse edges along the path
for (int v = sink; v != source; v = parent[v]) {
int u = parent[v];
rGraph[u][v] -= pathFlow;
rGraph[v][u] += pathFlow;
}
// Add path flow to overall flow
maxFlow += pathFlow;
}
return maxFlow;
}
// Returns true if there is an augmenting path in the residual graph
private static boolean bfs(int rGraph[][], int source, int sink, int parent[]) {
int V = rGraph.length;
boolean visited[] = new boolean[V];
Arrays.fill(visited, false);
Queue < Integer> queue = new LinkedList<>();
queue.add(source);
visited[source] = true;
parent[source] = -1;
// Standard BFS Loop
while (!queue.isEmpty()) {
int u = queue.poll();
for (int v = 0; v < V; v++) {
if (!visited[v] && rGraph[u][v] > 0) {
// If we find a connection to the sink node, then there is an augmenting path
if (v == sink) {
parent[v] = u;
return true;
}
queue.add(v);
parent[v] = u;
visited[v] = true;
}
}
}
// We didn't reach the sink
return false;
}
public static void main(String[] args) {
// Example usage
int graph[][] = {
{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}
};
int source = 0, sink = 5;
System.out.println("Maximum Flow: " + fordFulkerson(graph, source, sink));
}
}
#3 Ford-Fulkerson implement in C
Code -
C Programming
#include <stdio.h>
#include <limits.h>
#include <string.h>
#include <stdbool.h>
#define V 6 // Number of vertices in the graph
int min(int a, int b) {
return (a < b) ? a : b;
}
// 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[]) {
bool visited[V];
memset(visited, 0, sizeof(visited));
visited[s] = true;
parent[s] = -1;
// Create a queue, enqueue source vertex and mark source vertex as visited
int queue[V];
int front = 0, rear = 0;
queue[rear++] = s;
while (front != rear) {
int u = queue[front++];
for (int v = 0; v < V; v++) {
if (!visited[v] && rGraph[u][v] > 0) {
// If we find a connection to the sink node, then there is no point in BFS anymore
// We just have to set its parent and can return true
if (v == t) {
parent[v] = u;
return true;
}
visited[v] = true;
parent[v] = u;
queue[rear++] = v;
}
}
}
// We didn't reach the sink
return false;
}
// Ford-Fulkerson algorithm using Edmonds-Karp implementation
int fordFulkerson(int graph[V][V], int s, int t) {
int rGraph[V][V]; // Residual graph where rGraph[i][j] indicates residual capacity of edge from i to j
// Initialize residual graph as original graph
for (int u = 0; u < V; u++)
for (int 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
// Augument the flow while tere is path from source to sink
while (bfs(rGraph, s, t, parent)) {
// Find minimum residual capacity of the edhes along the path filled by BFS. Or we can say
// find the maximum flow through the path found.
int path_flow = INT_MAX;
for (int v = t; v != s; v = parent[v]) {
int u = parent[v];
path_flow = min(path_flow, rGraph[u][v]);
}
// update residual capacities of the edges and reverse edges along the path
for (int v = t; v != s; v = parent[v]) {
int u = parent[v];
rGraph[u][v] -= path_flow;
rGraph[v][u] += path_flow;
}
// add path flow to overall flow
max_flow += path_flow;
}
return max_flow;
}
int main() {
// Example graph
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} };
int source = 0, sink = 5;
printf("The maximum possible flow is %d\n", fordFulkerson(graph, source, sink));
return 0;
}
#4 Ford-Fulkerson implement in C++
Code -
C++ Programming
#include <iostream>
#include <climits>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int MAX_V = 100; // Maximum number of vertices in the graph
// Structure to represent an edge in the graph
struct Edge {
int v, u, capacity, flow;
};
class FordFulkerson {
private:
int V; // Number of vertices
int E; // Number of edges
vector < Edge> edges; // List of edges
vector<vector<int>> graph; // Adjacency matrix
public:
FordFulkerson(int vertices) : V(vertices), E(0) {
graph.resize(V, vector<int>(V, 0));
}
void addEdge(int u, int v, int capacity) {
edges.push_back({u, v, capacity, 0});
edges.push_back({v, u, 0, 0}); // Residual edge
graph[u][v] = E;
graph[v][u] = E + 1;
E += 2;
}
int fordFulkerson(int source, int sink) {
int maxFlow = 0;
while (true) {
vector<int> parent(V, -1); // Store the augmenting path
queue < pair<int, int>> q; // BFS queue
q.push({source, INT_MAX});
while (!q.empty()) {
int u = q.front().first;
int minCapacity = q.front().second;
q.pop();
for (int i = 0; i < V; ++i) {
if (parent[i] == -1 && graph[u][i] < edges[graph[u][i]].capacity) {
int newMinCapacity = min(minCapacity, edges[graph[u][i]].capacity - edges[graph[u][i]].flow);
parent[i] = graph[u][i];
q.push({i, newMinCapacity});
if (i == sink) {
// Found augmenting path
int pathCapacity = newMinCapacity;
int v = i;
while (v != source) {
int edgeIndex = parent[v];
edges[edgeIndex].flow += pathCapacity;
edges[edgeIndex ^ 1].flow -= pathCapacity;
v = edges[edgeIndex].u;
}
maxFlow += pathCapacity;
break;
}
}
}
}
if (parent[sink] == -1) {
// No augmenting path found
break;
}
}
return maxFlow;
}
};
int main() {
int V = 6; // Number of vertices in the graph
FordFulkerson graph(V);
// Add edges to the graph
graph.addEdge(0, 1, 10);
graph.addEdge(0, 2, 10);
graph.addEdge(1, 2, 2);
graph.addEdge(1, 3, 4);
graph.addEdge(2, 4, 9);
graph.addEdge(3, 4, 6);
graph.addEdge(3, 5, 10);
graph.addEdge(4, 5, 10);
int source = 0;
int sink = 5;
int maxFlow = graph.fordFulkerson(source, sink);
cout << "Maximum Flow: " << maxFlow << endl;
return 0;
}
Demonstration
Ford-Fulkerson Data Structure and Algorithm