From b8556e7edf263b266e3028901c276f925be5f470 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Sat, 25 Oct 2014 17:55:35 -0700 Subject: New command &satenum to enumerate SAT assignments of a miter in a naive way. --- src/aig/gia/giaQbf.c | 59 ++++++++++++++++++++++++++++++++++++++++++++ src/base/abci/abc.c | 69 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 128 insertions(+) diff --git a/src/aig/gia/giaQbf.c b/src/aig/gia/giaQbf.c index 7de3d587..a14ec443 100644 --- a/src/aig/gia/giaQbf.c +++ b/src/aig/gia/giaQbf.c @@ -54,6 +54,65 @@ extern Cnf_Dat_t * Mf_ManGenerateCnf( Gia_Man_t * pGia, int nLutSize, int fCnfOb /// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// +/**Function************************************************************* + + Synopsis [Naive way to enumerate SAT assignments.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Gia_ManSatEnum( Gia_Man_t * pGia, int nConfLimit, int nTimeOut, int fVerbose ) +{ + Cnf_Dat_t * pCnf; + sat_solver * pSat; + Vec_Int_t * vLits; + int i, iLit, iParVarBeg, Iter; + int nSolutions = 0, RetValue = 0; + abctime clkStart = Abc_Clock(); + pCnf = Mf_ManGenerateCnf( pGia, 8, 0, 1, 0 ); + pSat = (sat_solver *)Cnf_DataWriteIntoSolver( pCnf, 1, 0 ); + iParVarBeg = pCnf->nVars - Gia_ManPiNum(pGia) - 1; + Cnf_DataFree( pCnf ); + // iterate through the SAT assignment + vLits = Vec_IntAlloc( Gia_ManPiNum(pGia) ); + for ( Iter = 1 ; ; Iter++ ) + { + int status = sat_solver_solve( pSat, NULL, NULL, (ABC_INT64_T)nConfLimit, 0, 0, 0 ); + if ( status == l_False ) { RetValue = 1; break; } + if ( status == l_Undef ) { RetValue = 0; break; } + nSolutions++; + // extract SAT assignment + Vec_IntClear( vLits ); + for ( i = 0; i < Gia_ManPiNum(pGia); i++ ) + Vec_IntPush( vLits, Abc_Var2Lit(iParVarBeg+i, sat_solver_var_value(pSat, iParVarBeg+i)) ); + if ( fVerbose ) + { + printf( "%5d : ", Iter ); + Vec_IntForEachEntry( vLits, iLit, i ) + printf( "%d", !Abc_LitIsCompl(iLit) ); + printf( "\n" ); + } + // add clause + if ( !sat_solver_addclause( pSat, Vec_IntArray(vLits), Vec_IntArray(vLits) + Vec_IntSize(vLits) ) ) + { RetValue = 1; break; } + if ( nTimeOut && (Abc_Clock() - clkStart)/CLOCKS_PER_SEC >= nTimeOut ) { RetValue = 0; break; } + } + sat_solver_delete( pSat ); + Vec_IntFree( vLits ); + if ( nTimeOut && (Abc_Clock() - clkStart)/CLOCKS_PER_SEC >= nTimeOut ) + printf( "Enumerated %d assignments when timeout (%d sec) was reached. ", nSolutions, nTimeOut ); + else if ( nConfLimit && !RetValue ) + printf( "Enumerated %d assignments when conflict limit (%d) was reached. ", nSolutions, nConfLimit ); + else + printf( "Enumerated the complete set of %d assignments. ", nSolutions ); + Abc_PrintTime( 1, "Time", Abc_Clock() - clkStart ); + return RetValue; +} + /**Function************************************************************* Synopsis [Dumps the original problem in QDIMACS format.] diff --git a/src/base/abci/abc.c b/src/base/abci/abc.c index aa4c7e16..006d691d 100644 --- a/src/base/abci/abc.c +++ b/src/base/abci/abc.c @@ -378,6 +378,7 @@ static int Abc_CommandAbc9Lcorr ( Abc_Frame_t * pAbc, int argc, cha static int Abc_CommandAbc9Scorr ( Abc_Frame_t * pAbc, int argc, char ** argv ); static int Abc_CommandAbc9Choice ( Abc_Frame_t * pAbc, int argc, char ** argv ); static int Abc_CommandAbc9Sat ( Abc_Frame_t * pAbc, int argc, char ** argv ); +static int Abc_CommandAbc9SatEnum ( Abc_Frame_t * pAbc, int argc, char ** argv ); static int Abc_CommandAbc9Fraig ( Abc_Frame_t * pAbc, int argc, char ** argv ); static int Abc_CommandAbc9CFraig ( Abc_Frame_t * pAbc, int argc, char ** argv ); static int Abc_CommandAbc9Srm ( Abc_Frame_t * pAbc, int argc, char ** argv ); @@ -977,6 +978,7 @@ void Abc_Init( Abc_Frame_t * pAbc ) Cmd_CommandAdd( pAbc, "ABC9", "&scorr", Abc_CommandAbc9Scorr, 0 ); Cmd_CommandAdd( pAbc, "ABC9", "&choice", Abc_CommandAbc9Choice, 0 ); Cmd_CommandAdd( pAbc, "ABC9", "&sat", Abc_CommandAbc9Sat, 0 ); + Cmd_CommandAdd( pAbc, "ABC9", "&satenum", Abc_CommandAbc9SatEnum, 0 ); Cmd_CommandAdd( pAbc, "ABC9", "&fraig", Abc_CommandAbc9Fraig, 0 ); Cmd_CommandAdd( pAbc, "ABC9", "&cfraig", Abc_CommandAbc9CFraig, 0 ); Cmd_CommandAdd( pAbc, "ABC9", "&srm", Abc_CommandAbc9Srm, 0 ); @@ -29708,6 +29710,73 @@ usage: return 1; } +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_CommandAbc9SatEnum( Abc_Frame_t * pAbc, int argc, char ** argv ) +{ + extern int Gia_ManSatEnum( Gia_Man_t * p, int nConfLimit, int nTimeOut, int fVerbose ); + int c, nConfLimit = 0, nTimeOut = 0, fVerbose = 0; + Extra_UtilGetoptReset(); + while ( ( c = Extra_UtilGetopt( argc, argv, "CTvh" ) ) != EOF ) + { + switch ( c ) + { + case 'C': + if ( globalUtilOptind >= argc ) + { + Abc_Print( -1, "Command line switch \"-C\" should be followed by an integer.\n" ); + goto usage; + } + nConfLimit = atoi(argv[globalUtilOptind]); + globalUtilOptind++; + if ( nConfLimit < 0 ) + goto usage; + break; + case 'T': + if ( globalUtilOptind >= argc ) + { + Abc_Print( -1, "Command line switch \"-T\" should be followed by an integer.\n" ); + goto usage; + } + nTimeOut = atoi(argv[globalUtilOptind]); + globalUtilOptind++; + if ( nTimeOut < 0 ) + goto usage; + break; + case 'v': + fVerbose ^= 1; + break; + default: + goto usage; + } + } + if ( pAbc->pGia == NULL ) + { + Abc_Print( -1, "Abc_CommandAbc9SatEnum(): There is no AIG.\n" ); + return 1; + } + Gia_ManSatEnum( pAbc->pGia, nConfLimit, nTimeOut, fVerbose ); + return 0; + +usage: + Abc_Print( -2, "usage: &satenum [-CT ] [-vh]\n" ); + Abc_Print( -2, "\t enumerates solutions of the combinational miter\n" ); + Abc_Print( -2, "\t-C num : the max number of conflicts at a node [default = %d]\n", nConfLimit ); + Abc_Print( -2, "\t-T num : global timeout [default = %d]\n", nTimeOut ); + Abc_Print( -2, "\t-v : toggle printing verbose information [default = %s]\n", fVerbose? "yes": "no" ); + Abc_Print( -2, "\t-h : print the command usage\n"); + return 1; +} + /**Function************************************************************* Synopsis [] -- cgit v1.2.3