/**CFile*********************************************************************** FileName [cuddAndAbs.c] PackageName [cudd] Synopsis [Combined AND and existential abstraction for BDDs] Description [External procedures included in this module: Internal procedures included in this module: ] Author [Fabio Somenzi] Copyright [Copyright (c) 1995-2004, Regents of the University of Colorado All rights reserved. Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution. Neither the name of the University of Colorado nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission. THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.] ******************************************************************************/ #include "misc/util/util_hack.h" #include "cuddInt.h" ABC_NAMESPACE_IMPL_START /*---------------------------------------------------------------------------*/ /* Constant declarations */ /*---------------------------------------------------------------------------*/ /*---------------------------------------------------------------------------*/ /* Stucture declarations */ /*---------------------------------------------------------------------------*/ /*---------------------------------------------------------------------------*/ /* Type declarations */ /*---------------------------------------------------------------------------*/ /*---------------------------------------------------------------------------*/ /* Variable declarations */ /*---------------------------------------------------------------------------*/ #ifndef lint static char rcsid[] DD_UNUSED = "$Id: cuddAndAbs.c,v 1.19 2004/08/13 18:04:46 fabio Exp $"; #endif /*---------------------------------------------------------------------------*/ /* Macro declarations */ /*---------------------------------------------------------------------------*/ /**AutomaticStart*************************************************************/ /*---------------------------------------------------------------------------*/ /* Static function prototypes */ /*---------------------------------------------------------------------------*/ /**AutomaticEnd***************************************************************/ /*---------------------------------------------------------------------------*/ /* Definition of exported functions */ /*---------------------------------------------------------------------------*/ /**Function******************************************************************** Synopsis [Takes the AND of two BDDs and simultaneously abstracts the variables in cube.] Description [Takes the AND of two BDDs and simultaneously abstracts the variables in cube. The variables are existentially abstracted. Returns a pointer to the result is successful; NULL otherwise. Cudd_bddAndAbstract implements the semiring matrix multiplication algorithm for the boolean semiring.] SideEffects [None] SeeAlso [Cudd_addMatrixMultiply Cudd_addTriangle Cudd_bddAnd] ******************************************************************************/ DdNode * Cudd_bddAndAbstract( DdManager * manager, DdNode * f, DdNode * g, DdNode * cube) { DdNode *res; do { manager->reordered = 0; res = cuddBddAndAbstractRecur(manager, f, g, cube); } while (manager->reordered == 1); return(res); } /* end of Cudd_bddAndAbstract */ /**Function******************************************************************** Synopsis [Takes the AND of two BDDs and simultaneously abstracts the variables in cube. Returns NULL if too many nodes are required.] Description [Takes the AND of two BDDs and simultaneously abstracts the variables in cube. The variables are existentially abstracted. Returns a pointer to the result is successful; NULL otherwise. In particular, if the number of new nodes created exceeds limit, this function returns NULL.] SideEffects [None] SeeAlso [Cudd_bddAndAbstract] ******************************************************************************/ DdNode * Cudd_bddAndAbstractLimit( DdManager * manager, DdNode * f, DdNode * g, DdNode * cube, unsigned int limit) { DdNode *res; unsigned int saveLimit = manager->maxLive; manager->maxLive = (manager->keys - manager->dead) + (manager->keysZ - manager->deadZ) + limit; do { manager->reordered = 0; res = cuddBddAndAbstractRecur(manager, f, g, cube); } while (manager->reordered == 1); manager->maxLive = saveLimit; return(res); } /* end of Cudd_bddAndAbstractLimit */ /*---------------------------------------------------------------------------*/ /* Definition of internal functions */ /*---------------------------------------------------------------------------*/ /**Function******************************************************************** Synopsis [Takes the AND of two BDDs and simultaneously abstracts the variables in cube.] Description [Takes the AND of two BDDs and simultaneously abstracts the variables in cube. The variables are existentially abstracted. Returns a pointer to the result is successful; NULL otherwise.] SideEffects [None] SeeAlso [Cudd_bddAndAbstract] ******************************************************************************/ DdNode * cuddBddAndAbstractRecur( DdManager * manager, DdNode * f, DdNode * g, DdNode * cube) { DdNode *F, *ft, *fe, *G, *gt, *ge; DdNode *one, *zero, *r, *t, *e; unsigned int topf, topg, topcube, top, index; statLine(manager); one = DD_ONE(manager); zero = Cudd_Not(one); /* Terminal cases. */ if (f == zero || g == zero || f == Cudd_Not(g)) return(zero); if (f == one && g == one) return(one); if (cube == one) { return(cuddBddAndRecur(manager, f, g)); } if (f == one || f == g) { return(cuddBddExistAbstractRecur(manager, g, cube)); } if (g == one) { return(cuddBddExistAbstractRecur(manager, f, cube)); } /* At this point f, g, and cube are not constant. */ if (f > g) { /* Try to increase cache efficiency. */ DdNode *tmp = f; f = g; g = tmp; } /* Here we can skip the use of cuddI, because the operands are known ** to be non-constant. */ F = Cudd_Regular(f); G = Cudd_Regular(g); topf = manager->perm[F->index]; topg = manager->perm[G->index]; top = ddMin(topf, topg); topcube = manager->perm[cube->index]; while (topcube < top) { cube = cuddT(cube); if (cube == one) { return(cuddBddAndRecur(manager, f, g)); } topcube = manager->perm[cube->index]; } /* Now, topcube >= top. */ /* Check cache. */ if (F->ref != 1 || G->ref != 1) { r = cuddCacheLookup(manager, DD_BDD_AND_ABSTRACT_TAG, f, g, cube); if (r != NULL) { return(r); } } if ( manager->TimeStop && clock() > manager->TimeStop ) return NULL; if (topf == top) { index = F->index; ft = cuddT(F); fe = cuddE(F); if (Cudd_IsComplement(f)) { ft = Cudd_Not(ft); fe = Cudd_Not(fe); } } else { index = G->index; ft = fe = f; } if (topg == top) { gt = cuddT(G); ge = cuddE(G); if (Cudd_IsComplement(g)) { gt = Cudd_Not(gt); ge = Cudd_Not(ge); } } else { gt = ge = g; } if (topcube == top) { /* quantify */ DdNode *Cube = cuddT(cube); t = cuddBddAndAbstractRecur(manager, ft, gt, Cube); if (t == NULL) return(NULL); /* Special case: 1 OR anything = 1. Hence, no need to compute ** the else branch if t is 1. Likewise t + t * anything == t. ** Notice that t == fe implies that fe does not depend on the ** variables in Cube. Likewise for t == ge. */ if (t == one || t == fe || t == ge) { if (F->ref != 1 || G->ref != 1) cuddCacheInsert(manager, DD_BDD_AND_ABSTRACT_TAG, f, g, cube, t); return(t); } cuddRef(t); /* Special case: t + !t * anything == t + anything. */ if (t == Cudd_Not(fe)) { e = cuddBddExistAbstractRecur(manager, ge, Cube); } else if (t == Cudd_Not(ge)) { e = cuddBddExistAbstractRecur(manager, fe, Cube); } else { e = cuddBddAndAbstractRecur(manager, fe, ge, Cube); } if (e == NULL) { Cudd_IterDerefBdd(manager, t); return(NULL); } if (t == e) { r = t; cuddDeref(t); } else { cuddRef(e); r = cuddBddAndRecur(manager, Cudd_Not(t), Cudd_Not(e)); if (r == NULL) { Cudd_IterDerefBdd(manager, t); Cudd_IterDerefBdd(manager, e); return(NULL); } r = Cudd_Not(r); cuddRef(r); Cudd_DelayedDerefBdd(manager, t); Cudd_DelayedDerefBdd(manager, e); cuddDeref(r); } } else { t = cuddBddAndAbstractRecur(manager, ft, gt, cube); if (t == NULL) return(NULL); cuddRef(t); e = cuddBddAndAbstractRecur(manager, fe, ge, cube); if (e == NULL) { Cudd_IterDerefBdd(manager, t); return(NULL); } if (t == e) { r = t; cuddDeref(t); } else { cuddRef(e); if (Cudd_IsComplement(t)) { r = cuddUniqueInter(manager, (int) index, Cudd_Not(t), Cudd_Not(e)); if (r == NULL) { Cudd_IterDerefBdd(manager, t); Cudd_IterDerefBdd(manager, e); return(NULL); } r = Cudd_Not(r); } else { r = cuddUniqueInter(manager,(int)index,t,e); if (r == NULL) { Cudd_IterDerefBdd(manager, t); Cudd_IterDerefBdd(manager, e); return(NULL); } } cuddDeref(e); cuddDeref(t); } } if (F->ref != 1 || G->ref != 1) cuddCacheInsert(manager, DD_BDD_AND_ABSTRACT_TAG, f, g, cube, r); return (r); } /* end of cuddBddAndAbstractRecur */ /*---------------------------------------------------------------------------*/ /* Definition of static functions */ /*---------------------------------------------------------------------------*/ ABC_NAMESPACE_IMPL_END n251'>251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379
#!/bin/bash
#
# This transforms a CSV file into a gnuplot file.
# use option '-h' to display a help screen for all options.
#
# FracPete

# the usage of this script
function usage()
{
   echo 
   echo "usage: ${0##*/} [-i <file>] [-o <file>] [-g <file>] [-G <file>]"
   echo "       [-O <file>] [-d <delim>] [-t] [-x] [-a] [-l] [-T]"
   echo "       [-W <width> -H <height>]] [-F <x11|png|ps>]"
   echo "       [-b <files>] [-e]"
   echo "       [-h]"
   echo
   echo "Transforms a given CSV file into a gnuplot input file. It can also"
   echo "produce a gnuplot script for plotting the data, as well as batch"
   echo "processing of several files with automatic output generation."
   echo 
   echo " -h   this help"
   echo " -i   <file>"
   echo "      the CSV file to use as input"
   echo " -o   <file>"
   echo "      the gnuplot output file, output to stdout if not provided"
   echo " -g   <file>"
   echo "      generates a gnuplot script with this name to display the data"
   echo "      it assumes that the first column is the index for the x-axis."
   echo "      In combination with '-b' this parameter is only used to indicate"
   echo "      that a script is wanted, the filename itself is ignored."
   echo " -G   <file>"
   echo "      a file containing gnuplot options, comments etc. to be added "
   echo "      before the plots"
   echo " -O   <file>"
   echo "      generates a script that outputs the plot in the format specified"
   echo "      with '-F' in a file with the given name, instead of displaying "
   echo "      it in a window"
   echo " -d   <delim>"
   echo "      the delimiter that separates the columns, default: $DELIMITER"
   echo " -t   transposes the matrix first"
   echo " -x   adds a column for the x-axis (numbers starting from 1)"
   echo " -a   generates the average of the columns"
   echo " -l   adds 'with lines' to the gnuplot script"
   echo " -T   adds a number as title to the gnuplot script"
   echo " -F   <x11|png|ps>"
   echo "      the format of the output, default: $FORMAT"
   echo " -W   <width>"
   echo "      the width of the output (if '-F png'), default: $WIDTH"
   echo " -H   <height>"
   echo "      the height of the output (if '-F png'), default: $HEIGHT"
   echo " -b   <files>"
   echo "      processes the given files in batch mode, i.e. '-i' and '-o' are"
   echo "      not necessary. the files get new extensions automatically."
   echo "      Note: use \" if you're using wildcards like '*'"
   echo " -e   generates the desired output files directly, i.e. in creates a"
   echo "      temp. gnuplot file and runs this (in combination with '-b',"
   echo "      otherwise '-g' must be given). "
   echo "      Works only if format is ps or png ('-F')."
   echo 
}

# variables
INPUT=""
OUTPUT=""
OUTPUT_PLOT=""
GNUPLOT=""
GNUPLOT_OPTIONS=""
HAS_OUTPUT="no"
HAS_GNUPLOT="no"
DELIMITER=","
TRANSPOSE="no"
XAXIS="no"
AVERAGE="no"
LINES="no"
TITLE="no"
FORMAT="x11"
WIDTH="800"
HEIGHT="600"
BATCH_FILES=""
BATCH_OPTIONS=""
EXECUTE="no"

# interprete parameters
while getopts ":hi:o:g:d:txalTF:W:H:O:b:eG:" flag
do
   case $flag in
      i) INPUT=$OPTARG
         ;;
      o) OUTPUT=$OPTARG
         HAS_OUTPUT="yes"
         ;;
      g) GNUPLOT=$OPTARG
         HAS_GNUPLOT="yes"
         ;;
      G) GNUPLOT_OPTIONS=$OPTARG
         BATCH_OPTIONS="$BATCH_OPTIONS -$flag $OPTARG"
         ;;
      d) DELIMITER=$OPTARG
         ;;
      t) TRANSPOSE="yes"
         BATCH_OPTIONS="$BATCH_OPTIONS -$flag"
         ;;
      x) XAXIS="yes"
         BATCH_OPTIONS="$BATCH_OPTIONS -$flag"
         ;;
      a) AVERAGE="yes"
         BATCH_OPTIONS="$BATCH_OPTIONS -$flag"
         ;;
      l) LINES="yes"
         BATCH_OPTIONS="$BATCH_OPTIONS -$flag"
         ;;
      T) TITLE="yes"
         BATCH_OPTIONS="$BATCH_OPTIONS -$flag"
         ;;
      O) OUTPUT_PLOT=$OPTARG
         ;;
      W) WIDTH=$OPTARG
         BATCH_OPTIONS="$BATCH_OPTIONS -$flag $OPTARG"
         ;;
      H) HEIGHT=$OPTARG
         BATCH_OPTIONS="$BATCH_OPTIONS -$flag $OPTARG"
         ;;
      F) FORMAT=$OPTARG
         BATCH_OPTIONS="$BATCH_OPTIONS -$flag $OPTARG"
         ;;
      b) BATCH_FILES=$OPTARG
         ;;
      e) EXECUTE="yes"
         BATCH_OPTIONS="$BATCH_OPTIONS -$flag"
         ;;
      h) usage
         exit 0
         ;;
      *) echo
         echo "Unknown option: '-$OPTARG'"
         echo 
         usage
         exit 1
         ;;
   esac
done

# valid combinations of parameters?
if [ ! "$BATCH_FILES" = "" ] && [ "$EXECUTE" = "yes" ] && [ "$FORMAT" = "x11" ]
then
   echo
   echo "ERROR: a format other than '$FORMAT' must be specified if '-b' and"
   echo "       '-e' are specified, e.g. 'ps'."
   echo
   usage
   exit 2
fi

# batch-mode?
if [ ! "$BATCH_FILES" = "" ]
then
   for i in $BATCH_FILES
   do
      echo "$i..."

      # build options
      OPTIONS=$BATCH_OPTIONS
      OPTIONS="$OPTIONS -i $i"
      OPTIONS="$OPTIONS -o $i.dat"
      if [ "$HAS_GNUPLOT" = "yes" ]
      then
         OPTIONS="$OPTIONS -g $i.scr"
      fi
      if [ "$FORMAT" = "png" ]
      then
         OPTIONS="$OPTIONS -O $i.png"
      fi
      if [ "$FORMAT" = "ps" ]
      then
         OPTIONS="$OPTIONS -O $i.ps"
      fi
      
      # run script
      $0 $OPTIONS
   done
   
   exit 0
fi

# test files
if [ ! "$INPUT" = "" ] && [ ! -f "$INPUT" ]
then
   INPUT=""
fi
if [ ! "$GNUPLOT_OPTIONS" = "" ] && [ ! -f "$GNUPLOT_OPTIONS" ]
then
   echo "Warning: '$GNUPLOT_OPTIONS' not found - ignored!"
   GNUPLOT_OPTIONS=""
fi

if [ "$HAS_OUTPUT" = "no" ]
then
   OUTPUT=$INPUT".tmp"
fi

# everything provided?
if [ "$INPUT" = "" ] || [ "$DELIMITER" = "" ]
then
   echo 
   echo "ERROR: not all parameters provided or incorrect!"
   echo
   usage
   exit 1
fi

if [ "$EXECUTE" = "yes" ] && [ "$HAS_GNUPLOT" = "no" ]
then
   echo
   echo "ERROR: '-g' must be specified with option '-e'!"
   echo
   usage
   exit 3
fi

if [ "$OUTPUT_PLOT" = "" ] && [ ! "$FORMAT" = "x11" ]
then
   echo "Warning: output file for format '$FORMAT' not specified, falling back to 'x11'"
   FORMAT="x11"
fi

# some variables
TMPFILE=$OUTPUT".tmp"

# init
cp $INPUT $OUTPUT

# change modifier into " "
if [ ! "$DELIMITER" = " " ]
then
   cat $OUTPUT | sed s/$DELIMITER/" "/g > $TMPFILE
   cp $TMPFILE $OUTPUT
fi

# transpose matrix?
if [ "$TRANSPOSE" = "yes" ]
then
   cat $OUTPUT | exec awk '
   NR == 1 {
           n = NF
           for (i = 1; i <= NF; i++)
                   row[i] = $i
           next
   }
   {
           if (NF > n)
                   n = NF
           for (i = 1; i <= NF; i++)
                   row[i] = row[i] " " $i
   }
   END {
           for (i = 1; i <= n; i++)
                   print row[i]
   }' > $TMPFILE
   cp $TMPFILE $OUTPUT
fi

# average columns?
if [ "$AVERAGE" = "yes" ]
then
   COLCOUNT=`head -n1 $OUTPUT | wc -w | sed s/" "*//g`
   ROWCOUNT=`cat $OUTPUT | wc -l | sed s/" "*//g`
   rm -f $TMPFILE
   
   for ((i = 1; i <= $COLCOUNT; i++))
   do
      COL=`cat $OUTPUT | cut -f$i -d" "`
      
      # average
      TMP="("`echo $COL | sed s/" "/+/g`")/$ROWCOUNT"
      if [ $i -gt 1 ]
      then
         echo -n " " >> $TMPFILE
      fi
      TMP=`echo "scale=4; $TMP" | bc -l`
      echo -n $TMP >> $TMPFILE

      # stddev
      echo -n " " >> $TMPFILE
      TMP="sqrt(($ROWCOUNT * ("`echo $COL | sed s/" "/"^2+"/g | sed s/$/"^2"/g`") - ("`echo $COL | sed s/" "/"+"/g`")^2) / ($ROWCOUNT * ($ROWCOUNT - 1)))"
      TMP=`echo "scale=4; $TMP" | bc -l`
      echo -n $TMP >> $TMPFILE
   done
   echo >> $TMPFILE
   cp $TMPFILE $OUTPUT
fi

# add x-axis?
if [ "$XAXIS" = "yes" ]
then
   cat $OUTPUT | grep -n "." | sed s/":"/" "/g > $TMPFILE
   cp $TMPFILE $OUTPUT
fi

# gnuplot script?
if [ "$HAS_GNUPLOT" = "yes" ]
then
   # data columns
   COUNT=`head -n1 $OUTPUT | wc -w | sed s/" "*//g`

   # build output/format statement
   TERM="set terminal X11"
   OUT="set output"
   if [ "$FORMAT" = "png" ]
   then
      TERM="set terminal png size $WIDTH,$HEIGHT"
      OUT="set output \"$OUTPUT_PLOT\""
   fi
   if [ "$FORMAT" = "ps" ]
   then
      TERM="set terminal postscript"
      OUT="set output \"$OUTPUT_PLOT\""
   fi
   
   # build "with" statement
   TMP=""
   WITH=""
   if [ "$LINES" = "yes" ]
   then
      TMP=$TMP" lines"
   fi
   if [ "$TITLE" = "yes" ]
   then
      TMP=$TMP" title #"
   fi
   if [ ! "$TMP" = "" ]
   then
      WITH=" with"$TMP
   fi
   
   # init
   echo "# gnuplot script for '$OUTPUT'" > $GNUPLOT
   if [ ! "$GNUPLOT_OPTIONS" = "" ]
   then
      cat $GNUPLOT_OPTIONS >> $GNUPLOT
   fi

   # the plots
   echo "set title \"$INPUT\"" >> $GNUPLOT
   echo "plot \"$OUTPUT\" using 1:2 `echo $WITH | sed s/"#"/"\'1\'"/g`" >> $GNUPLOT
   for ((i = 2; i < $COUNT; i++))
   do
      echo "replot \"$OUTPUT\" using 1:$((i+1)) `echo $WITH | sed s/"#"/"\'$i\'"/g`" >> $GNUPLOT
   done
   echo >> $GNUPLOT

   # only pause if displayed in window
   if [ "$FORMAT" = "x11" ]
   then
      echo "pause -1" >> $GNUPLOT
   else
      echo "$TERM" >> $GNUPLOT
      echo "$OUT" >> $GNUPLOT
      echo "replot" >> $GNUPLOT
   fi

   # run gnuplot
   if [ "$EXECUTE" = "yes" ]
   then
      if [ "$FORMAT" = "x11" ]
      then
         echo "Press <Return> to close window..."
      fi
      gnuplot "$GNUPLOT"
   fi
fi

# clean up
rm -f $TMPFILE
if [ "$HAS_OUTPUT" = "no" ]
then
   cat $OUTPUT
   rm -f $OUTPUT
fi