abc/src/bdd/cudd/cuddZddSymm.c
/**Function********************************************************************

  Synopsis [Symmetric sifting algorithm for ZDDs.]

  Description [Symmetric sifting algorithm.
  Assumes that no dead nodes are present.
    <ol>
    <li> Order all the variables according to the number of entries in
    each unique subtable.
    <li> Sift the variable up and down, remembering each time the total
    size of the ZDD heap and grouping variables that are symmetric.
    <li> Select the best permutation.
    <li> Repeat 3 and 4 for all variables.
    </ol>
  Returns 1 plus the number of symmetric variables if successful; 0
  otherwise.]

  SideEffects [None]

  SeeAlso     [cuddZddSymmSiftingConv]

******************************************************************************/
Function
Synopsis [Symmetric sifting algorithm for ZDDs.]

Description [Symmetric sifting algorithm.
Assumes that no dead nodes are present.

 Order all the variables according to the number of entries in
each unique subtable.
 Sift the variable up and down, remembering each time the total
size of the ZDD heap and grouping variables that are symmetric.
 Select the best permutation.
 Repeat 3 and 4 for all variables.

Returns 1 plus the number of symmetric variables if successful; 0
otherwise.]




Function Synopsis [ Symmetric sifting algorithm for ZDDs . ] Description [ Symmetric sifting algorithm . Assumes that no dead nodes are present . Order all the variables according to the number of entries in each unique subtable . Sift the variable up and down remembering each time the total size of the ZDD heap and grouping variables that are symmetric . Select the best permutation . Repeat 3 and 4 for all variables . Returns 1 plus the number of symmetric variables if successful ; 0 otherwise . ]
int
cuddZddSymmSifting(
  DdManager * table,
  int  lower,
  int  upper)
{
    int         i;
    int         *var;
    int         nvars;
    int         x;
    int         result;
    int         symvars;
    int         symgroups;
    int         iteration;
#ifdef DD_STATS
    int         previousSize;
#endif
    nvars = table->sizeZ;
    var = NULL;
    zdd_entry = ABC_ALLOC(int, nvars);
    if (zdd_entry == NULL) {
        table->errorCode = CUDD_MEMORY_OUT;
        goto cuddZddSymmSiftingOutOfMem;
    }
    var = ABC_ALLOC(int, nvars);
    if (var == NULL) {
        table->errorCode = CUDD_MEMORY_OUT;
        goto cuddZddSymmSiftingOutOfMem;
    }
    for (i = 0; i < nvars; i++) {
        x = table->permZ[i];
        zdd_entry[i] = table->subtableZ[x].keys;
        var[i] = i;
    }
    qsort((void *)var, nvars, sizeof(int), (DD_QSFP)cuddZddUniqueCompare);
    for (i = lower; i <= upper; i++)
        table->subtableZ[i].next = i;
    iteration = ddMin(table->siftMaxVar, nvars);
    for (i = 0; i < iteration; i++) {
        if (zddTotalNumberSwapping >= table->siftMaxSwap)
            break;
        x = table->permZ[var[i]];
#ifdef DD_STATS
        previousSize = table->keysZ;
#endif
        if (x < lower || x > upper) continue;
        if (table->subtableZ[x].next == (unsigned) x) {
            result = cuddZddSymmSiftingAux(table, x, lower, upper);
            if (!result)
                goto cuddZddSymmSiftingOutOfMem;
#ifdef DD_STATS
            if (table->keysZ < (unsigned) previousSize) {
                (void) fprintf(table->out,"-");
            } else if (table->keysZ > (unsigned) previousSize) {
                (void) fprintf(table->out,"+");
#ifdef DD_VERBOSE
                (void) fprintf(table->out,"\nSize increased from %d to %d while sifting variable %d\n", previousSize, table->keysZ, var[i]);
#endif
            } else {
                (void) fprintf(table->out,"=");
            }
            fflush(table->out);
#endif
        }
    }
    ABC_FREE(var);
    ABC_FREE(zdd_entry);
    cuddZddSymmSummary(table, lower, upper, &symvars, &symgroups);
#ifdef DD_STATS
    (void) fprintf(table->out,"\n#:S_SIFTING %8d: symmetric variables\n",symvars);
    (void) fprintf(table->out,"#:G_SIFTING %8d: symmetric groups\n",symgroups);
#endif
    return(1+symvars);
cuddZddSymmSiftingOutOfMem:
    if (zdd_entry != NULL)
        ABC_FREE(zdd_entry);
    if (var != NULL)
        ABC_FREE(var);
    return(0);
}
int cuddZddSymmSifting ( DdManager * table , int lower , int upper ) { int i ; int * var ; int nvars ; int x ; int result ; int symvars ; int symgroups ; int iteration ; #ifdef DD_STATS int previousSize ; #endif nvars = table -> sizeZ ; var = NULL ; zdd_entry = ABC_ALLOC ( int , nvars ) ; if ( zdd_entry == NULL ) { table -> errorCode = CUDD_MEMORY_OUT ; goto cuddZddSymmSiftingOutOfMem ; } var = ABC_ALLOC ( int , nvars ) ; if ( var == NULL ) { table -> errorCode = CUDD_MEMORY_OUT ; goto cuddZddSymmSiftingOutOfMem ; } for ( i = 0 ; i < nvars ; i ++ ) { x = table -> permZ [ i ] ; zdd_entry [ i ] = table -> subtableZ [ x ] . keys ; var [ i ] = i ; } qsort ( ( void * ) var , nvars , sizeof ( int ) , ( DD_QSFP ) cuddZddUniqueCompare ) ; for ( i = lower ; i <= upper ; i ++ ) table -> subtableZ [ i ] . next = i ; iteration = ddMin ( table -> siftMaxVar , nvars ) ; for ( i = 0 ; i < iteration ; i ++ ) { if ( zddTotalNumberSwapping >= table -> siftMaxSwap ) break ; x = table -> permZ [ var [ i ] ] ; #ifdef DD_STATS previousSize = table -> keysZ ; #endif if ( x < lower || x > upper ) continue ; if ( table -> subtableZ [ x ] . next == ( unsigned ) x ) { result = cuddZddSymmSiftingAux ( table , x , lower , upper ) ; if ( ! result ) goto cuddZddSymmSiftingOutOfMem ; #ifdef DD_STATS if ( table -> keysZ < ( unsigned ) previousSize ) { ( void ) fprintf ( table -> out , " " ) ; } else if ( table -> keysZ > ( unsigned ) previousSize ) { ( void ) fprintf ( table -> out , " " ) ; #ifdef DD_VERBOSE ( void ) fprintf ( table -> out , " \n \n " , previousSize , table -> keysZ , var [ i ] ) ; #endif } else { ( void ) fprintf ( table -> out , " " ) ; } fflush ( table -> out ) ; #endif } } ABC_FREE ( var ) ; ABC_FREE ( zdd_entry ) ; cuddZddSymmSummary ( table , lower , upper , & symvars , & symgroups ) ; #ifdef DD_STATS ( void ) fprintf ( table -> out , " \n \n " , symvars ) ; ( void ) fprintf ( table -> out , " \n " , symgroups ) ; #endif return ( 1 + symvars ) ; cuddZddSymmSiftingOutOfMem : if ( zdd_entry != NULL ) ABC_FREE ( zdd_entry ) ; if ( var != NULL ) ABC_FREE ( var ) ; return ( 0 ) ; }
Function
Synopsis [Symmetric sifting algorithm for ZDDs.]
Function Synopsis [ Symmetric sifting algorithm for ZDDs . ]
/* Find order in which to sift variables. */ /* Initialize the symmetry of each subtable to itself. */