DSA Maximum Flow

Welcome to TheCodingCollege.com! In this tutorial, we dive into the Maximum Flow problem, a fundamental concept in graph theory and an essential topic in Data Structures and Algorithms (DSA). Maximum Flow has applications in networking, transportation, and optimization problems, making it a vital tool for problem-solving.

What is Maximum Flow?

The Maximum Flow problem involves finding the maximum amount of flow that can pass from a source node (ss) to a sink node (tt) in a flow network without exceeding the capacity of edges.

Key Definitions

  1. Flow Network: A directed graph where each edge has a capacity that defines the maximum flow allowed through it.
  2. Source (s): The starting node of the flow.
  3. Sink (t): The destination node for the flow.
  4. Flow: The actual amount of flow sent along an edge, which must satisfy:
    • 0≤flow≤capacity0 \leq \text{flow} \leq \text{capacity}.
    • The total incoming flow equals the total outgoing flow for all nodes except ss and tt.
  5. Residual Graph: Represents the remaining capacity of edges after some flow has been sent.

Applications of Maximum Flow

  • Network Routing: Efficiently managing data transmission in computer networks.
  • Transportation: Optimizing traffic flow in road networks.
  • Bipartite Matching: Solving pairing problems in resource allocation.
  • Project Planning: Balancing workloads in supply chains.

Algorithms to Solve Maximum Flow

1. Ford-Fulkerson Algorithm

  • Uses a greedy approach with augmenting paths.
  • Time Complexity: O(E×max_flow)O(E \times \text{max\_flow}), where EE is the number of edges.
  • Handles capacities in integers efficiently.

2. Edmonds-Karp Algorithm

  • An implementation of the Ford-Fulkerson Algorithm using BFS.
  • Time Complexity: O(V×E2)O(V \times E^2), where VV is the number of vertices.

3. Push-Relabel Algorithm

  • Works by maintaining a preflow and gradually converting it into a valid flow.
  • Time Complexity: O(V2×E)O(V^2 \times E).

Ford-Fulkerson Algorithm Implementation

Python Code Implementation

from collections import deque

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[0] * vertices for _ in range(vertices)]

    def add_edge(self, u, v, capacity):
        self.graph[u][v] = capacity

    def bfs(self, source, sink, parent):
        visited = [False] * self.V
        queue = deque([source])
        visited[source] = True

        while queue:
            u = queue.popleft()

            for v, capacity in enumerate(self.graph[u]):
                if not visited[v] and capacity > 0:
                    queue.append(v)
                    visited[v] = True
                    parent[v] = u
                    if v == sink:
                        return True
        return False

    def ford_fulkerson(self, source, sink):
        parent = [-1] * self.V
        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
g = Graph(6)
g.add_edge(0, 1, 16)
g.add_edge(0, 2, 13)
g.add_edge(1, 2, 10)
g.add_edge(1, 3, 12)
g.add_edge(2, 1, 4)
g.add_edge(2, 4, 14)
g.add_edge(3, 2, 9)
g.add_edge(3, 5, 20)
g.add_edge(4, 3, 7)
g.add_edge(4, 5, 4)

source, sink = 0, 5
print("The Maximum Flow is:", g.ford_fulkerson(source, sink))

Dry Run Example

Graph Representation

  • Vertices: 0,1,2,3,4,50, 1, 2, 3, 4, 5
  • Edges:
    • (0→1,16), (0→2,13)
    • (1→3,12), (2→4,14)
    • (4→5,4) etc.

Execution

  1. Find augmenting path using BFS: 0→1→3→5.
  2. Update flow in the residual graph.
  3. Repeat until no augmenting path exists.

Result: Maximum Flow = 2323.

Time Complexity

  1. Ford-Fulkerson: O(E×max_flow)
  2. Edmonds-Karp: O(V×E2).

Advantages

  1. Efficient for small and medium-sized graphs.
  2. Flexible for various flow problems.

Disadvantages

  1. High complexity for dense graphs.
  2. May not handle fractional capacities (in the naive Ford-Fulkerson).

Real-World Applications

  • Streaming Platforms: Bandwidth optimization.
  • Logistics: Optimizing supply chains.
  • Air Traffic: Balancing flight routes.

Conclusion

The Maximum Flow problem and its solutions, like Ford-Fulkerson and Edmonds-Karp algorithms, are vital in solving real-world optimization problems. Mastering these techniques equips you with powerful tools for network optimization.

Leave a Comment