Java bipartite matching: reroute an assignment with an augmenting path

Last updated: 30 Sept 20264 min read

tutorial

An augmenting-path matcher grows a one-to-one worker-to-task assignment by rerouting an earlier assignment when a new worker needs its task.

A local greedy pick can block a full match

Worker zero accepts tasks zero or one; worker one accepts only zero; worker two accepts one or two. If worker zero takes zero first, worker one must move worker zero to one. The DFS tries that reroute and reaches three assigned tasks.

The right-side visited array is fresh for each worker's search. Reusing it across workers would hide a valid reroute. Task IDs must be validated against the declared task count before using them as array indices. Max flow generalizes this assignment view with capacities.

This is a baseline matcher

The DFS implementation is suited to small graphs and explanation. Large bipartite graphs need stronger algorithms and workload tests. No monetary or fairness objective is encoded: it maximizes cardinality only.

Working program

import java.util.Arrays;
public class ReviewerAssignment {
    static boolean augment(int reviewer, int[][] choices, boolean[] seen, int[] owner) {
        for (int task : choices[reviewer]) {
            if (task < 0 || task >= owner.length) throw new IllegalArgumentException("task id");
            if (seen[task]) continue;
            seen[task] = true;
            if (owner[task] == -1 || augment(owner[task], choices, seen, owner)) {
                owner[task] = reviewer;
                return true;
            }
        }
        return false;
    }
    static int maximum(int[][] choices, int taskCount) {
        int[] owner = new int[taskCount];
        Arrays.fill(owner, -1);
        int assigned = 0;
        for (int reviewer = 0; reviewer < choices.length; reviewer++)
            if (augment(reviewer, choices, new boolean[taskCount], owner)) assigned++;
        return assigned;
    }
    public static void main(String[] args) {
        System.out.println(maximum(new int[][]{{0, 1}, {0}, {1, 2}}, 3));
        if (maximum(new int[][]{{0}, {0}}, 1) != 1) throw new AssertionError("one task");
    }
}

Output

Costs and boundaries

For W reviewers, T tasks and E preference edges, this simple augmenting DFS can take O(W E) time and O(W+T) extra stack, owner and visited space, excluding caller-owned input. Deep reroutes can exhaust the Java call stack. It finds maximum cardinality, not a minimum-cost or fair assignment.

Common Mistakes

Do not keep one seen array for every reviewer search.
Do not count a first-choice greedy assignment as maximum.
Do not accept out-of-range task IDs as valid input.