Python bipartite matching: augment an assignment instead of taking the first free slot

Operation contract

The roster lists which workers may take which slots. Each worker attempts a path through its allowed slots; if a slot is occupied, the search tries moving its current worker elsewhere. The new worker succeeds only when that chain reaches a free slot. A per-attempt visited-slot set prevents repeated traversal. The example makes the flexible worker move from slot zero to slot one, allowing the restricted worker to take slot zero. First-free greedy assignment would miss that second match.

Failure and ownership boundary

The graph accepts up to eight workers and eight slots, with exact integer endpoints and no duplicate edge in a worker row. It maximizes pair count, not fairness, priority or total monetary weight. Traversal order makes the displayed assignment repeatable but does not imply a unique optimum. Python graph BFS: mark a vertex when it enters the queue, Python union-find: connected groups with path compression and Python weighted interval scheduling: reconstruct the accepted nonoverlapping jobs solve different graph or optimization problems.

Working program

def maximum_assignment(allowed, slot_count):
    if type(allowed) is not list or len(allowed) > 8 or type(slot_count) is not int or not 0 <= slot_count <= 8:
        raise ValueError("roster bounds")
    for row in allowed:
        if type(row) is not list or any(type(slot) is not int or not 0 <= slot < slot_count for slot in row) or len(set(row)) != len(row):
            raise ValueError("slot endpoints")
    owners = [-1] * slot_count
    def augment(worker, visited):
        for slot in allowed[worker]:
            if slot in visited:
                continue
            visited.add(slot)
            if owners[slot] == -1 or augment(owners[slot], visited):
                owners[slot] = worker
                return True
        return False
    for worker in range(len(allowed)):
        augment(worker, set())
    return sorted((worker, slot) for slot, worker in enumerate(owners) if worker != -1)

print("pairs:", maximum_assignment([[0, 1], [0]], 2))
print("isolated:", maximum_assignment([[], [1]], 2))
print("empty:", maximum_assignment([], 0))
try:
    maximum_assignment([[True]], 2)
except ValueError:
    print("Boolean endpoint rejected")

Output

pairs: [(0, 1), (1, 0)]
isolated: [(1, 1)]
empty: []
Boolean endpoint rejected

Costs and limits

Each augmentation scans reachable edges with visited slots, and at most W attempts are made for W workers. The usual bound is O(W times E) edge work plus validation and output sorting; slot ownership takes O(S) storage. The small explicit caps bound recursion. This is the simple augmenting-path algorithm, not Hopcroft-Karp or a measured production scheduler.

Common Mistakes

• Greedy first-free assignment can leave a feasible slot unused.
• A maximum-cardinality match says nothing about fairness or weighted cost.

Connected lessons

Python graph BFS: mark a vertex when it enters the queue, Python weighted interval scheduling: reconstruct the accepted nonoverlapping jobs, Python topological sort: dependency order and cycle rejection.

Trace the related workflow

Python maximum flow: residual edges permit earlier choices to be revised.