Edmond's Blossom Algorithm

Step 1 of 36 Init

Every vertex starts with the same budget: half the maximum edge weight. Internally, we double all budgets to ensure things stay integers, and that doubling is shown in the visualization as well.

An edge is "tight" when its endpoints' budgets sum to exactly 2× the edge weight. The highest-weight edges are tight from the start; lower-weight edges become tight as S-vertex budgets are spent during delta steps.

Legend

Vertices

S — active searchers, queued for scanning. Unmatched vertices start as S; matched vertices become S when their partner becomes T.

T — reached via a tight edge from an S-vertex. Never queued directly; their matched partner immediately becomes S and joins the queue.

Unlabeled — not yet reached by the search in this stage.

Active — the vertex currently being operated on this step.

Edges

Matched — in the current matching. The algorithm maximizes total weight of these edges.

Unmatched — available but not currently in the matching.

Active — involved in the current operation.

During Scan Steps

Each edge from the scanned S-vertex is classified by its slack and the neighbor's label:

Grow — tight (slack = 0) to an unlabeled vertex. Tree extends: neighbor becomes T, its matched partner becomes S.

S–S — tight to another S-vertex. Either an augmenting path (different trees) or a blossom (same tree).

Tight-T — tight to a T-vertex. Already in the tree; no action needed.

Δ₂ candidate — not tight, neighbor is unlabeled. Tracked for the next delta step.

Δ₃ candidate — not tight, neighbor is S. Tracked for the next delta step. Slack shrinks at 2× rate since both endpoints are S.

Budget (the number below each vertex name) starts at half the max edge weight, shown at 2× scale to keep values integer. S-budgets decrease during delta steps; T-budgets increase.

Slack = budget[x] + budget[y] − 2×weight. Zero means the edge is tight and the algorithm can use it. During scans, each edge is annotated with this arithmetic.

Blossom (dashed purple group) — an odd cycle contracted into a single super-vertex. This is the key trick that makes matching work on non-bipartite graphs. Blossoms have their own budget that increases (if S) or decreases (if T) during delta steps.

Examples

Maximum weighted matching algorithm overview

This visualizer steps through an implementation of the blossom algorithm, which finds a maximum weight matching in a graph: a set of edges (pairs of vertices) where no vertex appears twice and the total weight is as large as possible. This is used internally by our chess tournament manager to pair players in a Swiss tournament. For each round in a Swiss tournament, each possible combination of players can be thought of as an edge on the graph whose weight corresponds to the pairing rules (have these two players played before, their score, etc). This algorithm gives us the "matching" (combination of matched players) that maximizes their weight (best possible pairing among all pairings).

Stages and substages

The algorithm starts with no matches and then proceeds in stages. Each stage tries to increase the total number of matches by one. It does this by searching for an "augmenting path": a chain of edges that alternate between matched and unmatched. Once found, the algorithm flips the match status of those edges. Because the augmented path has one more unmatched edge than matched edge, this flipping increases the overall matching by one. If no augmenting path can be found, this means the optimal matching has been found and the matching cannot be improved.

Inside each stage, the algorithm builds search trees starting from each unmatched vertex. Each vertex has a "budget" based originally on the maximum weight of the graph. If no augmented path can be found directly, the algorithm spends down some of the budget. This happens repeatedly until a new augmented path can be found, or the budgets prove no path exists.

Budgets, slack, and tight edges

Every vertex has a budget which starts as half of the maximum input edge weight. Each edge has a related "slack". The slack for an edge that connects vertices x and y is calculated as budget[x] + budget[y] − weight. An edge is "tight" when its slack is zero. Once an edge is considered "tight" it can be added to the augmented path.

NOTE: All values are stored at 2× scale to avoid imprecision stemming from floating point division. The slack formula in this visualization reflects these 2× values.

The search: S and T labels

The algorithm searches outward from each unmatched vertex. Vertices are labeled S or T to track their depth: At the start of each stage, all unmatched vertices are labeled S and go into a queue (everything else starts unlabeled). One-by-one, these are pulled off the queue. Each edge is examined and categorized as follows:

Tight edge → unlabeled: Grow the search tree by labeling the neighbor T, labeling its matching partner S and adding that newly S-labeled vertex to the search queue. When this happens, we also mark that the original S vertex was the "parent" of the edge. This is important for the next case.
Tight edge → S: If the S vertex is part of the same search tree, we need to form a blossom. Otherwise, we've found an augmenting path. If we've found an augmenting path the search can conclude and we can flip our augmenting path's matched/unmatched to gain a new edge.
Tight edge → T: already in the tree, skip
Not tight: recorded as a candidate for the next delta step (see below)

Delta steps: spending budgets

When queue empties without finding an augmenting path, the algorithm adjusts each vertex budget by some value δ to make a new edge tight. S-vertex budgets decrease by δ and T-vertex budgets increase by δ. This increase/decrease is important in order to keep the existing tight edges tight.

The size of δ is the minimum of four candidates:

Δ	Source	What happens
Δ₁	min S-vertex budget	Budget hits 0 → stage ends, matching is optimal
Δ₂	min slack among S → unlabeled	Edge becomes tight → tree grows
Δ₃	½ min slack among S → S	Edge becomes tight → augmenting path or blossom
Δ₄	min T-blossom budget	Budget hits 0 → expand blossom

NOTE: Δ₃ uses half the slack because both S-endpoints spend budget simultaneously, so slack shrinks at 2× rate.

Blossoms: handling odd cycles

When a tight edge connects two S-vertices in the same tree (remember that as we scan from S vertices, we label where we started searching from), it forms an "odd cycle." The algorithm contracts this cycle into a single super-vertex called a blossom. This is necessary because odd cycles break the alternating-path logic.

Former T-vertices inside a blossom become S, unlocking their edges for scanning. Blossoms can be nested (a blossom can contain other blossoms). When a T-blossom's budget reaches zero (Δ₄), it is expanded back into its sub-blossoms and scanning continues from the newly exposed S-vertices.