PostgreSQL Source Code git master
geqo_recombination.h File Reference
#include "optimizer/geqo.h"
Include dependency graph for geqo_recombination.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures

struct  Edge
 
struct  City
 

Macros

#define DAD   1 /* indicator for gene from dad */
 
#define MOM   0 /* indicator for gene from mom */
 

Typedefs

typedef struct Edge Edge
 
typedef struct City City
 

Functions

void init_tour (PlannerInfo *root, Gene *tour, int num_gene)
 
Edgealloc_edge_table (PlannerInfo *root, int num_gene)
 
void free_edge_table (PlannerInfo *root, Edge *edge_table)
 
float gimme_edge_table (PlannerInfo *root, Gene *tour1, Gene *tour2, int num_gene, Edge *edge_table)
 
int gimme_tour (PlannerInfo *root, Edge *edge_table, Gene *new_gene, int num_gene)
 
void pmx (PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene)
 
Cityalloc_city_table (PlannerInfo *root, int num_gene)
 
void free_city_table (PlannerInfo *root, City *city_table)
 
int cx (PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene, City *city_table)
 
void px (PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene, City *city_table)
 
void ox1 (PlannerInfo *root, Gene *mom, Gene *dad, Gene *offspring, int num_gene, City *city_table)
 
void ox2 (PlannerInfo *root, Gene *mom, Gene *dad, Gene *offspring, int num_gene, City *city_table)
 

Macro Definition Documentation

◆ DAD

#define DAD   1 /* indicator for gene from dad */

Definition at line 54 of file geqo_recombination.h.

◆ MOM

#define MOM   0 /* indicator for gene from mom */

Definition at line 55 of file geqo_recombination.h.

Typedef Documentation

◆ City

typedef struct City City

◆ Edge

typedef struct Edge Edge

Function Documentation

◆ alloc_city_table()

City * alloc_city_table ( PlannerInfo root,
int  num_gene 
)

Referenced by geqo().

◆ alloc_edge_table()

Edge * alloc_edge_table ( PlannerInfo root,
int  num_gene 
)

Definition at line 56 of file geqo_erx.c.

57{
58 Edge *edge_table;
59
60 /*
61 * palloc one extra location so that nodes numbered 1..n can be indexed
62 * directly; 0 will not be used
63 */
64
65 edge_table = (Edge *) palloc((num_gene + 1) * sizeof(Edge));
66
67 return edge_table;
68}
struct Edge Edge
void * palloc(Size size)
Definition: mcxt.c:1317

References palloc().

Referenced by geqo().

◆ cx()

int cx ( PlannerInfo root,
Gene tour1,
Gene tour2,
Gene offspring,
int  num_gene,
City city_table 
)

◆ free_city_table()

void free_city_table ( PlannerInfo root,
City city_table 
)

Referenced by geqo().

◆ free_edge_table()

void free_edge_table ( PlannerInfo root,
Edge edge_table 
)

Definition at line 76 of file geqo_erx.c.

77{
78 pfree(edge_table);
79}
void pfree(void *pointer)
Definition: mcxt.c:1521

References pfree().

Referenced by geqo().

◆ gimme_edge_table()

float gimme_edge_table ( PlannerInfo root,
Gene tour1,
Gene tour2,
int  num_gene,
Edge edge_table 
)

Definition at line 95 of file geqo_erx.c.

97{
98 int i,
99 index1,
100 index2;
101 int edge_total; /* total number of unique edges in two genes */
102
103 /* at first clear the edge table's old data */
104 for (i = 1; i <= num_gene; i++)
105 {
106 edge_table[i].total_edges = 0;
107 edge_table[i].unused_edges = 0;
108 }
109
110 /* fill edge table with new data */
111
112 edge_total = 0;
113
114 for (index1 = 0; index1 < num_gene; index1++)
115 {
116 /*
117 * presume the tour is circular, i.e. 1->2, 2->3, 3->1 this operation
118 * maps n back to 1
119 */
120
121 index2 = (index1 + 1) % num_gene;
122
123 /*
124 * edges are bidirectional, i.e. 1->2 is same as 2->1 call gimme_edge
125 * twice per edge
126 */
127
128 edge_total += gimme_edge(root, tour1[index1], tour1[index2], edge_table);
129 gimme_edge(root, tour1[index2], tour1[index1], edge_table);
130
131 edge_total += gimme_edge(root, tour2[index1], tour2[index2], edge_table);
132 gimme_edge(root, tour2[index2], tour2[index1], edge_table);
133 }
134
135 /* return average number of edges per index */
136 return ((float) (edge_total * 2) / (float) num_gene);
137}
static int gimme_edge(PlannerInfo *root, Gene gene1, Gene gene2, Edge *edge_table)
Definition: geqo_erx.c:154
int i
Definition: isn.c:72
tree ctl root
Definition: radixtree.h:1857
int unused_edges
int total_edges

References gimme_edge(), i, root, Edge::total_edges, and Edge::unused_edges.

Referenced by geqo().

◆ gimme_tour()

int gimme_tour ( PlannerInfo root,
Edge edge_table,
Gene new_gene,
int  num_gene 
)

Definition at line 196 of file geqo_erx.c.

197{
198 int i;
199 int edge_failures = 0;
200
201 /* choose int between 1 and num_gene */
202 new_gene[0] = (Gene) geqo_randint(root, num_gene, 1);
203
204 for (i = 1; i < num_gene; i++)
205 {
206 /*
207 * as each point is entered into the tour, remove it from the edge
208 * table
209 */
210
211 remove_gene(root, new_gene[i - 1], edge_table[(int) new_gene[i - 1]], edge_table);
212
213 /* find destination for the newly entered point */
214
215 if (edge_table[new_gene[i - 1]].unused_edges > 0)
216 new_gene[i] = gimme_gene(root, edge_table[(int) new_gene[i - 1]], edge_table);
217
218 else
219 { /* cope with fault */
220 edge_failures++;
221
222 new_gene[i] = edge_failure(root, new_gene, i - 1, edge_table, num_gene);
223 }
224
225 /* mark this node as incorporated */
226 edge_table[(int) new_gene[i - 1]].unused_edges = -1;
227 } /* for (i=1; i<num_gene; i++) */
228
229 return edge_failures;
230}
static Gene gimme_gene(PlannerInfo *root, Edge edge, Edge *edge_table)
Definition: geqo_erx.c:282
static Gene edge_failure(PlannerInfo *root, Gene *gene, int index, Edge *edge_table, int num_gene)
Definition: geqo_erx.c:372
static void remove_gene(PlannerInfo *root, Gene gene, Edge edge, Edge *edge_table)
Definition: geqo_erx.c:240
int Gene
Definition: geqo_gene.h:30
int geqo_randint(PlannerInfo *root, int upper, int lower)
Definition: geqo_random.c:36

References edge_failure(), geqo_randint(), gimme_gene(), i, remove_gene(), and root.

Referenced by geqo().

◆ init_tour()

void init_tour ( PlannerInfo root,
Gene tour,
int  num_gene 
)

Definition at line 34 of file geqo_recombination.c.

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 */
48 if (num_gene > 0)
49 tour[0] = (Gene) 1;
50
51 for (i = 1; i < num_gene; i++)
52 {
53 j = geqo_randint(root, i, 0);
54 /* i != j check avoids fetching uninitialized array element */
55 if (i != j)
56 tour[i] = tour[j];
57 tour[j] = (Gene) (i + 1);
58 }
59}
int j
Definition: isn.c:73

References geqo_randint(), i, j, and root.

Referenced by random_init_pool().

◆ ox1()

void ox1 ( PlannerInfo root,
Gene mom,
Gene dad,
Gene offspring,
int  num_gene,
City city_table 
)

Referenced by geqo().

◆ ox2()

void ox2 ( PlannerInfo root,
Gene mom,
Gene dad,
Gene offspring,
int  num_gene,
City city_table 
)

Referenced by geqo().

◆ pmx()

void pmx ( PlannerInfo root,
Gene tour1,
Gene tour2,
Gene offspring,
int  num_gene 
)

Referenced by geqo().

◆ px()

void px ( PlannerInfo root,
Gene tour1,
Gene tour2,
Gene offspring,
int  num_gene,
City city_table 
)