Blossom algorithm
You are encouraged to solve this task according to the task description, using any language you may know.
- The Blossom Algorithm
- The Blossom algorithm, developed by Jack Edmonds in 1965, is a seminal algorithm that solves the maximum matching problem for general graphs by extending the augmenting path concept to handle odd cycles.
- Core Idea
- Shrinking Blossoms
- The key insight of the Blossom algorithm is to identify an odd cycle (a blossom) when encountered during the search for an augmenting path. When a blossom is detected, the algorithm contracts or shrinks the entire cycle into a single "pseudo-vertex". This creates a smaller, auxiliary graph.
- The search for an augmenting path then continues in this contracted graph. If an augmenting path is found in the contracted graph that involves a pseudo-vertex (representing a shrunk blossom), this path can be "lifted" back to the original graph. The structure of the blossom allows the algorithm to find a corresponding augmenting path in the original graph that utilizes edges within the blossom.
- This process of shrinking blossoms, searching for augmenting paths in the contracted graph, and expanding blossoms to find paths in the original graph is repeated until no more augmenting paths are found, at which point the current matching is maximum.
- Problem
- Maximum Matching in General Graphs
- The problem addressed by the Blossom algorithm is finding a Maximum matching|maximum matching in a Graph (discrete mathematics)|general graph. Unlike Bipartite graph|bipartite graphs, general graphs can contain Cycle (graph theory)|odd-length cycles.
- Graph and Matching Definition
- A Graph (discrete mathematics)|graph G is formally defined by a set of Vertex (graph theory)|vertices V and a set of Edge (graph theory)|edges E, denoted as . An edge connects two vertices.
- A Matching (graph theory)|matching M in G is a subset of the edges E such that no two edges in M share a common vertex. That is, for any two distinct edges and , the sets of vertices and are disjoint.
- Maximum Matching
- A Maximum matching|maximum matching is a matching M with the largest possible number of edges among all possible matchings in the graph G. The size of the matching is .
- The objective of the maximum matching problem is to find a matching M such that is maximized.
- Challenge in General Graphs
- Odd Cycles
- For Bipartite graph|bipartite graphs, efficient algorithms exist (e.g., Hopcroft-Karp algorithm) that rely on finding Augmenting path|augmenting paths. An augmenting path with respect to a matching M is a path that starts and ends at unmatched vertex|unmatched vertices, and its edges alternate between being outside M and inside M. If such a path exists, the matching can be increased by one edge by flipping the edges along the path (taking edges not in M and removing edges in M along the path). Berge's lemma states that a matching is maximum if and only if it has no augmenting path.
- However, the presence of Cycle (graph theory)|odd-length cycles in general graphs complicates the search for augmenting paths. Standard Breadth-first search|BFS techniques used for bipartite graphs can get "confused" by odd cycles, which are sometimes called blossoms or flowers in this context. An odd cycle can contain an even number of matched edges and an odd number of unmatched edges with respect to an alternating path leading into it, potentially preventing the discovery of a true augmenting path using simple methods.
- Objective
- Given a general graph , the problem is to compute a matching such that its size is maximum. The Blossom algorithm provides a polynomial-time solution to this problem.
- Complexity
- The original Blossom algorithm by Edmonds has a time complexity of . Subsequent improvements by Edmonds and others, including Robert Tarjan|Tarjan, led to more efficient versions. Modern implementations using advanced data structures achieve a time complexity of , which is generally considered very efficient for this problem. An variant is also commonly cited and easier to implement.
C++
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct Blossom {
int n;
const vector<vector<int>>& adj;
vector<int> match, p, base;
vector<bool> used, blossom;
queue<int> q;
Blossom(const vector<vector<int>>& _adj)
: n((int)_adj.size()), adj(_adj),
match(n, -1), p(n), base(n),
used(n), blossom(n)
{}
int lca(int a, int b) {
vector<bool> used_path(n, false);
while (true) {
a = base[a];
used_path[a] = true;
if (match[a] < 0) break;
a = p[match[a]];
}
while (true) {
b = base[b];
if (used_path[b]) return b;
b = p[match[b]];
}
}
void markPath(int v, int b, int x) {
// mark blossom vertices on path from v to base b
while (base[v] != b) {
blossom[base[v]] = blossom[base[match[v]]] = true;
p[v] = x;
x = match[v];
v = p[x];
}
}
bool findPath(int root) {
fill(used.begin(), used.end(), false);
fill(p.begin(), p.end(), -1);
for (int i = 0; i < n; ++i) base[i] = i;
while (!q.empty()) q.pop();
used[root] = true;
q.push(root);
while (!q.empty()) {
int v = q.front(); q.pop();
for (int u : adj[v]) {
if (base[v] == base[u] || match[v] == u)
continue;
if (u == root || (match[u] >= 0 && p[match[u]] >= 0)) {
// blossom found
int curbase = lca(v, u);
fill(blossom.begin(), blossom.end(), false);
markPath(v, curbase, u);
markPath(u, curbase, v);
for (int i = 0; i < n; ++i) {
if (blossom[base[i]]) {
base[i] = curbase;
if (!used[i]) {
used[i] = true;
q.push(i);
}
}
}
}
else if (p[u] < 0) {
// extend tree
p[u] = v;
if (match[u] < 0) {
// augmenting path found
int cur = u;
while (cur != -1) {
int prev = p[cur];
int nxt = (prev >= 0 ? match[prev] : -1);
match[cur] = prev;
match[prev] = cur;
cur = nxt;
}
return true;
}
used[match[u]] = true;
q.push(match[u]);
}
}
}
return false;
}
// Returns {match, size_of_matching}
pair<vector<int>,int> solve() {
int res = 0;
for (int v = 0; v < n; ++v) {
if (match[v] < 0 && findPath(v))
++res;
}
return { match, res };
}
};
int main() {
// Example: 5‑cycle (odd cycle) 0–1–2–3–4–0
int n = 5;
vector<pair<int,int>> edges = {{0,1},{1,2},{2,3},{3,4},{4,0}};
vector<vector<int>> adj(n);
for (auto& e : edges) {
adj[e.first].push_back(e.second);
adj[e.second].push_back(e.first);
}
Blossom bf(adj);
auto [match, msize] = bf.solve();
cout << "Maximum matching size: " << msize << "\n";
cout << "Matched pairs:\n";
for (int u = 0; u < n; ++u) {
int v = match[u];
if (v >= 0 && u < v) {
cout << " " << u << " – " << v << "\n";
}
}
return 0;
}
- Output:
Maximum matching size: 2 Matched pairs: 0 – 1 2 – 3
FreeBASIC
Type Queue
Dato(Any) As Integer
Front As Integer
Rear As Integer
Size As Integer
Capacity As Integer
End Type
' Queue operations
Function CreateQueue(capacity As Integer) As Queue
Dim q As Queue
q.Capacity = capacity
q.Size = 0
q.Front = 0
q.Rear = -1
Redim q.Dato(capacity - 1)
Return q
End Function
Function isEmpty(q As Queue) As Integer
Return (q.Size = 0)
End Function
Sub Enqueue(Byref q As Queue, item As Integer)
q.Rear = (q.Rear + 1) Mod q.Capacity
q.Dato(q.Rear) = item
q.Size += 1
End Sub
Function Dequeue(Byref q As Queue) As Integer
Dim item As Integer = q.Dato(q.Front)
q.Front = (q.Front + 1) Mod q.Capacity
q.Size -= 1
Return item
End Function
Sub ClearQueue(Byref q As Queue)
q.Size = 0
q.Front = 0
q.Rear = -1
End Sub
' Global variables for the algorithm
Dim Shared g_n As Integer
Dim Shared g_adj() As Integer
Dim Shared g_adjSize() As Integer
Dim Shared g_match() As Integer
Dim Shared g_p() As Integer
Dim Shared g_base() As Integer
Dim Shared g_used() As Integer
Dim Shared g_blossom() As Integer
Dim Shared g_q As Queue
' Find least common ancestor of a and b in the forest of alternating tree
Function LCA(a As Integer, b As Integer) As Integer
Dim usedPath(g_n-1) As Integer
' Mark path from a to root
Do
a = g_base(a)
usedPath(a) = 1
If g_match(a) = -1 Then Exit Do
a = g_p(g_match(a))
Loop
' Find first marked vertex in path from b to root
Do
b = g_base(b)
If usedPath(b) Then Return b
b = g_p(g_match(b))
Loop
Return -1 ' Should never reach here
End Function
' Mark vertices along the path from v to base b, setting their parent to x
Sub MarkPath(v As Integer, b As Integer, x As Integer)
While g_base(v) <> b
g_blossom(g_base(v)) = 1
g_blossom(g_base(g_match(v))) = 1
g_p(v) = x
x = g_match(v)
v = g_p(x)
Wend
End Sub
' Try to find an augmenting path starting from root
Function FindPath(root As Integer) As Boolean
Dim As Integer i, j
' Reset arrays
For i = 0 To g_n-1
g_used(i) = 0
g_p(i) = -1
g_base(i) = i
g_blossom(i) = 0
Next
ClearQueue(g_q)
g_used(root) = 1
Enqueue(g_q, root)
While Not isEmpty(g_q)
Dim v As Integer = Dequeue(g_q)
For i = 0 To g_adjSize(v) - 1
Dim u As Integer = g_adj(v * g_n + i)
' Two cases to skip
If g_base(v) = g_base(u) Or g_match(v) = u Then Continue For
' Found a blossom or an odd cycle edge
If u = root Or (g_match(u) <> -1 And g_p(g_match(u)) <> -1) Then
Dim curbase As Integer = LCA(v, u)
' Reset blossom array
For j = 0 To g_n-1
g_blossom(j) = 0
Next
MarkPath(v, curbase, u)
MarkPath(u, curbase, v)
' Contract blossom
For j = 0 To g_n-1
If g_blossom(g_base(j)) Then
g_base(j) = curbase
If Not g_used(j) Then
g_used(j) = 1
Enqueue(g_q, j)
End If
End If
Next
' Otherwise extend the alternating tree
Elseif g_p(u) = -1 Then
g_p(u) = v
If g_match(u) = -1 Then
' Augmenting path found: flip matches along the path
Dim curr As Integer = u
While curr <> -1
Dim prev As Integer = g_p(curr)
If prev = -1 Then Exit While
Dim sgte As Integer = g_match(prev)
g_match(curr) = prev
g_match(prev) = curr
curr = sgte
Wend
Return True
End If
' Else continue BFS from the matched partner
g_used(g_match(u)) = 1
Enqueue(g_q, g_match(u))
End If
Next
Wend
Return False
End Function
' Edmonds' Blossom Algorithm
Sub MaxMatching(adj() As Integer, adjSize() As Integer, n As Integer, match() As Integer, Byref matchSize As Integer)
Dim As Integer i, j, v
' Set up global variables
g_n = n
Redim g_adj(n*n-1)
Redim g_adjSize(n-1)
Redim g_match(n-1)
Redim g_p(n-1)
Redim g_base(n-1)
Redim g_used(n-1)
Redim g_blossom(n-1)
g_q = CreateQueue(n * n)
' Copy input arrays to global arrays
For i = 0 To n-1
g_adjSize(i) = adjSize(i)
For j = 0 To adjSize(i)-1
g_adj(i * n + j) = adj(i * n + j)
Next
Next
' Initialize match array
For i = 0 To n-1
g_match(i) = -1
Next
' Main loop: try to grow matching by finding augmenting paths
matchSize = 0
For v = 0 To n-1
If g_match(v) = -1 Then
If FindPath(v) Then matchSize += 1
End If
Next
' Copy result back to output array
For i= 0 To n-1
match(i) = g_match(i)
Next
End Sub
' Example: 5-cycle (odd cycle)
' Vertices: 0-1-2-3-4-0
Dim As Integer n = 5
Dim As Integer edges(4, 1) = { {0,1}, {1,2}, {2,3}, {3,4}, {4,0} }
Dim As Integer i, u, v
' Create adjacency list representation
Dim As Integer adj(n*n-1) ' Flattened adjacency list
Dim As Integer adjSize(n-1) ' Size of each adjacency list
For i = 0 To 4
u = edges(i, 0)
v = edges(i, 1)
adj(u * n + adjSize(u)) = v
adjSize(u) += 1
adj(v * n + adjSize(v)) = u
adjSize(v) += 1
Next
' Find maximum matching
Dim As Integer match(n-1)
Dim As Integer matchSize
MaxMatching(adj(), adjSize(), n, match(), matchSize)
' Print results
Print "Maximum matching size:"; matchSize
Print "Matched pairs:"
Dim seen(n*n-1) As Integer
For u = 0 To n-1
v = match(u)
If v <> -1 And u < v Then Print " " & u & " - " & v
Next
Sleep
- Output:
Maximum matching size: 2 Matched pairs: 0 – 1 2 – 3.
Go
package main
import (
"fmt"
)
type Blossom struct {
n int
adj [][]int
match []int
p []int
base []int
used []bool
blossom []bool
queue []int
}
func NewBlossom(adj [][]int) *Blossom {
n := len(adj)
match := make([]int, n)
p := make([]int, n)
base := make([]int, n)
used := make([]bool, n)
blossom := make([]bool, n)
for i := 0; i < n; i++ {
match[i] = -1
p[i] = -1
base[i] = i
}
return &Blossom{
n: n,
adj: adj,
match: match,
p: p,
base: base,
used: used,
blossom: blossom,
queue: make([]int, 0, n),
}
}
// least common ancestor of x and y in the alternating forest
func (bm *Blossom) lca(x, y int) int {
usedPath := make([]bool, bm.n)
for {
x = bm.base[x]
usedPath[x] = true
if bm.match[x] < 0 {
break
}
x = bm.p[bm.match[x]]
}
for {
y = bm.base[y]
if usedPath[y] {
return y
}
y = bm.p[bm.match[y]]
}
}
// mark path from v up to base0, setting parents to x
func (bm *Blossom) markPath(v, base0, x int) {
for bm.base[v] != base0 {
mv := bm.match[v]
bm.blossom[bm.base[v]] = true
bm.blossom[bm.base[mv]] = true
bm.p[v] = x
x = mv
v = bm.p[x]
}
}
// attempt to find an augmenting path from root
func (bm *Blossom) findPath(root int) bool {
// reset BFS state
for i := 0; i < bm.n; i++ {
bm.used[i] = false
bm.p[i] = -1
bm.base[i] = i
}
bm.queue = bm.queue[:0]
bm.used[root] = true
bm.queue = append(bm.queue, root)
qi := 0
for qi < len(bm.queue) {
v := bm.queue[qi]
qi++
for _, u := range bm.adj[v] {
if bm.base[v] == bm.base[u] || bm.match[v] == u {
continue
}
// blossom found
if u == root || (bm.match[u] >= 0 && bm.p[bm.match[u]] >= 0) {
curbase := bm.lca(v, u)
for i := 0; i < bm.n; i++ {
bm.blossom[i] = false
}
bm.markPath(v, curbase, u)
bm.markPath(u, curbase, v)
for i := 0; i < bm.n; i++ {
if bm.blossom[bm.base[i]] {
bm.base[i] = curbase
if !bm.used[i] {
bm.used[i] = true
bm.queue = append(bm.queue, i)
}
}
}
} else if bm.p[u] < 0 {
// extend tree
bm.p[u] = v
if bm.match[u] < 0 {
// augmenting path found
cur := u
for cur >= 0 {
prev := bm.p[cur]
nxt := -1
if prev >= 0 {
nxt = bm.match[prev]
bm.match[cur] = prev
bm.match[prev] = cur
}
cur = nxt
}
return true
}
// enqueue matched partner
mu := bm.match[u]
if !bm.used[mu] {
bm.used[mu] = true
bm.queue = append(bm.queue, mu)
}
}
}
}
return false
}
// Solve returns the matching array and the size of the matching
func (bm *Blossom) Solve() ([]int, int) {
res := 0
for v := 0; v < bm.n; v++ {
if bm.match[v] < 0 {
if bm.findPath(v) {
res++
}
}
}
return bm.match, res
}
func main() {
// Example: 5‑cycle 0–1–2–3–4–0
n := 5
edges := [][2]int{{0, 1}, {1, 2}, {2, 3}, {3, 4}, {4, 0}}
adj := make([][]int, n)
for _, e := range edges {
u, v := e[0], e[1]
adj[u] = append(adj[u], v)
adj[v] = append(adj[v], u)
}
bm := NewBlossom(adj)
match, size := bm.Solve()
fmt.Printf("Maximum matching size: %d\n", size)
fmt.Println("Matched pairs:")
for u, v := range match {
if v >= 0 && u < v {
fmt.Printf(" %d – %d\n", u, v)
}
}
}
- Output:
Maximum matching size: 2 Matched pairs: 0 – 1 2 – 3
Java
import java.util.*;
public class Main {
private int n;
private List<List<Integer>> adj;
private int[] match, p, base;
private boolean[] used, blossom;
private Deque<Integer> queue;
public Main(List<List<Integer>> adj) {
this.n = adj.size();
this.adj = adj;
this.match = new int[n];
this.p = new int[n];
this.base = new int[n];
this.used = new boolean[n];
this.blossom = new boolean[n];
this.queue = new ArrayDeque<>();
Arrays.fill(match, -1);
}
// Find least common ancestor of a and b in the alternating forest
private int lca(int a, int b) {
boolean[] usedPath = new boolean[n];
while (true) {
a = base[a];
usedPath[a] = true;
if (match[a] < 0) break;
a = p[match[a]];
}
while (true) {
b = base[b];
if (usedPath[b]) return b;
b = p[match[b]];
}
}
// Mark vertices along the path from v to base b, setting their parent to x
private void markPath(int v, int b, int x) {
while (base[v] != b) {
int mv = match[v];
blossom[base[v]] = true;
blossom[base[mv]] = true;
p[v] = x;
x = mv;
v = p[x];
}
}
// Try to find an augmenting path starting from root
private boolean findPath(int root) {
Arrays.fill(used, false);
Arrays.fill(p, -1);
for (int i = 0; i < n; i++) {
base[i] = i;
}
queue.clear();
used[root] = true;
queue.add(root);
while (!queue.isEmpty()) {
int v = queue.poll();
for (int u : adj.get(v)) {
if (base[v] == base[u] || match[v] == u) {
continue;
}
// Blossom found
if (u == root || (match[u] >= 0 && p[match[u]] >= 0)) {
int curbase = lca(v, u);
Arrays.fill(blossom, false);
markPath(v, curbase, u);
markPath(u, curbase, v);
for (int i = 0; i < n; i++) {
if (blossom[base[i]]) {
base[i] = curbase;
if (!used[i]) {
used[i] = true;
queue.add(i);
}
}
}
} else if (p[u] < 0) {
// Extend the alternating tree
p[u] = v;
// Found augmenting path
if (match[u] < 0) {
int cur = u;
while (cur >= 0) {
int prev = p[cur];
int next = (prev >= 0 ? match[prev] : -1);
match[cur] = prev;
match[prev] = cur;
cur = next;
}
return true;
}
// Continue BFS from the matched partner
int mu = match[u];
if (!used[mu]) {
used[mu] = true;
queue.add(mu);
}
}
}
}
return false;
}
// Compute maximum matching; returns the size
public int solve() {
int res = 0;
for (int v = 0; v < n; v++) {
if (match[v] < 0) {
if (findPath(v)) {
res++;
}
}
}
return res;
}
public int[] getMatch() {
return match;
}
public static void main(String[] args) {
// Example: 5‑cycle (odd cycle) 0–1–2–3–4–0
int n = 5;
int[][] edges = { {0,1}, {1,2}, {2,3}, {3,4}, {4,0} };
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) {
adj.add(new ArrayList<>());
}
for (int[] e : edges) {
adj.get(e[0]).add(e[1]);
adj.get(e[1]).add(e[0]);
}
Main blossom = new Main(adj);
int msize = blossom.solve();
int[] match = blossom.getMatch();
System.out.println("Maximum matching size: " + msize);
System.out.println("Matched pairs:");
for (int u = 0; u < n; u++) {
int v = match[u];
if (v >= 0 && u < v) {
System.out.println(" " + u + " – " + v);
}
}
}
}
- Output:
Maximum matching size: 2 Matched pairs: 0 – 1 2 – 3
JavaScript
class Blossom {
constructor(adj) {
this.n = adj.length;
this.adj = adj;
this.match = new Array(this.n).fill(-1);
this.p = new Array(this.n).fill(-1);
this.base = new Array(this.n);
this.used = new Array(this.n).fill(false);
this.blossom = new Array(this.n).fill(false);
this.queue = [];
}
// Find least common ancestor of a and b in the alternating forest
lca(a, b) {
const usedPath = new Array(this.n).fill(false);
while (true) {
a = this.base[a];
usedPath[a] = true;
if (this.match[a] === -1) break;
a = this.p[this.match[a]];
}
while (true) {
b = this.base[b];
if (usedPath[b]) return b;
b = this.p[this.match[b]];
}
}
// Mark path from v up to base0, setting parents to x
markPath(v, base0, x) {
while (this.base[v] !== base0) {
const mv = this.match[v];
this.blossom[this.base[v]] = this.blossom[this.base[mv]] = true;
this.p[v] = x;
x = mv;
v = this.p[x];
}
}
// Try to find an augmenting path from root
findPath(root) {
this.used.fill(false);
this.p.fill(-1);
for (let i = 0; i < this.n; i++) {
this.base[i] = i;
}
this.queue = [];
this.used[root] = true;
this.queue.push(root);
while (this.queue.length > 0) {
const v = this.queue.shift();
for (const u of this.adj[v]) {
// Skip same base or matched edge
if (this.base[v] === this.base[u] || this.match[v] === u) {
continue;
}
// Blossom detected
if (
u === root ||
(this.match[u] !== -1 && this.p[this.match[u]] !== -1)
) {
const curbase = this.lca(v, u);
this.blossom.fill(false);
this.markPath(v, curbase, u);
this.markPath(u, curbase, v);
for (let i = 0; i < this.n; i++) {
if (this.blossom[this.base[i]]) {
this.base[i] = curbase;
if (!this.used[i]) {
this.used[i] = true;
this.queue.push(i);
}
}
}
}
// Otherwise, extend the alternating tree
else if (this.p[u] === -1) {
this.p[u] = v;
// If u is free, we found an augmenting path
if (this.match[u] === -1) {
let cur = u;
while (cur !== -1) {
const prev = this.p[cur];
const next = prev === -1 ? -1 : this.match[prev];
this.match[cur] = prev;
this.match[prev] = cur;
cur = next;
}
return true;
}
// Enqueue the matched partner
const mu = this.match[u];
if (!this.used[mu]) {
this.used[mu] = true;
this.queue.push(mu);
}
}
}
}
return false;
}
// Compute maximum matching; returns [matchArray, size]
solve() {
let size = 0;
for (let v = 0; v < this.n; v++) {
if (this.match[v] === -1) {
if (this.findPath(v)) {
size++;
}
}
}
return [this.match, size];
}
}
// Example usage
(function() {
// 5-cycle: 0–1–2–3–4–0
const n = 5;
const edges = [
[0, 1],
[1, 2],
[2, 3],
[3, 4],
[4, 0],
];
const adj = Array.from({ length: n }, () => []);
for (const [u, v] of edges) {
adj[u].push(v);
adj[v].push(u);
}
const blossom = new Blossom(adj);
const [match, msize] = blossom.solve();
console.log(`Maximum matching size: ${msize}`);
console.log("Matched pairs:");
const seen = new Set();
for (let u = 0; u < n; u++) {
const v = match[u];
if (v !== -1 && !seen.has(`${v},${u}`)) {
console.log(` ${u} – ${v}`);
seen.add(`${u},${v}`);
}
}
})();
- Output:
Maximum matching size: 2 Matched pairs: 0 – 1 2 – 3
Julia
using DataStructures # for Deque
struct BlossomMatching
nv::Int # number of vertices
matches::Vector{Int}
parents::Vector{Int}
base_vertices::Vector{Int}
used::Vector{Bool}
blossom::Vector{Bool}
end
"""Find least common ancestor of a and b in the forest of alternating tree."""
function lca(m::BlossomMatching, a, b)
used_path = falses(m.nv)
while true
a = m.base_vertices[a]
used_path[a] = true
m.matches[a] == 0 && break
a = m.parents[m.matches[a]]
end
while true
b = m.base_vertices[b]
used_path[b] && return b
b = m.parents[m.matches[b]]
end
end
"""Mark vertices along the path from v to base b, setting their parent to x."""
function mark_path!(m::BlossomMatching, v, b, x)
while m.base_vertices[v] != b
m.blossom[m.base_vertices[v]] = true
m.blossom[m.base_vertices[m.matches[v]]] = true
m.parents[v] = x
x = m.matches[v]
v = m.parents[x]
end
end
"""Try to find an augmenting path starting from root."""
function find_path!(m::BlossomMatching, adj, root)
# reset struct
m.used .= false
m.parents .= 0
m.base_vertices .= collect(1:m.nv)
q = Deque{Int}()
m.used[root] = true
push!(q, root)
while !isempty(q)
v = popfirst!(q)
for u in adj[v]
# two cases to skip
if m.base_vertices[v] == m.base_vertices[u] || m.matches[v] == u
continue
end
# found a blossom or an odd cycle edge
if u == root || m.matches[u] != 0 && m.parents[m.matches[u]] != 0
curbase = lca(m, v, u)
m.blossom .= false
mark_path!(m, v, curbase, u)
mark_path!(m, u, curbase, v)
# contract blossom
for i in 1:m.nv
if m.blossom[m.base_vertices[i]]
m.base_vertices[i] = curbase
if !m.used[i]
m.used[i] = true
push!(q, i)
end
end
end
# otherwise extend the alternating tree
elseif m.parents[u] == 0
m.parents[u] = v
if m.matches[u] == 0
# augmenting path found: flip matches along the path
curr = u
while curr != 0
prev = m.parents[curr]
nxt = prev != 0 ? m.matches[prev] : 0
m.matches[curr] = prev
m.matches[prev] = curr
curr = nxt
end
return true
end
# else continue BFS from the matches partner
m.used[m.matches[u]] = true
push!(q, m.matches[u])
end
end
end
return false
end
"""
Finds maximum matching in a general undirected graph using Edmonds' Blossom algorithm.
Input: adj — list of lists, adj[u] is the list of neighbors of u (1-indexed).
Returns: match, size
match — list where match[u] = v if u–v is in the matching, or 0
size — number of matches edges
"""
function max_matching(n, adj)
n <= 0 && return Int[], 0 # since the graph has no edges
m = BlossomMatching(n, zeros(Int, n), zeros(Int, n), zeros(Int, n), falses(n), falses(n))
# grow matching by finding augmenting paths
match_count = count(v -> m.matches[v] == 0 && find_path!(m, adj, v), 1:n)
return m.matches, match_count
end
function test_blossom()
# Example: 5‑cycle (odd cycle)
# Vertices: 0–1–2–3–4–0
nv = 5
edges = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)]
adj = [Int[] for _ in 1:nv]
for (u, v) in edges
push!(adj[u + 1], v + 1) # convert zero based to one based input
end
matches, msize = max_matching(nv, adj)
println("Maximum matching size: $msize")
println("Matched pairs:")
seen = Set{Tuple{Int, Int}}()
for (u, v) in enumerate(matches)
if v != 0 && (v, u) ∉ seen
println(" $(u - 1) – $(v - 1)") # 1 based to 0 based output
push!(seen, (u, v))
end
end
end
test_blossom()
- Output:
Maximum matching size: 2 Matched pairs: 0 – 1 2 – 3
Phix
integer n
sequence matches, paths, bases, blossom
// least common ancestor of x and y in the alternating forest
function lca(integer x, y)
sequence usedPath := repeat(false, n)
while true do
x = bases[x]
usedPath[x] = true
if matches[x] < 0 then exit end if
x = paths[matches[x]]
end while
while true do
y = bases[y]
if usedPath[y] then exit end if
y = paths[matches[y]]
end while
return y
end function
// mark path from v up to base0, setting parents to x
procedure markPath(integer v, base0, x)
while bases[v] != base0 do
integer mv := matches[v]
blossom[bases[v]] = true
blossom[bases[mv]] = true
paths[v] = x
x = mv
v = paths[x]
end while
end procedure
// attempt to find an augmenting path from root
function findPath(sequence adj, integer root)
// reset BFS state
paths = repeat(-1,n)
bases = tagset(n)
sequence queue = {root},
used = repeat(false,n)
used[root] = true
integer qi := 1
while qi <= length(queue) do
integer v := queue[qi]
qi += 1
for u in adj[v] do
if bases[v] != bases[u] and matches[v] != u then
// blossom found
if u == root
or (matches[u] >= 0 and paths[matches[u]] >= 0) then
integer curbase := lca(v,u)
blossom = repeat(false,n)
markPath(v,curbase,u)
markPath(u,curbase,v)
for i=1 to n do
if blossom[bases[i]] then
bases[i] = curbase
if not used[i] then
used[i] = true
queue &= i
end if
end if
end for
elsif paths[u] < 0 then
// extend tree
paths[u] = v
if matches[u] < 0 then
// augmenting path found
integer cur := u
while cur > 0 do
integer prev := paths[cur],
nxt := -1
if prev > 0 then
nxt = matches[prev]
matches[cur] = prev
matches[prev] = cur
end if
cur = nxt
end while
return true
end if
// enqueue matched partner
integer mu := matches[u]
if not used[mu] then
used[mu] = true
queue &= mu
end if
end if
end if
end for
end while
return false
end function
// Solve returns the matching array and the size of the matching
function solve(sequence adj)
integer res := 0
matches = repeat(-1,n)
for v=1 to n do
if matches[v] < 0 then
if findPath(adj,v) then
res += 1
end if
end if
end for
return res
end function
// Example: 5-cycle 0–1–2–3–4–0
n = 5
sequence adj := repeat({},n)
for e in {{1,2},{2,3},{3,4},{4,5},{5,1}} do
integer {u,v} := e
adj[u] = append(adj[u], v)
adj[v] = append(adj[v], u)
end for
integer size := solve(adj)
printf(1,"Maximum matching size: %d\n", size)
printf(1,"Matched pairs:\n")
for u,v in matches do
if v>=1 and u<v then
printf(1," %d - %d\n", {u,v})
end if
end for
- Output:
Maximum matching size: 2 Matched pairs: 1 - 2 3 - 4
Python
from collections import deque
def max_matching(adj):
"""
Finds maximum matching in a general undirected graph using Edmonds' Blossom algorithm.
Input: adj — list of lists, adj[u] is the list of neighbors of u (0-indexed).
Returns: match, size
match — list where match[u] = v if u–v is in the matching, or -1
size — number of matched edges
"""
n = len(adj)
match = [-1] * n # match[u] = v if u is matched to v
p = [-1] * n # parent in the alternating tree
base = list(range(n)) # base[u] = base vertex of blossom containing u
q = deque() # queue for BFS
used = [False] * n # whether vertex is in the tree
blossom = [False] * n # helper array for marking blossoms
def lca(a, b):
"""Find least common ancestor of a and b in the forest of alternating tree."""
used_path = [False] * n
while True:
a = base[a]
used_path[a] = True
if match[a] == -1: break
a = p[match[a]]
while True:
b = base[b]
if used_path[b]:
return b
b = p[match[b]]
def mark_path(v, b, x):
"""Mark vertices along the path from v to base b, setting their parent to x."""
while base[v] != b:
blossom[base[v]] = blossom[base[match[v]]] = True
p[v] = x
x = match[v]
v = p[x]
def find_path(root):
"""Try to find an augmenting path starting from root."""
# reset
used[:] = [False] * n
p[:] = [-1] * n
for i in range(n):
base[i] = i
q.clear()
used[root] = True
q.append(root)
while q:
v = q.popleft()
for u in adj[v]:
# two cases to skip
if base[v] == base[u] or match[v] == u:
continue
# found a blossom or an odd cycle edge
if u == root or (match[u] != -1 and p[match[u]] != -1):
curbase = lca(v, u)
blossom[:] = [False] * n
mark_path(v, curbase, u)
mark_path(u, curbase, v)
# contract blossom
for i in range(n):
if blossom[base[i]]:
base[i] = curbase
if not used[i]:
used[i] = True
q.append(i)
# otherwise extend the alternating tree
elif p[u] == -1:
p[u] = v
if match[u] == -1:
# augmenting path found: flip matches along the path
curr = u
while curr != -1:
prev = p[curr]
nxt = match[prev] if prev != -1 else -1
match[curr] = prev
match[prev] = curr
curr = nxt
return True
# else continue BFS from the matched partner
used[match[u]] = True
q.append(match[u])
return False
# Main loop: try to grow matching by finding augmenting paths
res = 0
for v in range(n):
if match[v] == -1:
if find_path(v):
res += 1
return match, res
if __name__ == "__main__":
# Example: 5‑cycle (odd cycle)
# Vertices: 0–1–2–3–4–0
n = 5
edges = [(0,1), (1,2), (2,3), (3,4), (4,0)]
adj = [[] for _ in range(n)]
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
match, msize = max_matching(adj)
print(f"Maximum matching size: {msize}")
print("Matched pairs:")
seen = set()
for u, v in enumerate(match):
if v != -1 and (v, u) not in seen:
print(f" {u} – {v}")
seen.add((u, v))
- Output:
Maximum matching size: 2 Matched pairs: 0 – 1 2 – 3
Raku
# 20250512 Raku programming solution
# least common ancestor of x and y in the alternating forest
sub lca($x is copy, $y is copy, @bases, @matches, @paths, $n) {
my @usedPath = False xx $n;
loop {
@usedPath[$x = @bases[$x]] = True;
@matches[$x] < 0 ?? ( last ) !! $x = @paths[@matches[$x]]
}
loop {
@usedPath[$y = @bases[$y]].Bool ?? ( last ) !! $y = @paths[@matches[$y]]
}
return $y;
}
# mark path from v up to base0, setting parents to x
sub markPath($v is copy, $base0, $x is copy, @bases, @matches, @paths, @blossom) {
while @bases[$v] != $base0 {
my $mv = @matches[$v];
@blossom[@bases[$mv]] = @blossom[@bases[$v]] = True;
@paths[$v] = $x;
$v = @paths[ $x = $mv ];
}
}
# attempt to find an augmenting path from root
sub findPath(@adj, $root, $n, @matches is copy) {
my @paths = -1 xx $n;
my @bases = ^$n;
my @queue = ($root);
my (@used, @blossom) is default( False );
@used[$root] = True;
while my $v = @queue.shift {
for @adj[$v].flat -> $u {
next unless @bases[$v] != @bases[$u] && @matches[$v] != $u;
if $u == $root || (@matches[$u] != -1 && @paths[@matches[$u]] != -1) {
# Found a blossom; contract it
my $curbase = lca($v, $u, @bases, @matches, @paths, $n);
markPath($v, $curbase, $u, @bases, @matches, @paths, @blossom);
markPath($u, $curbase, $v, @bases, @matches, @paths, @blossom);
@queue.push: gather for ^$n -> $i {
if @blossom[@bases[$i]] {
@bases[$i] = $curbase;
unless @used[$i] { @used[take $i] = True }
}
}
} elsif @paths[$u] == -1 { # extend tree
@paths[$u] = $v;
if @matches[$u] == -1 { # augmenting path found
my $v = $u;
while $v != -1 {
my $prev = @paths[$v];
my $next = ( $prev != -1 ) ?? @matches[$prev] !! -1;
@matches[$v] = $prev;
@matches[$prev] = $v if $prev != -1;
$v = $next;
}
return (@matches, True);
}
@used[@matches[$u]] = True;
@queue.push: @matches[$u];
}
}
}
return (@matches, False);
}
# find and return the matching array and the size of the matching
sub solve(@adj) {
my @matches = -1 xx ( my $n = @adj.elems );
my $res = 0;
for ^$n -> $v {
if @matches[$v] == -1 {
my ($new_matches, $found) = findPath(@adj, $v, $n, @matches);
if $found {
@matches = @$new_matches;
$res++;
}
}
}
return (@matches, $res);
}
# Example: 5-cycle (0–1–2–3–4–0)
my $n = 5;
my @edges = (0,1), (1,2), (2,3), (3,4), (4,0);
my @adj = [ [] xx $n ];
for @edges -> ($u, $v) {
@adj[$u].push($v);
@adj[$v].push($u);
}
my ($matches, $msize) = solve(@adj);
say "Maximum matching size: $msize";
say "Matched pairs:";
for $matches.kv -> $u, $v { say " $u – $v" if $v != -1 && $u < $v }
You may Attempt This Online!
Rust
use std::collections::VecDeque;
struct Blossom {
n: usize,
adj: Vec<Vec<usize>>,
matching: Vec<Option<usize>>, // matching[v] = Some(u) if v–u is matched
parent: Vec<Option<usize>>, // parent in the alternating tree
base: Vec<usize>, // base[v] = base vertex of blossom containing v
used: Vec<bool>, // used[v] = whether v is in the BFS tree
blossom: Vec<bool>, // helper array for marking blossoms
q: VecDeque<usize>, // BFS queue
}
impl Blossom {
fn new(adj: Vec<Vec<usize>>) -> Self {
let n = adj.len();
Blossom {
n,
adj,
matching: vec![None; n],
parent: vec![None; n],
base: (0..n).collect(),
used: vec![false; n],
blossom: vec![false; n],
q: VecDeque::new(),
}
}
// Find least common ancestor of a and b in the forest of alternating tree.
fn lca(&self, mut a: usize, mut b: usize) -> usize {
let mut used_path = vec![false; self.n];
// climb from a
loop {
a = self.base[a];
used_path[a] = true;
if let Some(ma) = self.matching[a] {
if let Some(pa) = self.parent[ma] {
a = pa;
continue;
}
}
break;
}
// climb from b until we hit a marked vertex
loop {
b = self.base[b];
if used_path[b] {
return b;
}
if let Some(mb) = self.matching[b] {
if let Some(pb) = self.parent[mb] {
b = pb;
continue;
}
}
// In a valid alternating forest this should always terminate
}
}
// Mark vertices along the path from v to base b, setting their parent to x.
fn mark_path(&mut self, mut v: usize, b: usize, mut x: usize) {
while self.base[v] != b {
let mv = self.matching[v].unwrap();
self.blossom[self.base[v]] = true;
self.blossom[self.base[mv]] = true;
self.parent[v] = Some(x);
x = mv;
v = self.parent[x].unwrap();
}
}
// Try to find an augmenting path starting from root.
fn find_path(&mut self, root: usize) -> bool {
// Reset BFS state
self.used.fill(false);
self.parent.fill(None);
for i in 0..self.n {
self.base[i] = i;
}
self.q.clear();
self.used[root] = true;
self.q.push_back(root);
while let Some(v) = self.q.pop_front() {
// clone neighbors to avoid borrowing self.adj across the BFS loop
let neighbors = self.adj[v].clone();
for u in neighbors {
if self.base[v] == self.base[u] || self.matching[v] == Some(u) {
continue;
}
// Found a blossom
if u == root
|| (self.matching[u].is_some()
&& self.parent[self.matching[u].unwrap()].is_some())
{
let curbase = self.lca(v, u);
self.blossom.fill(false);
self.mark_path(v, curbase, u);
self.mark_path(u, curbase, v);
for i in 0..self.n {
if self.blossom[self.base[i]] {
self.base[i] = curbase;
if !self.used[i] {
self.used[i] = true;
self.q.push_back(i);
}
}
}
}
// Otherwise, try to extend the alternating tree
else if self.parent[u].is_none() {
self.parent[u] = Some(v);
// If u is free, we've found an augmenting path
if self.matching[u].is_none() {
let mut cur = u;
while let Some(prev) = self.parent[cur] {
let next = self.matching[prev];
self.matching[cur] = Some(prev);
self.matching[prev] = Some(cur);
if let Some(nxt) = next {
cur = nxt;
} else {
break;
}
}
return true;
}
// Otherwise enqueue the matched partner
let mu = self.matching[u].unwrap();
if !self.used[mu] {
self.used[mu] = true;
self.q.push_back(mu);
}
}
}
}
false
}
// Main solver: returns (matching, size_of_matching)
fn solve(&mut self) -> (Vec<Option<usize>>, usize) {
let mut res = 0;
for v in 0..self.n {
if self.matching[v].is_none() && self.find_path(v) {
res += 1;
}
}
(self.matching.clone(), res)
}
}
fn main() {
// Example: 5‑cycle (odd cycle) 0–1–2–3–4–0
let n = 5;
let edges = vec![(0,1), (1,2), (2,3), (3,4), (4,0)];
let mut adj = vec![Vec::new(); n];
for &(u, v) in &edges {
adj[u].push(v);
adj[v].push(u);
}
let mut blossom = Blossom::new(adj);
let (matching, msize) = blossom.solve();
println!("Maximum matching size: {}", msize);
println!("Matched pairs:");
for u in 0..n {
if let Some(v) = matching[u] {
if u < v {
println!(" {} – {}", u, v);
}
}
}
}
- Output:
Maximum matching size: 2 Matched pairs: 0 – 1 2 – 3
Wren
import "./queue" for Deque
import "./set" for Set
/* Finds maximum matching in a general undirected graph using Edmonds' Blossom algorithm.
Input: adj — list of lists, adj[u] is the list of neighbors of u (0-indexed).
Returns: match, size
match — list where match[u] = v if u–v is in the matching, or -1
size — number of matched edges
*/
var maxMatching = Fn.new { |adj|
var n = adj.count
var match = List.filled(n, -1) // match[u] = v if u is matched to v
var p = List.filled(n, -1) // parent in the alternating tree
var base = (0...n).toList // base[u] = base vertex of blossom containing u
var q = Deque.new() // queue for BFS
var used = List.filled(n, false) // whether vertex is in the tree
var blossom = List.filled(n, false) // helper array for marking blossoms
// Find least common ancestor of a and b in the forest of alternating tree.
var lca = Fn.new { |a, b|
var usedPath = List.filled(n, false)
while (true) {
a = base[a]
usedPath[a] = true
if (match[a] == -1) break
a = p[match[a]]
}
while (true) {
b = base[b]
if (usedPath[b]) return b
b = p[match[b]]
}
}
// Mark vertices along the path from v to base b, setting their parent to x.
var markPath = Fn.new { |v, b, x|
while (base[v] != b) {
blossom[base[v]] = blossom[base[match[v]]] = true
p[v] = x
x = match[v]
v = p[x]
}
}
// Try to find an augmenting path starting from root.
var findPath = Fn.new { |root|
// reset
used = List.filled(n, false)
p = List.filled(n, -1)
for (i in 0...n) base[i] = i
q.clear()
used[root] = true
q.pushBack(root)
while (!q.isEmpty) {
var v = q.popFront()
for (u in adj[v]) {
// two cases to skip
if (base[v] == base[u] || match[v] == u) continue
// found a blossom or an odd cycle edge
if (u == root || (match[u] != -1 && p[match[u]] != -1)) {
var curbase = lca.call(v, u)
blossom = List.filled(n, false)
markPath.call(v, curbase, u)
markPath.call(u, curbase, v)
// contract blossom
for (i in 0...n) {
if (blossom[base[i]]) {
base[i] = curbase
if (!used[i]) {
used[i] = true
q.pushBack(i)
}
}
}
// otherwise extend the alternating tree
} else if (p[u] == -1) {
p[u] = v
if (match[u] == -1) {
// augmenting path found: flip matches along the path
var curr = u
while (curr != -1) {
var prev = p[curr]
var next = (prev != -1) ? match[prev] : -1
match[curr] = prev
match[prev] = curr
curr = next
}
return true
}
// else continue BFS from the matched partner
used[match[u]] = true
q.pushBack(match[u])
}
}
}
return false
}
// Main loop: try to grow matching by finding augmenting paths.
var res = 0
for (v in 0...n) {
if (match[v] == -1) {
if (findPath.call(v)) res = res + 1
}
}
return [match, res]
}
// Example: 5‑cycle (odd cycle)
// Vertices: 0–1–2–3–4–0
var n = 5
var edges = [ [0, 1], [1, 2], [2, 3], [3, 4], [4, 0] ]
var adj = List.filled(n, null)
for (i in 0...n) adj[i] = []
for (e in edges) {
var u = e[0]
var v = e[1]
adj[u].add(v)
adj[v].add(u)
}
var res = maxMatching.call(adj)
var match = res[0]
var msize = res[1]
System.print("Maximum matching size: %(msize)")
System.print("Matched pairs:")
var seen = Set.new()
var u = -1
for (v in match) {
u = u + 1
if (v != -1 && !seen.contains([v, u].toString)) {
System.print(" %(u) – %(v)")
seen.add([u, v].toString)
}
}
- Output:
Maximum matching size: 2 Matched pairs: 0 – 1 2 – 3
Zig
const std = @import("std");
const Blossom = struct {
n: usize,
adj: [][]usize,
matching: []?usize, // matching[v] = u if v--u is matched
parent: []?usize, // parent in the alternating tree
base: []usize, // base[v] = base vertex of blossom containing v
used: []bool, // used[v] = whether v is in the BFS tree
blossom: []bool, // helper array for marking blossoms
q: std.fifo.LinearFifo(usize, .Dynamic), // BFS queue
allocator: std.mem.Allocator,
fn init(allocator: std.mem.Allocator, adj: [][]usize) !Blossom {
const n = adj.len;
const matching = try allocator.alloc(?usize, n);
const parent = try allocator.alloc(?usize, n);
var base = try allocator.alloc(usize, n);
const used = try allocator.alloc(bool, n);
const blossom = try allocator.alloc(bool, n);
const q = std.fifo.LinearFifo(usize, .Dynamic).init(allocator);
@memset(matching, null);
@memset(parent, null);
for (0..n) |i| {
base[i] = i;
}
@memset(used, false);
@memset(blossom, false);
return Blossom{
.n = n,
.adj = adj,
.matching = matching,
.parent = parent,
.base = base,
.used = used,
.blossom = blossom,
.q = q,
.allocator = allocator,
};
}
fn deinit(self: *Blossom) void {
self.allocator.free(self.matching);
self.allocator.free(self.parent);
self.allocator.free(self.base);
self.allocator.free(self.used);
self.allocator.free(self.blossom);
self.q.deinit();
}
// Find least common ancestor of a and b in the forest of alternating tree.
fn lca(self: *const Blossom, a_in: usize, b_in: usize) usize {
var a = a_in;
var b = b_in;
var used_path = self.allocator.alloc(bool, self.n) catch unreachable;
defer self.allocator.free(used_path);
@memset(used_path, false);
// climb from a
while (true) {
a = self.base[a];
used_path[a] = true;
if (self.matching[a]) |ma| {
if (self.parent[ma]) |pa| {
a = pa;
continue;
}
}
break;
}
// climb from b until we hit a marked vertex
while (true) {
b = self.base[b];
if (used_path[b]) {
return b;
}
if (self.matching[b]) |mb| {
if (self.parent[mb]) |pb| {
b = pb;
continue;
}
}
// In a valid alternating forest this should always terminate
unreachable;
}
}
// Mark vertices along the path from v to base b, setting their parent to x.
fn markPath(self: *Blossom, v_in: usize, b: usize, x_in: usize) void {
var v = v_in;
var x = x_in;
while (self.base[v] != b) {
const mv = self.matching[v].?;
self.blossom[self.base[v]] = true;
self.blossom[self.base[mv]] = true;
self.parent[v] = x;
x = mv;
v = self.parent[x].?;
}
}
// Try to find an augmenting path starting from root.
fn findPath(self: *Blossom, root: usize) bool {
// Reset BFS state
@memset(self.used, false);
@memset(self.parent, null);
for (0..self.n) |i| {
self.base[i] = i;
}
self.q.head = 0;
self.q.count = 0;
self.used[root] = true;
self.q.writeItem(root) catch unreachable;
while (self.q.readItem()) |v| {
for (self.adj[v]) |u| {
if (self.base[v] == self.base[u] or self.matching[v] == u) {
continue;
}
// Found a blossom
if (u == root or
(self.matching[u] != null and self.parent[self.matching[u].?] != null)) {
const curbase = self.lca(v, u);
@memset(self.blossom, false);
self.markPath(v, curbase, u);
self.markPath(u, curbase, v);
for (0..self.n) |i| {
if (self.blossom[self.base[i]]) {
self.base[i] = curbase;
if (!self.used[i]) {
self.used[i] = true;
self.q.writeItem(i) catch unreachable;
}
}
}
}
// Otherwise, try to extend the alternating tree
else if (self.parent[u] == null) {
self.parent[u] = v;
// If u is free, we've found an augmenting path
if (self.matching[u] == null) {
var cur = u;
while (self.parent[cur]) |prev| {
const next = self.matching[prev];
self.matching[cur] = prev;
self.matching[prev] = cur;
cur = next orelse break;
}
return true;
}
// Otherwise enqueue the matched partner
const mu = self.matching[u].?;
if (!self.used[mu]) {
self.used[mu] = true;
self.q.writeItem(mu) catch unreachable;
}
}
}
}
return false;
}
// Main solver: returns (matching, size_of_matching)
fn solve(self: *Blossom) struct { matching: []?usize, size: usize } {
var res: usize = 0;
for (0..self.n) |v| {
if (self.matching[v] == null and self.findPath(v)) {
res += 1;
}
}
const result_matching = self.allocator.alloc(?usize, self.n) catch unreachable;
@memcpy(result_matching, self.matching);
return .{ .matching = result_matching, .size = res };
}
};
pub fn main() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
// Example: 5‑cycle (odd cycle) 0--1--2--3--4--0
const n: usize = 5;
const edges = [_][2]usize{
.{0, 1}, .{1, 2}, .{2, 3}, .{3, 4}, .{4, 0}
};
var adj = try allocator.alloc([]usize, n);
defer {
for (adj) |neighbors| {
allocator.free(neighbors);
}
allocator.free(adj);
}
// Initialize empty adjacency lists
for (0..n) |i| {
adj[i] = try allocator.alloc(usize, 0);
}
// Count neighbors for each vertex
var counts = try allocator.alloc(usize, n);
defer allocator.free(counts);
@memset(counts, 0);
for (edges) |edge| {
counts[edge[0]] += 1;
counts[edge[1]] += 1;
}
// Allocate space for neighbors
for (0..n) |i| {
allocator.free(adj[i]);
adj[i] = try allocator.alloc(usize, counts[i]);
counts[i] = 0; // Reset to use as index
}
// Fill adjacency lists
for (edges) |edge| {
const u = edge[0];
const v = edge[1];
adj[u][counts[u]] = v;
counts[u] += 1;
adj[v][counts[v]] = u;
counts[v] += 1;
}
var blossom = try Blossom.init(allocator, adj);
defer blossom.deinit();
const result = blossom.solve();
defer allocator.free(result.matching);
const stdout = std.io.getStdOut().writer();
try stdout.print("Maximum matching size: {d}\n", .{result.size});
try stdout.print("Matched pairs:\n", .{});
for (0..n) |u| {
if (result.matching[u]) |v| {
if (u < v) {
try stdout.print(" {d} -- {d}\n", .{u, v});
}
}
}
}
- Output:
Maximum matching size: 2 Matched pairs: 0 -- 1 2 -- 3