|
INPUT: Graph ''G'', matching ''M'' on ''G''
OUTPUT: augmenting path ''P'' in ''G'' or empty path if none found
B0101 '''function''' ''find_augmenting_path''( ''G'', ''M'' ) : ''P''
B0202 ''F'' ← empty forest
B0303 unmark all vertices and edges in ''G'', mark all edges of ''M''
B0505 '''for each''' exposed vertex ''v'' '''do'''
B0606 create a singleton tree { ''v'' } and add the tree to ''F''
B0707 '''end for'''
B0808 '''while''' there is an unmarked vertex ''v'' in ''F'' with ''distance( v, root( v ) )'' even '''do'''
B0909 '''while''' there exists an unmarked edge ''e'' = { ''v'', ''w'' } '''do'''
B1010 '''if''' ''w'' is not in ''F'' '''then'''
// ''w'' is matched, so add ''e'' and ''w'''s matched edge to ''F''
B1111 ''x'' ← vertex matched to ''w'' in ''M''
B1212 add edges { ''v'', ''w'' } and { ''w'', ''x'' } to the tree of ''v''
B1313 '''else'''
B1414 '''if''' ''distance( w, root( w ) )'' is odd '''then'''
// Do nothing.
B1515 '''else'''
B1616 '''if''' ''root( v )'' ≠ ''root( w )'' '''then'''
// Report an augmenting path in F <math>\cup</math> { ''e'' }.
B1717 ''P'' ← path ( ''root''( ''v'' ) → ... → ''v'' ) → ( ''w'' → ... → ''root''( ''w'' ) )
B1818 '''return''' ''P''
B1919 '''else'''
// Contract a blossom in ''G'' and look for the path in the contracted graph.
B2020 ''B'' ← blossom formed by ''e'' and edges on the path ''v'' → ''w'' in ''T''
B2121 ''G’, M’'' ← contract ''G'' and ''M'' by ''B''
B2222 ''P’'' ← ''find_augmenting_path''( ''G’'', ''M’'' )
B2323 ''P'' ← lift ''P’'' to ''G''
B2424 '''return''' ''P''
B2525 '''end if'''
B2626 '''end if'''
B2727 '''end if'''
B2828 mark edge ''e''
B2929 '''end while'''
B3030 mark vertex ''v''
B3131 '''end while'''
B3232 '''return''' empty path
B3333 '''end function'''
===Examples===
| 