ম্যাক্স ফ্লো — ফোর্ড-ফুলকারসন ও ম্যাক্স-ফ্লো মিন-কাট

from collections import deque, defaultdict

def edmonds_karp(capacity, source, sink):
    # residual[u][v] = u থেকে v-তে বর্তমানে আরও কতটা ফ্লো পাঠানো সম্ভব
    residual = defaultdict(lambda: defaultdict(int))
    for (u, v), c in capacity.items():
        residual[u][v] += c
        residual[v][u] += 0  # রিভার্স রেসিডুয়াল এজ অস্তিত্বে আনা (শুরুতে ০)

    def bfs_find_path():
        parent = {source: None}
        queue = deque([source])
        while queue:
            u = queue.popleft()
            if u == sink:
                break
            for v, cap in residual[u].items():
                if cap > 0 and v not in parent:
                    parent[v] = u
                    queue.append(v)
        if sink not in parent:
            return None
        path = []
        node = sink
        while node is not None:
            path.append(node)
            node = parent[node]
        path.reverse()
        return path

    max_flow = 0
    while True:
        path = bfs_find_path()
        if path is None:
            break
        bottleneck = min(residual[path[i]][path[i + 1]] for i in range(len(path) - 1))
        for i in range(len(path) - 1):
            u, v = path[i], path[i + 1]
            residual[u][v] -= bottleneck
            residual[v][u] += bottleneck
        max_flow += bottleneck

    return max_flow, residual

def reachable_in_residual(residual, source):
    visited = {source}
    queue = deque([source])
    while queue:
        u = queue.popleft()
        for v, cap in residual[u].items():
            if cap > 0 and v not in visited:
                visited.add(v)
                queue.append(v)
    return visited

# ক্লাসিক টেক্সটবুক উদাহরণ: s=0, v1=1, v2=2, v3=3, v4=4, t=5
capacity = {
    (0, 1): 16, (0, 2): 13,
    (1, 3): 12,
    (2, 1): 4, (2, 4): 14,
    (3, 2): 9, (3, 5): 20,
    (4, 3): 7, (4, 5): 4,
}
source, sink = 0, 5

max_flow, final_residual = edmonds_karp(capacity, source, sink)
print(f"এডমন্ডস-কার্প দিয়ে গণনা করা ম্যাক্স ফ্লো: {max_flow}")

# ফাইনাল রেসিডুয়াল গ্রাফ থেকে মিন কাট বের করা
reachable = reachable_in_residual(final_residual, source)
print(f"রেসিডুয়াল গ্রাফে s থেকে রিচেবল সেট S: {sorted(reachable)}")

cut_edges = []
cut_capacity = 0
for (u, v), c in capacity.items():
    if u in reachable and v not in reachable:
        cut_edges.append((u, v, c))
        cut_capacity += c

print(f"মিন কাট অতিক্রমকারী এজসমূহ (S থেকে T): {cut_edges}")
print(f"মিন কাটের মোট ক্যাপাসিটি: {cut_capacity}")
print(f"ম্যাক্স ফ্লো == মিন কাট ক্যাপাসিটি? {max_flow == cut_capacity}")

assert max_flow == cut_capacity, "ম্যাক্স-ফ্লো মিন-কাট থিওরেম লঙ্ঘিত -- ইমপ্লিমেন্টেশনে বাগ আছে!"
print("\nম্যাক্স-ফ্লো মিন-কাট থিওরেম কম্পিউটেশনালি যাচাই সম্পন্ন।")