🌊 Maximum Flow Fundamentals

🎯 What is Maximum Flow?

Maximum flow is a fundamental problem in network flow theory. Given a directed graph with capacities on edges, find the maximum amount of flow that can be sent from a source node to a sink node.

Network: Directed graph G = (V, E) with capacities c(u,v) ≥ 0
Source (s): Where flow originates
Sink (t): Where flow terminates
Constraints: Flow ≤ capacity, conservation at intermediate nodes
Goal: Maximize total flow from s to t

📌 Augmenting Path📌 Residual Graph📌 Max-Flow Min-Cut Theorem

The Core Insight

Key Insight: Maximum flow problems can be solved by repeatedly finding augmenting paths in a residual graph until no more paths exist. The amount of flow equals the capacity of the minimum cut.

Three Main Algorithms:

Ford-Fulkerson DFS-based augmenting paths
Edmonds-Karp BFS-based (guaranteed polynomial)
Dinic's BFS + DFS (most efficient in practice)

# Maximum Flow Problem Statement
# Given:
#   - Directed graph G = (V, E)
#   - Capacity c(u,v) for each edge
#   - Source s, sink t
#
# Find: Maximum flow f such that:
#   1. 0 ≤ f(u,v) ≤ c(u,v) for all edges
#   2. ∑ f(u,v) = ∑ f(v,u) for all v ≠ s,t (conservation)
#   3. Maximize ∑ f(s,v) (total flow out of source)
#
# Example:
# Graph with edges: s->a(3), s->b(2), a->b(1), a->t(3), b->t(2)
# Maximum flow = 4 (s->a->t: 3, s->b->t: 1)

🔵 Ford-Fulkerson Algorithm

🎯 The Classic Algorithm

Ford-Fulkerson uses DFS to find augmenting paths in the residual graph. It works well for integer capacities and is the foundation of all max-flow algorithms.

Approach: While augmenting path exists, send flow
Residual Graph: Contains forward edges (remaining capacity) and backward edges (can cancel flow)
Time: O(E × f) where f is max flow value
Note: May be exponential for irrational capacities

# Ford-Fulkerson Algorithm
from collections import defaultdict

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = defaultdict(dict)
    
    def add_edge(self, u, v, capacity):
        self.graph[u][v] = capacity
        if v not in self.graph: self.graph[v] = {}
        if u not in self.graph[v]: self.graph[v][u] = 0
    
    def dfs(self, s, t, visited, flow):
        if s == t:
            return flow
        
        visited[s] = True
        
        for v in self.graph[s]:
            if not visited[v] and self.graph[s][v] > 0:
                # Try to send flow through this edge
                bottleneck = self.dfs(v, t, visited, min(flow, self.graph[s][v]))
                
                if bottleneck > 0:
                    # Update residual capacities
                    self.graph[s][v] -= bottleneck
                    self.graph[v][s] += bottleneck
                    return bottleneck
        
        return 0
    
    def max_flow(self, s, t):
        max_flow = 0
        
        while True:
            visited = [False] * self.V
            # Find augmenting path using DFS
            path_flow = self.dfs(s, t, visited, float('inf'))
            
            if path_flow == 0:
                break
            
            max_flow += path_flow
        
        return max_flow

# Example Usage
g = Graph(4)
g.add_edge(0, 1, 3)  # s -> a
g.add_edge(0, 2, 2)  # s -> b
g.add_edge(1, 2, 1)  # a -> b
g.add_edge(1, 3, 3)  # a -> t
g.add_edge(2, 3, 2)  # b -> t

print(f"Max Flow: {g.max_flow(0, 3)}")  # Output: 4

🔴 Edmonds-Karp Algorithm

🎯 Ford-Fulkerson with BFS

Edmonds-Karp is a specialization of Ford-Fulkerson that uses BFS to find the shortest augmenting path (in terms of number of edges). This guarantees polynomial time.

Approach: Use BFS to find shortest augmenting path
Time: O(V × E²) or O(V × E × f)
Guaranteed: Always terminates in polynomial time
Use Case: When you need guaranteed performance

# Edmonds-Karp Algorithm
from collections import deque

def edmonds_karp(graph, capacity, s, t):
    n = len(graph)
    flow = [[0] * n for _ in range(n)]
    max_flow = 0
    
    while True:
        # BFS to find augmenting path
        visited = [False] * n
        parent = [-1] * n
        queue = deque([s])
        visited[s] = True
        
        while queue:
            u = queue.popleft()
            for v in graph[u]:
                if not visited[v] and capacity[u][v] - flow[u][v] > 0:
                    visited[v] = True
                    parent[v] = u
                    if v == t:
                        break
                    queue.append(v)
        
        if not visited[t]:
            break
        
        # Find bottleneck capacity
        path_flow = float('inf')
        v = t
        while v != s:
            u = parent[v]
            path_flow = min(path_flow, capacity[u][v] - flow[u][v])
            v = u
        
        # Update flow along the path
        v = t
        while v != s:
            u = parent[v]
            flow[u][v] += path_flow
            flow[v][u] -= path_flow
            v = u
        
        max_flow += path_flow
    
    return max_flow

# Example Usage
# graph = adjacency list
# capacity = 2D list of capacities

🟣 Dinic's Algorithm

🎯 The Fastest in Practice

Dinic's algorithm uses level graphs (BFS) and blocking flows (DFS) to achieve O(V² × E) time, but performs much better in practice.

Approach: Build level graph, send blocking flow
Time: O(V² × E) worst-case, O(E × √V) for bipartite matching
Space: O(V + E)
Use Case: Most efficient for dense graphs

# Dinic's Algorithm
from collections import deque

class Dinic:
    def __init__(self, n):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.level = [0] * n
        self.it = [0] * n
    
    def add_edge(self, u, v, cap):
        self.graph[u].append([v, cap, len(self.graph[v])])
        self.graph[v].append([u, 0, len(self.graph[u]) - 1])
    
    def bfs(self, s, t):
        self.level = [-1] * self.n
        self.level[s] = 0
        queue = deque([s])
        
        while queue:
            u = queue.popleft()
            for v, cap, rev in self.graph[u]:
                if cap > 0 and self.level[v] == -1:
                    self.level[v] = self.level[u] + 1
                    queue.append(v)
        
        return self.level[t] != -1
    
    def dfs(self, u, t, f):
        if u == t:
            return f
        
        while self.it[u] < len(self.graph[u]):
            v, cap, rev = self.graph[u][self.it[u]]
            
            if cap > 0 and self.level[v] == self.level[u] + 1:
                pushed = self.dfs(v, t, min(f, cap))
                if pushed > 0:
                    # Update capacities
                    self.graph[u][self.it[u]][1] -= pushed
                    self.graph[v][rev][1] += pushed
                    return pushed
            
            self.it[u] += 1
        
        return 0
    
    def max_flow(self, s, t):
        flow = 0
        
        while self.bfs(s, t):
            self.it = [0] * self.n
            while True:
                pushed = self.dfs(s, t, float('inf'))
                if pushed == 0:
                    break
                flow += pushed
        
        return flow

# Example Usage
dinic = Dinic(4)
dinic.add_edge(0, 1, 3)  # s -> a
dinic.add_edge(0, 2, 2)  # s -> b
dinic.add_edge(1, 2, 1)  # a -> b
dinic.add_edge(1, 3, 3)  # a -> t
dinic.add_edge(2, 3, 2)  # b -> t

print(f"Max Flow: {dinic.max_flow(0, 3)}")  # Output: 4

📊 Residual Graphs & Augmenting Paths

🎯 The Core Data Structure

The residual graph is the key to understanding max-flow algorithms. It represents the remaining capacity for each edge and the ability to cancel flow.

Residual Capacity: c_f(u,v) = c(u,v) - f(u,v) for forward edges
Backward Edges: c_f(v,u) = f(u,v) (can cancel flow)
Augmenting Path: Path from s to t in the residual graph
Key Insight: Max flow achieved when no augmenting path exists

# Residual Graph Visualization
# Original Graph:
# s --(3)--> a --(3)--> t
# |           |
# (2)         (1)
# |           |
# v           v
# b --(2)--> t

# After sending 2 units from s->b->t:
# Residual Graph:
# s --(3)--> a --(3)--> t
# |           |
# (0)         (1)
# |           |
# v           v
# b --(0)--> t
# b --(2)--> s (backward edge)
# t --(2)--> b (backward edge)

# Augmenting Path: s -> a -> b -> t (using residual edges)
# This allows re-routing flow from b to a!

✂️ Min-Cut Theorem (Max-Flow Min-Cut)

🎯 The Fundamental Theorem

The Max-Flow Min-Cut Theorem states that the maximum flow value is equal to the capacity of the minimum cut. This is the most important theorem in network flow.

Cut: Partition of vertices into S and T, with s ∈ S, t ∈ T
Cut Capacity: Sum of capacities of edges from S to T
Theorem: max_flow = min_cut_capacity
Applications: Image segmentation, network reliability

# Finding the Min-Cut
def min_cut_from_flow(graph, flow, s, t):
    n = len(graph)
    visited = [False] * n
    queue = deque([s])
    visited[s] = True
    
    # BFS on residual graph
    while queue:
        u = queue.popleft()
        for v in graph[u]:
            if not visited[v] and flow[u][v] < capacity[u][v]:
                visited[v] = True
                queue.append(v)
    
    # S = visited nodes, T = unvisited nodes
    min_cut_edges = []
    for i in range(n):
        if visited[i]:
            for j in graph[i]:
                if not visited[j] and capacity[i][j] > 0:
                    min_cut_edges.append((i, j, capacity[i][j]))
    
    return visited, min_cut_edges

# Example:
# Min-Cut capacity = Max Flow = 4
# S = {s, a, b}, T = {t}
# Cut edges: a->t(3), b->t(1) → Total = 4

⏱️ Time & Space Complexities

Algorithm	Time Complexity	Space Complexity	Notes
Ford-Fulkerson	O(E × f)	O(V + E)	f = max flow value
Edmonds-Karp	O(V × E²)	O(V + E)	Guaranteed polynomial
Dinic's	O(V² × E)	O(V + E)	Best in practice
Push-Relabel	O(V³)	O(V + E)	Good for dense graphs
Bipartite Matching	O(E × √V)	O(V + E)	Special case
Min-Cost Max-Flow	O(F × E log V)	O(V + E)	F = flow value

🌀 Flow Variations

Multi-Source Multi-Sink: Multiple sources and sinks (add super source/sink)
Vertex Capacities: Capacities on vertices (split vertices)
Lower Bounds: Minimum flow on edges (feasible circulation)
Min-Cost Max-Flow: Maximize flow with minimum cost
Max-Flow with Demands: Each node has demand or supply
Circulation Problem: Flow with no source/sink
Maximum Closure: Finding maximum weight closure

🔗 Bipartite Matching

🎯 Maximum Matching in Bipartite Graphs

Maximum bipartite matching is a classic application of max-flow. Create a source connected to left vertices and right vertices connected to sink.

Reduction: s -> L -> R -> t with capacity 1
Time: O(E × √V) (Hopcroft-Karp) or O(V × E²) (Edmonds-Karp)
Applications: Job assignment, room allocation, etc.

# Bipartite Matching via Max-Flow
def bipartite_matching(left, right, edges):
    # left: list of left vertices
    # right: list of right vertices
    # edges: list of (l, r) pairs
    
    n = len(left) + len(right) + 2
    s = len(left) + len(right)
    t = s + 1
    
    dinic = Dinic(n)
    
    # Connect source to left vertices
    for i in range(len(left)):
        dinic.add_edge(s, i, 1)
    
    # Connect right vertices to sink
    for j in range(len(right)):
        dinic.add_edge(len(left) + j, t, 1)
    
    # Connect left to right
    for l, r in edges:
        dinic.add_edge(l, len(left) + r, 1)
    
    return dinic.max_flow(s, t)

# Example:
# left = ['A', 'B', 'C']
# right = ['X', 'Y', 'Z']
# edges = [(0,0), (0,1), (1,0), (1,2), (2,1)]
# Max matching = 3 (A-X, B-Z, C-Y)

📈 Push-Relabel Algorithm

🎯 Preflow-Push Method

The push-relabel algorithm uses a different approach: it maintains a preflow and pushes excess flow from higher-height nodes to lower-height nodes.

Approach: Push excess flow, relabel heights
Time: O(V³) worst-case, O(V² × √E) in practice
Space: O(V + E)
Use Case: Very dense graphs, parallel implementation

# Push-Relabel Algorithm (Simplified)
def push_relabel(graph, capacity, s, t):
    n = len(graph)
    flow = [[0] * n for _ in range(n)]
    excess = [0] * n
    height = [0] * n
    height[s] = n
    
    # Initialize preflow
    for v in graph[s]:
        flow[s][v] = capacity[s][v]
        flow[v][s] = -capacity[s][v]
        excess[v] = capacity[s][v]
        excess[s] -= capacity[s][v]
    
    def push(u, v):
        send = min(excess[u], capacity[u][v] - flow[u][v])
        if send > 0:
            flow[u][v] += send
            flow[v][u] -= send
            excess[u] -= send
            excess[v] += send
            return True
        return False
    
    def relabel(u):
        min_height = float('inf')
        for v in graph[u]:
            if capacity[u][v] - flow[u][v] > 0:
                min_height = min(min_height, height[v])
        if min_height < float('inf'):
            height[u] = min_height + 1
            return True
        return False
    
    # Main loop
    while True:
        active = [i for i in range(n) if i != s and i != t and excess[i] > 0]
        if not active:
            break
        
        for u in active:
            pushed = False
            for v in graph[u]:
                if capacity[u][v] - flow[u][v] > 0 and height[u] == height[v] + 1:
                    if push(u, v):
                        pushed = True
                        break
            
            if not pushed:
                relabel(u)
    
    return sum(flow[s][i] for i in range(n))

💰 Min-Cost Max-Flow

🎯 Cheapest Way to Send Flow

Min-cost max-flow finds the maximum flow with the minimum total cost. Each edge has both capacity and cost per unit of flow.

Approach: Successive shortest path (with potentials)
Time: O(F × E log V) where F is flow value
Applications: Transportation, assignment, logistics

# Min-Cost Max-Flow (Successive Shortest Path)
def min_cost_max_flow(graph, capacity, cost, s, t, max_flow):
    n = len(graph)
    flow = [[0] * n for _ in range(n)]
    total_cost = 0
    total_flow = 0
    
    while total_flow < max_flow:
        # Dijkstra with potentials
        dist = [float('inf')] * n
        parent = [-1] * n
        dist[s] = 0
        
        # Use heap for Dijkstra
        import heapq
        heap = [(0, s)]
        
        while heap:
            d, u = heapq.heappop(heap)
            if d > dist[u]:
                continue
            
            for v in graph[u]:
                if capacity[u][v] - flow[u][v] > 0:
                    new_dist = dist[u] + cost[u][v]
                    if new_dist < dist[v]:
                        dist[v] = new_dist
                        parent[v] = u
                        heapq.heappush(heap, (new_dist, v))
        
        if dist[t] == float('inf'):
            break
        
        # Find bottleneck
        bottleneck = max_flow - total_flow
        v = t
        while v != s:
            u = parent[v]
            bottleneck = min(bottleneck, capacity[u][v] - flow[u][v])
            v = u
        
        # Update flow and cost
        v = t
        while v != s:
            u = parent[v]
            flow[u][v] += bottleneck
            flow[v][u] -= bottleneck
            total_cost += bottleneck * cost[u][v]
            v = u
        
        total_flow += bottleneck
    
    return total_flow, total_cost

🌍 Real-World Applications

Network Routing: Traffic optimization, packet routing
Transportation: Logistics, supply chain optimization
Image Segmentation: Graph cuts for computer vision
Job Assignment: Matching workers to tasks
Sports Scheduling: Fair scheduling, tournament design
Data Science: Maximum closure, feature selection
Telecommunications: Bandwidth allocation
Resource Allocation: Optimal resource distribution

🧠 Advanced Flow Concepts

Circulation with Demands: Feasible flow with node demands
Minimum Cut with Vertex Weights: Vertex capacities in cuts
Project Selection: Maximum weight closure
Image Segmentation: Graph cut segmentation
Multi-Commodity Flow: Multiple types of flow
Dynamic Flows: Flow over time
Maximum Closure: Finding maximum weight closed set

📝 Interview Patterns & Problems

🎯 Key Interview Questions

Classic: "Find maximum flow in a given network"
Bipartite Matching: "Maximum pairs in a matching problem"
Min-Cut: "Find the minimum cut in a network"
Job Assignment: "Assign jobs to workers with constraints"
Circuit Design: "Maximum flow in a circuit"
Transportation: "Maximum flow in a transportation network"
Image Segmentation: "Use max-flow for image segmentation"

# Interview Problem: Maximum Bipartite Matching
def max_bipartite_matching(n, m, edges):
    # n = left vertices, m = right vertices
    # edges = list of (l, r) pairs
    # Create flow network and solve max flow
    # This is a classic interview problem
    
    # Use Dinic's algorithm
    total = n + m + 2
    s = n + m
    t = s + 1
    dinic = Dinic(total)
    
    for i in range(n):
        dinic.add_edge(s, i, 1)
    
    for j in range(m):
        dinic.add_edge(n + j, t, 1)
    
    for l, r in edges:
        dinic.add_edge(l, n + r, 1)
    
    return dinic.max_flow(s, t)

# Interview Problem: Maximum Flow with Vertex Capacities
def max_flow_vertex_capacities(graph, capacities, s, t):
    # Split each vertex into in and out vertices
    # Add edge from in to out with vertex capacity
    # Solve max flow on the transformed graph
    pass

# Interview Problem: Min-Cost Flow
def min_cost_transportation(supply, demand, costs):
    # supply: supply at each source
    # demand: demand at each sink
    # costs: cost matrix between sources and sinks
    # Solve min-cost flow
    pass