boolean arbitaryMatching ( final int [ ] [ ] graph , final BitSet subset ) { final BitSet unmatched = new BitSet ( ) ; // indicates the deg of each vertex in unmatched subset final int [ ] deg = new int [ graph . length ] ; // queue/stack of vertices with deg1 vertices final int [ ] deg1 = new int [ graph . length ] ; int nd1 = 0 , nMatched = 0 ; for ( int v = subset . nextSetBit ( 0 ) ; v >= 0 ; v = subset . nextSetBit ( v + 1 ) ) { if ( matched ( v ) ) { assert subset . get ( other ( v ) ) ; nMatched ++ ; continue ; } unmatched . set ( v ) ; for ( int w : graph [ v ] ) if ( subset . get ( w ) && unmatched ( w ) ) deg [ v ] ++ ; if ( deg [ v ] == 1 ) deg1 [ nd1 ++ ] = v ; } while ( ! unmatched . isEmpty ( ) ) { int v = - 1 ; // attempt to select a vertex with degree = 1 (in matched set) while ( nd1 > 0 ) { v = deg1 [ -- nd1 ] ; if ( unmatched . get ( v ) ) break ; } // no unmatched degree 1 vertex, select the first unmatched if ( v < 0 || unmatched . get ( v ) ) v = unmatched . nextSetBit ( 0 ) ; unmatched . clear ( v ) ; // find a unmatched edge and match it, adjacent degrees are updated for ( final int w : graph [ v ] ) { if ( unmatched . get ( w ) ) { match ( v , w ) ; nMatched += 2 ; unmatched . clear ( w ) ; // update neighbors of w and v (if needed) for ( final int u : graph [ w ] ) if ( -- deg [ u ] == 1 && unmatched . get ( u ) ) deg1 [ nd1 ++ ] = u ; // if deg == 1, w is the only neighbor if ( deg [ v ] > 1 ) { for ( final int u : graph [ v ] ) if ( -- deg [ u ] == 1 && unmatched . get ( u ) ) deg1 [ nd1 ++ ] = u ; } break ; } } } return nMatched == subset . cardinality ( ) ; }
Assign an arbitrary matching that covers the subset of vertices .