← Back to branch summary

~ubuntu-branches/ubuntu/oneiric/postgresql-9.1/oneiric-security

« back to all changes in this revision

Viewing changes to src/backend/optimizer/geqo/geqo_recombination.c

  • Committer: Bazaar Package Importer
  • Author(s): Martin Pitt
  • Date: 2011-05-11 10:41:53 UTC
  • Revision ID: james.westby@ubuntu.com-20110511104153-psbh2o58553fv1m0
Tags: upstream-9.1~beta1
Import upstream version 9.1~beta1

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/backend/optimizer/geqo/geqo_recombination.c
 
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
 *       Essentially, this routine fills an array with all possible
 
33
 *       points on the tour and randomly chooses the 'next' city from
 
34
 *       this array.  When a city is chosen, the array is shortened
 
35
 *       and the procedure repeated.
 
36
 */
 
37
void
 
38
init_tour(PlannerInfo *root, Gene *tour, int num_gene)
 
39
{
 
40
        Gene       *tmp;
 
41
        int                     remainder;
 
42
        int                     next,
 
43
                                i;
 
44
 
 
45
        /* Fill a temp array with the IDs of all not-yet-visited cities */
 
46
        tmp = (Gene *) palloc(num_gene * sizeof(Gene));
 
47
 
 
48
        for (i = 0; i < num_gene; i++)
 
49
                tmp[i] = (Gene) (i + 1);
 
50
 
 
51
        remainder = num_gene - 1;
 
52
 
 
53
        for (i = 0; i < num_gene; i++)
 
54
        {
 
55
                /* choose value between 0 and remainder inclusive */
 
56
                next = geqo_randint(root, remainder, 0);
 
57
                /* output that element of the tmp array */
 
58
                tour[i] = tmp[next];
 
59
                /* and delete it */
 
60
                tmp[next] = tmp[remainder];
 
61
                remainder--;
 
62
        }
 
63
 
 
64
        pfree(tmp);
 
65
}
 
66
 
 
67
/* alloc_city_table
 
68
 *
 
69
 *       allocate memory for city table
 
70
 */
 
71
City *
 
72
alloc_city_table(PlannerInfo *root, int num_gene)
 
73
{
 
74
        City       *city_table;
 
75
 
 
76
        /*
 
77
         * palloc one extra location so that nodes numbered 1..n can be indexed
 
78
         * directly; 0 will not be used
 
79
         */
 
80
        city_table = (City *) palloc((num_gene + 1) * sizeof(City));
 
81
 
 
82
        return city_table;
 
83
}
 
84
 
 
85
/* free_city_table
 
86
 *
 
87
 *        deallocate memory of city table
 
88
 */
 
89
void
 
90
free_city_table(PlannerInfo *root, City *city_table)
 
91
{
 
92
        pfree(city_table);
 
93
}