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

  Synopsis    [Extracts a dense superset from a BDD with the shortest paths
  heuristic.]

  Description [Extracts a dense superset from a BDD.  The procedure is
  identical to the subset procedure except for the fact that it
  receives the complement of the given function. Extracting the subset
  of the complement function is equivalent to extracting the superset
  of the function.  This procedure tries to preserve the shortest
  paths of the complement BDD, because they give many minterms and
  contribute few nodes.  This procedure may increase the number of
  nodes in trying to create the superset or reduce the number of nodes
  due to recombination as compared to the original BDD. Hence the
  threshold may not be strictly adhered to. In practice, recombination
  overshadows the increase in the number of nodes and results in small
  BDDs as compared to the threshold.  The hardlimit specifies whether
  threshold needs to be strictly adhered to. If it is set to 1, the
  procedure ensures that result is never larger than the specified
  limit but may be considerably less than the threshold. Returns a
  pointer to the BDD for the superset if successful; NULL
  otherwise. The value for numVars should be as close as possible to
  the size of the support of f for better efficiency.  However, it is
  safe to pass the value returned by Cudd_ReadSize for numVar.  If 0
  is passed, then the value returned by Cudd_ReadSize is used.]

  SideEffects [None]

  SeeAlso     [Cudd_SubsetShortPaths Cudd_SupersetHeavyBranch Cudd_ReadSize]

******************************************************************************/
Function
Synopsis    [Extracts a dense superset from a BDD with the shortest paths
heuristic.]

Description [Extracts a dense superset from a BDD.  The procedure is
identical to the subset procedure except for the fact that it
receives the complement of the given function. Extracting the subset
of the complement function is equivalent to extracting the superset
of the function.  This procedure tries to preserve the shortest
paths of the complement BDD, because they give many minterms and
contribute few nodes.  This procedure may increase the number of
nodes in trying to create the superset or reduce the number of nodes
due to recombination as compared to the original BDD. Hence the
threshold may not be strictly adhered to. In practice, recombination
overshadows the increase in the number of nodes and results in small
BDDs as compared to the threshold.  The hardlimit specifies whether
threshold needs to be strictly adhered to. If it is set to 1, the
procedure ensures that result is never larger than the specified
limit but may be considerably less than the threshold. Returns a
pointer to the BDD for the superset if successful; NULL
otherwise. The value for numVars should be as close as possible to
the size of the support of f for better efficiency.  However, it is
safe to pass the value returned by Cudd_ReadSize for numVar.  If 0
is passed, then the value returned by Cudd_ReadSize is used.]




Function Synopsis [ Extracts a dense superset from a BDD with the shortest paths heuristic . ] Description [ Extracts a dense superset from a BDD . The procedure is identical to the subset procedure except for the fact that it receives the complement of the given function . Extracting the subset of the complement function is equivalent to extracting the superset of the function . This procedure tries to preserve the shortest paths of the complement BDD because they give many minterms and contribute few nodes . This procedure may increase the number of nodes in trying to create the superset or reduce the number of nodes due to recombination as compared to the original BDD . Hence the threshold may not be strictly adhered to . In practice recombination overshadows the increase in the number of nodes and results in small BDDs as compared to the threshold . The hardlimit specifies whether threshold needs to be strictly adhered to . If it is set to 1 the procedure ensures that result is never larger than the specified limit but may be considerably less than the threshold . Returns a pointer to the BDD for the superset if successful ; NULL otherwise . The value for numVars should be as close as possible to the size of the support of f for better efficiency . However it is safe to pass the value returned by Cudd_ReadSize for numVar . If 0 is passed then the value returned by Cudd_ReadSize is used . ]
DdNode *
Cudd_SupersetShortPaths(
  DdManager * dd ,
  DdNode * f ,
  int  numVars ,
  int  threshold ,
  int  hardlimit )
{
    DdNode *subset, *g;
    g = Cudd_Not(f);
    memOut = 0;
    do {
        dd->reordered = 0;
        subset = cuddSubsetShortPaths(dd, g, numVars, threshold, hardlimit);
    } while((dd->reordered ==1) && (!memOut));
    return(Cudd_NotCond(subset, (subset != NULL)));
}
DdNode * Cudd_SupersetShortPaths ( DdManager * dd , DdNode * f , int numVars , int threshold , int hardlimit ) { DdNode * subset , * g ; g = Cudd_Not ( f ) ; memOut = 0 ; do { dd -> reordered = 0 ; subset = cuddSubsetShortPaths ( dd , g , numVars , threshold , hardlimit ) ; } while ( ( dd -> reordered == 1 ) && ( ! memOut ) ) ; return ( Cudd_NotCond ( subset , ( subset != NULL ) ) ) ; }
Function
Synopsis    [Extracts a dense superset from a BDD with the shortest paths
heuristic.]
Function Synopsis [ Extracts a dense superset from a BDD with the shortest paths heuristic . ]
/* manager */ /* function to be superset */ /* number of variables in the support of f */ /* maximum number of nodes in the subset */ /* flag: 1 if threshold is a hard limit */