TheAlgorithms/Java · error · IllegalArgumentException

Capacity matrix must be square

Error message

Capacity matrix must be square

What it means

EdmondsKarp.maxFlow throws this IllegalArgumentException when any row of the capacity matrix is null or has a length different from the matrix dimension n. The algorithm requires a square n×n matrix to map every (source, sink) pair to a capacity entry.

Source

Thrown at src/main/java/com/thealgorithms/graph/EdmondsKarp.java:43

    /**
     * Computes the maximum flow from {@code source} to {@code sink} in the provided capacity matrix.
     *
     * @param capacity the capacity matrix representing the directed graph; must be square and non-null
     * @param source the source vertex index
     * @param sink the sink vertex index
     * @return the value of the maximum flow between {@code source} and {@code sink}
     * @throws IllegalArgumentException if the matrix is {@code null}, not square, contains negative
     *         capacities, or if {@code source} / {@code sink} indices are invalid
     */
    public static int maxFlow(int[][] capacity, int source, int sink) {
        if (capacity == null || capacity.length == 0) {
            throw new IllegalArgumentException("Capacity matrix must not be null or empty");
        }

        final int n = capacity.length;
        for (int row = 0; row < n; row++) {
            if (capacity[row] == null || capacity[row].length != n) {
                throw new IllegalArgumentException("Capacity matrix must be square");
            }
            for (int col = 0; col < n; col++) {
                if (capacity[row][col] < 0) {
                    throw new IllegalArgumentException("Capacities must be non-negative");
                }
            }
        }

        if (source < 0 || source >= n || sink < 0 || sink >= n) {
            throw new IllegalArgumentException("Source and sink must be valid vertex indices");
        }
        if (source == sink) {
            return 0;
        }

        final int[][] residual = new int[n][n];
        for (int i = 0; i < n; i++) {
            residual[i] = Arrays.copyOf(capacity[i], n);

View on GitHub (pinned to fdfb9a395b)

Solutions

1. Allocate the matrix as new int[n][n] where n is the vertex count.
2. If constructing from edges, first size n, then fill cap[u][v] for each edge.
3. Verify all rows are non-null and length n before calling.

Example fix

// before
int[][] cap = new int[numEdges][]; // wrong: ragged
for (Edge e : edges) cap[e.u] = new int[n];

// after
int[][] cap = new int[n][n];
for (Edge e : edges) cap[e.u][e.v] = e.weight;

for (int[] row : capacity) {
    if (row == null || row.length != capacity.length) {
        throw new IllegalArgumentException("Non-square matrix");
    }
}

boolean isSquare(int[][] cap) {
    if (cap == null) return false;
    for (int[] row : cap) if (row == null || row.length != cap.length) return false;
    return true;
}

When it happens

Trigger: Passing a ragged 2D array (rows of differing lengths), a matrix with a null row, or a rectangular non-square matrix (e.g. n×m where m != n).

Common situations: Building the matrix from an edge list using new int[numEdges][] instead of new int[n][n]. Accidentally transposing dimensions. A row left null after partial initialization.

Related errors

• Capacity matrix must be square
• Source and sink must be valid vertex indices
• Capacity matrix must not be null or empty
• Capacities must be non-negative
• Source and sink must be valid vertex indices

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