src/img/imgMonolithic.c

Go to the documentation of this file.

#include "imgInt.h"

static char rcsid[] UNUSED = "$Id: imgMonolithic.c,v 1.23 2002/08/27 08:43:12 fabio Exp $";

/*---------------------------------------------------------------------------*/
/* Static function prototypes                                                */
/*---------------------------------------------------------------------------*/

static mdd_t * ImageComputeMonolithic(mdd_t *methodData, mdd_t *fromLowerBound, mdd_t *fromUpperBound, array_t *toCareSetArray, array_t *smoothVars, mdd_t *smoothCube);

/*---------------------------------------------------------------------------*/
/* Definition of exported functions                                          */
/*---------------------------------------------------------------------------*/


    
/*---------------------------------------------------------------------------*/
/* Definition of internal functions                                          */
/*---------------------------------------------------------------------------*/


void *
ImgImageInfoInitializeMono(void *methodData, ImgFunctionData_t * functionData,
                           Img_DirectionType directionType)
{
  if (!methodData){ /* Need to compute */
    int          i;
    mdd_t       *monolithicT;
    array_t     *rootRelations = array_alloc(mdd_t*, 0);
    graph_t     *mddNetwork    = functionData->mddNetwork;
    mdd_manager *mddManager    = Part_PartitionReadMddManager(mddNetwork);
    array_t     *roots         = functionData->roots;
    array_t     *leaves        = array_join(functionData->domainVars,
                                            functionData->quantifyVars);
    array_t     *rootFunctions = Part_PartitionBuildFunctions(mddNetwork, roots,
                                                              leaves,
                                                              NIL(mdd_t)); 
    
    array_free(leaves);
    
    
    /*
     * Take the product of the transition relation of all the root nodes
     * and smooth out the quantify variables.
     */
    
    /*
     * Iterate over the function of all the root nodes.
     */  
    for (i=0; i<array_n(rootFunctions); i++) {
      Mvf_Function_t *rootFunction  = array_fetch(Mvf_Function_t*, rootFunctions, i);
      int             rangeVarMddId = array_fetch(int, functionData->rangeVars, i);
      mdd_t          *rootRelation =
          Mvf_FunctionBuildRelationWithVariable(rootFunction,
                                                rangeVarMddId); 
      array_insert_last(mdd_t*, rootRelations, rootRelation);
    }
    
    Mvf_FunctionArrayFree(rootFunctions);
    monolithicT = Img_MultiwayLinearAndSmooth(mddManager, rootRelations,
                                              functionData->quantifyVars,
                                              functionData->domainVars,
                                              Img_Iwls95_c, Img_Forward_c);
    mdd_array_free(rootRelations);
    return ((void *)monolithicT);
  }
  else {
    return methodData;
  }
}



mdd_t *
ImgImageInfoComputeFwdMono(
  ImgFunctionData_t * functionData,
  Img_ImageInfo_t * imageInfo,
  mdd_t *fromLowerBound,
  mdd_t *fromUpperBound,
  array_t * toCareSetArray)
{
  return  ImageComputeMonolithic((mdd_t *) imageInfo->methodData,
                                 fromLowerBound, fromUpperBound,
                                 toCareSetArray, functionData->domainBddVars,
                                 functionData->domainCube);  
}

  
mdd_t *
ImgImageInfoComputeFwdWithDomainVarsMono(
  ImgFunctionData_t *functionData,
  Img_ImageInfo_t *imageInfo,
  mdd_t *fromLowerBound,
  mdd_t *fromUpperBound,
  array_t *toCareSetArray)
{
  array_t *toCareSetArrayRV = ImgSubstituteArray(toCareSetArray,
                                                 functionData, Img_D2R_c);
  mdd_t *imageRV = ImgImageInfoComputeFwdMono(functionData,
                                              imageInfo,
                                              fromLowerBound,
                                              fromUpperBound,
                                              toCareSetArrayRV);
  mdd_t *imageDV = ImgSubstitute(imageRV, functionData, Img_R2D_c);

  mdd_array_free(toCareSetArrayRV);
  mdd_free(imageRV);
  return imageDV;
}

mdd_t *
ImgImageInfoComputeBwdMono(
  ImgFunctionData_t * functionData,
  Img_ImageInfo_t *imageInfo,
  mdd_t *fromLowerBound,
  mdd_t *fromUpperBound,
  array_t *toCareSetArray)
{
  return ImageComputeMonolithic((mdd_t*)imageInfo->methodData, fromLowerBound,
                                fromUpperBound, toCareSetArray,  
                                functionData->rangeBddVars,
                                functionData->rangeCube);  
}

mdd_t *
ImgImageInfoComputeBwdWithDomainVarsMono(
  ImgFunctionData_t * functionData,
  Img_ImageInfo_t *imageInfo,
  mdd_t *fromLowerBound,
  mdd_t *fromUpperBound,
  array_t *toCareSetArray)
{
  mdd_t *fromLowerBoundRV = ImgSubstitute(fromLowerBound,
                                          functionData, Img_D2R_c);
  mdd_t *fromUpperBoundRV = ImgSubstitute(fromUpperBound,
                                          functionData, Img_D2R_c);
  mdd_t *image = ImgImageInfoComputeBwdMono(functionData,
                                            imageInfo,
                                            fromLowerBoundRV,
                                            fromUpperBoundRV,
                                            toCareSetArray);
  mdd_free(fromLowerBoundRV);
  mdd_free(fromUpperBoundRV);
  return image;
}



void
ImgImageInfoFreeMono(void * methodData)
{
  mdd_free((mdd_t *)methodData);
}

void
ImgImageInfoPrintMethodParamsMono(void *methodData, FILE *fp)
{
  mdd_t *monolithicRelation = (mdd_t *)methodData;
  (void) fprintf(fp,"Printing information about image method: Monolithic\n");  
  (void) fprintf(fp,"\tSize of monolithic relation = %10ld\n",
                 (long) bdd_size(monolithicRelation));
}

void
ImgRestoreTransitionRelationMono(Img_ImageInfo_t *imageInfo,
        Img_DirectionType directionType)
{
  mdd_free((mdd_t *) imageInfo->methodData);
  imageInfo->methodData = (mdd_t *)imageInfo->savedRelation;
  imageInfo->savedRelation = NIL(void);
  return;
}

void
ImgDuplicateTransitionRelationMono(Img_ImageInfo_t *imageInfo)
{
  imageInfo->savedRelation = (void *)mdd_dup((mdd_t *) imageInfo->methodData);
  return;
}

void
ImgMinimizeTransitionRelationMono(Img_ImageInfo_t *imageInfo,
        array_t *constrainArray, Img_MinimizeType minimizeMethod,
        int printStatus)
{
  mdd_t *relation, *simplifiedRelation;
  int i, size = 0;
  mdd_t *constrain;

  relation = (mdd_t *)imageInfo->methodData;

  if (printStatus)
    size = bdd_size(relation);

  for (i = 0; i < array_n(constrainArray); i++) {
    constrain = array_fetch(mdd_t *, constrainArray, i);
    simplifiedRelation = Img_MinimizeImage(relation, constrain, minimizeMethod,
                                           TRUE);
    if (printStatus) {
      (void) fprintf(vis_stdout, "Info: minimized relation %d | %d => %d\n",
                     bdd_size(relation), bdd_size(constrain),
                     bdd_size(simplifiedRelation));
    }
    mdd_free(relation);
    relation = simplifiedRelation;
  }
  imageInfo->methodData = (void *)relation;

  if (printStatus) {
    (void) fprintf(vis_stdout,
        "IMG Info: minimized relation [%d | %ld => %d]\n",
                   size, bdd_size_multiple(constrainArray),
                   bdd_size(relation));
  }
}

void
ImgAddDontCareToTransitionRelationMono(Img_ImageInfo_t *imageInfo,
        array_t *constrainArray, Img_MinimizeType minimizeMethod,
        int printStatus)
{
  mdd_t *relation, *simplifiedRelation;
  int i, size = 0;
  mdd_t *constrain;

  relation = (mdd_t *)imageInfo->methodData;

  if (printStatus)
    size = bdd_size(relation);

  for (i = 0; i < array_n(constrainArray); i++) {
    constrain = array_fetch(mdd_t *, constrainArray, i);
    simplifiedRelation = Img_AddDontCareToImage(relation,
                                             constrain, minimizeMethod);
    if (printStatus) {
      (void) fprintf(vis_stdout, "Info: minimized relation %d | %d => %d\n",
                     bdd_size(relation), bdd_size(constrain),
                     bdd_size(simplifiedRelation));
    }
    mdd_free(relation);
    relation = simplifiedRelation;
  }
  imageInfo->methodData = (void *)relation;

  if (printStatus) {
    (void) fprintf(vis_stdout,
        "IMG Info: minimized relation [%d | %ld => %d]\n",
                   size, bdd_size_multiple(constrainArray),
                   bdd_size(relation));
  }
}


void
ImgAbstractTransitionRelationMono(Img_ImageInfo_t *imageInfo,
        array_t *abstractVars, mdd_t *abstractCube, int printStatus)
{
  mdd_t *relation, *abstractedRelation;

  relation = (mdd_t *)imageInfo->methodData;
  if (abstractCube)
    abstractedRelation = bdd_smooth_with_cube(relation, abstractCube);
  else
    abstractedRelation = bdd_smooth(relation, abstractVars);
  if (printStatus) {
    (void) fprintf(vis_stdout, "Info: abstracted relation %d => %d\n",
                     bdd_size(relation), bdd_size(abstractedRelation));
  }
  mdd_free(relation);
  imageInfo->methodData = (void *)abstractedRelation;
}


int
ImgApproximateTransitionRelationMono(mdd_manager *mgr,
        Img_ImageInfo_t *imageInfo,
        bdd_approx_dir_t approxDir,
        bdd_approx_type_t approxMethod,
        int approxThreshold,
        double approxQuality,
        double approxQualityBias,
        mdd_t *bias)
{
  mdd_t *relation, *approxRelation;
  int   unchanged;

  relation = (mdd_t *)imageInfo->methodData;
  approxRelation = Img_ApproximateImage(mgr, relation, approxDir, approxMethod,
                                        approxThreshold, approxQuality,
                                        approxQualityBias, bias);
  if (bdd_is_tautology(approxRelation, 1)) {
    fprintf(vis_stdout, "** img warning : bdd_one from subsetting.\n");
    mdd_free(approxRelation);
    unchanged = 1;
  } else if (bdd_is_tautology(approxRelation, 0)) {
    fprintf(vis_stdout, "** img warning : bdd_zero from subsetting.\n");
    mdd_free(approxRelation);
    unchanged = 1;
  } else if (mdd_equal(approxRelation, relation)) {
    mdd_free(approxRelation);
    unchanged = 1;
  } else {
    mdd_free(relation);
    imageInfo->methodData = (void *)approxRelation;
    unchanged = 0;
  }
  return(unchanged);
}

void 
ImgImageConstrainAndClusterTransitionRelationMono(Img_ImageInfo_t *imageInfo,
                                                  mdd_t *constrain,
                                                  Img_MinimizeType minimizeMethod,
                                                  boolean underApprox,
                                                  boolean cleanUp,
                                                  boolean forceReorder,
                                                  int printStatus)
{
  ImgFunctionData_t *functionData = &(imageInfo->functionData);
  mdd_t *methodData = (mdd_t *)imageInfo->methodData;
  int          i;
  mdd_t       *monolithicT;
  array_t     *rootRelations = array_alloc(mdd_t*, 0);
  graph_t     *mddNetwork    = functionData->mddNetwork;
  mdd_manager *mddManager    = Part_PartitionReadMddManager(mddNetwork);
  array_t     *roots         = functionData->roots;
  array_t     *leaves        = array_join(functionData->domainVars,
                                          functionData->quantifyVars);
  array_t     *rootFunctions;
  mdd_t       *relation;
  
  /*free existing  relation. */
  if (!methodData) ImgImageInfoFreeMono(methodData);    
  if (forceReorder) bdd_reorder(mddManager);
  rootFunctions = Part_PartitionBuildFunctions(mddNetwork, roots,
                                               leaves,
                                               NIL(mdd_t)); 
  
  array_free(leaves);
    
  /*
   * Take the product of the transition relation of all the root nodes
   * and smooth out the quantify variables.
   */
  
  /*
   * Iterate over the function of all the root nodes.
   */  
  for (i=0; i<array_n(rootFunctions); i++) {
    Mvf_Function_t *rootFunction  = array_fetch(Mvf_Function_t*, rootFunctions, i);
    int             rangeVarMddId = array_fetch(int, functionData->rangeVars, i);
    mdd_t          *rootRelation =
      Mvf_FunctionBuildRelationWithVariable(rootFunction,
                                            rangeVarMddId); 
    array_insert_last(mdd_t*, rootRelations, rootRelation);
  }
  Mvf_FunctionArrayFree(rootFunctions);

  /* Constrain the bit relaitons */
  if (constrain) {
    arrayForEachItem(mdd_t *, rootRelations, i, relation) {
      mdd_t *simplifiedRelation;
      simplifiedRelation = Img_MinimizeImage(relation, constrain,
                                             minimizeMethod, underApprox);
      if (printStatus) {
        (void) fprintf(vis_stdout, "Info: minimized relation %d | %d => %d\n",
                       bdd_size(relation), bdd_size(constrain),
                       bdd_size(simplifiedRelation));
      }
      mdd_free(relation);
      array_insert(mdd_t *, rootRelations, i, simplifiedRelation);
    }
  }

  /* build the monolithic transition relation. */
  monolithicT = Img_MultiwayLinearAndSmooth(mddManager, rootRelations,
                                            functionData->quantifyVars,
                                            functionData->domainVars,
                                            Img_Iwls95_c, Img_Forward_c);
  mdd_array_free(rootRelations);
  imageInfo->methodData = (void *)monolithicT;
  if (printStatus) {
    ImgImageInfoPrintMethodParamsMono(monolithicT, vis_stdout);
  }

}



/*---------------------------------------------------------------------------*/
/* Definition of static functions                                            */
/*---------------------------------------------------------------------------*/
static mdd_t *
ImageComputeMonolithic(mdd_t *methodData, mdd_t *fromLowerBound, mdd_t
                *fromUpperBound, array_t *toCareSetArray,
                array_t *smoothVars, mdd_t *smoothCube)
{
  mdd_t       *domainSubset, *image;
  mdd_t       *optimizedRelation, *subOptimizedRelation;
  mdd_t       *monolithicT = (mdd_t *)methodData;
  
  assert(monolithicT != NIL(mdd_t));
  
  /*
   * Optimization steps:
   * Choose the domainSubset optimally.
   * Reduce the transition relation wrt to care set and domainSubset.
   */
  domainSubset = bdd_between(fromLowerBound,fromUpperBound);
  subOptimizedRelation = bdd_cofactor_array(monolithicT, toCareSetArray);
  optimizedRelation = bdd_cofactor(subOptimizedRelation, domainSubset);  
  mdd_free(domainSubset);
  mdd_free(subOptimizedRelation);
  /*optimizedRelation = bdd_and(fromLowerBound, monolithicT, 1, 1);*/
  if (smoothCube)
    image = bdd_smooth_with_cube(optimizedRelation, smoothCube);
  else {
    if (array_n(smoothVars) == 0)
      image = mdd_dup(optimizedRelation);
    else
      image = bdd_smooth(optimizedRelation, smoothVars);
  }

  mdd_free(optimizedRelation);
  return image;
}