blossom

Documentation

Overview

Package blossom implements Edmonds' maximum weight matching algorithm for general graphs. It supports both int64 weights (MaxWeightMatching) and arbitrary-precision *big.Int weights (MaxWeightMatchingBig).

This is a Go port of Joris van Rantwijk's Python reference implementation.

Index

• func MaxWeightMatching(edges []BlossomEdge, maxCardinality bool) []int
• func MaxWeightMatchingBig(edges []BigEdge, maxCardinality bool) []int
• type BigEdge
• type BlossomEdge

Functions

func MaxWeightMatching

func MaxWeightMatching(edges []BlossomEdge, maxCardinality bool) []int

MaxWeightMatching computes a maximum weight matching on a general undirected graph using Edmonds' Blossom algorithm.

edges: list of undirected weighted edges. Vertex indices are 0-based and inferred from the edges (max index + 1 = number of vertices).

maxCardinality: if true, finds matching with maximum number of edges first, then maximizes weight among those. If false, maximizes weight only (may leave matchable vertices unmatched).

Returns a slice m where m[i] is the vertex matched to i, or -1 if unmatched. The slice length equals the number of vertices.

func MaxWeightMatchingBig

func MaxWeightMatchingBig(edges []BigEdge, maxCardinality bool) []int

MaxWeightMatchingBig computes a maximum weight matching on a general undirected graph using Edmonds' Blossom algorithm with big.Int weights.

edges: list of undirected weighted edges. Vertex indices are 0-based. maxCardinality: if true, maximize edges first, then weight.

Returns a slice m where m[i] is the vertex matched to i, or -1 if unmatched.

Types

type BigEdge

type BigEdge struct {
	I, J   int      // vertex indices (0-based)
	Weight *big.Int // edge weight (higher = preferred)
}

BigEdge represents an undirected weighted edge with multi-precision weight.

type BlossomEdge

type BlossomEdge struct {
	I, J   int   // vertex indices (0-based)
	Weight int64 // edge weight (higher = preferred)
}

BlossomEdge represents an undirected weighted edge in the matching graph.