Network Flow

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): """Find if there's a path from source to sink""" visited = [False] * self.V queue = [source] visited[source] = True while queue: u = queue.pop(0) for v in range(self.V): if not visited[v] and self.graph[u][v] > 0: queue.append(v) visited[v] = True parent[v] = u if v == sink: return True return False def ford_fulkerson(self, source, sink): """Find maximum flow from source to sink""" parent = [-1] * self.V max_flow = 0 while self.bfs(source, sink, parent): # Find minimum capacity along the path path_flow = float("inf") s = sink while s != source: path_flow = min(path_flow, self.graph[parent[s]][s]) s = parent[s] # Update residual capacities v = sink while v != source: u = parent[v] self.graph[u][v] -= path_flow self.graph[v][u] += path_flow v = parent[v] max_flow += path_flow return max_flow # Example usage g = Graph(6) g.add_edge(0, 1, 16) # s -> a g.add_edge(0, 2, 13) # s -> b g.add_edge(1, 2, 10) # a -> b g.add_edge(1, 3, 12) # a -> c g.add_edge(2, 1, 4) # b -> a g.add_edge(2, 4, 14) # b -> d g.add_edge(3, 2, 9) # c -> b g.add_edge(3, 5, 20) # c -> t g.add_edge(4, 3, 7) # d -> c g.add_edge(4, 5, 4) # d -> t print(f"Maximum flow: {g.ford_fulkerson(0, 5)}") # Output: Maximum flow: 23

def max_bipartite_matching(graph, m, n): """ Maximum matching in bipartite graph m: size of left set, n: size of right set """ # Create flow network V = m + n + 2 # +2 for source and sink flow_graph = [[0] * V for _ in range(V)] # Connect source to left vertices for i in range(1, m + 1): flow_graph[0][i] = 1 # Connect edges in bipartite graph for u in range(m): for v in graph[u]: flow_graph[u + 1][m + 1 + v] = 1 # Connect right vertices to sink for i in range(m + 1, m + n + 1): flow_graph[i][V - 1] = 1 # Run max flow g = Graph(V) g.graph = flow_graph return g.ford_fulkerson(0, V - 1) # Example: Job assignment job_graph = [ [0, 1], # Worker 0 can do jobs 0, 1 [1, 2], # Worker 1 can do jobs 1, 2 [0, 2], # Worker 2 can do jobs 0, 2 ] print(f"Maximum matching: {max_bipartite_matching(job_graph, 3, 3)}")

def find_min_cut(capacity, source, sink): """Find minimum s-t cut""" n = len(capacity) residual = [row[:] for row in capacity] # Run max flow g = Graph(n) g.graph = residual max_flow = g.ford_fulkerson(source, sink) # Find reachable vertices from source visited = [False] * n queue = [source] visited[source] = True while queue: u = queue.pop(0) for v in range(n): if not visited[v] and g.graph[u][v] > 0: visited[v] = True queue.append(v) # Find cut edges cut_edges = [] for u in range(n): for v in range(n): if visited[u] and not visited[v] and capacity[u][v] > 0: cut_edges.append((u, v)) return max_flow, cut_edges

from collections import deque class Dinic: def __init__(self, n): self.n = n self.graph = [[] for _ in range(n)] self.level = [-1] * n class Edge: def __init__(self, to, rev, cap): self.to = to self.rev = rev self.cap = cap def add_edge(self, u, v, cap): """Add edge with capacity""" self.graph[u].append(self.Edge(v, len(self.graph[v]), cap)) self.graph[v].append(self.Edge(u, len(self.graph[u]) - 1, 0)) def bfs(self, source, sink): """Build level graph""" self.level = [-1] * self.n self.level[source] = 0 queue = deque([source]) while queue: v = queue.popleft() for edge in self.graph[v]: if self.level[edge.to] < 0 and edge.cap > 0: self.level[edge.to] = self.level[v] + 1 queue.append(edge.to) return self.level[sink] >= 0 def dfs(self, v, sink, flow): """Find blocking flow""" if v == sink: return flow for edge in self.graph[v]: if (self.level[v] < self.level[edge.to] and edge.cap > 0): d = self.dfs(edge.to, sink, min(flow, edge.cap)) if d > 0: edge.cap -= d self.graph[edge.to][edge.rev].cap += d return d return 0 def max_flow(self, source, sink): """Dinic's algorithm - O(V²E)""" flow = 0 while self.bfs(source, sink): while True: f = self.dfs(source, sink, float('inf')) if f == 0: break flow += f return flow