New command &satenum to enumerate SAT assignments of a miter in a naive way.

2 files changed, 128 insertions, 0 deletions

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
@@ -56,6 +56,65 @@ extern Cnf_Dat_t * Mf_ManGenerateCnf( Gia_Man_t * pGia, int nLutSize, int fCnfOb
 
 /**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.]
 
   Description []
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 );
@@ -29719,6 +29721,73 @@ usage:
   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 <num>] [-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    []
+
+  Description []
+
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
 int Abc_CommandAbc9Fraig( Abc_Frame_t * pAbc, int argc, char ** argv )
 {
     Cec_ParFra_t ParsFra, * pPars = &ParsFra;