DSA Edmonds-Karp Algorithm

from collections import deque

def max_flow(capacity, source, sink, strategy="bfs"):
    if source not in capacity or sink not in capacity or source == sink:
        raise ValueError("Distinct declared source and sink required")
    if strategy not in ("bfs", "dfs"):
        raise ValueError("Unknown path strategy")
    residual = {vertex: {} for vertex in capacity}
    for vertex, neighbors in capacity.items():
        for target, amount in neighbors.items():
            if target not in capacity or type(amount) is not int or amount < 0:
                raise ValueError("Nonnegative integer capacities required")
            residual[vertex][target] = residual[vertex].get(target, 0) + amount
            residual[target].setdefault(vertex, 0)
    value = 0
    while True:
        parent = {source: None}
        pending = deque([source])
        while pending and sink not in parent:
            vertex = pending.popleft() if strategy == "bfs" else pending.pop()
            for target, available in residual[vertex].items():
                if available > 0 and target not in parent:
                    parent[target] = vertex
                    pending.append(target)
                    if target == sink:
                        break
        if sink not in parent:
            return value, residual
        amount = None
        target = sink
        while target != source:
            previous = parent[target]
            available = residual[previous][target]
            amount = available if amount is None else min(amount, available)
            target = previous
        target = sink
        while target != source:
            previous = parent[target]
            residual[previous][target] -= amount
            residual[target][previous] += amount
            target = previous
        value += amount

capacity = {"tank": {"oak": 3, "pond": 2}, "oak": {"pond": 1, "beds": 2}, "pond": {"beds": 3}, "beds": {}}
value, residual = max_flow(capacity, "tank", "beds", strategy="bfs")
reached, pending = {"tank"}, ["tank"]
while pending:
    vertex = pending.pop()
    for target, amount in residual[vertex].items():
        if amount > 0 and target not in reached:
            reached.add(target)
            pending.append(target)
cut = sum(amount for vertex in reached for target, amount in capacity[vertex].items() if target not in reached)
print(value, cut)
print("beds" in reached)