Maxflow Mincut Theorem

Let's talk about Maxflow and Mincut. These are like two sides of the same coin when dealing with network flow problems. If you ever wondered how stuff moves through a network, whether its water in pipes, cars on roads, or data in a network, then youre already thinking in terms of max flow and min cut.

What is Maxflow?

Maxflow (Maximum Flow) is all about figuring out the most stuff (data, water, traffic) that can move from one point (source) to another (sink) in a network without breaking any capacity limits. Imagine a bunch of pipes carrying water, and you want to know the maximum amount of water that can flow through the system without overflowing.

What is Mincut?

Mincut (Minimum Cut) is kind of the opposite. Its about finding the weakest link in the network that, if cut, would completely stop the flow from the source to the sink. Think of it like identifying the narrowest point in a road system where a traffic jam would completely block all movement.

Maxflow and Mincut Theorem

Heres something cool: The Maxflow-Mincut Theorem says that the maximum flow in a network is equal to the total capacity of the smallest set of edges that, if removed, would stop the flow completely. This means if you

These concepts arent just theoretical; they are used in real life all the time:

• Traffic Management: Figuring out the best way to manage congestion in roads.
• Computer Networks: Making sure data packets travel efficiently.
• Airline Scheduling: Ensuring flights are assigned to routes in the best way possible.
• Water Distribution: Managing water flow in pipelines to avoid shortages.
• Project Management: Finding the critical path in workflows to improve efficiency.

Example to Understand Maxflow

Imagine a city with roads connecting different areas. If you want to get the max number of cars from the start point to the endpoint, thats maxflow. Now, let's write code.

Maxflow using Ford-Fulkerson Algorithm

Steps to find the maxflow in a graph using the Ford-Fulkerson Algorithm:

1. Start with the initial flow as 0.
2. While there is an augmenting path from source to sink:
    a. Find the path with the minimum capacity.
    b. Increase the flow along the path.
3. The maximum flow is the sum of all flows along the augmenting paths.

Here's the code to find the maxflow in a graph using the Ford-Fulkerson Algorithm:

#include <stdio.h>
#include <string.h>
#include <limits.h>

#define V 6  // Number of vertices

// Function to perform DFS and find an augmenting path
int dfs(int rGraph[V][V], int s, int t, int parent[]) {
   int visited[V];
   memset(visited, 0, sizeof(visited));  
   int stack[V], top = -1;
   stack[++top] = s;
   visited[s] = 1;

   while (top >= 0) {
      int u = stack[top--];
      for (int v = 0; v < V; v++) {
         if (!visited[v] && rGraph[u][v] > 0) {
            stack[++top] = v;
            visited[v] = 1;
            parent[v] = u;
            if (v == t) {
               return 1;
            }
         }
      }
   }
   return 0;
}

// Ford-Fulkerson algorithm to find the max-flow
int fordFulkerson(int graph[V][V], int source, int sink) {
   int rGraph[V][V];  // Residual graph
   for (int i = 0; i < V; i++) {
      for (int j = 0; j < V; j++) {
         rGraph[i][j] = graph[i][j];
      }
   }

   int parent[V];
   int maxFlow = 0;

   // Augment the flow while there is an augmenting path
   while (dfs(rGraph, source, sink, parent)) {
      int pathFlow = INT_MAX;
      for (int v = sink; v != source; v = parent[v]) {
         int u = parent[v];
         pathFlow = (pathFlow < rGraph[u][v]) ? pathFlow : rGraph[u][v];
      }
      maxFlow += pathFlow;

      // Update the residual graph
      for (int v = sink; v != source; v = parent[v]) {
         int u = parent[v];
         rGraph[u][v] -= pathFlow;
         rGraph[v][u] += pathFlow;
      }
   }
   return maxFlow;
}

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("Maximum flow: %d\n", fordFulkerson(graph, source, sink));

   return 0;
}

Maximum flow: 23

#include <iostream>
#include <climits>

#define V 6  // Number of vertices

using namespace std;

// Function to perform DFS and find an augmenting path
bool dfs(int rGraph[V][V], int s, int t, int parent[]) {
   bool visited[V] = {0};
   int stack[V], top = -1;
   stack[++top] = s;
   visited[s] = true;

   while (top >= 0) {
      int u = stack[top--];
      for (int v = 0; v < V; v++) {
         if (!visited[v] && rGraph[u][v] > 0) {
            stack[++top] = v;
            visited[v] = true;
            parent[v] = u;
            if (v == t)
               return true;
         }
      }
   }
   return false;
}

// Ford-Fulkerson algorithm to find the max-flow
int fordFulkerson(int graph[V][V], int source, int sink) {
   int rGraph[V][V];  // Residual graph
   for (int i = 0; i < V; i++) {
      for (int j = 0; j < V; j++) {
         rGraph[i][j] = graph[i][j];
      }
   }

   int parent[V];
   int maxFlow = 0;

   // Augment the flow while there is an augmenting path
   while (dfs(rGraph, source, sink, parent)) {
      int pathFlow = INT_MAX;
      for (int v = sink; v != source; v = parent[v]) {
         int u = parent[v];
         pathFlow = (pathFlow < rGraph[u][v]) ? pathFlow : rGraph[u][v];
      }
      maxFlow += pathFlow;

      // Update the residual graph
      for (int v = sink; v != source; v = parent[v]) {
         int u = parent[v];
         rGraph[u][v] -= pathFlow;
         rGraph[v][u] += pathFlow;
      }
   }
   return maxFlow;
}

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;

   cout << "Maximum flow: " << fordFulkerson(graph, source, sink) << endl;

   return 0;
}

Maximum flow: 23

import java.util.*;

public class Maxflow {
   static final int V = 6;  // Number of vertices

   // Function to perform DFS and find an augmenting path
   static boolean dfs(int rGraph[][], int s, int t, int parent[]) {
      boolean visited[] = new boolean[V];
      Stack<Integer> stack = new Stack<>();
      stack.push(s);
      visited[s] = true;

      while (!stack.isEmpty()) {
         int u = stack.pop();
         for (int v = 0; v < V; v++) {
            if (!visited[v] && rGraph[u][v] > 0) {
               stack.push(v);
               visited[v] = true;
               parent[v] = u;
               if (v == t)
                  return true;
            }
         }
      }
      return false;
   }

   // Ford-Fulkerson algorithm to find the max-flow
   static int fordFulkerson(int graph[][], int source, int sink) {
      int rGraph[][] = new int[V][V];  // Residual graph
      for (int i = 0; i < V; i++) {
         for (int j = 0; j < V; j++) {
            rGraph[i][j] = graph[i][j];
         }
      }

      int parent[] = new int[V];
      int maxFlow = 0;

      // Augment the flow while there is an augmenting path
      while (dfs(rGraph, source, sink, parent)) {
         int pathFlow = Integer.MAX_VALUE;
         for (int v = sink; v != source; v = parent[v]) {
            int u = parent[v];
            pathFlow = Math.min(pathFlow, rGraph[u][v]);
         }
         maxFlow += pathFlow;

         // Update the residual graph
         for (int v = sink; v != source; v = parent[v]) {
            int u = parent[v];
            rGraph[u][v] -= pathFlow;
            rGraph[v][u] += pathFlow;
         }
      }
      return maxFlow;
   }

   public static void main(String[] args) {
      // Example graph
      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));
   }
}

Maximum flow: 23

V = 6  # Number of vertices

# Function to perform DFS and find an augmenting path
def dfs(rGraph, s, t, parent):
   visited = [False] * V
   stack = []
   stack.append(s)
   visited[s] = True

   while stack:
      u = stack.pop()
      for v in range(V):
         if not visited[v] and rGraph[u][v] > 0:
            stack.append(v)
            visited[v] = True
            parent[v] = u
            if v == t:
               return True
   return False

# Ford-Fulkerson algorithm to find the max-flow
def fordFulkerson(graph, source, sink):
   rGraph = [[0] * V for _ in range(V)]  # Residual graph
   for i in range(V):
      for j in range(V):
         rGraph[i][j] = graph[i][j]

   parent = [-1] * V
   maxFlow = 0

   # Augment the flow while there is an augmenting path
   while dfs(rGraph, source, sink, parent):
      pathFlow = float('inf')
      v = sink
      while v != source:
         u = parent[v]
         pathFlow = min(pathFlow, rGraph[u][v])
         v = parent[v]
      maxFlow += pathFlow

      # Update the residual graph
      v = sink
      while v != source:
         u = parent[v]
         rGraph[u][v] -= pathFlow
         rGraph[v][u] += pathFlow
         v = parent[v]
   return maxFlow

# Example graph
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]]
source, sink = 0, 5

print("Maximum flow:", fordFulkerson(graph, source, sink))

Maximum flow: 23

Example to Understand Mincut

We already know what mincut is, let's code to find the mincut in a graph using the Ford-Fulkerson Algorithm:

Mincut using Ford-Fulkerson Algorithm

Steps to find the mincut in a graph using the Ford-Fulkerson Algorithm:

Initialize the graph and residual graph, and set up the parent[] array to track paths.
Perform BFS to find an augmenting path from source to sink in the residual graph.
Update residual graph by reducing the flow along the found path and adding reverse flow.
Repeat BFS until no augmenting path is found.
Perform DFS to find all reachable vertices from the source in the residual graph.
Print the edges that go from a reachable vertex to a non-reachable vertex, which form the minimum cut.

Now, let's see how to find the mincut in a graph using the Ford-Fulkerson Algorithm:

#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <stdbool.h>

#define V 6

// Simple queue structure for BFS
typedef struct {
   int items[V];
   int front, rear;
} Queue;

void initQueue(Queue* q) {
   q->front = -1;
   q->rear = -1;
}

int isEmpty(Queue* q) {
   return q->front == -1;
}

void enqueue(Queue* q, int value) {
   if (q->rear == V - 1)
      return; // Queue overflow
   if (q->front == -1)
      q->front = 0;
   q->items[++(q->rear)] = value;
}

int dequeue(Queue* q) {
   if (isEmpty(q))
      return -1; // Queue underflow
   int item = q->items[q->front];
   if (q->front == q->rear)
      q->front = q->rear = -1;
   else
      q->front++;
   return item;
}

int bfs(int rGraph[V][V], int s, int t, int parent[]) {
   bool visited[V];
   memset(visited, 0, sizeof(visited));

   Queue q;
   initQueue(&q);
   enqueue(&q, s);
   visited[s] = 1;
   parent[s] = -1;

   while (!isEmpty(&q)) {
      int u = dequeue(&q);

      for (int v = 0; v < V; v++) {
         if (!visited[v] && rGraph[u][v] > 0) {
            enqueue(&q, v);
            parent[v] = u;
            visited[v] = 1;
         }
      }
   }
   return (visited[t] == 1);
}

void dfs(int rGraph[V][V], int s, bool visited[]) {
   visited[s] = 1;
   for (int i = 0; i < V; i++) {
      if (rGraph[s][i] && !visited[i])
         dfs(rGraph, i, visited);
   }
}

void minCut(int graph[V][V], int s, int t) {
   int u, v;
   int rGraph[V][V];
   for (u = 0; u < V; u++) {
      for (v = 0; v < V; v++) {
         rGraph[u][v] = graph[u][v];
      }
   }

   int parent[V];
   while (bfs(rGraph, s, t, parent)) {
      int path_flow = INT_MAX;
      for (v = t; v != s; v = parent[v]) {
         u = parent[v];
         path_flow = (path_flow < rGraph[u][v]) ? path_flow : rGraph[u][v];
      }

      for (v = t; v != s; v = parent[v]) {
         u = parent[v];
         rGraph[u][v] -= path_flow;
         rGraph[v][u] += path_flow;
      }
   }

   bool visited[V];
   memset(visited, 0, sizeof(visited));
   dfs(rGraph, s, visited);

   for (int i = 0; i < V; i++) {
      for (int j = 0; j < V; j++) {
         if (visited[i] && !visited[j] && graph[i][j]) {
            printf("%d - %d\n", i, j);
         }
      }
   }
}

int main() {
   int graph[V][V] = {
      {0, 10, 0, 10, 0, 0},
      {0, 0, 5, 0, 0, 0},
      {0, 0, 0, 0, 10, 0},
      {0, 0, 0, 0, 0, 20},
      {0, 0, 0, 0, 0, 10},
      {0, 0, 0, 0, 0, 0}
   };
   printf("Minimum Cut Edges: \n");
   minCut(graph, 0, 5);

   return 0;
}

Minimum Cut Edges:
0 - 3
1 - 2

#include <iostream>
#include <limits.h>
#include <cstring>
#include <queue>
using namespace std;

// Define the number of vertices in the graph
#define NUM_VERTICES 6

// Helper function to perform BFS and check if there's a path from source to sink
// It also updates the parent array with the path
bool bfs(int residualGraph[NUM_VERTICES][NUM_VERTICES], int source, int sink, int parent[]) {
   // Array to track visited vertices
   bool visited[NUM_VERTICES];
   memset(visited, false, sizeof(visited));

   // Queue for BFS traversal, starting with the source
   queue<int> q;
   q.push(source);
   visited[source] = true;
   parent[source] = -1;

   // Perform BFS
   while (!q.empty()) {
      int node = q.front();
      q.pop();

      // Explore all adjacent nodes
      for (int adj = 0; adj < NUM_VERTICES; adj++) {
         if (!visited[adj] && residualGraph[node][adj] > 0) {
            q.push(adj);
            parent[adj] = node;
            visited[adj] = true;
         }
      }
   }

   // Return true if the sink is reachable
   return (visited[sink] == true);
}

// Recursive DFS to find all reachable vertices from the source
void dfs(int residualGraph[NUM_VERTICES][NUM_VERTICES], int source, bool visited[]) {
   visited[source] = true;
   for (int i = 0; i < NUM_VERTICES; i++) {
      if (residualGraph[source][i] && !visited[i]) {
         dfs(residualGraph, i, visited);
      }
   }
}

// Function to compute and print the minimum cut
void findMinCut(int originalGraph[NUM_VERTICES][NUM_VERTICES], int source, int sink) {
   int u, v;

   // Initialize the residual graph
   int residualGraph[NUM_VERTICES][NUM_VERTICES];
   for (u = 0; u < NUM_VERTICES; u++) {
      for (v = 0; v < NUM_VERTICES; v++) {
         residualGraph[u][v] = originalGraph[u][v];
      }
   }

   // Array to store the path from source to sink
   int parent[NUM_VERTICES];

   // Augment the flow while there is a path from source to sink
   while (bfs(residualGraph, source, sink, parent)) {
      // Find the minimum capacity along the path
      int pathFlow = INT_MAX;
      for (v = sink; v != source; v = parent[v]) {
         u = parent[v];
         pathFlow = min(pathFlow, residualGraph[u][v]);
      }

      // Update the residual graph capacities
      for (v = sink; v != source; v = parent[v]) {
         u = parent[v];
         residualGraph[u][v] -= pathFlow;
         residualGraph[v][u] += pathFlow;
      }
   }

   // At this point, the maximum flow is found. Now find the reachable vertices
   bool visited[NUM_VERTICES];
   memset(visited, false, sizeof(visited));
   dfs(residualGraph, source, visited);

   // Print all edges that are from reachable to non-reachable vertices in the original graph
   cout << "Minimum Cut Edges: \n";
   for (int i = 0; i < NUM_VERTICES; i++) {
      for (int j = 0; j < NUM_VERTICES; j++) {
         if (visited[i] && !visited[j] && originalGraph[i][j]) {
            cout << i << " - " << j << endl;
         }
      }
   }
}

int main() {
   // Example graph
   int graph[NUM_VERTICES][NUM_VERTICES] = {
      {0, 10, 0, 10, 0, 0},
      {0, 0, 5, 0, 0, 0},
      {0, 0, 0, 0, 10, 0},
      {0, 0, 0, 0, 0, 20},
      {0, 0, 0, 0, 0, 10},
      {0, 0, 0, 0, 0, 0}
   };

   // Find the minimum cut between source (0) and sink (5)
   findMinCut(graph, 0, 5);

   return 0;
}

Minimum Cut Edges: 
0 - 3
1 - 2

import java.util.*;

public class MinCut {
   static final int V = 6;

   // Function to perform BFS and find if there's a path from source to sink
   static boolean bfs(int rGraph[][], int s, int t, int parent[]) {
      boolean visited[] = new boolean[V];
      Arrays.fill(visited, false);

      Queue<Integer> q = new LinkedList<>();
      q.add(s);
      visited[s] = true;
      parent[s] = -1;

      while (!q.isEmpty()) {
         int u = q.poll();

         for (int v = 0; v < V; v++) {
            if (!visited[v] && rGraph[u][v] > 0) {
               q.add(v);
               parent[v] = u;
               visited[v] = true;
            }
         }
      }

      return visited[t];
   }

   // Function to perform DFS and mark all reachable vertices from source
   static void dfs(int rGraph[][], int s, boolean visited[]) {
      visited[s] = true;
      for (int i = 0; i < V; i++) {
         if (rGraph[s][i] > 0 && !visited[i]) {
            dfs(rGraph, i, visited);
         }
      }
   }

   // Function to print the minimum cut
   static void minCut(int graph[][], int s, int t) {
      int rGraph[][] = new int[V][V];
      for (int i = 0; i < V; i++) {
         for (int j = 0; j < V; j++) {
            rGraph[i][j] = graph[i][j];
         }
      }

      int parent[] = new int[V];

      while (bfs(rGraph, s, t, parent)) {
         int pathFlow = Integer.MAX_VALUE;
         for (int v = t; v != s; v = parent[v]) {
            int u = parent[v];
            pathFlow = Math.min(pathFlow, rGraph[u][v]);
         }

         for (int v = t; v != s; v = parent[v]) {
            int u = parent[v];
            rGraph[u][v] -= pathFlow;
            rGraph[v][u] += pathFlow;
         }
      }

      boolean visited[] = new boolean[V];
      Arrays.fill(visited, false);
      dfs(rGraph, s, visited);

      System.out.println("Minimum Cut Edges:");
      for (int i = 0; i < V; i++) {
         for (int j = 0; j < V; j++) {
            if (visited[i] && !visited[j] && graph[i][j] > 0) {
               System.out.println(i + " - " + j);
            }
         }
      }
   }

   public static void main(String[] args) {
      int graph[][] = { 
         {0, 10, 0, 10, 0, 0},
         {0, 0, 5, 0, 0, 0},
         {0, 0, 0, 0, 10, 0},
         {0, 0, 0, 0, 0, 20},
         {0, 0, 0, 0, 0, 10},
         {0, 0, 0, 0, 0, 0}
      };
      minCut(graph, 0, 5);
   }
}

Minimum Cut Edges:
0 - 3
1 - 2

from collections import deque

V = 6

# Function to perform BFS and find if there's a path from source to sink
def bfs(rGraph, s, t, parent):
   visited = [False] * V
   q = deque([s])
   visited[s] = True
   parent[s] = -1

   while q:
      u = q.popleft()
      for v in range(V):
         if not visited[v] and rGraph[u][v] > 0:
            q.append(v)
            parent[v] = u
            visited[v] = True

   return visited[t]

# Function to perform DFS and mark all reachable vertices from source
def dfs(rGraph, s, visited):
   visited[s] = True
   for i in range(V):
      if rGraph[s][i] > 0 and not visited[i]:
         dfs(rGraph, i, visited)

# Function to print the minimum cut
def minCut(graph, s, t):
   rGraph = [row[:] for row in graph]

   parent = [-1] * V

   while bfs(rGraph, s, t, parent):
      pathFlow = float("inf")
      v = t
      while v != s:
         u = parent[v]
         pathFlow = min(pathFlow, rGraph[u][v])
         v = parent[v]

      v = t
      while v != s:
         u = parent[v]
         rGraph[u][v] -= pathFlow
         rGraph[v][u] += pathFlow
         v = parent[v]

   visited = [False] * V
   dfs(rGraph, s, visited)

   print("Minimum Cut Edges:")
   for i in range(V):
      for j in range(V):
         if visited[i] and not visited[j] and graph[i][j] > 0:
            print(f"{i} - {j}")

# Driver code
graph = [ 
   [0, 10, 0, 10, 0, 0],
   [0, 0, 5, 0, 0, 0],
   [0, 0, 0, 0, 10, 0],
   [0, 0, 0, 0, 0, 20],
   [0, 0, 0, 0, 0, 10],
   [0, 0, 0, 0, 0, 0]
]

minCut(graph, 0, 5)

Minimum Cut Edges:
0 - 3
1 - 2

Conclusion

Maxflow helps us figure out how much we can push through a system, while Mincut tells us where the weakest spots are. Both are super useful in real-life applications, from networks to transportation and beyond. Learning these concepts can help solve big optimization problems in different fields.