Module weighted_general 

Maximum-weight matching on a general (non-bipartite) weighted graph.

Implements Edmonds’ weighted blossom algorithm in the O(n^3) primal-dual array formulation of Galil (1986) — the same formulation underlying Van Rantwijk’s mwmatching / NetworkX max_weight_matching. Unlike the cardinality-only blossom_v_simple, this finds a matching of maximum total weight (which need not be a maximum-cardinality matching), maintaining vertex potentials y_v and blossom potentials z_B with the usual complementary-slackness invariants:

• slack(u,v) = y_u + y_v - 2 w(u,v) >= 0 for every edge,
• matched edges and full blossoms are tight (slack 0),
• unmatched vertices keep y_v >= 0 (so leaving a vertex unmatched is optimal exactly when y_v = 0).

Alternating trees are grown from free vertices; odd cycles are contracted into blossoms and expanded as the dual variables are adjusted. The public entry point is WeightedGeneralMatching.

Structs

WeightedGeneralMatching

Maximum-weight matching solver for a general undirected weighted graph.

WeightedMatchingResult

Result of a maximum-weight general matching solve.