TheAlgorithms/Java · error · IllegalArgumentException

Capacities must be non-negative

Error message

Capacities must be non-negative

What it means

GomoryHuTree.validateCapacityMatrix throws this IllegalArgumentException when any capacity cell is negative. The Gomory-Hu construction repeatedly solves max-flow sub-problems, each of which requires non-negative capacities.

Source

Thrown at src/main/java/com/thealgorithms/graph/GomoryHuTree.java:65

                weight[s] = weight[t];
                weight[t] = f;
            }
        }
        return new int[][] {parent, weight};
    }

    private static void validateCapacityMatrix(int[][] cap) {
        if (cap == null || cap.length == 0) {
            throw new IllegalArgumentException("Capacity matrix must not be null or empty");
        }
        final int n = cap.length;
        for (int i = 0; i < n; i++) {
            if (cap[i] == null || cap[i].length != n) {
                throw new IllegalArgumentException("Capacity matrix must be square");
            }
            for (int j = 0; j < n; j++) {
                if (cap[i][j] < 0) {
                    throw new IllegalArgumentException("Capacities must be non-negative");
                }
            }
        }
    }

    private static final class MaxFlowResult {
        final int flow;
        final boolean[] reachable;
        MaxFlowResult(int flow, boolean[] reachable) {
            this.flow = flow;
            this.reachable = reachable;
        }
    }

    private static MaxFlowResult edmondsKarpWithMinCut(int[][] capacity, int source, int sink) {
        final int n = capacity.length;
        int[][] residual = new int[n][n];
        for (int i = 0; i < n; i++) {

View on GitHub (pinned to fdfb9a395b)

Solutions

1. Represent 'no edge' as 0, never -1.
2. Clamp parsed values: cap[u][v] = Math.max(0, val).
3. Add a unit test that asserts no negatives after matrix construction.

Example fix

// before
cap[u][v] = hasEdge ? w : -1;

// after
cap[u][v] = hasEdge ? w : 0;

for (int i = 0; i < cap.length; i++)
    for (int j = 0; j < cap[i].length; j++)
        if (cap[i][j] < 0) cap[i][j] = 0; // clamp

boolean allNonNegative(int[][] cap) {
    for (int[] row : cap) for (int v : row) if (v < 0) return false;
    return true;
}

When it happens

Trigger: Passing a matrix with any cell < 0, including sentinels like -1 for 'no edge'.

Common situations: Using -1 as a no-edge sentinel. Signed weights from a file not clamped. Negative values introduced by buggy residual arithmetic before calling the validator.

Related errors

• Capacities must be non-negative
• Capacity matrix must not be null or empty
• Capacity matrix must be square
• Costs must be non-negative
• Capacities must be non-negative

AI-assisted analysis of TheAlgorithms/Java@fdfb9a395b (2026-08-13). Data as JSON: /api/errors/a24c873f5cc9cbe8. Report an issue: GitHub.