Network Flow & Resource Allocation

Having mastered graph basics and pathfinding, we now turn to a specialized area of graph theory: Network Flow. This powerful framework allows us to model systems where “stuff” (like data, water, goods, or tasks) flows through a network with limited capacities. Understanding network flow algorithms is crucial for optimizing resource allocation, transportation, and communication systems.

🌊 What is a Flow Network?

A Flow Network (or Capacity Network) is a directed graph where each edge has a capacity and represents a specific amount of “flow” that can pass through it.

Key Terminology:

• Graph G = (V, E): A directed graph.
• Source (s): A special vertex from which flow originates. It has no incoming edges (or its capacity is infinite).
• Sink (t): A special vertex where flow terminates. It has no outgoing edges (or its capacity is infinite).
• Capacity (c(u, v)): The maximum amount of flow that can pass through an edge (u, v). c(u, v) ≥ 0.
• Flow (f(u, v)): The actual amount of flow passing through an edge (u, v).
  • 0 ≤ f(u, v) ≤ c(u, v) (Flow cannot exceed capacity).
  • f(u, v) = -f(v, u) (Flow from u to v is negative of flow from v to u).
• Conservation of Flow: For every vertex u (except source s and sink t), the total incoming flow must equal the total outgoing flow.
  • Σ f(v, u) = Σ f(u, w) for all u ≠ s, t.
• Residual Capacity: The remaining capacity on an edge. residual_c(u, v) = c(u, v) - f(u, v).
• Residual Graph: A graph representing the residual capacities of edges. It also includes “backward” edges for reducing existing flow.
• Augmenting Path: A path from source s to sink t in the residual graph along which we can push additional flow.

The Goal: Find the Maximum Flow (Max-Flow) from the source s to the sink t in the network.

Analogy: A water pipe system. The source is a reservoir, the sink is a city. Each pipe has a maximum capacity (diameter). We want to find the maximum amount of water we can deliver from the reservoir to the city without overflowing any pipes.

💡 Max-Flow Min-Cut Theorem

This is a fundamental theorem in network flow theory that provides a powerful duality:

Max-Flow Min-Cut Theorem: The maximum amount of flow that can pass from the source to the sink in a flow network is equal to the minimum capacity of a cut separating the source and the sink.

• Cut (s-t Cut): A partition of the vertices V into two sets, S and T, such that s ∈ S and t ∈ T.
• Capacity of a Cut: The sum of capacities of all edges that go from a vertex in S to a vertex in T. (Edges from T to S are ignored for cut capacity).

Why it matters: This theorem provides a theoretical upper bound for the max flow and links the problem of finding max flow to finding a min cut. It’s used in many proofs and can transform certain max-flow problems into min-cut problems, which are sometimes easier to solve.

Analogy: In our water pipe system, a “cut” is like selecting a set of pipes (edges) that, if completely blocked, would disconnect the reservoir from the city. The “capacity of the cut” is the total water these pipes could carry. The theorem says the maximum water you can send from the reservoir to the city is equal to the minimum capacity of any such “bottleneck” set of pipes.

algorithms: Edmonds-Karp

The Ford-Fulkerson algorithm is a general framework for solving the maximum flow problem. The Edmonds-Karp algorithm is a specific implementation of Ford-Fulkerson that uses Breadth-First Search (BFS) to find augmenting paths in the residual graph.

How Edmonds-Karp Works:

1. Initialize flow: Set f(u, v) = 0 for all edges.
2. Repeat while an augmenting path from s to t exists in the residual graph: a. Find Augmenting Path: Use BFS on the residual graph to find a path from s to t. BFS is used because it finds the shortest augmenting path (in terms of number of edges), which is key to Edmonds-Karp’s complexity. b. Calculate Path Flow: Find the bottleneck capacity of this path – the minimum residual capacity of any edge along the path. This is the maximum flow we can push through this specific path. c. Augment Flow: For every edge (u, v) on the augmenting path:
   • Increase f(u, v) by the path flow.
   • Decrease f(v, u) (the flow in the backward edge in the residual graph) by the path flow. This backward edge allows us to “undo” or reroute flow if a better path is found.
3. When no more augmenting paths can be found, the total flow achieved is the maximum flow.

        
          
from collections import deque

def bfs_edmonds_karp(graph, source, sink, parent_map):
  visited = {node: False for node in graph}
  queue = deque()

  queue.append(source)
  visited[source] = True
  parent_map[source] = -1 # Source has no parent

  while queue:
      u = queue.popleft()

      for v, capacity in graph[u].items():
          # Only consider edges with remaining capacity in residual graph
          if not visited[v] and capacity > 0:
              visited[v] = True
              parent_map[v] = u # Store path
              queue.append(v)
              if v == sink: # Found a path to sink
                  return True
  return False # No path found

def edmonds_karp(graph, source, sink):
  # Initialize flow to 0 for all edges
  # residual_graph will store current residual capacities
  residual_graph = {u: {v: graph[u].get(v, 0) for v in graph} for u in graph}

  # Add reverse edges with 0 initial capacity for undirected component of residual graph
  for u in graph:
      for v in graph[u]:
          if v not in residual_graph:
              residual_graph[v] = {}
          if u not in residual_graph[v]:
              residual_graph[v][u] = 0 # Backward edge capacity initially 0

  max_flow = 0
  parent_map = {node: None for node in graph} # To reconstruct path

  while bfs_edmonds_karp(residual_graph, source, sink, parent_map):
      # Find bottleneck capacity of the augmenting path
      path_flow = float('infinity')
      s = sink
      while s != source:
          p = parent_map[s]
          path_flow = min(path_flow, residual_graph[p][s])
          s = p
      
      max_flow += path_flow

      # Update residual capacities along the path
      s = sink
      while s != source:
          p = parent_map[s]
          residual_graph[p][s] -= path_flow      # Forward edge
          residual_graph[s][p] += path_flow      # Backward edge
          s = p
          
  return max_flow

# Main for demonstration
# Graph: {u: {v: capacity}}
# S --(10)--> A --(5)--> D --(10)--> T
# |           |          ^
# (10)        (15)        |
# |           |          |
# V           V          |
# B --(9)--> C --(8)--> E --(10)--> T
# |         / |          ^
# (4)      /  (4)        |
# |       /    |         |
# V      /     V         |
#   <-- G --(2)--> F --(10)--> T
# This is a simplified representation for demonstration.
# In a true residual graph, capacities on reverse edges are dynamic.

example_graph = {
  'S': {'A': 10, 'B': 10},
  'A': {'C': 15, 'D': 5},
  'B': {'C': 9},
  'C': {'D': 15, 'E': 4},
  'D': {'T': 10},
  'E': {'T': 10},
  'T': {} # Sink has no outgoing edges
}

# Add 0 capacity reverse edges to residual_graph initially for complete representation
for u in list(example_graph.keys()):
  if u not in example_graph:
      example_graph[u] = {}
  for v in list(example_graph[u].keys()):
      if v not in example_graph:
          example_graph[v] = {}
      if u not in example_graph[v]:
          example_graph[v][u] = 0


source_node = 'S'
sink_node = 'T'
max_network_flow = edmonds_karp(example_graph, source_node, sink_node)

print(f"Max flow from {source_node} to {sink_node}: {max_network_flow}")
# Expected max flow for a common textbook example similar to this is 19.
# The exact flow depends on the full graph definition, including implicit 0-capacity reverse edges.

        
      

Complexity (Edmonds-Karp Algorithm):

• Time Complexity: O(V * E^2) - In each iteration, BFS takes O(E) time. The number of augmenting paths found can be at most O(V * E) (for integer capacities), leading to V iterations (one for each unique vertex). Thus, O(V * E * E) = O(V * E^2). For unit capacities, it’s O(E^2).
• Space Complexity: O(V + E) for storing the graph and residual graph, plus O(V) for BFS queue and parent map.

Interesting Note: The Edmonds-Karp algorithm is a relatively simple and easy-to-understand implementation of the Ford-Fulkerson method. While it’s polynomial time, faster max-flow algorithms exist for very large networks (e.g., Dinic’s algorithm, Push-Relabel algorithm) that have better worst-case time complexities.

🏗️ Resource Allocation with Network Flow

Network flow provides a powerful framework for modeling and solving a wide range of resource allocation and optimization problems. By mapping real-world entities to nodes, and capacities/demands to edges, complex challenges can be transformed into a maximum flow problem.

Common Applications:

• Supply Chain & Logistics:
  • Transportation: Maximize goods shipped from factories (sources) to customers (sinks) through a network of distribution centers (intermediate nodes) with limited transportation links (edges) and warehouse capacities.
  • Traffic Management: Model roads as edges with capacity (number of cars per hour) to find maximum traffic flow.
• Telecommunication Networks:
  • Data Routing: Maximize data throughput from a server to clients, respecting bandwidth limitations on network links.
  • Load Balancing: Distribute network traffic effectively.
• Project Management:
  • Project Scheduling: Model tasks as nodes, dependencies as edges, and task durations as capacities/costs.
  • Personnel Assignment: Assign workers (source) to tasks (sink) based on skills and availability to maximize efficiency or cover all tasks.
• Bipartite Matching: Find the maximum number of pairings in a bipartite graph (e.g., job applicants to jobs, students to projects) – this can be modeled as a max-flow problem.

Analogy: A company has several factories (sources) that produce different components, and several assembly plants (sinks) that need these components. Each road between locations has a certain truck capacity. The goal is to maximize the number of components moved from factories to assembly plants while respecting road capacities and minimizing bottlenecks. This is a classic maximum flow problem.

Interesting Note: Many seemingly disparate problems can be reduced to a maximum flow problem, demonstrating the versatility of this algorithmic technique. This ability to “reduce” a problem to a known algorithm is a fundamental concept in algorithm design and computational complexity theory. This makes network flow an incredibly valuable tool in a wide range of fields.