|
INPUT: Graph ''G'', matching ''M'' on ''G''
OUTPUT: augmenting path ''P'' in ''G'' or empty path if none found
01B01 '''function''' ''find_augmenting_path''( ''G'', ''M'' ) : ''P''
02B02 ''F'' ← empty forest
03B03 unmark all vertices and edges in ''G'', mark all edges of ''M''
05B05 '''for each''' exposed vertex ''v'' '''do'''
06B06 create a singleton tree { ''v'' } and add the tree to ''F''
07B07 '''end for'''
08B08 '''while''' there is an unmarked vertex ''v'' in ''F'' with ''distance( v, root( v ) )'' even '''do'''
09B09 '''while''' there exists an unmarked edge ''e'' = { ''v'', ''w'' } '''do'''
10B10 '''if''' ''w'' is not in ''F'' '''then'''
// ''w'' is matched, so add ''e'' and ''w'''s matched edge to ''F''
11B11 ''x'' ← vertex matched to ''w'' in ''M''
12B12 add edges { ''v'', ''w'' } and { ''w'', ''x'' } to the tree of ''v''
13B13 '''else'''
14B14 '''if''' ''distance( w, root( w ) )'' is odd '''then'''
// Do nothing.
15B15 '''else'''
16B16 '''if''' ''root( v )'' ≠ ''root( w )'' '''then'''
// Report an augmenting path in F <math>\cup</math> { ''e'' }.
17B17 ''P'' ← path ( ''root''( ''v'' ) → ... → ''v'' ) → ( ''w'' → ... → ''root''( ''w'' ) )
18B18 '''return''' ''P''
19B19 '''else'''
// Contract a blossom in ''G'' and look for the path in the contracted graph.
20B20 ''B'' ← blossom formed by ''e'' and edges on the path ''v'' → ''w'' in ''T''
21B21 ''G’, M’'' ← contract ''G'' and ''M'' by ''B''
22B22 ''P’'' ← ''find_augmenting_path''( ''G’'', ''M’'' )
23B23 ''P'' ← lift ''P’'' to ''G''
24B24 '''return''' ''P''
25B25 '''end if'''
26B26 '''end if'''
27B27 '''end if'''
28B28 mark edge ''e''
29B29 '''end while'''
30B30 mark vertex ''v''
31B31 '''end while'''
32B32 '''return''' empty path
33B33 '''end function'''
===Examples===
| 