summaryrefslogtreecommitdiffstats
path: root/src/misc/extra
diff options
context:
space:
mode:
Diffstat (limited to 'src/misc/extra')
-rw-r--r--src/misc/extra/extra.h2
-rw-r--r--src/misc/extra/extraUtilBitMatrix.c72
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 ///
////////////////////////////////////////////////////////////////////////