private boolean augment ( ) { // reset data structures Arrays . fill ( even , NIL ) ; Arrays . fill ( odd , NIL ) ; dsf = new DisjointSetForest ( graph . length ) ; bridges . clear ( ) ; queue . clear ( ) ; // enqueue every unmatched vertex and place in the // even level (level = 0) for ( int v = 0 ; v < graph . length ; v ++ ) { if ( subset . get ( v ) && matching . unmatched ( v ) ) { even [ v ] = v ; queue . add ( v ) ; } } // for each 'free' vertex, start a bfs search while ( ! queue . isEmpty ( ) ) { int v = queue . remove ( 0 ) ; for ( int w : graph [ v ] ) { if ( ! subset . get ( w ) ) continue ; // the endpoints of the edge are both at even levels in the // forest - this means it is either an augmenting path or // a blossom if ( even [ dsf . getRoot ( w ) ] != NIL ) { if ( check ( v , w ) ) return true ; } // add the edge to the forest if is not already and extend // the tree with this matched edge else if ( odd [ w ] == NIL ) { odd [ w ] = v ; int u = matching . other ( w ) ; // add the matched edge (potential though a blossom) if it // isn't in the forest already if ( even [ dsf . getRoot ( u ) ] == NIL ) { even [ u ] = w ; queue . add ( u ) ; } } } } // no augmenting paths, matching is maximum return false ; }
Find an augmenting path an alternate it s matching . If an augmenting path was found then the search must be restarted . If a blossom was detected the blossom is contracted and the search continues .