Blossom algorithm

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 ${\displaystyle G=(V,E)}$. 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 ${\displaystyle e_{1}={u_{1},v_{1}}\in M}$ and ${\displaystyle e_{2}={u_{2},v_{2}}\in M}$, the sets of vertices ${\displaystyle {u_{1},v_{1}}}$ and ${\displaystyle {u_{2},v_{2}}}$ 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 ${\displaystyle |M|}$.

The objective of the maximum matching problem is to find a matching M such that ${\displaystyle |M|}$ 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 ${\displaystyle G=(V,E)}$, the problem is to compute a matching ${\displaystyle M\subseteq E}$ such that its size ${\displaystyle |M|}$ 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 ${\displaystyle O(|V|^{2}|E|)}$. 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 ${\displaystyle O(|E|{\sqrt {|V|}})}$, which is generally considered very efficient for this problem. An ${\displaystyle O(|V|^{3})}$ variant is also commonly cited and easier to implement.

C++

Works with: C++17

Translation of: Python

#include<iostream>#include<vector>#include<queue>#include<algorithm>usingnamespacestd;structBlossom{intn;constvector<vector<int>>&adj;vector<int>match,p,base;vector<bool>used,blossom;queue<int>q;Blossom(constvector<vector<int>>&_adj):n((int)_adj.size()),adj(_adj),match(n,-1),p(n),base(n),used(n),blossom(n){}intlca(inta,intb){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])returnb;b=p[match[b]];}}voidmarkPath(intv,intb,intx){// mark blossom vertices on path from v to base bwhile(base[v]!=b){blossom[base[v]]=blossom[base[match[v]]]=true;p[v]=x;x=match[v];v=p[x];}}boolfindPath(introot){fill(used.begin(),used.end(),false);fill(p.begin(),p.end(),-1);for(inti=0;i<n;++i)base[i]=i;while(!q.empty())q.pop();used[root]=true;q.push(root);while(!q.empty()){intv=q.front();q.pop();for(intu:adj[v]){if(base[v]==base[u]||match[v]==u)continue;if(u==root||(match[u]>=0&&p[match[u]]>=0)){// blossom foundintcurbase=lca(v,u);fill(blossom.begin(),blossom.end(),false);markPath(v,curbase,u);markPath(u,curbase,v);for(inti=0;i<n;++i){if(blossom[base[i]]){base[i]=curbase;if(!used[i]){used[i]=true;q.push(i);}}}}elseif(p[u]<0){// extend treep[u]=v;if(match[u]<0){// augmenting path foundintcur=u;while(cur!=-1){intprev=p[cur];intnxt=(prev>=0?match[prev]:-1);match[cur]=prev;match[prev]=cur;cur=nxt;}returntrue;}used[match[u]]=true;q.push(match[u]);}}}returnfalse;}// Returns {match, size_of_matching}pair<vector<int>,int>solve(){intres=0;for(intv=0;v<n;++v){if(match[v]<0&&findPath(v))++res;}return{match,res};}};intmain(){// Example: 5‑cycle (odd cycle) 0–1–2–3–4–0intn=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);}Blossombf(adj);auto[match,msize]=bf.solve();cout<<"Maximum matching size: "<<msize<<"\n";cout<<"Matched pairs:\n";for(intu=0;u<n;++u){intv=match[u];if(v>=0&&u<v){cout<<" "<<u<<" – "<<v<<"\n";}}return0;}

Output:

Maximum matching size: 2 Matched pairs: 0 – 1 2 – 3 

FreeBASIC

TypeQueueDato(Any)AsIntegerFrontAsIntegerRearAsIntegerSizeAsIntegerCapacityAsIntegerEndType' Queue operationsFunctionCreateQueue(capacityAsInteger)AsQueueDimqAsQueueq.Capacity=capacityq.Size=0q.Front=0q.Rear=-1Redimq.Dato(capacity-1)ReturnqEndFunctionFunctionisEmpty(qAsQueue)AsIntegerReturn(q.Size=0)EndFunctionSubEnqueue(ByrefqAsQueue,itemAsInteger)q.Rear=(q.Rear+1)Modq.Capacityq.Dato(q.Rear)=itemq.Size+=1EndSubFunctionDequeue(ByrefqAsQueue)AsIntegerDimitemAsInteger=q.Dato(q.Front)q.Front=(q.Front+1)Modq.Capacityq.Size-=1ReturnitemEndFunctionSubClearQueue(ByrefqAsQueue)q.Size=0q.Front=0q.Rear=-1EndSub' Global variables for the algorithmDimSharedg_nAsIntegerDimSharedg_adj()AsIntegerDimSharedg_adjSize()AsIntegerDimSharedg_match()AsIntegerDimSharedg_p()AsIntegerDimSharedg_base()AsIntegerDimSharedg_used()AsIntegerDimSharedg_blossom()AsIntegerDimSharedg_qAsQueue' Find least common ancestor of a and b in the forest of alternating treeFunctionLCA(aAsInteger,bAsInteger)AsIntegerDimusedPath(g_n-1)AsInteger' Mark path from a to rootDoa=g_base(a)usedPath(a)=1Ifg_match(a)=-1ThenExitDoa=g_p(g_match(a))Loop' Find first marked vertex in path from b to rootDob=g_base(b)IfusedPath(b)ThenReturnbb=g_p(g_match(b))LoopReturn-1' Should never reach hereEndFunction' Mark vertices along the path from v to base b, setting their parent to xSubMarkPath(vAsInteger,bAsInteger,xAsInteger)Whileg_base(v)<>bg_blossom(g_base(v))=1g_blossom(g_base(g_match(v)))=1g_p(v)=xx=g_match(v)v=g_p(x)WendEndSub' Try to find an augmenting path starting from rootFunctionFindPath(rootAsInteger)AsBooleanDimAsIntegeri,j' Reset arraysFori=0Tog_n-1g_used(i)=0g_p(i)=-1g_base(i)=ig_blossom(i)=0NextClearQueue(g_q)g_used(root)=1Enqueue(g_q,root)WhileNotisEmpty(g_q)DimvAsInteger=Dequeue(g_q)Fori=0Tog_adjSize(v)-1DimuAsInteger=g_adj(v*g_n+i)' Two cases to skipIfg_base(v)=g_base(u)Org_match(v)=uThenContinueFor' Found a blossom or an odd cycle edgeIfu=rootOr(g_match(u)<>-1Andg_p(g_match(u))<>-1)ThenDimcurbaseAsInteger=LCA(v,u)' Reset blossom arrayForj=0Tog_n-1g_blossom(j)=0NextMarkPath(v,curbase,u)MarkPath(u,curbase,v)' Contract blossomForj=0Tog_n-1Ifg_blossom(g_base(j))Theng_base(j)=curbaseIfNotg_used(j)Theng_used(j)=1Enqueue(g_q,j)EndIfEndIfNext' Otherwise extend the alternating treeElseifg_p(u)=-1Theng_p(u)=vIfg_match(u)=-1Then' Augmenting path found: flip matches along the pathDimcurrAsInteger=uWhilecurr<>-1DimprevAsInteger=g_p(curr)Ifprev=-1ThenExitWhileDimsgteAsInteger=g_match(prev)g_match(curr)=prevg_match(prev)=currcurr=sgteWendReturnTrueEndIf' Else continue BFS from the matched partnerg_used(g_match(u))=1Enqueue(g_q,g_match(u))EndIfNextWendReturnFalseEndFunction' Edmonds' Blossom AlgorithmSubMaxMatching(adj()AsInteger,adjSize()AsInteger,nAsInteger,match()AsInteger,ByrefmatchSizeAsInteger)DimAsIntegeri,j,v' Set up global variablesg_n=nRedimg_adj(n*n-1)Redimg_adjSize(n-1)Redimg_match(n-1)Redimg_p(n-1)Redimg_base(n-1)Redimg_used(n-1)Redimg_blossom(n-1)g_q=CreateQueue(n*n)' Copy input arrays to global arraysFori=0Ton-1g_adjSize(i)=adjSize(i)Forj=0ToadjSize(i)-1g_adj(i*n+j)=adj(i*n+j)NextNext' Initialize match arrayFori=0Ton-1g_match(i)=-1Next' Main loop: try to grow matching by finding augmenting pathsmatchSize=0Forv=0Ton-1Ifg_match(v)=-1ThenIfFindPath(v)ThenmatchSize+=1EndIfNext' Copy result back to output arrayFori=0Ton-1match(i)=g_match(i)NextEndSub' Example: 5-cycle (odd cycle)' Vertices: 0-1-2-3-4-0DimAsIntegern=5DimAsIntegeredges(4,1)={{0,1},{1,2},{2,3},{3,4},{4,0}}DimAsIntegeri,u,v' Create adjacency list representationDimAsIntegeradj(n*n-1)' Flattened adjacency listDimAsIntegeradjSize(n-1)' Size of each adjacency listFori=0To4u=edges(i,0)v=edges(i,1)adj(u*n+adjSize(u))=vadjSize(u)+=1adj(v*n+adjSize(v))=uadjSize(v)+=1Next' Find maximum matchingDimAsIntegermatch(n-1)DimAsIntegermatchSizeMaxMatching(adj(),adjSize(),n,match(),matchSize)' Print resultsPrint"Maximum matching size:";matchSizePrint"Matched pairs:"Dimseen(n*n-1)AsIntegerForu=0Ton-1v=match(u)Ifv<>-1Andu<vThenPrint" "&u&" - "&vNextSleep

Output:

Maximum matching size: 2 Matched pairs: 0 – 1 2 – 3.

Go

Translation of: C++

packagemainimport("fmt")typeBlossomstruct{nintadj[][]intmatch[]intp[]intbase[]intused[]boolblossom[]boolqueue[]int}funcNewBlossom(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)fori:=0;i<n;i++{match[i]=-1p[i]=-1base[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 forestfunc(bm*Blossom)lca(x,yint)int{usedPath:=make([]bool,bm.n)for{x=bm.base[x]usedPath[x]=trueifbm.match[x]<0{break}x=bm.p[bm.match[x]]}for{y=bm.base[y]ifusedPath[y]{returny}y=bm.p[bm.match[y]]}}// mark path from v up to base0, setting parents to xfunc(bm*Blossom)markPath(v,base0,xint){forbm.base[v]!=base0{mv:=bm.match[v]bm.blossom[bm.base[v]]=truebm.blossom[bm.base[mv]]=truebm.p[v]=xx=mvv=bm.p[x]}}// attempt to find an augmenting path from rootfunc(bm*Blossom)findPath(rootint)bool{// reset BFS statefori:=0;i<bm.n;i++{bm.used[i]=falsebm.p[i]=-1bm.base[i]=i}bm.queue=bm.queue[:0]bm.used[root]=truebm.queue=append(bm.queue,root)qi:=0forqi<len(bm.queue){v:=bm.queue[qi]qi++for_,u:=rangebm.adj[v]{ifbm.base[v]==bm.base[u]||bm.match[v]==u{continue}// blossom foundifu==root||(bm.match[u]>=0&&bm.p[bm.match[u]]>=0){curbase:=bm.lca(v,u)fori:=0;i<bm.n;i++{bm.blossom[i]=false}bm.markPath(v,curbase,u)bm.markPath(u,curbase,v)fori:=0;i<bm.n;i++{ifbm.blossom[bm.base[i]]{bm.base[i]=curbaseif!bm.used[i]{bm.used[i]=truebm.queue=append(bm.queue,i)}}}}elseifbm.p[u]<0{// extend treebm.p[u]=vifbm.match[u]<0{// augmenting path foundcur:=uforcur>=0{prev:=bm.p[cur]nxt:=-1ifprev>=0{nxt=bm.match[prev]bm.match[cur]=prevbm.match[prev]=cur}cur=nxt}returntrue}// enqueue matched partnermu:=bm.match[u]if!bm.used[mu]{bm.used[mu]=truebm.queue=append(bm.queue,mu)}}}}returnfalse}// Solve returns the matching array and the size of the matchingfunc(bm*Blossom)Solve()([]int,int){res:=0forv:=0;v<bm.n;v++{ifbm.match[v]<0{ifbm.findPath(v){res++}}}returnbm.match,res}funcmain(){// Example: 5‑cycle 0–1–2–3–4–0n:=5edges:=[][2]int{{0,1},{1,2},{2,3},{3,4},{4,0}}adj:=make([][]int,n)for_,e:=rangeedges{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:")foru,v:=rangematch{ifv>=0&&u<v{fmt.Printf(" %d – %d\n",u,v)}}}

Output:

Maximum matching size: 2 Matched pairs: 0 – 1 2 – 3 

Java

Translation of: C++

importjava.util.*;publicclassMain{privateintn;privateList<List<Integer>>adj;privateint[]match,p,base;privateboolean[]used,blossom;privateDeque<Integer>queue;publicMain(List<List<Integer>>adj){this.n=adj.size();this.adj=adj;this.match=newint[n];this.p=newint[n];this.base=newint[n];this.used=newboolean[n];this.blossom=newboolean[n];this.queue=newArrayDeque<>();Arrays.fill(match,-1);}// Find least common ancestor of a and b in the alternating forestprivateintlca(inta,intb){boolean[]usedPath=newboolean[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])returnb;b=p[match[b]];}}// Mark vertices along the path from v to base b, setting their parent to xprivatevoidmarkPath(intv,intb,intx){while(base[v]!=b){intmv=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 rootprivatebooleanfindPath(introot){Arrays.fill(used,false);Arrays.fill(p,-1);for(inti=0;i<n;i++){base[i]=i;}queue.clear();used[root]=true;queue.add(root);while(!queue.isEmpty()){intv=queue.poll();for(intu:adj.get(v)){if(base[v]==base[u]||match[v]==u){continue;}// Blossom foundif(u==root||(match[u]>=0&&p[match[u]]>=0)){intcurbase=lca(v,u);Arrays.fill(blossom,false);markPath(v,curbase,u);markPath(u,curbase,v);for(inti=0;i<n;i++){if(blossom[base[i]]){base[i]=curbase;if(!used[i]){used[i]=true;queue.add(i);}}}}elseif(p[u]<0){// Extend the alternating treep[u]=v;// Found augmenting pathif(match[u]<0){intcur=u;while(cur>=0){intprev=p[cur];intnext=(prev>=0?match[prev]:-1);match[cur]=prev;match[prev]=cur;cur=next;}returntrue;}// Continue BFS from the matched partnerintmu=match[u];if(!used[mu]){used[mu]=true;queue.add(mu);}}}}returnfalse;}// Compute maximum matching; returns the sizepublicintsolve(){intres=0;for(intv=0;v<n;v++){if(match[v]<0){if(findPath(v)){res++;}}}returnres;}publicint[]getMatch(){returnmatch;}publicstaticvoidmain(String[]args){// Example: 5‑cycle (odd cycle) 0–1–2–3–4–0intn=5;int[][]edges={{0,1},{1,2},{2,3},{3,4},{4,0}};List<List<Integer>>adj=newArrayList<>();for(inti=0;i<n;i++){adj.add(newArrayList<>());}for(int[]e:edges){adj.get(e[0]).add(e[1]);adj.get(e[1]).add(e[0]);}Mainblossom=newMain(adj);intmsize=blossom.solve();int[]match=blossom.getMatch();System.out.println("Maximum matching size: "+msize);System.out.println("Matched pairs:");for(intu=0;u<n;u++){intv=match[u];if(v>=0&&u<v){System.out.println(" "+u+" – "+v);}}}}

Output:

Maximum matching size: 2 Matched pairs: 0 – 1 2 – 3 

JavaScript

Translation of: C++

classBlossom{constructor(adj){this.n=adj.length;this.adj=adj;this.match=newArray(this.n).fill(-1);this.p=newArray(this.n).fill(-1);this.base=newArray(this.n);this.used=newArray(this.n).fill(false);this.blossom=newArray(this.n).fill(false);this.queue=[];}// Find least common ancestor of a and b in the alternating forestlca(a,b){constusedPath=newArray(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])returnb;b=this.p[this.match[b]];}}// Mark path from v up to base0, setting parents to xmarkPath(v,base0,x){while(this.base[v]!==base0){constmv=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 rootfindPath(root){this.used.fill(false);this.p.fill(-1);for(leti=0;i<this.n;i++){this.base[i]=i;}this.queue=[];this.used[root]=true;this.queue.push(root);while(this.queue.length>0){constv=this.queue.shift();for(constuofthis.adj[v]){// Skip same base or matched edgeif(this.base[v]===this.base[u]||this.match[v]===u){continue;}// Blossom detectedif(u===root||(this.match[u]!==-1&&this.p[this.match[u]]!==-1)){constcurbase=this.lca(v,u);this.blossom.fill(false);this.markPath(v,curbase,u);this.markPath(u,curbase,v);for(leti=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 treeelseif(this.p[u]===-1){this.p[u]=v;// If u is free, we found an augmenting pathif(this.match[u]===-1){letcur=u;while(cur!==-1){constprev=this.p[cur];constnext=prev===-1?-1:this.match[prev];this.match[cur]=prev;this.match[prev]=cur;cur=next;}returntrue;}// Enqueue the matched partnerconstmu=this.match[u];if(!this.used[mu]){this.used[mu]=true;this.queue.push(mu);}}}}returnfalse;}// Compute maximum matching; returns [matchArray, size]solve(){letsize=0;for(letv=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–0constn=5;constedges=[[0,1],[1,2],[2,3],[3,4],[4,0],];constadj=Array.from({length:n},()=>[]);for(const[u,v]ofedges){adj[u].push(v);adj[v].push(u);}constblossom=newBlossom(adj);const[match,msize]=blossom.solve();console.log(`Maximum matching size: ${msize}`);console.log("Matched pairs:");constseen=newSet();for(letu=0;u<n;u++){constv=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 

Python

fromcollectionsimportdequedefmax_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 vp=[-1]*n# parent in the alternating treebase=list(range(n))# base[u] = base vertex of blossom containing uq=deque()# queue for BFSused=[False]*n# whether vertex is in the treeblossom=[False]*n# helper array for marking blossomsdeflca(a,b):"""Find least common ancestor of a and b in the forest of alternating tree."""used_path=[False]*nwhileTrue:a=base[a]used_path[a]=Trueifmatch[a]==-1:breaka=p[match[a]]whileTrue:b=base[b]ifused_path[b]:returnbb=p[match[b]]defmark_path(v,b,x):"""Mark vertices along the path from v to base b, setting their parent to x."""whilebase[v]!=b:blossom[base[v]]=blossom[base[match[v]]]=Truep[v]=xx=match[v]v=p[x]deffind_path(root):"""Try to find an augmenting path starting from root."""# resetused[:]=[False]*np[:]=[-1]*nforiinrange(n):base[i]=iq.clear()used[root]=Trueq.append(root)whileq:v=q.popleft()foruinadj[v]:# two cases to skipifbase[v]==base[u]ormatch[v]==u:continue# found a blossom or an odd cycle edgeifu==rootor(match[u]!=-1andp[match[u]]!=-1):curbase=lca(v,u)blossom[:]=[False]*nmark_path(v,curbase,u)mark_path(u,curbase,v)# contract blossomforiinrange(n):ifblossom[base[i]]:base[i]=curbaseifnotused[i]:used[i]=Trueq.append(i)# otherwise extend the alternating treeelifp[u]==-1:p[u]=vifmatch[u]==-1:# augmenting path found: flip matches along the pathcurr=uwhilecurr!=-1:prev=p[curr]nxt=match[prev]ifprev!=-1else-1match[curr]=prevmatch[prev]=currcurr=nxtreturnTrue# else continue BFS from the matched partnerused[match[u]]=Trueq.append(match[u])returnFalse# Main loop: try to grow matching by finding augmenting pathsres=0forvinrange(n):ifmatch[v]==-1:iffind_path(v):res+=1returnmatch,resif__name__=="__main__":# Example: 5‑cycle (odd cycle)# Vertices: 0–1–2–3–4–0n=5edges=[(0,1),(1,2),(2,3),(3,4),(4,0)]adj=[[]for_inrange(n)]foru,vinedges:adj[u].append(v)adj[v].append(u)match,msize=max_matching(adj)print(f"Maximum matching size: {msize}")print("Matched pairs:")seen=set()foru,vinenumerate(match):ifv!=-1and(v,u)notinseen:print(f" {u} – {v}")seen.add((u,v))

Output:

Maximum matching size: 2 Matched pairs: 0 – 1 2 – 3 

Rust

Translation of: C++

usestd::collections::VecDeque;structBlossom{n: usize,adj: Vec<Vec<usize>>,matching: Vec<Option<usize>>,// matching[v] = Some(u) if v–u is matchedparent: Vec<Option<usize>>,// parent in the alternating treebase: Vec<usize>,// base[v] = base vertex of blossom containing vused: Vec<bool>,// used[v] = whether v is in the BFS treeblossom: Vec<bool>,// helper array for marking blossomsq: VecDeque<usize>,// BFS queue}implBlossom{fnnew(adj: Vec<Vec<usize>>)-> Self{letn=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.fnlca(&self,muta: usize,mutb: usize)-> usize{letmutused_path=vec![false;self.n];// climb from aloop{a=self.base[a];used_path[a]=true;ifletSome(ma)=self.matching[a]{ifletSome(pa)=self.parent[ma]{a=pa;continue;}}break;}// climb from b until we hit a marked vertexloop{b=self.base[b];ifused_path[b]{returnb;}ifletSome(mb)=self.matching[b]{ifletSome(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.fnmark_path(&mutself,mutv: usize,b: usize,mutx: usize){whileself.base[v]!=b{letmv=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.fnfind_path(&mutself,root: usize)-> bool{// Reset BFS stateself.used.fill(false);self.parent.fill(None);foriin0..self.n{self.base[i]=i;}self.q.clear();self.used[root]=true;self.q.push_back(root);whileletSome(v)=self.q.pop_front(){// clone neighbors to avoid borrowing self.adj across the BFS loopletneighbors=self.adj[v].clone();foruinneighbors{ifself.base[v]==self.base[u]||self.matching[v]==Some(u){continue;}// Found a blossomifu==root||(self.matching[u].is_some()&&self.parent[self.matching[u].unwrap()].is_some()){letcurbase=self.lca(v,u);self.blossom.fill(false);self.mark_path(v,curbase,u);self.mark_path(u,curbase,v);foriin0..self.n{ifself.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 treeelseifself.parent[u].is_none(){self.parent[u]=Some(v);// If u is free, we've found an augmenting pathifself.matching[u].is_none(){letmutcur=u;whileletSome(prev)=self.parent[cur]{letnext=self.matching[prev];self.matching[cur]=Some(prev);self.matching[prev]=Some(cur);ifletSome(nxt)=next{cur=nxt;}else{break;}}returntrue;}// Otherwise enqueue the matched partnerletmu=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)fnsolve(&mutself)-> (Vec<Option<usize>>,usize){letmutres=0;forvin0..self.n{ifself.matching[v].is_none()&&self.find_path(v){res+=1;}}(self.matching.clone(),res)}}fnmain(){// Example: 5‑cycle (odd cycle) 0–1–2–3–4–0letn=5;letedges=vec![(0,1),(1,2),(2,3),(3,4),(4,0)];letmutadj=vec![Vec::new();n];for&(u,v)in&edges{adj[u].push(v);adj[v].push(u);}letmutblossom=Blossom::new(adj);let(matching,msize)=blossom.solve();println!("Maximum matching size: {}",msize);println!("Matched pairs:");foruin0..n{ifletSome(v)=matching[u]{ifu<v{println!(" {} – {}",u,v);}}}}

Output:

Maximum matching size: 2 Matched pairs: 0 – 1 2 – 3 

Wren

Translation of: Python

Library:Wren-queue

Library:Wren-set

import"./queue"forDequeimport"./set"forSet/* 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*/varmaxMatching=Fn.new{|adj|varn=adj.countvarmatch=List.filled(n,-1)// match[u] = v if u is matched to vvarp=List.filled(n,-1)// parent in the alternating treevarbase=(0...n).toList// base[u] = base vertex of blossom containing uvarq=Deque.new()// queue for BFSvarused=List.filled(n,false)// whether vertex is in the treevarblossom=List.filled(n,false)// helper array for marking blossoms// Find least common ancestor of a and b in the forest of alternating tree.varlca=Fn.new{|a,b|varusedPath=List.filled(n,false)while(true){a=base[a]usedPath[a]=trueif(match[a]==-1)breaka=p[match[a]]}while(true){b=base[b]if(usedPath[b])returnbb=p[match[b]]}}// Mark vertices along the path from v to base b, setting their parent to x.varmarkPath=Fn.new{|v,b,x|while(base[v]!=b){blossom[base[v]]=blossom[base[match[v]]]=truep[v]=xx=match[v]v=p[x]}}// Try to find an augmenting path starting from root.varfindPath=Fn.new{|root|// resetused=List.filled(n,false)p=List.filled(n,-1)for(iin0...n)base[i]=iq.clear()used[root]=trueq.pushBack(root)while(!q.isEmpty){varv=q.popFront()for(uinadj[v]){// two cases to skipif(base[v]==base[u]||match[v]==u)continue// found a blossom or an odd cycle edgeif(u==root||(match[u]!=-1&&p[match[u]]!=-1)){varcurbase=lca.call(v,u)blossom=List.filled(n,false)markPath.call(v,curbase,u)markPath.call(u,curbase,v)// contract blossomfor(iin0...n){if(blossom[base[i]]){base[i]=curbaseif(!used[i]){used[i]=trueq.pushBack(i)}}}// otherwise extend the alternating tree}elseif(p[u]==-1){p[u]=vif(match[u]==-1){// augmenting path found: flip matches along the pathvarcurr=uwhile(curr!=-1){varprev=p[curr]varnext=(prev!=-1)?match[prev]:-1match[curr]=prevmatch[prev]=currcurr=next}returntrue}// else continue BFS from the matched partnerused[match[u]]=trueq.pushBack(match[u])}}}returnfalse}// Main loop: try to grow matching by finding augmenting paths.varres=0for(vin0...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–0varn=5varedges=[[0,1],[1,2],[2,3],[3,4],[4,0]]varadj=List.filled(n,null)for(iin0...n)adj[i]=[]for(einedges){varu=e[0]varv=e[1]adj[u].add(v)adj[v].add(u)}varres=maxMatching.call(adj)varmatch=res[0]varmsize=res[1]System.print("Maximum matching size: %(msize)")System.print("Matched pairs:")varseen=Set.new()varu=-1for(vinmatch){u=u+1if(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

Translation of: Rust

conststd=@import("std");constBlossom=struct{n:usize,adj:[][]usize,matching:[]?usize,// matching[v] = u if v--u is matchedparent:[]?usize,// parent in the alternating treebase:[]usize,// base[v] = base vertex of blossom containing vused:[]bool,// used[v] = whether v is in the BFS treeblossom:[]bool,// helper array for marking blossomsq:std.fifo.LinearFifo(usize,.Dynamic),// BFS queueallocator:std.mem.Allocator,fninit(allocator:std.mem.Allocator,adj:[][]usize)!Blossom{constn=adj.len;constmatching=tryallocator.alloc(?usize,n);constparent=tryallocator.alloc(?usize,n);varbase=tryallocator.alloc(usize,n);constused=tryallocator.alloc(bool,n);constblossom=tryallocator.alloc(bool,n);constq=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);returnBlossom{.n=n,.adj=adj,.matching=matching,.parent=parent,.base=base,.used=used,.blossom=blossom,.q=q,.allocator=allocator,};}fndeinit(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.fnlca(self:*constBlossom,a_in:usize,b_in:usize)usize{vara=a_in;varb=b_in;varused_path=self.allocator.alloc(bool,self.n)catchunreachable;deferself.allocator.free(used_path);@memset(used_path,false);// climb from awhile(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 vertexwhile(true){b=self.base[b];if(used_path[b]){returnb;}if(self.matching[b])|mb|{if(self.parent[mb])|pb|{b=pb;continue;}}// In a valid alternating forest this should always terminateunreachable;}}// Mark vertices along the path from v to base b, setting their parent to x.fnmarkPath(self:*Blossom,v_in:usize,b:usize,x_in:usize)void{varv=v_in;varx=x_in;while(self.base[v]!=b){constmv=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.fnfindPath(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)catchunreachable;while(self.q.readItem())|v|{for(self.adj[v])|u|{if(self.base[v]==self.base[u]orself.matching[v]==u){continue;}// Found a blossomif(u==rootor(self.matching[u]!=nullandself.parent[self.matching[u].?]!=null)){constcurbase=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)catchunreachable;}}}}// Otherwise, try to extend the alternating treeelseif(self.parent[u]==null){self.parent[u]=v;// If u is free, we've found an augmenting pathif(self.matching[u]==null){varcur=u;while(self.parent[cur])|prev|{constnext=self.matching[prev];self.matching[cur]=prev;self.matching[prev]=cur;cur=nextorelsebreak;}returntrue;}// Otherwise enqueue the matched partnerconstmu=self.matching[u].?;if(!self.used[mu]){self.used[mu]=true;self.q.writeItem(mu)catchunreachable;}}}}returnfalse;}// Main solver: returns (matching, size_of_matching)fnsolve(self:*Blossom)struct{matching:[]?usize,size:usize}{varres:usize=0;for(0..self.n)|v|{if(self.matching[v]==nullandself.findPath(v)){res+=1;}}constresult_matching=self.allocator.alloc(?usize,self.n)catchunreachable;@memcpy(result_matching,self.matching);return.{.matching=result_matching,.size=res};}};pubfnmain()!void{vargpa=std.heap.GeneralPurposeAllocator(.{}){};defer_=gpa.deinit();constallocator=gpa.allocator();// Example: 5‑cycle (odd cycle) 0--1--2--3--4--0constn:usize=5;constedges=[_][2]usize{.{0,1},.{1,2},.{2,3},.{3,4},.{4,0}};varadj=tryallocator.alloc([]usize,n);defer{for(adj)|neighbors|{allocator.free(neighbors);}allocator.free(adj);}// Initialize empty adjacency listsfor(0..n)|i|{adj[i]=tryallocator.alloc(usize,0);}// Count neighbors for each vertexvarcounts=tryallocator.alloc(usize,n);deferallocator.free(counts);@memset(counts,0);for(edges)|edge|{counts[edge[0]]+=1;counts[edge[1]]+=1;}// Allocate space for neighborsfor(0..n)|i|{allocator.free(adj[i]);adj[i]=tryallocator.alloc(usize,counts[i]);counts[i]=0;// Reset to use as index}// Fill adjacency listsfor(edges)|edge|{constu=edge[0];constv=edge[1];adj[u][counts[u]]=v;counts[u]+=1;adj[v][counts[v]]=u;counts[v]+=1;}varblossom=tryBlossom.init(allocator,adj);deferblossom.deinit();constresult=blossom.solve();deferallocator.free(result.matching);conststdout=std.io.getStdOut().writer();trystdout.print("Maximum matching size: {d}\n",.{result.size});trystdout.print("Matched pairs:\n",.{});for(0..n)|u|{if(result.matching[u])|v|{if(u<v){trystdout.print(" {d} -- {d}\n",.{u,v});}}}}

Output:

Maximum matching size: 2 Matched pairs: 0 -- 1 2 -- 3