public boolean perfect ( int [ ] [ ] graph , BitSet subset ) { if ( graph . length != match . length || subset . cardinality ( ) > graph . length ) throw new IllegalArgumentException ( "graph and matching had different capacity" ) ; // and odd set can never provide a perfect matching if ( ( subset . cardinality ( ) & 0x1 ) == 0x1 ) return false ; // arbitrary matching was perfect if ( arbitaryMatching ( graph , subset ) ) return true ; EdmondsMaximumMatching . maxamise ( this , graph , subset ) ; // the matching is imperfect if any vertex was for ( int v = subset . nextSetBit ( 0 ) ; v >= 0 ; v = subset . nextSetBit ( v + 1 ) ) if ( unmatched ( v ) ) return false ; return true ; }
Attempt to augment the matching such that it is perfect over the subset of vertices in the provided graph .