/**CFile**************************************************************** FileName [extraZddTrunc.c] PackageName [extra] Synopsis [Procedure to truncate a ZDD using variable probabilities.] Author [Alan Mishchenko] Affiliation [UC Berkeley] Date [Ver. 2.0. Started - September 1, 2003.] Revision [$Id: extraZddTrunc.c,v 1.0 2003/05/21 18:03:50 alanmi Exp $] ***********************************************************************/ #include #include #include #include #include "misc/st/st.h" #include "bdd/cudd/cuddInt.h" #ifdef _WIN32 #define inline __inline // compatible with MS VS 6.0 #endif ABC_NAMESPACE_IMPL_START #define TEST_VAR_MAX 10 #define TEST_SET_MAX 10 /*---------------------------------------------------------------------------*/ /* Constant declarations */ /*---------------------------------------------------------------------------*/ /*---------------------------------------------------------------------------*/ /* Stucture declarations */ /*---------------------------------------------------------------------------*/ /*---------------------------------------------------------------------------*/ /* Type declarations */ /*---------------------------------------------------------------------------*/ /*---------------------------------------------------------------------------*/ /* Variable declarations */ /*---------------------------------------------------------------------------*/ /*---------------------------------------------------------------------------*/ /* Macro declarations */ /*---------------------------------------------------------------------------*/ /**AutomaticStart*************************************************************/ /*---------------------------------------------------------------------------*/ /* Static function prototypes */ /*---------------------------------------------------------------------------*/ // dynamic vector of intergers typedef struct Vec_Int_t_ Vec_Int_t; struct Vec_Int_t_ { int nCap; int nSize; int * pArray; }; static inline Vec_Int_t * Vec_IntAlloc( int nCap ) { Vec_Int_t * p; p = ABC_ALLOC( Vec_Int_t, 1 ); if ( nCap > 0 && nCap < 16 ) nCap = 16; p->nSize = 0; p->nCap = nCap; p->pArray = p->nCap? ABC_ALLOC( int, p->nCap ) : NULL; return p; } static inline void Vec_IntFree( Vec_Int_t * p ) { ABC_FREE( p->pArray ); ABC_FREE( p ); } static inline int * Vec_IntReleaseArray( Vec_Int_t * p ) { int * pArray = p->pArray; p->nCap = 0; p->nSize = 0; p->pArray = NULL; return pArray; } static inline int Vec_IntAddToEntry( Vec_Int_t * p, int i, int Addition ) { assert( i >= 0 && i < p->nSize ); return p->pArray[i] += Addition; } static inline void Vec_IntGrow( Vec_Int_t * p, int nCapMin ) { if ( p->nCap >= nCapMin ) return; p->pArray = ABC_REALLOC( int, p->pArray, nCapMin ); assert( p->pArray ); p->nCap = nCapMin; } static inline int Vec_IntPop( Vec_Int_t * p ) { assert( p->nSize > 0 ); return p->pArray[--p->nSize]; } static inline void Vec_IntPush( Vec_Int_t * p, int Entry ) { if ( p->nSize == p->nCap ) { if ( p->nCap < 16 ) Vec_IntGrow( p, 16 ); else Vec_IntGrow( p, 2 * p->nCap ); } p->pArray[p->nSize++] = Entry; } static inline void Vec_IntAppend( Vec_Int_t * vVec1, Vec_Int_t * vVec2 ) { int i; for ( i = 0; i < vVec2->nSize; i++ ) Vec_IntPush( vVec1, vVec2->pArray[i] ); } /**AutomaticEnd***************************************************************/ /*---------------------------------------------------------------------------*/ /* Definition of exported functions */ /*---------------------------------------------------------------------------*/ /**Function******************************************************************** Synopsis [Compute the set of subsets whose probability is more than ProbLimit.] Description [The resulting array has the following form: The first integer entry is the number of resulting subsets. The following integer entries in the array contain as many subsets. Each subset is an array of integers followed by -1. See how subsets are printed in the included test procedure below.] SideEffects [] SeeAlso [] ******************************************************************************/ void Extra_zddTruncate_rec( DdManager * dd, DdNode * zFunc, // zFunc is the ZDD to be truncated double * pVarProbs, // pVarProbs is probabilities of each variable (should have at least dd->sizeZ entries) double ProbLimit, // ProbLimit is the limit on the probabilities (only those more than this will be collected) double ProbThis, // current path probability Vec_Int_t * vSubset, // current subset under construction Vec_Int_t * vResult ) // resulting subsets to be returned to the user { // quit if probability of the path is less then the limit if ( ProbThis < ProbLimit ) return; // quit if there is no subsets if ( zFunc == Cudd_ReadZero(dd) ) return; // quit and save a new subset if there is one if ( zFunc == Cudd_ReadOne(dd) ) { Vec_IntAddToEntry( vResult, 0, 1 ); Vec_IntAppend( vResult, vSubset ); Vec_IntPush( vResult, -1 ); return; } // call recursively for the set without the given variable Extra_zddTruncate_rec( dd, cuddE(zFunc), pVarProbs, ProbLimit, ProbThis, vSubset, vResult ); // call recursively for the set with the given variable Vec_IntPush( vSubset, Cudd_NodeReadIndex(zFunc) ); Extra_zddTruncate_rec( dd, cuddT(zFunc), pVarProbs, ProbLimit, ProbThis * pVarProbs[Cudd_NodeReadIndex(zFunc)], vSubset, vResult ); Vec_IntPop( vSubset ); } int * Extra_zddTruncate( DdManager * dd, DdNode * zFunc, // zFunc is the ZDD to be truncated double * pVarProbs, // pVarProbs is probabilities of each variable (should have at least dd->sizeZ entries) double ProbLimit ) // ProbLimit is the limit on the probabilities (only those more than this will be collected) { Vec_Int_t * vSubset, * vResult; int i, sizeZ = Cudd_ReadZddSize(dd); int * pResult; // check that probabilities are reasonable assert( ProbLimit > 0 && ProbLimit <= 1 ); for ( i = 0; i < sizeZ; i++ ) assert( pVarProbs[i] > 0 && pVarProbs[i] <= 1 ); // enumerate assignments satisfying the probability limit vSubset = Vec_IntAlloc( sizeZ ); vResult = Vec_IntAlloc( 10 * sizeZ ); Vec_IntPush( vResult, 0 ); Extra_zddTruncate_rec( dd, zFunc, pVarProbs, ProbLimit, 1, vSubset, vResult ); Vec_IntFree( vSubset ); pResult = Vec_IntReleaseArray( vResult ); Vec_IntFree( vResult ); return pResult; } // end of Extra_zddTruncate /**Function************************************************************* Synopsis [Creates the combination composed of a single ZDD variable.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ DdNode * Extra_zddVariable( DdManager * dd, int iVar ) { DdNode * zRes; do { dd->reordered = 0; zRes = cuddZddGetNode( dd, iVar, Cudd_ReadOne(dd), Cudd_ReadZero(dd) ); } while (dd->reordered == 1); return zRes; } /**Function******************************************************************** Synopsis [Creates ZDD representing a given set of subsets.] Description [] SideEffects [] SeeAlso [] ******************************************************************************/ DdNode * Extra_zddCreateSubsets( DdManager * dd, int pSubsets[][TEST_VAR_MAX+1], int nSubsets ) { int i, k; DdNode * zOne, * zVar, * zRes, * zTemp; zRes = Cudd_ReadZero(dd); Cudd_Ref( zRes ); for ( i = 0; i < nSubsets; i++ ) { zOne = Cudd_ReadOne(dd); Cudd_Ref( zOne ); for ( k = 0; pSubsets[i][k] != -1; k++ ) { assert( pSubsets[i][k] < TEST_VAR_MAX ); zVar = Extra_zddVariable( dd, pSubsets[i][k] ); zOne = Cudd_zddUnateProduct( dd, zTemp = zOne, zVar ); Cudd_Ref( zOne ); Cudd_RecursiveDerefZdd( dd, zTemp ); } zRes = Cudd_zddUnion( dd, zRes, zOne ); Cudd_Ref( zRes ); Cudd_RecursiveDerefZdd( dd, zOne ); } Cudd_Deref( zRes ); return zRes; } /**Function******************************************************************** Synopsis [Prints a set of subsets represented using as an array.] Description [] SideEffects [] SeeAlso [] ******************************************************************************/ void Extra_zddPrintSubsets( int * pSubsets ) { int i, k, Counter = 0; printf( "The set contains %d subsets:\n", pSubsets[0] ); for ( i = k = 0; i < pSubsets[0]; i++ ) { printf( "Subset %3d : {", Counter ); for ( k++; pSubsets[k] != -1; k++ ) printf( " %d", pSubsets[k] ); printf( " }\n" ); Counter++; } } /**Function******************************************************************** Synopsis [Testbench for the above truncation procedure.] Description [] SideEffects [] SeeAlso [] ******************************************************************************/ void Extra_zddTruncateTest() { // input data int nSubsets = 5; int pSubsets[TEST_SET_MAX][TEST_VAR_MAX+1] = { {0, 3, 5, -1}, {1, 2, 3, 6, 9, -1}, {1, 5, 7, 8, -1}, {2, 4, -1}, {0, 5, 6, 9, -1} }; // varible probabilities double pVarProbs[TEST_VAR_MAX] = { 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1 }; double ProbLimit = 0.001; // output data int * pOutput; // start the manager and create ZDD representing the input subsets DdManager * dd = Cudd_Init( 0, TEST_VAR_MAX, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS , 0 ); DdNode * zFunc = Extra_zddCreateSubsets( dd, pSubsets, nSubsets ); Cudd_Ref( zFunc ); assert( nSubsets <= TEST_SET_MAX ); // print the input ZDD printf( "The initial ZDD representing %d subsets:\n", nSubsets ); Cudd_zddPrintMinterm( dd, zFunc ); // compute the result of truncation pOutput = Extra_zddTruncate( dd, zFunc, pVarProbs, ProbLimit ); // print the resulting ZDD printf( "The resulting ZDD representing %d subsets:\n", pOutput[0] ); // print the resulting subsets Extra_zddPrintSubsets( pOutput ); // cleanup ABC_FREE( pOutput ); Cudd_RecursiveDerefZdd( dd, zFunc ); Cudd_Quit( dd ); } //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// ABC_NAMESPACE_IMPL_END