diff options
Diffstat (limited to 'src/misc/extra')
| -rw-r--r-- | src/misc/extra/extra.h | 2 | ||||
| -rw-r--r-- | src/misc/extra/extraUtilBitMatrix.c | 72 |
2 files changed, 66 insertions, 8 deletions
diff --git a/src/misc/extra/extra.h b/src/misc/extra/extra.h index 14a3d950..f36b113f 100644 --- a/src/misc/extra/extra.h +++ b/src/misc/extra/extra.h @@ -185,6 +185,8 @@ extern void Extra_BitMatrixDelete2( Extra_BitMat_t * p, int i, int k ); extern void Extra_BitMatrixOr( Extra_BitMat_t * p, int i, unsigned * pInfo ); extern void Extra_BitMatrixOrTwo( Extra_BitMat_t * p, int i, int j ); extern int Extra_BitMatrixCountOnesUpper( Extra_BitMat_t * p ); +extern int Extra_BitMatrixIsDisjoint( Extra_BitMat_t * p1, Extra_BitMat_t * p2 ); +extern int Extra_BitMatrixIsClique( Extra_BitMat_t * p ); /*=== extraUtilFile.c ========================================================*/ diff --git a/src/misc/extra/extraUtilBitMatrix.c b/src/misc/extra/extraUtilBitMatrix.c index f0532dba..93cbbeac 100644 --- a/src/misc/extra/extraUtilBitMatrix.c +++ b/src/misc/extra/extraUtilBitMatrix.c @@ -28,14 +28,14 @@ struct Extra_BitMat_t_ { - unsigned ** ppData; - int nSize; - int nWords; - int nBitShift; - unsigned uMask; - int nLookups; - int nInserts; - int nDeletes; + unsigned ** ppData; // bit data + int nSize; // the number of bits in one dimension + int nWords; // the number of words in one dimension + int nBitShift; // the number of bits to shift to get words + unsigned uMask; // the mask to get the number of bits in the word + int nLookups; // the number of lookups + int nInserts; // the number of inserts + int nDeletes; // the number of deletions }; /*---------------------------------------------------------------------------*/ @@ -352,6 +352,62 @@ int Extra_BitMatrixCountOnesUpper( Extra_BitMat_t * p ) return nTotal; } +/**Function************************************************************* + + Synopsis [Returns 1 if the matrices have no entries in common.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Extra_BitMatrixIsDisjoint( Extra_BitMat_t * p1, Extra_BitMat_t * p2 ) +{ + int i, w; + assert( p1->nSize == p2->nSize ); + for ( i = 0; i < p1->nSize; i++ ) + for ( w = 0; w < p1->nWords; w++ ) + if ( p1->ppData[i][w] & p2->ppData[i][w] ) + return 0; + return 1; +} + +/**Function************************************************************* + + Synopsis [Returns 1 if the matrix is a set of cliques.] + + Description [For example pairwise symmetry info should satisfy this property.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Extra_BitMatrixIsClique( Extra_BitMat_t * pMat ) +{ + int v, u, i; + for ( v = 0; v < pMat->nSize; v++ ) + for ( u = v+1; u < pMat->nSize; u++ ) + { + if ( !Extra_BitMatrixLookup1( pMat, v, u ) ) + continue; + // v and u are symmetric + for ( i = 0; i < pMat->nSize; i++ ) + { + if ( i == v || i == u ) + continue; + // i is neither v nor u + // the symmetry status of i is the same w.r.t. to v and u + if ( Extra_BitMatrixLookup1( pMat, i, v ) != Extra_BitMatrixLookup1( pMat, i, u ) ) + return 0; + } + } + return 1; +} + + //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// |