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

  Synopsis    [Main dynamic reordering routine.]

  Description [Main dynamic reordering routine.
  Calls one of the possible reordering procedures:
  <ul>
  <li>Swapping
  <li>Sifting
  <li>Symmetric Sifting
  <li>Group Sifting
  <li>Window Permutation
  <li>Simulated Annealing
  <li>Genetic Algorithm
  <li>Dynamic Programming (exact)
  </ul>

  For sifting, symmetric sifting, group sifting, and window
  permutation it is possible to request reordering to convergence.<p>

  The core of all methods is the reordering procedure
  cuddSwapInPlace() which swaps two adjacent variables and is based
  on Rudell's paper.
  Returns 1 in case of success; 0 otherwise. In the case of symmetric
  sifting (with and without convergence) returns 1 plus the number of
  symmetric variables, in case of success.]

  SideEffects [Changes the variable order for all diagrams and clears
  the cache.]

******************************************************************************/
Function
Synopsis    [Main dynamic reordering routine.]

Description [Main dynamic reordering routine.
Calls one of the possible reordering procedures:

Swapping
Sifting
Symmetric Sifting
Group Sifting
Window Permutation
Simulated Annealing
Genetic Algorithm
Dynamic Programming (exact)


For sifting, symmetric sifting, group sifting, and window
permutation it is possible to request reordering to convergence.

The core of all methods is the reordering procedure
cuddSwapInPlace() which swaps two adjacent variables and is based
on Rudell's paper.
Returns 1 in case of success; 0 otherwise. In the case of symmetric
sifting (with and without convergence) returns 1 plus the number of
symmetric variables, in case of success.]

SideEffects [Changes the variable order for all diagrams and clears
the cache.]
Function Synopsis [ Main dynamic reordering routine . ] Description [ Main dynamic reordering routine . Calls one of the possible reordering procedures : Swapping Sifting Symmetric Sifting Group Sifting Window Permutation Simulated Annealing Genetic Algorithm Dynamic Programming ( exact ) For sifting symmetric sifting group sifting and window permutation it is possible to request reordering to convergence . The core of all methods is the reordering procedure cuddSwapInPlace () which swaps two adjacent variables and is based on Rudell ' s paper . Returns 1 in case of success ; 0 otherwise . In the case of symmetric sifting ( with and without convergence ) returns 1 plus the number of symmetric variables in case of success . ] SideEffects [ Changes the variable order for all diagrams and clears the cache . ]
int
Cudd_ReduceHeap(
  DdManager * table ,
  Cudd_ReorderingType heuristic ,
  int  minsize )
{
    DdHook *hook;
    int result;
    unsigned int nextDyn;
#ifdef DD_STATS
    unsigned int initialSize;
    unsigned int finalSize;
#endif
    long localTime;
    if (table->keys - table->dead < (unsigned) minsize)
        return(1);
    if (heuristic == CUDD_REORDER_SAME) {
        heuristic = table->autoMethod;
    }
    if (heuristic == CUDD_REORDER_NONE) {
        return(1);
    }
    table->reorderings++;
    localTime = util_cpu_time();
    hook = table->preReorderingHook;
    while (hook != NULL) {
        int res = (hook->f)(table, "BDD", (void *)heuristic);
        if (res == 0) return(0);
        hook = hook->next;
    }
    if (!ddReorderPreprocess(table)) return(0);
    ddTotalNumberSwapping = 0;
    if (table->keys > table->peakLiveNodes) {
        table->peakLiveNodes = table->keys;
    }
#ifdef DD_STATS
    initialSize = table->keys - table->isolated;
    ddTotalNISwaps = 0;
    switch(heuristic) {
    case CUDD_REORDER_RANDOM:
    case CUDD_REORDER_RANDOM_PIVOT:
        (void) fprintf(table->out,"#:I_RANDOM  ");
        break;
    case CUDD_REORDER_SIFT:
    case CUDD_REORDER_SIFT_CONVERGE:
    case CUDD_REORDER_SYMM_SIFT:
    case CUDD_REORDER_SYMM_SIFT_CONV:
    case CUDD_REORDER_GROUP_SIFT:
    case CUDD_REORDER_GROUP_SIFT_CONV:
        (void) fprintf(table->out,"#:I_SIFTING ");
        break;
    case CUDD_REORDER_WINDOW2:
    case CUDD_REORDER_WINDOW3:
    case CUDD_REORDER_WINDOW4:
    case CUDD_REORDER_WINDOW2_CONV:
    case CUDD_REORDER_WINDOW3_CONV:
    case CUDD_REORDER_WINDOW4_CONV:
        (void) fprintf(table->out,"#:I_WINDOW  ");
        break;
    case CUDD_REORDER_ANNEALING:
        (void) fprintf(table->out,"#:I_ANNEAL  ");
        break;
    case CUDD_REORDER_GENETIC:
        (void) fprintf(table->out,"#:I_GENETIC ");
        break;
    case CUDD_REORDER_LINEAR:
    case CUDD_REORDER_LINEAR_CONVERGE:
        (void) fprintf(table->out,"#:I_LINSIFT ");
        break;
    case CUDD_REORDER_EXACT:
        (void) fprintf(table->out,"#:I_EXACT   ");
        break;
    default:
        return(0);
    }
    (void) fprintf(table->out,"%8d: initial size",initialSize);
#endif
    if (table->reordCycle && table->reorderings % table->reordCycle == 0) {
        double saveGrowth = table->maxGrowth;
        table->maxGrowth = table->maxGrowthAlt;
        result = cuddTreeSifting(table,heuristic);
        table->maxGrowth = saveGrowth;
    } else {
        result = cuddTreeSifting(table,heuristic);
    }
#ifdef DD_STATS
    (void) fprintf(table->out,"\n");
    finalSize = table->keys - table->isolated;
    (void) fprintf(table->out,"#:F_REORDER %8d: final size\n",finalSize);
    (void) fprintf(table->out,"#:T_REORDER %8g: total time (sec)\n",
                   ((double)(util_cpu_time() - localTime)/1000.0));
    (void) fprintf(table->out,"#:N_REORDER %8d: total swaps\n",
                   ddTotalNumberSwapping);
    (void) fprintf(table->out,"#:M_REORDER %8d: NI swaps\n",ddTotalNISwaps);
#endif
    if (result == 0)
        return(0);
    if (!ddReorderPostprocess(table))
        return(0);
    if (table->realign) {
        if (!cuddZddAlignToBdd(table))
            return(0);
    }
    nextDyn = (table->keys - table->constants.keys + 1) *
              DD_DYN_RATIO + table->constants.keys;
    if (table->reorderings < 20 || nextDyn > table->nextDyn)
        table->nextDyn = nextDyn;
    else
        table->nextDyn += 20;
    table->reordered = 1;
    hook = table->postReorderingHook;
    while (hook != NULL) {
        int res = (hook->f)(table, "BDD", (void *)localTime);
        if (res == 0) return(0);
        hook = hook->next;
    }
    table->reordTime += util_cpu_time() - localTime;
    return(result);
}
int Cudd_ReduceHeap ( DdManager * table , Cudd_ReorderingType heuristic , int minsize ) { DdHook * hook ; int result ; unsigned int nextDyn ; #ifdef DD_STATS unsigned int initialSize ; unsigned int finalSize ; #endif long localTime ; if ( table -> keys - table -> dead < ( unsigned ) minsize ) return ( 1 ) ; if ( heuristic == CUDD_REORDER_SAME ) { heuristic = table -> autoMethod ; } if ( heuristic == CUDD_REORDER_NONE ) { return ( 1 ) ; } table -> reorderings ++ ; localTime = util_cpu_time ( ) ; hook = table -> preReorderingHook ; while ( hook != NULL ) { int res = ( hook -> f ) ( table , " " , ( void * ) heuristic ) ; if ( res == 0 ) return ( 0 ) ; hook = hook -> next ; } if ( ! ddReorderPreprocess ( table ) ) return ( 0 ) ; ddTotalNumberSwapping = 0 ; if ( table -> keys > table -> peakLiveNodes ) { table -> peakLiveNodes = table -> keys ; } #ifdef DD_STATS initialSize = table -> keys - table -> isolated ; ddTotalNISwaps = 0 ; switch ( heuristic ) { case CUDD_REORDER_RANDOM : case CUDD_REORDER_RANDOM_PIVOT : ( void ) fprintf ( table -> out , " " ) ; break ; case CUDD_REORDER_SIFT : case CUDD_REORDER_SIFT_CONVERGE : case CUDD_REORDER_SYMM_SIFT : case CUDD_REORDER_SYMM_SIFT_CONV : case CUDD_REORDER_GROUP_SIFT : case CUDD_REORDER_GROUP_SIFT_CONV : ( void ) fprintf ( table -> out , " " ) ; break ; case CUDD_REORDER_WINDOW2 : case CUDD_REORDER_WINDOW3 : case CUDD_REORDER_WINDOW4 : case CUDD_REORDER_WINDOW2_CONV : case CUDD_REORDER_WINDOW3_CONV : case CUDD_REORDER_WINDOW4_CONV : ( void ) fprintf ( table -> out , " " ) ; break ; case CUDD_REORDER_ANNEALING : ( void ) fprintf ( table -> out , " " ) ; break ; case CUDD_REORDER_GENETIC : ( void ) fprintf ( table -> out , " " ) ; break ; case CUDD_REORDER_LINEAR : case CUDD_REORDER_LINEAR_CONVERGE : ( void ) fprintf ( table -> out , " " ) ; break ; case CUDD_REORDER_EXACT : ( void ) fprintf ( table -> out , " " ) ; break ; default : return ( 0 ) ; } ( void ) fprintf ( table -> out , " " , initialSize ) ; #endif if ( table -> reordCycle && table -> reorderings % table -> reordCycle == 0 ) { double saveGrowth = table -> maxGrowth ; table -> maxGrowth = table -> maxGrowthAlt ; result = cuddTreeSifting ( table , heuristic ) ; table -> maxGrowth = saveGrowth ; } else { result = cuddTreeSifting ( table , heuristic ) ; } #ifdef DD_STATS ( void ) fprintf ( table -> out , " \n " ) ; finalSize = table -> keys - table -> isolated ; ( void ) fprintf ( table -> out , " \n " , finalSize ) ; ( void ) fprintf ( table -> out , " \n " , ( ( double ) ( util_cpu_time ( ) - localTime ) / 1000.0 ) ) ; ( void ) fprintf ( table -> out , " \n " , ddTotalNumberSwapping ) ; ( void ) fprintf ( table -> out , " \n " , ddTotalNISwaps ) ; #endif if ( result == 0 ) return ( 0 ) ; if ( ! ddReorderPostprocess ( table ) ) return ( 0 ) ; if ( table -> realign ) { if ( ! cuddZddAlignToBdd ( table ) ) return ( 0 ) ; } nextDyn = ( table -> keys - table -> constants . keys + 1 ) * DD_DYN_RATIO + table -> constants . keys ; if ( table -> reorderings < 20 || nextDyn > table -> nextDyn ) table -> nextDyn = nextDyn ; else table -> nextDyn += 20 ; table -> reordered = 1 ; hook = table -> postReorderingHook ; while ( hook != NULL ) { int res = ( hook -> f ) ( table , " " , ( void * ) localTime ) ; if ( res == 0 ) return ( 0 ) ; hook = hook -> next ; } table -> reordTime += util_cpu_time ( ) - localTime ; return ( result ) ; }
Function
Synopsis    [Main dynamic reordering routine.]
Function Synopsis [ Main dynamic reordering routine . ]
/* DD manager */ /* method used for reordering */ /* bound below which no reordering occurs */ /* Don't reorder if there are too many dead nodes. */ /* This call to Cudd_ReduceHeap does initiate reordering. Therefore
    ** we count it.
    */ /* Run the hook functions. */ /* See if we should use alternate threshold for maximum growth. */ /* Run hook functions. */ /* Update cumulative reordering time. */