Age         Owner                  TLA  Line data    Source code

                                  1                 : /*------------------------------------------------------------------------
                                  2                 : *
                                  3                 : * geqo_recombination.c
                                  4                 : *    misc recombination procedures
                                  5                 : *
                                  6                 : * src/backend/optimizer/geqo/geqo_recombination.c
                                  7                 : *
                                  8                 : *-------------------------------------------------------------------------
                                  9                 : */
                                 10                 : 
                                 11                 : /* contributed by:
                                 12                 :    =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
                                 13                 :    *  Martin Utesch              * Institute of Automatic Control      *
                                 14                 :    =                             = University of Mining and Technology =
                                 15                 :    *  utesch@aut.tu-freiberg.de  * Freiberg, Germany                   *
                                 16                 :    =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
                                 17                 :  */
                                 18                 : 
                                 19                 : /* -- parts of this are adapted from D. Whitley's Genitor algorithm -- */
                                 20                 : 
                                 21                 : #include "postgres.h"
                                 22                 : 
                                 23                 : #include "optimizer/geqo_random.h"
                                 24                 : #include "optimizer/geqo_recombination.h"
                                 25                 : 
                                 26                 : 
                                 27                 : /*
                                 28                 :  * init_tour
                                 29                 :  *
                                 30                 :  *   Randomly generates a legal "traveling salesman" tour
                                 31                 :  *   (i.e. where each point is visited only once.)
                                 32                 :  */
                                 33                 : void
 5015 tgl                        34 CBC         192 : init_tour(PlannerInfo *root, Gene *tour, int num_gene)
                                 35                 : {
                                 36                 :     int         i,
                                 37                 :                 j;
                                 38                 : 
                                 39                 :     /*
                                 40                 :      * We must fill the tour[] array with a random permutation of the numbers
                                 41                 :      * 1 .. num_gene.  We can do that in one pass using the "inside-out"
                                 42                 :      * variant of the Fisher-Yates shuffle algorithm.  Notionally, we append
                                 43                 :      * each new value to the array and then swap it with a randomly-chosen
                                 44                 :      * array element (possibly including itself, else we fail to generate
                                 45                 :      * permutations with the last city last).  The swap step can be optimized
                                 46                 :      * by combining it with the insertion.
                                 47                 :      */
 2712                            48             192 :     if (num_gene > 0)
                                 49             192 :         tour[0] = (Gene) 1;
                                 50                 : 
                                 51             960 :     for (i = 1; i < num_gene; i++)
                                 52                 :     {
                                 53             768 :         j = geqo_randint(root, i, 0);
                                 54                 :         /* i != j check avoids fetching uninitialized array element */
                                 55             768 :         if (i != j)
                                 56             546 :             tour[i] = tour[j];
                                 57             768 :         tour[j] = (Gene) (i + 1);
                                 58                 :     }
bruce                      59             192 : }
                                 60                 : 
                                 61                 : /* city table is used in these recombination methods: */
                                 62                 : #if defined(CX) || defined(PX) || defined(OX1) || defined(OX2)
                                 63                 : 
                                 64                 : /* alloc_city_table
                                 65                 :  *
                                 66                 :  *   allocate memory for city table
                                 67                 :  */
                                 68                 : City *
                                 69                 : alloc_city_table(PlannerInfo *root, int num_gene)
                                 70                 : {
                                 71                 :     City       *city_table;
                                 72                 : 
                                 73                 :     /*
                                 74                 :      * palloc one extra location so that nodes numbered 1..n can be indexed
                                 75                 :      * directly; 0 will not be used
                                 76                 :      */
                                 77                 :     city_table = (City *) palloc((num_gene + 1) * sizeof(City));
                                 78                 : 
                                 79                 :     return city_table;
                                 80                 : }
                                 81                 : 
                                 82                 : /* free_city_table
                                 83                 :  *
                                 84                 :  *    deallocate memory of city table
                                 85                 :  */
                                 86                 : void
                                 87                 : free_city_table(PlannerInfo *root, City * city_table)
                                 88                 : {
                                 89                 :     pfree(city_table);
                                 90                 : }
                                 91                 : 
                                 92                 : #endif                          /* CX || PX || OX1 || OX2 */