Blossom algorithm: Difference between revisions

Revision as of 08:45, 30 September 2020

Revision as of 09:12, 30 September 2020

Line 68:

INPUT: Graph ''G'', initial matching ''M'' on ''G''

OUTPUT: maximum matching ''M*'' on ''G''

A1 '''function''' ''find_maximum_matching''( ''G'', ''M'' ) : ''M*''

A2 ''P'' ← ''find_augmenting_path''( ''G'', ''M'' )

A3 '''if''' ''P'' is non-empty '''then'''

A4 '''return''' ''find_maximum_matching''( ''G'', augment ''M'' along ''P'' )

A5 '''else'''

A6 '''return''' M

A7 '''end if'''

A8 '''end function'''

Line 119:

INPUT: Graph ''G'', matching ''M'' on ''G''

OUTPUT: augmenting path ''P'' in ''G'' or empty path if none found

B01 '''function''' ''find_augmenting_path''( ''G'', ''M'' ) : ''P''

B02 ''F'' ← empty forest

B03 unmark all vertices and edges in ''G'', mark all edges of ''M''

Line 125:

B06 create a singleton tree { ''v'' } and add the tree to ''F''

B07 '''end for'''

B08 '''while''' there is an unmarked vertex ''v'' in ''F'' with ''distance( v, root( v ) )'' even '''do'''

B09 '''while''' there exists an unmarked edge ''e'' = { ''v'', ''w'' } '''do'''

B10 '''if''' ''w'' is not in ''F'' '''then'''

Line 132:

B12 add edges { ''v'', ''w'' } and { ''w'', ''x'' } to the tree of ''v''

B13 '''else'''

B14 '''if''' ''distance( w, root( w ) )'' is odd '''then'''

// Do nothing.

B15 '''else'''

B16 '''if''' ''root( v )'' ≠ ''root( w )'' '''then'''

// Report an augmenting path in F <math>\cup</math> { ''e'' }.

B17 ''P'' ← path ( ''root''( ''v'' ) → ... → ''v'' ) → ( ''w'' → ... → ''root''( ''w'' ) )

B18 '''return''' ''P''

B19 '''else'''

Line 143:

B20 ''B'' ← blossom formed by ''e'' and edges on the path ''v'' → ''w'' in ''T''

B21 ''G’, M’'' ← contract ''G'' and ''M'' by ''B''

B22 ''P’'' ← ''find_augmenting_path''( ''G’'', ''M’'' )

B23 ''P'' ← lift ''P’'' to ''G''

B24 '''return''' ''P''