| /**CFile**************************************************************** |
| |
| FileName [extraUtilBitMatrix.c] |
| |
| PackageName [extra] |
| |
| Synopsis [Various reusable software utilities.] |
| |
| Author [Alan Mishchenko] |
| |
| Affiliation [UC Berkeley] |
| |
| Date [Ver. 1.0. Started - September 1, 2003.] |
| |
| Revision [$Id: extraUtilBitMatrix.c,v 1.0 2003/09/01 00:00:00 alanmi Exp $] |
| |
| ***********************************************************************/ |
| |
| #include "extra.h" |
| |
| ABC_NAMESPACE_IMPL_START |
| |
| |
| /*---------------------------------------------------------------------------*/ |
| /* Constant declarations */ |
| /*---------------------------------------------------------------------------*/ |
| |
| /*---------------------------------------------------------------------------*/ |
| /* Stucture declarations */ |
| /*---------------------------------------------------------------------------*/ |
| |
| struct Extra_BitMat_t_ |
| { |
| 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 |
| }; |
| |
| /*---------------------------------------------------------------------------*/ |
| /* Type declarations */ |
| /*---------------------------------------------------------------------------*/ |
| |
| /*---------------------------------------------------------------------------*/ |
| /* Variable declarations */ |
| /*---------------------------------------------------------------------------*/ |
| |
| /*---------------------------------------------------------------------------*/ |
| /* Macro declarations */ |
| /*---------------------------------------------------------------------------*/ |
| |
| |
| /**AutomaticStart*************************************************************/ |
| |
| /*---------------------------------------------------------------------------*/ |
| /* Static function prototypes */ |
| /*---------------------------------------------------------------------------*/ |
| |
| /**AutomaticEnd***************************************************************/ |
| |
| |
| /*---------------------------------------------------------------------------*/ |
| /* Definition of exported functions */ |
| /*---------------------------------------------------------------------------*/ |
| |
| /**Function************************************************************* |
| |
| Synopsis [Starts the bit matrix.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Extra_BitMat_t * Extra_BitMatrixStart( int nSize ) |
| { |
| Extra_BitMat_t * p; |
| int i; |
| p = ABC_ALLOC( Extra_BitMat_t, 1 ); |
| memset( p, 0, sizeof(Extra_BitMat_t) ); |
| p->nSize = nSize; |
| p->nBitShift = (sizeof(unsigned) == 4) ? 5: 6; |
| p->uMask = (sizeof(unsigned) == 4) ? 31: 63; |
| p->nWords = nSize / (8 * sizeof(unsigned)) + ((nSize % (8 * sizeof(unsigned))) > 0); |
| p->ppData = ABC_ALLOC( unsigned *, nSize ); |
| p->ppData[0] = ABC_ALLOC( unsigned, nSize * p->nWords ); |
| memset( p->ppData[0], 0, sizeof(unsigned) * nSize * p->nWords ); |
| for ( i = 1; i < nSize; i++ ) |
| p->ppData[i] = p->ppData[i-1] + p->nWords; |
| return p; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Stops the bit matrix.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Extra_BitMatrixClean( Extra_BitMat_t * p ) |
| { |
| memset( p->ppData[0], 0, sizeof(unsigned) * p->nSize * p->nWords ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Stops the bit matrix.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Extra_BitMatrixStop( Extra_BitMat_t * p ) |
| { |
| ABC_FREE( p->ppData[0] ); |
| ABC_FREE( p->ppData ); |
| ABC_FREE( p ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Prints the bit-matrix.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Extra_BitMatrixPrint( Extra_BitMat_t * pMat ) |
| { |
| int i, k, nVars; |
| printf( "\n" ); |
| nVars = Extra_BitMatrixReadSize( pMat ); |
| for ( i = 0; i < nVars; i++ ) |
| { |
| for ( k = 0; k <= i; k++ ) |
| printf( " " ); |
| for ( k = i+1; k < nVars; k++ ) |
| if ( Extra_BitMatrixLookup1( pMat, i, k ) ) |
| printf( "1" ); |
| else |
| printf( "." ); |
| printf( "\n" ); |
| } |
| } |
| |
| |
| /**Function************************************************************* |
| |
| Synopsis [Reads the matrix size.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Extra_BitMatrixReadSize( Extra_BitMat_t * p ) |
| { |
| return p->nSize; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Inserts the element into the upper part.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Extra_BitMatrixInsert1( Extra_BitMat_t * p, int i, int k ) |
| { |
| p->nInserts++; |
| if ( i < k ) |
| p->ppData[i][k>>p->nBitShift] |= (1<<(k & p->uMask)); |
| else |
| p->ppData[k][i>>p->nBitShift] |= (1<<(i & p->uMask)); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Inserts the element into the upper part.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Extra_BitMatrixLookup1( Extra_BitMat_t * p, int i, int k ) |
| { |
| p->nLookups++; |
| if ( i < k ) |
| return ((p->ppData[i][k>>p->nBitShift] & (1<<(k & p->uMask))) > 0); |
| else |
| return ((p->ppData[k][i>>p->nBitShift] & (1<<(i & p->uMask))) > 0); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Inserts the element into the upper part.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Extra_BitMatrixDelete1( Extra_BitMat_t * p, int i, int k ) |
| { |
| p->nDeletes++; |
| if ( i < k ) |
| p->ppData[i][k>>p->nBitShift] &= ~(1<<(k & p->uMask)); |
| else |
| p->ppData[k][i>>p->nBitShift] &= ~(1<<(i & p->uMask)); |
| } |
| |
| |
| |
| /**Function************************************************************* |
| |
| Synopsis [Inserts the element into the upper part.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Extra_BitMatrixInsert2( Extra_BitMat_t * p, int i, int k ) |
| { |
| p->nInserts++; |
| if ( i > k ) |
| p->ppData[i][k>>p->nBitShift] |= (1<<(k & p->uMask)); |
| else |
| p->ppData[k][i>>p->nBitShift] |= (1<<(i & p->uMask)); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Inserts the element into the upper part.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Extra_BitMatrixLookup2( Extra_BitMat_t * p, int i, int k ) |
| { |
| p->nLookups++; |
| if ( i > k ) |
| return ((p->ppData[i][k>>p->nBitShift] & (1<<(k & p->uMask))) > 0); |
| else |
| return ((p->ppData[k][i>>p->nBitShift] & (1<<(i & p->uMask))) > 0); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Inserts the element into the upper part.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Extra_BitMatrixDelete2( Extra_BitMat_t * p, int i, int k ) |
| { |
| p->nDeletes++; |
| if ( i > k ) |
| p->ppData[i][k>>p->nBitShift] &= ~(1<<(k & p->uMask)); |
| else |
| p->ppData[k][i>>p->nBitShift] &= ~(1<<(i & p->uMask)); |
| } |
| |
| |
| /**Function************************************************************* |
| |
| Synopsis [Inserts the element into the upper part.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Extra_BitMatrixOr( Extra_BitMat_t * p, int i, unsigned * pInfo ) |
| { |
| int w; |
| for ( w = 0; w < p->nWords; w++ ) |
| p->ppData[i][w] |= pInfo[w]; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Inserts the element into the upper part.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Extra_BitMatrixOrTwo( Extra_BitMat_t * p, int i, int j ) |
| { |
| int w; |
| for ( w = 0; w < p->nWords; w++ ) |
| p->ppData[i][w] = p->ppData[j][w] = (p->ppData[i][w] | p->ppData[j][w]); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Counts the number of 1's in the upper rectangle.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Extra_BitMatrixCountOnesUpper( Extra_BitMat_t * p ) |
| { |
| int i, k, nTotal = 0; |
| for ( i = 0; i < p->nSize; i++ ) |
| for ( k = i + 1; k < p->nSize; k++ ) |
| nTotal += ( (p->ppData[i][k>>5] & (1 << (k&31))) > 0 ); |
| 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 /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| |
| ABC_NAMESPACE_IMPL_END |
| |
