Applications of flow: matching, circulations and project selection

from collections import deque
def max_flow(cap, s, t):
    """cap: dict {(u, v): capacity}. Returns (value, flow dict, set reachable from s at the end)."""
    r, adj = {}, {}
    for (u, v), c in cap.items():
        r[(u, v)] = r.get((u, v), 0) + c; r.setdefault((v, u), 0)
        adj.setdefault(u, set()).add(v); adj.setdefault(v, set()).add(u)
    value = 0
    while True:
        par = {s: None}; q = deque([s])
        while q and t not in par:
            u = q.popleft()
            for v in sorted(adj[u], key=str):
                if r[(u, v)] > 0 and v not in par: par[v] = u; q.append(v)
        if t not in par:
            return value, {e: cap[e] - r[e] for e in cap}, set(par)
        path, v = [], t
        while par[v] is not None: path.append((par[v], v)); v = par[v]
        b = min(r[e] for e in path)
        for u, v in path: r[(u, v)] -= b; r[(v, u)] += b
        value += b

# Drivers and the vans they are licensed to drive. Find the largest assignment.
licensed = {"Amir": ["V1", "V2"], "Bea": ["V1"], "Chen": ["V2", "V3", "V4"],
            "Dana": ["V1", "V2"], "Eli": ["V4", "V5"], "Fern": ["V3"]}
cap = {}
for d, vans in licensed.items():
    cap[("s", d)] = 1
    for v in vans: cap[(d, v)] = 1
for v in {v for vs in licensed.values() for v in vs}: cap[(v, "t")] = 1
value, flow, S = max_flow(cap, "s", "t")
print("drivers assigned:", value)
for (a, b), f in sorted(flow.items()):
    if f and a in licensed and b != "t": print("  ", a, "->", b)
# Konig: a minimum vertex cover = drivers NOT reachable from s, plus vans that ARE reachable.
cover = [d for d in licensed if d not in S] + sorted(v for v in S if v.startswith("V"))
print("minimum vertex cover:", cover, " size", len(cover))
assert all(d in cover or v in cover for d, vs in licensed.items() for v in vs)

drivers assigned: 5
   Amir -> V1
   Chen -> V4
   Dana -> V2
   Eli -> V5
   Fern -> V3
minimum vertex cover: ['Chen', 'Eli', 'Fern', 'V1', 'V2']  size 5

from collections import deque
def max_flow(cap, s, t):
    """cap: dict {(u, v): capacity}. Returns (value, flow dict, set reachable from s at the end)."""
    r, adj = {}, {}
    for (u, v), c in cap.items():
        r[(u, v)] = r.get((u, v), 0) + c; r.setdefault((v, u), 0)
        adj.setdefault(u, set()).add(v); adj.setdefault(v, set()).add(u)
    value = 0
    while True:
        par = {s: None}; q = deque([s])
        while q and t not in par:
            u = q.popleft()
            for v in sorted(adj[u], key=str):
                if r[(u, v)] > 0 and v not in par: par[v] = u; q.append(v)
        if t not in par:
            return value, {e: cap[e] - r[e] for e in cap}, set(par)
        path, v = [], t
        while par[v] is not None: path.append((par[v], v)); v = par[v]
        b = min(r[e] for e in path)
        for u, v in path: r[(u, v)] -= b; r[(v, u)] += b
        value += b

# How many edge-disjoint routes lead from the depot to the hub? (Menger: = minimum edge cut.)
roads = [("depot", "a"), ("depot", "b"), ("depot", "c"), ("a", "d"), ("b", "d"), ("b", "e"),
         ("c", "e"), ("d", "hub"), ("e", "hub"), ("a", "b"), ("e", "d"), ("c", "hub")]
cap = {e: 1 for e in roads}
value, flow, S = max_flow(cap, "depot", "hub")
print("edge-disjoint depot-hub routes:", value)
used = {e for e, f in flow.items() if f}
for _ in range(value):                       # peel off one path at a time from the flow
    p, x = ["depot"], "depot"
    while x != "hub":
        e = next(e for e in sorted(used) if e[0] == x); used.remove(e); x = e[1]; p.append(x)
    print("  ", " -> ".join(p))
print("closing these roads cuts the depot from the hub:",
      [e for e in roads if e[0] in S and e[1] not in S])

edge-disjoint depot-hub routes: 3
   depot -> a -> d -> hub
   depot -> b -> e -> hub
   depot -> c -> hub
closing these roads cuts the depot from the hub: [('depot', 'a'), ('depot', 'b'), ('depot', 'c')]

from collections import deque
def max_flow(cap, s, t):
    """cap: dict {(u, v): capacity}. Returns (value, flow dict, set reachable from s at the end)."""
    r, adj = {}, {}
    for (u, v), c in cap.items():
        r[(u, v)] = r.get((u, v), 0) + c; r.setdefault((v, u), 0)
        adj.setdefault(u, set()).add(v); adj.setdefault(v, set()).add(u)
    value = 0
    while True:
        par = {s: None}; q = deque([s])
        while q and t not in par:
            u = q.popleft()
            for v in sorted(adj[u], key=str):
                if r[(u, v)] > 0 and v not in par: par[v] = u; q.append(v)
        if t not in par:
            return value, {e: cap[e] - r[e] for e in cap}, set(par)
        path, v = [], t
        while par[v] is not None: path.append((par[v], v)); v = par[v]
        b = min(r[e] for e in path)
        for u, v in path: r[(u, v)] -= b; r[(v, u)] += b
        value += b

# Circulation with demands: warehouses supply pallets, stores need them, roads have capacities.
# Feasible iff the max flow from a super source to a super sink saturates all supplies.
supply = {"W1": 9, "W2": 6}                  # positive = supply
demand = {"S1": 5, "S2": 4, "S3": 6}
roads = {("W1", "S1"): 5, ("W1", "S2"): 3, ("W1", "X"): 4, ("W2", "X"): 6, ("X", "S2"): 3,
         ("X", "S3"): 6, ("W2", "S1"): 2}
def feasible(roads):
    cap = dict(roads)
    for w, a in supply.items(): cap[("src", w)] = a
    for s, b in demand.items(): cap[(s, "snk")] = b
    value, flow, _ = max_flow(cap, "src", "snk")
    return value, flow
need = sum(demand.values())
value, flow = feasible(roads)
print("total demand", need, " deliverable", value, " feasible:", value == need)
roads2 = dict(roads); roads2[("X", "S2")] = 0           # road works close one road
value2, _ = feasible(roads2)
print("after closing X->S2: deliverable", value2, " feasible:", value2 == need)

total demand 15  deliverable 15  feasible: True
after closing X->S2: deliverable 14  feasible: False

from collections import deque
def max_flow(cap, s, t):
    """cap: dict {(u, v): capacity}. Returns (value, flow dict, set reachable from s at the end)."""
    r, adj = {}, {}
    for (u, v), c in cap.items():
        r[(u, v)] = r.get((u, v), 0) + c; r.setdefault((v, u), 0)
        adj.setdefault(u, set()).add(v); adj.setdefault(v, set()).add(u)
    value = 0
    while True:
        par = {s: None}; q = deque([s])
        while q and t not in par:
            u = q.popleft()
            for v in sorted(adj[u], key=str):
                if r[(u, v)] > 0 and v not in par: par[v] = u; q.append(v)
        if t not in par:
            return value, {e: cap[e] - r[e] for e in cap}, set(par)
        path, v = [], t
        while par[v] is not None: path.append((par[v], v)); v = par[v]
        b = min(r[e] for e in path)
        for u, v in path: r[(u, v)] -= b; r[(v, u)] += b
        value += b

# Project selection as a minimum cut. Each project has a profit (positive) or cost (negative);
# some projects require others. Choose a prerequisite-closed set of maximum total profit.
profit = {"new route": 45, "night shift": 18, "app": 25, "warehouse": -50, "vans": -22, "hiring": -10}
needs = [("new route", "vans"), ("new route", "hiring"), ("night shift", "warehouse"),
         ("night shift", "hiring"), ("app", "warehouse")]
INF = 10 ** 9
cap = {}
for p, x in profit.items():
    if x > 0: cap[("s", p)] = x
    else: cap[(p, "t")] = -x
for a, b in needs: cap[(a, b)] = INF                 # choosing a forces choosing b
value, flow, S = max_flow(cap, "s", "t")
chosen = sorted(S - {"s"})
best = sum(x for x in profit.values() if x > 0) - value
print("chosen projects:", chosen)
print("net profit:", best, "= positive profits", sum(x for x in profit.values() if x > 0), "- min cut", value)
from itertools import combinations
names = list(profit)
brute = max(sum(profit[p] for p in A) for r in range(len(names) + 1) for A in combinations(names, r)
            if all(b in A for a, b in needs if a in A))
print("brute force over all closed sets:", brute)

chosen projects: ['hiring', 'new route', 'vans']
net profit: 13 = positive profits 88 - min cut 75
brute force over all closed sets: 13

from collections import deque
def max_flow(cap, s, t):
    """cap: dict {(u, v): capacity}. Returns (value, flow dict, set reachable from s at the end)."""
    r, adj = {}, {}
    for (u, v), c in cap.items():
        r[(u, v)] = r.get((u, v), 0) + c; r.setdefault((v, u), 0)
        adj.setdefault(u, set()).add(v); adj.setdefault(v, set()).add(u)
    value = 0
    while True:
        par = {s: None}; q = deque([s])
        while q and t not in par:
            u = q.popleft()
            for v in sorted(adj[u], key=str):
                if r[(u, v)] > 0 and v not in par: par[v] = u; q.append(v)
        if t not in par:
            return value, {e: cap[e] - r[e] for e in cap}, set(par)
        path, v = [], t
        while par[v] is not None: path.append((par[v], v)); v = par[v]
        b = min(r[e] for e in path)
        for u, v in path: r[(u, v)] -= b; r[(v, u)] += b
        value += b

# Is a team mathematically eliminated? Can team X still finish with at least as many wins
# as everyone else, if X wins all its remaining games and other results go its way?
wins = {"Otters": 83, "Hawks": 80, "Lynx": 80, "Moose": 77}
left = {("Otters", "Hawks"): 4, ("Otters", "Lynx"): 3, ("Otters", "Moose"): 3,
        ("Hawks", "Lynx"): 3, ("Hawks", "Moose"): 2, ("Lynx", "Moose"): 2}
def eliminated(x):
    best = wins[x] + sum(g for pair, g in left.items() if x in pair)
    if any(wins[y] > best for y in wins): return True
    cap = {}
    games = {pair: g for pair, g in left.items() if x not in pair and g}
    for (a, b), g in games.items():
        cap[("s", (a, b))] = g; cap[((a, b), a)] = g; cap[((a, b), b)] = g
    for y in wins:
        if y != x: cap[(y, "t")] = best - wins[y]
    value, _, _ = max_flow(cap, "s", "t")
    return value < sum(games.values())       # some game cannot be assigned without overtaking x
for team in wins:
    print(f"{team:7s} wins {wins[team]}  eliminated: {eliminated(team)}")

Otters  wins 83  eliminated: False
Hawks   wins 80  eliminated: False
Lynx    wins 80  eliminated: False
Moose   wins 77  eliminated: True