Given a directed capacity graph, a source vertex, and a sink vertex, find the maximum flow from the source to the sink using breadth-first search to select augmenting paths.
Store capacities in a residual adjacency matrix. Run breadth-first search from the source over edges with positive residual capacity and record each vertex's parent. If the sink is reachable, find the bottleneck capacity along the parent path, update forward and reverse residual capacities, and add the bottleneck to the total flow. Stop when the sink is unreachable.
class Graph:
def __init__(self, size):
self.adj_matrix = [[0] * size for _ in range(size)]
self.size = size
self.vertex_data = [''] * size
def add_edge(self, u, v, c):
self.adj_matrix[u][v] = c
def add_vertex_data(self, vertex, data):
if 0 <= vertex < self.size:
self.vertex_data[vertex] = data
def bfs(self, s, t, parent):
visited = [False] * self.size
queue = [] # Using list as a queue
queue.append(s)
visited[s] = True
while queue:
u = queue.pop(0) # Pop from the start of the list
for ind, val in enumerate(self.adj_matrix[u]):
if not visited[ind] and val > 0:
queue.append(ind)
visited[ind] = True
parent[ind] = u
return visited[t]
def edmonds_karp(self, source, sink):
parent = [-1] * self.size
max_flow = 0
while self.bfs(source, sink, parent):
path_flow = float("Inf")
s = sink
while(s != source):
path_flow = min(path_flow, self.adj_matrix[parent[s]][s])
s = parent[s]
max_flow += path_flow
v = sink
while(v != source):
u = parent[v]
self.adj_matrix[u][v] -= path_flow
self.adj_matrix[v][u] += path_flow
v = parent[v]
path = []
v = sink
while(v != source):
path.append(v)
v = parent[v]
path.append(source)
path.reverse()
path_names = [self.vertex_data[node] for node in path]
print("Path:", " -> ".join(path_names), ", Flow:", path_flow)
return max_flow
# Example usage:
g = Graph(6)
vertex_names = ['s', 'v1', 'v2', 'v3', 'v4', 't']
for i, name in enumerate(vertex_names):
g.add_vertex_data(i, name)
g.add_edge(0, 1, 3) # s -> v1, cap: 3
g.add_edge(0, 2, 7) # s -> v2, cap: 7
g.add_edge(1, 3, 3) # v1 -> v3, cap: 3
g.add_edge(1, 4, 4) # v1 -> v4, cap: 4
g.add_edge(2, 1, 5) # v2 -> v1, cap: 5
g.add_edge(2, 4, 3) # v2 -> v4, cap: 3
g.add_edge(3, 4, 3) # v3 -> v4, cap: 3
g.add_edge(3, 5, 2) # v3 -> t, cap: 2
g.add_edge(4, 5, 6) # v4 -> t, cap: 6
source = 0; sink = 5
print("The maximum possible flow is %d " % g.edmonds_karp(source, sink))
#Python
//=include edmonds-karp.js