Crate integer_blossom 

Minimum-weight perfect matching on a complete graph (general, non-bipartite).

Many pairing problems (round-robin/Swiss-style tournament pairing among them) are matching problems on a general graph — any vertex may pair with any other — so bipartite methods (Hungarian) don’t apply and we need the blossom algorithm. This crate implements the classic O(V³) primal-dual blossom algorithm for maximum weight matching, then reduces the problem most callers actually care about — a minimum-weight perfect matching — to it:

On a complete graph with strictly positive edge weights, the maximum-weight matching is necessarily perfect (any two unmatched vertices are adjacent by a positive-weight edge, so leaving them unmatched is never optimal). Weighting each edge offset - cost, with offset chosen above every cost so all weights stay ≥ 1, therefore yields the minimum-cost perfect matching.

Both are exposed: max_weight_matching solves the general problem — an arbitrary (possibly sparse, possibly odd-order) graph, leaving a vertex unmatched where that is optimal — and min_weight_perfect_matching applies the reduction above. Both are thin wrappers over one pooled solver, differing only in how they fill edges and shape the result.

Weights are generic over Weight so callers can pick a type just wide enough for their largest weight — i32/i64 for most instances, i128 when more headroom is needed (e.g. to stack large lexicographic multipliers when scalarizing a multi-criteria cost). Should an instance ever outgrow i128, a fixed-width 256-bit Weight impl would be the next step (a heap-allocated bignum isn’t — it’d add allocation to every arithmetic op in this O(V³) inner loop); benchmarking a non-allocating 256-bit uint against i128 on the same instances measured it at only ~1.7x slower, so the headroom is cheap if it’s ever needed.

The implementation is original — built from the published blossom algorithm, not ported from any codebase — and is checked against a brute-force oracle in the tests below.

Traits

Weight

Edge-weight type for the blossom solver: a signed integer wide enough to hold the caller’s largest weight without overflow.

Functions

max_weight_matching

Compute a maximum-total-weight matching of the n vertices, where weight is the row-major n × n weight matrix — the weight of the edge between i and j is weight[i * n + j]. Returns mate, where mate[i] is Some(j) if i is matched to j and None if i is left unmatched.

min_weight_perfect_matching

Compute a minimum-total-cost perfect matching of the n vertices, where cost is the row-major n × n cost matrix — the cost of pairing i with j is cost[i * n + j]. Returns mate, where mate[i] is the partner of vertex i.