Version abc71001

1 files changed, 921 insertions, 0 deletions

diff --git a/src/bdd/cudd/cuddGenetic.c b/src/bdd/cudd/cuddGenetic.c
new file mode 100644
index 00000000..9fe03dad
--- /dev/null
+++ b/src/bdd/cudd/cuddGenetic.c
@@ -0,0 +1,921 @@
+/**CFile***********************************************************************
+
+  FileName    [cuddGenetic.c]
+
+  PackageName [cudd]
+
+  Synopsis    [Genetic algorithm for variable reordering.]
+
+  Description [Internal procedures included in this file:
+        <ul>
+        <li> cuddGa()
+        </ul>
+    Static procedures included in this module:
+        <ul>
+        <li> make_random()
+        <li> sift_up()
+        <li> build_dd()
+        <li> largest()
+        <li> rand_int()
+        <li> array_hash()
+        <li> array_compare()
+        <li> find_best()
+        <li> find_average_fitness()
+        <li> PMX()
+        <li> roulette()
+        </ul>
+
+  The genetic algorithm implemented here is as follows.  We start with
+  the current DD order.  We sift this order and use this as the
+  reference DD.  We only keep 1 DD around for the entire process and
+  simply rearrange the order of this DD, storing the various orders
+  and their corresponding DD sizes.  We generate more random orders to
+  build an initial population. This initial population is 3 times the
+  number of variables, with a maximum of 120. Each random order is
+  built (from the reference DD) and its size stored.  Each random
+  order is also sifted to keep the DD sizes fairly small.  Then a
+  crossover is performed between two orders (picked randomly) and the
+  two resulting DDs are built and sifted.  For each new order, if its
+  size is smaller than any DD in the population, it is inserted into
+  the population and the DD with the largest number of nodes is thrown
+  out. The crossover process happens up to 50 times, and at this point
+  the DD in the population with the smallest size is chosen as the
+  result.  This DD must then be built from the reference DD.]
+
+  SeeAlso     []
+
+  Author      [Curt Musfeldt, Alan Shuler, Fabio Somenzi]
+
+  Copyright [This file was created at the University of Colorado at
+  Boulder.  The University of Colorado at Boulder makes no warranty
+  about the suitability of this software for any purpose.  It is
+  presented on an AS IS basis.]
+
+******************************************************************************/
+
+#include "util_hack.h"
+#include "cuddInt.h"
+
+/*---------------------------------------------------------------------------*/
+/* Constant declarations                                                     */
+/*---------------------------------------------------------------------------*/
+
+/*---------------------------------------------------------------------------*/
+/* Stucture declarations                                                     */
+/*---------------------------------------------------------------------------*/
+
+/*---------------------------------------------------------------------------*/
+/* Type declarations                                                         */
+/*---------------------------------------------------------------------------*/
+
+/*---------------------------------------------------------------------------*/
+/* Variable declarations                                                     */
+/*---------------------------------------------------------------------------*/
+
+#ifndef lint
+static char rcsid[] DD_UNUSED = "$Id: cuddGenetic.c,v 1.1.1.1 2003/02/24 22:23:52 wjiang Exp $";
+#endif
+
+static int popsize;        /* the size of the population */
+static int numvars;        /* the number of input variables in the ckt. */
+/* storedd stores the population orders and sizes. This table has two
+** extra rows and one extras column. The two extra rows are used for the
+** offspring produced by a crossover. Each row stores one order and its
+** size. The order is stored by storing the indices of variables in the
+** order in which they appear in the order. The table is in reality a
+** one-dimensional array which is accessed via a macro to give the illusion
+** it is a two-dimensional structure.
+*/
+static int *storedd;
+static st_table *computed;    /* hash table to identify existing orders */
+static int *repeat;        /* how many times an order is present */
+static int large;        /* stores the index of the population with
+                ** the largest number of nodes in the DD */
+static int result;
+static int cross;        /* the number of crossovers to perform */
+
+/*---------------------------------------------------------------------------*/
+/* Macro declarations                                                        */
+/*---------------------------------------------------------------------------*/
+
+/* macro used to access the population table as if it were a
+** two-dimensional structure.
+*/
+#define STOREDD(i,j)    storedd[(i)*(numvars+1)+(j)]
+
+
+/**AutomaticStart*************************************************************/
+
+/*---------------------------------------------------------------------------*/
+/* Static function prototypes                                                */
+/*---------------------------------------------------------------------------*/
+
+static int make_random ARGS((DdManager *table, int lower));
+static int sift_up ARGS((DdManager *table, int x, int x_low));
+static int build_dd ARGS((DdManager *table, int num, int lower, int upper));
+static int largest ARGS(());
+static int rand_int ARGS((int a));
+static int array_hash ARGS((char *array, int modulus));
+static int array_compare ARGS((const char *array1, const char *array2));
+static int find_best ARGS(());
+static double find_average_fitness ARGS(());
+static int PMX ARGS((int maxvar));
+static int roulette ARGS((int *p1, int *p2));
+
+/**AutomaticEnd***************************************************************/
+
+
+/*---------------------------------------------------------------------------*/
+/* Definition of exported functions                                          */
+/*---------------------------------------------------------------------------*/
+
+/*---------------------------------------------------------------------------*/
+/* Definition of internal functions                                          */
+/*---------------------------------------------------------------------------*/
+
+
+/**Function********************************************************************
+
+  Synopsis    [Genetic algorithm for DD reordering.]
+
+  Description [Genetic algorithm for DD reordering.
+  The two children of a crossover will be stored in
+  storedd[popsize] and storedd[popsize+1] --- the last two slots in the
+  storedd array.  (This will make comparisons and replacement easy.)
+  Returns 1 in case of success; 0 otherwise.]
+
+  SideEffects [None]
+
+  SeeAlso     []
+
+******************************************************************************/
+int
+cuddGa(
+  DdManager * table /* manager */,
+  int  lower /* lowest level to be reordered */,
+  int  upper /* highest level to be reorderded */)
+{
+    int     i,n,m;        /* dummy/loop vars */
+    int        index;
+    double    average_fitness;
+    int        small;        /* index of smallest DD in population */
+
+    /* Do an initial sifting to produce at least one reasonable individual. */
+    if (!cuddSifting(table,lower,upper)) return(0);
+
+    /* Get the initial values. */
+    numvars = upper - lower + 1; /* number of variables to be reordered */
+    if (table->populationSize == 0) {
+    popsize = 3 * numvars;  /* population size is 3 times # of vars */
+    if (popsize > 120) {
+        popsize = 120;    /* Maximum population size is 120 */
+    }
+    } else {
+    popsize = table->populationSize;  /* user specified value */
+    }
+    if (popsize < 4) popsize = 4;    /* enforce minimum population size */
+
+    /* Allocate population table. */
+    storedd = ALLOC(int,(popsize+2)*(numvars+1));
+    if (storedd == NULL) {
+    table->errorCode = CUDD_MEMORY_OUT;
+    return(0);
+    }
+
+    /* Initialize the computed table. This table is made up of two data
+    ** structures: A hash table with the key given by the order, which says
+    ** if a given order is present in the population; and the repeat
+    ** vector, which says how many copies of a given order are stored in
+    ** the population table. If there are multiple copies of an order, only
+    ** one has a repeat count greater than 1. This copy is the one pointed
+    ** by the computed table.
+    */
+    repeat = ALLOC(int,popsize);
+    if (repeat == NULL) {
+    table->errorCode = CUDD_MEMORY_OUT;
+    FREE(storedd);
+    return(0);
+    }
+    for (i = 0; i < popsize; i++) {
+    repeat[i] = 0;
+    }
+    computed = st_init_table(array_compare,array_hash);
+    if (computed == NULL) {
+    table->errorCode = CUDD_MEMORY_OUT;
+    FREE(storedd);
+    FREE(repeat);
+    return(0);
+    }
+
+    /* Copy the current DD and its size to the population table. */
+    for (i = 0; i < numvars; i++) {
+    STOREDD(0,i) = table->invperm[i+lower]; /* order of initial DD */
+    }
+    STOREDD(0,numvars) = table->keys - table->isolated; /* size of initial DD */
+
+    /* Store the initial order in the computed table. */
+    if (st_insert(computed,(char *)storedd,(char *) 0) == ST_OUT_OF_MEM) {
+    FREE(storedd);
+    FREE(repeat);
+    st_free_table(computed);
+    return(0);
+    }
+    repeat[0]++;
+
+    /* Insert the reverse order as second element of the population. */
+    for (i = 0; i < numvars; i++) {
+    STOREDD(1,numvars-1-i) = table->invperm[i+lower]; /* reverse order */
+    }
+
+    /* Now create the random orders. make_random fills the population
+    ** table with random permutations. The successive loop builds and sifts
+    ** the DDs for the reverse order and each random permutation, and stores
+    ** the results in the computed table.
+    */
+    if (!make_random(table,lower)) {
+    table->errorCode = CUDD_MEMORY_OUT;
+    FREE(storedd);
+    FREE(repeat);
+    st_free_table(computed);
+    return(0);
+    }
+    for (i = 1; i < popsize; i++) {
+    result = build_dd(table,i,lower,upper);    /* build and sift order */
+    if (!result) {
+        FREE(storedd);
+        FREE(repeat);
+        st_free_table(computed);
+        return(0);
+    }
+    if (st_lookup(computed,(char *)&STOREDD(i,0),(char **)&index)) {
+        repeat[index]++;
+    } else {
+        if (st_insert(computed,(char *)&STOREDD(i,0),(char *)(long)i) ==
+        ST_OUT_OF_MEM) {
+        FREE(storedd);
+        FREE(repeat);
+        st_free_table(computed);
+        return(0);
+        }
+        repeat[i]++;
+    }
+    }
+
+#if 0
+#ifdef DD_STATS
+    /* Print the initial population. */
+    (void) fprintf(table->out,"Initial population after sifting\n");
+    for (m = 0; m < popsize; m++) {
+    for (i = 0; i < numvars; i++) {
+        (void) fprintf(table->out," %2d",STOREDD(m,i));
+    }
+    (void) fprintf(table->out," : %3d (%d)\n",
+               STOREDD(m,numvars),repeat[m]);
+    }
+#endif
+#endif
+
+    small = find_best();
+    average_fitness = find_average_fitness();
+#ifdef DD_STATS
+    (void) fprintf(table->out,"\nInitial population: best fitness = %d, average fitness %8.3f",STOREDD(small,numvars),average_fitness);
+#endif
+
+    /* Decide how many crossovers should be tried. */
+    if (table->numberXovers == 0) {
+    cross = 3*numvars;
+    if (cross > 60) {    /* do a maximum of 50 crossovers */
+        cross = 60;
+    }
+    } else {
+    cross = table->numberXovers;      /* use user specified value */
+    }
+
+    /* Perform the crossovers to get the best order. */
+    for (m = 0; m < cross; m++) {
+    if (!PMX(table->size)) {    /* perform one crossover */
+        table->errorCode = CUDD_MEMORY_OUT;
+        FREE(storedd);
+        FREE(repeat);
+        st_free_table(computed);
+        return(0);
+    }
+    /* The offsprings are left in the last two entries of the
+    ** population table. These are now considered in turn.
+    */
+    for (i = popsize; i <= popsize+1; i++) {
+        result = build_dd(table,i,lower,upper); /* build and sift child */
+        if (!result) {
+        FREE(storedd);
+        FREE(repeat);
+        st_free_table(computed);
+        return(0);
+        }
+        large = largest();    /* find the largest DD in population */
+
+        /* If the new child is smaller than the largest DD in the current
+        ** population, enter it into the population in place of the
+        ** largest DD.
+        */
+        if (STOREDD(i,numvars) < STOREDD(large,numvars)) {
+        /* Look up the largest DD in the computed table.
+        ** Decrease its repetition count. If the repetition count
+        ** goes to 0, remove the largest DD from the computed table.
+        */
+        result = st_lookup(computed,(char *)&STOREDD(large,0),(char
+        **)&index);
+        if (!result) {
+            FREE(storedd);
+            FREE(repeat);
+            st_free_table(computed);
+            return(0);
+        }
+        repeat[index]--;
+        if (repeat[index] == 0) {
+            int *pointer = &STOREDD(index,0);
+            result = st_delete(computed, (char **)&pointer,NULL);
+            if (!result) {
+            FREE(storedd);
+            FREE(repeat);
+            st_free_table(computed);
+            return(0);
+            }
+        }
+        /* Copy the new individual to the entry of the
+        ** population table just made available and update the
+        ** computed table.
+        */
+        for (n = 0; n <= numvars; n++) {
+            STOREDD(large,n) = STOREDD(i,n);
+        }
+        if (st_lookup(computed,(char *)&STOREDD(large,0),(char
+        **)&index)) {
+            repeat[index]++;
+        } else {
+            if (st_insert(computed,(char *)&STOREDD(large,0),
+            (char *)(long)large) == ST_OUT_OF_MEM) {
+            FREE(storedd);
+            FREE(repeat);
+            st_free_table(computed);
+            return(0);
+            }
+            repeat[large]++;
+        }
+        }
+    }
+    }
+
+    /* Find the smallest DD in the population and build it;
+    ** that will be the result.
+    */
+    small = find_best();
+
+    /* Print stats on the final population. */
+#ifdef DD_STATS
+    average_fitness = find_average_fitness();
+    (void) fprintf(table->out,"\nFinal population: best fitness = %d, average fitness %8.3f",STOREDD(small,numvars),average_fitness);
+#endif
+
+    /* Clean up, build the result DD, and return. */
+    st_free_table(computed);
+    computed = NULL;
+    result = build_dd(table,small,lower,upper);
+    FREE(storedd);
+    FREE(repeat);
+    return(result);
+
+} /* end of cuddGa */
+
+
+/*---------------------------------------------------------------------------*/
+/* Definition of static functions                                            */
+/*---------------------------------------------------------------------------*/
+
+/**Function********************************************************************
+
+  Synopsis    [Generates the random sequences for the initial population.]
+
+  Description [Generates the random sequences for the initial population.
+  The sequences are permutations of the indices between lower and
+  upper in the current order.]
+
+  SideEffects [None]
+
+  SeeAlso     []
+
+******************************************************************************/
+static int
+make_random(
+  DdManager * table,
+  int  lower)
+{
+    int i,j;        /* loop variables */
+    int    *used;        /* is a number already in a permutation */
+    int    next;        /* next random number without repetitions */
+
+    used = ALLOC(int,numvars);
+    if (used == NULL) {
+    table->errorCode = CUDD_MEMORY_OUT;
+    return(0);
+    }
+#if 0
+#ifdef DD_STATS
+    (void) fprintf(table->out,"Initial population before sifting\n");
+    for (i = 0; i < 2; i++) {
+    for (j = 0; j < numvars; j++) {
+        (void) fprintf(table->out," %2d",STOREDD(i,j));
+    }
+    (void) fprintf(table->out,"\n");
+    }
+#endif
+#endif
+    for (i = 2; i < popsize; i++) {
+           for (j = 0; j < numvars; j++) {
+        used[j] = 0;
+    }
+    /* Generate a permutation of {0...numvars-1} and use it to
+    ** permute the variables in the layesr from lower to upper.
+    */
+           for (j = 0; j < numvars; j++) {
+        do {
+        next = rand_int(numvars-1);
+        } while (used[next] != 0);
+        used[next] = 1;
+        STOREDD(i,j) = table->invperm[next+lower];
+           }
+#if 0
+#ifdef DD_STATS
+    /* Print the order just generated. */
+    for (j = 0; j < numvars; j++) {
+        (void) fprintf(table->out," %2d",STOREDD(i,j));
+    }
+    (void) fprintf(table->out,"\n");
+#endif
+#endif
+    }
+    FREE(used);
+    return(1);
+
+} /* end of make_random */
+
+
+/**Function********************************************************************
+
+  Synopsis    [Moves one variable up.]
+
+  Description [Takes a variable from position x and sifts it up to
+  position x_low;  x_low should be less than x. Returns 1 if successful;
+  0 otherwise]
+
+  SideEffects [None]
+
+  SeeAlso     []
+
+******************************************************************************/
+static int
+sift_up(
+  DdManager * table,
+  int  x,
+  int  x_low)
+{
+    int        y;
+    int        size;
+
+    y = cuddNextLow(table,x);
+    while (y >= x_low) {
+    size = cuddSwapInPlace(table,y,x);
+    if (size == 0) {
+        return(0);
+    }
+    x = y;
+    y = cuddNextLow(table,x);
+    }
+    return(1);
+
+} /* end of sift_up */
+
+
+/**Function********************************************************************
+
+  Synopsis [Builds a DD from a given order.]
+
+  Description [Builds a DD from a given order.  This procedure also
+  sifts the final order and inserts into the array the size in nodes
+  of the result. Returns 1 if successful; 0 otherwise.]
+
+  SideEffects [None]
+
+  SeeAlso     []
+
+******************************************************************************/
+static int
+build_dd(
+  DdManager * table,
+  int  num /* the index of the individual to be built */,
+  int  lower,
+  int  upper)
+{
+    int     i,j;        /* loop vars */
+    int     position;
+    int        index;
+    int        limit;        /* how large the DD for this order can grow */
+    int        size;
+
+    /* Check the computed table. If the order already exists, it
+    ** suffices to copy the size from the existing entry.
+    */
+    if (computed && st_lookup(computed,(char *)&STOREDD(num,0),(char **)&index)) {
+    STOREDD(num,numvars) = STOREDD(index,numvars);
+#ifdef DD_STATS
+    (void) fprintf(table->out,"\nCache hit for index %d", index);
+#endif
+    return(1);
+    }
+
+    /* Stop if the DD grows 20 times larges than the reference size. */
+    limit = 20 * STOREDD(0,numvars);
+
+    /* Sift up the variables so as to build the desired permutation.
+    ** First the variable that has to be on top is sifted to the top.
+    ** Then the variable that has to occupy the secon position is sifted
+    ** up to the second position, and so on.
+    */
+    for (j = 0; j < numvars; j++) {
+    i = STOREDD(num,j);
+    position = table->perm[i];
+    result = sift_up(table,position,j+lower);
+    if (!result) return(0);
+    size = table->keys - table->isolated;
+    if (size > limit) break;
+    }
+
+    /* Sift the DD just built. */
+#ifdef DD_STATS
+    (void) fprintf(table->out,"\n");
+#endif
+    result = cuddSifting(table,lower,upper);
+    if (!result) return(0);
+
+    /* Copy order and size to table. */
+    for (j = 0; j < numvars; j++) {
+    STOREDD(num,j) = table->invperm[lower+j];
+    }
+    STOREDD(num,numvars) = table->keys - table->isolated; /* size of new DD */
+    return(1);
+
+} /* end of build_dd */
+
+
+/**Function********************************************************************
+
+  Synopsis    [Finds the largest DD in the population.]
+
+  Description [Finds the largest DD in the population. If an order is
+  repeated, it avoids choosing the copy that is in the computed table
+  (it has repeat[i] > 1).]
+
+  SideEffects [None]
+
+  SeeAlso     []
+
+******************************************************************************/
+static int
+largest(
+   )
+{
+    int i;    /* loop var */
+    int big;    /* temporary holder to return result */
+
+    big = 0;
+    while (repeat[big] > 1) big++;
+    for (i = big + 1; i < popsize; i++) {
+    if (STOREDD(i,numvars) >= STOREDD(big,numvars) && repeat[i] <= 1) {
+        big = i;
+    }
+    }
+    return(big);
+
+} /* end of largest */
+
+
+/**Function********************************************************************
+
+  Synopsis    [Generates a random number between 0 and the integer a.]
+
+  Description []
+
+  SideEffects [None]
+
+  SeeAlso     []
+
+******************************************************************************/
+static int
+rand_int(
+  int  a)
+{
+    return(Cudd_Random() % (a+1));
+
+} /* end of rand_int */
+
+
+/**Function********************************************************************
+
+  Synopsis    [Hash function for the computed table.]
+
+  Description [Hash function for the computed table. Returns the bucket
+  number.]
+
+  SideEffects [None]
+
+  SeeAlso     []
+
+******************************************************************************/
+static int
+array_hash(
+  char * array,
+  int  modulus)
+{
+    int val = 0;
+    int i;
+    int *intarray;
+
+    intarray = (int *) array;
+
+    for (i = 0; i < numvars; i++) {
+    val = val * 997 + intarray[i];
+    }
+
+    return ((val < 0) ? -val : val) % modulus;
+
+} /* end of array_hash */
+
+
+/**Function********************************************************************
+
+  Synopsis    [Comparison function for the computed table.]
+
+  Description [Comparison function for the computed table. Returns 0 if
+  the two arrays are equal; 1 otherwise.]
+
+  SideEffects [None]
+
+  SeeAlso     []
+
+******************************************************************************/
+static int
+array_compare(
+  const char * array1,
+  const char * array2)
+{
+    int i;
+    int *intarray1, *intarray2;
+
+    intarray1 = (int *) array1;
+    intarray2 = (int *) array2;
+
+    for (i = 0; i < numvars; i++) {
+    if (intarray1[i] != intarray2[i]) return(1);
+    }
+    return(0);
+
+} /* end of array_compare */
+
+
+/**Function********************************************************************
+
+  Synopsis    [Returns the index of the fittest individual.]
+
+  Description []
+
+  SideEffects [None]
+
+  SeeAlso     []
+
+******************************************************************************/
+static int
+find_best(
+   )
+{
+    int i,small;
+
+    small = 0;
+    for (i = 1; i < popsize; i++) {
+    if (STOREDD(i,numvars) < STOREDD(small,numvars)) {
+        small = i;
+    }
+    }
+    return(small);
+
+} /* end of find_best */
+
+
+/**Function********************************************************************
+
+  Synopsis    [Returns the average fitness of the population.]
+
+  Description []
+
+  SideEffects [None]
+
+  SeeAlso     []
+
+******************************************************************************/
+static double
+find_average_fitness(
+   )
+{
+    int i;
+    int total_fitness = 0;
+    double average_fitness;
+
+    for (i = 0; i < popsize; i++) {
+    total_fitness += STOREDD(i,numvars);
+    }
+    average_fitness = (double) total_fitness / (double) popsize;
+    return(average_fitness);
+
+} /* end of find_average_fitness */
+
+
+/**Function********************************************************************
+
+  Synopsis [Performs the crossover between two parents.]
+
+  Description [Performs the crossover between two randomly chosen
+  parents, and creates two children, x1 and x2. Uses the Partially
+  Matched Crossover operator.]
+
+  SideEffects [None]
+
+  SeeAlso     []
+
+******************************************************************************/
+static int
+PMX(
+  int  maxvar)
+{
+    int     cut1,cut2;    /* the two cut positions (random) */
+    int     mom,dad;    /* the two randomly chosen parents */
+    int        *inv1;        /* inverse permutations for repair algo */
+    int        *inv2;
+    int     i;        /* loop vars */
+    int        u,v;        /* aux vars */
+
+    inv1 = ALLOC(int,maxvar);
+    if (inv1 == NULL) {
+    return(0);
+    }
+    inv2 = ALLOC(int,maxvar);
+    if (inv2 == NULL) {
+    FREE(inv1);
+    return(0);
+    }
+
+    /* Choose two orders from the population using roulette wheel. */
+    if (!roulette(&mom,&dad)) {
+    FREE(inv1);
+    FREE(inv2);
+    return(0);
+    }
+
+    /* Choose two random cut positions. A cut in position i means that
+    ** the cut immediately precedes position i.  If cut1 < cut2, we
+    ** exchange the middle of the two orderings; otherwise, we
+    ** exchange the beginnings and the ends.
+    */
+    cut1 = rand_int(numvars-1);
+    do {
+    cut2 = rand_int(numvars-1);
+    } while (cut1 == cut2);
+
+#if 0
+    /* Print out the parents. */
+    (void) fprintf(table->out,
+           "Crossover of %d (mom) and %d (dad) between %d and %d\n",
+           mom,dad,cut1,cut2);
+    for (i = 0; i < numvars; i++) {
+    if (i == cut1 || i == cut2) (void) fprintf(table->out,"|");
+    (void) fprintf(table->out,"%2d ",STOREDD(mom,i));
+    }
+    (void) fprintf(table->out,"\n");
+    for (i = 0; i < numvars; i++) {
+    if (i == cut1 || i == cut2) (void) fprintf(table->out,"|");
+    (void) fprintf(table->out,"%2d ",STOREDD(dad,i));
+    }
+    (void) fprintf(table->out,"\n");
+#endif
+
+    /* Initialize the inverse permutations: -1 means yet undetermined. */
+    for (i = 0; i < maxvar; i++) {
+    inv1[i] = -1;
+    inv2[i] = -1;
+    }
+
+    /* Copy the portions whithin the cuts. */
+    for (i = cut1; i != cut2; i = (i == numvars-1) ? 0 : i+1) {
+    STOREDD(popsize,i) = STOREDD(dad,i);
+    inv1[STOREDD(popsize,i)] = i;
+    STOREDD(popsize+1,i) = STOREDD(mom,i);
+    inv2[STOREDD(popsize+1,i)] = i;
+    }
+
+    /* Now apply the repair algorithm outside the cuts. */
+    for (i = cut2; i != cut1; i = (i == numvars-1 ) ? 0 : i+1) {
+    v = i;
+    do {
+        u = STOREDD(mom,v);
+        v = inv1[u];
+    } while (v != -1);
+    STOREDD(popsize,i) = u;
+    inv1[u] = i;
+    v = i;
+    do {
+        u = STOREDD(dad,v);
+        v = inv2[u];
+    } while (v != -1);
+    STOREDD(popsize+1,i) = u;
+    inv2[u] = i;
+    }
+
+#if 0
+    /* Print the results of crossover. */
+    for (i = 0; i < numvars; i++) {
+    if (i == cut1 || i == cut2) (void) fprintf(table->out,"|");
+    (void) fprintf(table->out,"%2d ",STOREDD(popsize,i));
+    }
+    (void) fprintf(table->out,"\n");
+    for (i = 0; i < numvars; i++) {
+    if (i == cut1 || i == cut2) (void) fprintf(table->out,"|");
+    (void) fprintf(table->out,"%2d ",STOREDD(popsize+1,i));
+    }
+    (void) fprintf(table->out,"\n");
+#endif
+
+    FREE(inv1);
+    FREE(inv2);
+    return(1);
+
+} /* end of PMX */
+
+
+/**Function********************************************************************
+
+  Synopsis    [Selects two parents with the roulette wheel method.]
+
+  Description [Selects two distinct parents with the roulette wheel method.]
+
+  SideEffects [The indices of the selected parents are returned as side
+  effects.]
+
+  SeeAlso     []
+
+******************************************************************************/
+static int
+roulette(
+  int * p1,
+  int * p2)
+{
+    double *wheel;
+    double spin;
+    int i;
+
+    wheel = ALLOC(double,popsize);
+    if (wheel == NULL) {
+    return(0);
+    }
+
+    /* The fitness of an individual is the reciprocal of its size. */
+    wheel[0] = 1.0 / (double) STOREDD(0,numvars);
+
+    for (i = 1; i < popsize; i++) {
+    wheel[i] = wheel[i-1] + 1.0 / (double) STOREDD(i,numvars);
+    }
+
+    /* Get a random number between 0 and wheel[popsize-1] (that is,
+    ** the sum of all fitness values. 2147483561 is the largest number
+    ** returned by Cudd_Random.
+    */
+    spin = wheel[numvars-1] * (double) Cudd_Random() / 2147483561.0;
+
+    /* Find the lucky element by scanning the wheel. */
+    for (i = 0; i < popsize; i++) {
+    if (spin <= wheel[i]) break;
+    }
+    *p1 = i;
+
+    /* Repeat the process for the second parent, making sure it is
+    ** distinct from the first.
+    */
+    do {
+    spin = wheel[popsize-1] * (double) Cudd_Random() / 2147483561.0;
+    for (i = 0; i < popsize; i++) {
+        if (spin <= wheel[i]) break;
+    }
+    } while (i == *p1);
+    *p2 = i;
+
+    FREE(wheel);
+    return(1);
+
+} /* end of roulette */
+