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:73
tree ctl root
Definition: radixtree.h:1886
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:74

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 
)