PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
geqo_erx.c File Reference
Include dependency graph for geqo_erx.c:

Go to the source code of this file.

Functions

static int gimme_edge (PlannerInfo *root, Gene gene1, Gene gene2, Edge *edge_table)
 
static void remove_gene (PlannerInfo *root, Gene gene, Edge edge, Edge *edge_table)
 
static Gene gimme_gene (PlannerInfo *root, Edge edge, Edge *edge_table)
 
static Gene edge_failure (PlannerInfo *root, Gene *gene, int index, Edge *edge_table, 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)
 

Function Documentation

Edge* alloc_edge_table ( PlannerInfo root,
int  num_gene 
)

Definition at line 54 of file geqo_erx.c.

References palloc().

Referenced by geqo().

55 {
56  Edge *edge_table;
57 
58  /*
59  * palloc one extra location so that nodes numbered 1..n can be indexed
60  * directly; 0 will not be used
61  */
62 
63  edge_table = (Edge *) palloc((num_gene + 1) * sizeof(Edge));
64 
65  return edge_table;
66 }
struct Edge Edge
void * palloc(Size size)
Definition: mcxt.c:849
static Gene edge_failure ( PlannerInfo root,
Gene gene,
int  index,
Edge edge_table,
int  num_gene 
)
static

Definition at line 373 of file geqo_erx.c.

References elog, ERROR, geqo_randint, i, and LOG.

Referenced by gimme_tour().

374 {
375  int i;
376  Gene fail_gene = gene[index];
377  int remaining_edges = 0;
378  int four_count = 0;
379  int rand_decision;
380 
381 
382  /*
383  * how many edges remain? how many gene with four total (initial) edges
384  * remain?
385  */
386 
387  for (i = 1; i <= num_gene; i++)
388  {
389  if ((edge_table[i].unused_edges != -1) && (i != (int) fail_gene))
390  {
391  remaining_edges++;
392 
393  if (edge_table[i].total_edges == 4)
394  four_count++;
395  }
396  }
397 
398  /*
399  * random decision of the gene with remaining edges and whose total_edges
400  * == 4
401  */
402 
403  if (four_count != 0)
404  {
405 
406  rand_decision = geqo_randint(root, four_count - 1, 0);
407 
408  for (i = 1; i <= num_gene; i++)
409  {
410 
411  if ((Gene) i != fail_gene &&
412  edge_table[i].unused_edges != -1 &&
413  edge_table[i].total_edges == 4)
414  {
415 
416  four_count--;
417 
418  if (rand_decision == four_count)
419  return (Gene) i;
420  }
421  }
422 
423  elog(LOG, "no edge found via random decision and total_edges == 4");
424  }
425  else if (remaining_edges != 0)
426  {
427  /* random decision of the gene with remaining edges */
428  rand_decision = geqo_randint(root, remaining_edges - 1, 0);
429 
430  for (i = 1; i <= num_gene; i++)
431  {
432 
433  if ((Gene) i != fail_gene &&
434  edge_table[i].unused_edges != -1)
435  {
436 
437  remaining_edges--;
438 
439  if (rand_decision == remaining_edges)
440  return i;
441  }
442  }
443 
444  elog(LOG, "no edge found via random decision with remaining edges");
445  }
446 
447  /*
448  * edge table seems to be empty; this happens sometimes on the last point
449  * due to the fact that the first point is removed from the table even
450  * though only one of its edges has been determined
451  */
452 
453  else
454  { /* occurs only at the last point in the tour;
455  * simply look for the point which is not yet
456  * used */
457 
458  for (i = 1; i <= num_gene; i++)
459  if (edge_table[i].unused_edges >= 0)
460  return (Gene) i;
461 
462  elog(LOG, "no edge found via looking for the last unused point");
463  }
464 
465 
466  /* ... should never be reached */
467  elog(ERROR, "no edge found");
468  return 0; /* to keep the compiler quiet */
469 }
#define geqo_randint(root, upper, lower)
Definition: geqo_random.h:38
int Gene
Definition: geqo_gene.h:30
#define LOG
Definition: elog.h:26
Definition: type.h:89
#define ERROR
Definition: elog.h:43
int i
#define elog
Definition: elog.h:219
void free_edge_table ( PlannerInfo root,
Edge edge_table 
)

Definition at line 74 of file geqo_erx.c.

References pfree().

Referenced by geqo().

75 {
76  pfree(edge_table);
77 }
void pfree(void *pointer)
Definition: mcxt.c:950
static int gimme_edge ( PlannerInfo root,
Gene  gene1,
Gene  gene2,
Edge edge_table 
)
static

Definition at line 152 of file geqo_erx.c.

References Abs, Edge::edge_list, i, Edge::total_edges, and Edge::unused_edges.

Referenced by gimme_edge_table().

153 {
154  int i;
155  int edges;
156  int city1 = (int) gene1;
157  int city2 = (int) gene2;
158 
159 
160  /* check whether edge city1->city2 already exists */
161  edges = edge_table[city1].total_edges;
162 
163  for (i = 0; i < edges; i++)
164  {
165  if ((Gene) Abs(edge_table[city1].edge_list[i]) == city2)
166  {
167 
168  /* mark shared edges as negative */
169  edge_table[city1].edge_list[i] = 0 - city2;
170 
171  return 0;
172  }
173  }
174 
175  /* add city1->city2; */
176  edge_table[city1].edge_list[edges] = city2;
177 
178  /* increment the number of edges from city1 */
179  edge_table[city1].total_edges++;
180  edge_table[city1].unused_edges++;
181 
182  return 1;
183 }
int Gene
Definition: geqo_gene.h:30
int total_edges
#define Abs(x)
Definition: c.h:812
Gene edge_list[4]
int i
int unused_edges
float gimme_edge_table ( PlannerInfo root,
Gene tour1,
Gene tour2,
int  num_gene,
Edge edge_table 
)

Definition at line 93 of file geqo_erx.c.

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

Referenced by geqo().

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

Definition at line 282 of file geqo_erx.c.

References Abs, Edge::edge_list, elog, ERROR, geqo_randint, i, and Edge::unused_edges.

Referenced by gimme_tour().

283 {
284  int i;
285  Gene friend;
286  int minimum_edges;
287  int minimum_count = -1;
288  int rand_decision;
289 
290  /*
291  * no point has edges to more than 4 other points thus, this contrived
292  * minimum will be replaced
293  */
294 
295  minimum_edges = 5;
296 
297  /* consider candidate destination points in edge list */
298 
299  for (i = 0; i < edge.unused_edges; i++)
300  {
301  friend = (Gene) edge.edge_list[i];
302 
303  /*
304  * give priority to shared edges that are negative; so return 'em
305  */
306 
307  /*
308  * negative values are caught here so we need not worry about
309  * converting to absolute values
310  */
311  if (friend < 0)
312  return (Gene) Abs(friend);
313 
314 
315  /*
316  * give priority to candidates with fewest remaining unused edges;
317  * find out what the minimum number of unused edges is
318  * (minimum_edges); if there is more than one candidate with the
319  * minimum number of unused edges keep count of this number
320  * (minimum_count);
321  */
322 
323  /*
324  * The test for minimum_count can probably be removed at some point
325  * but comments should probably indicate exactly why it is guaranteed
326  * that the test will always succeed the first time around. If it can
327  * fail then the code is in error
328  */
329 
330 
331  if (edge_table[(int) friend].unused_edges < minimum_edges)
332  {
333  minimum_edges = edge_table[(int) friend].unused_edges;
334  minimum_count = 1;
335  }
336  else if (minimum_count == -1)
337  elog(ERROR, "minimum_count not set");
338  else if (edge_table[(int) friend].unused_edges == minimum_edges)
339  minimum_count++;
340 
341  } /* for (i=0; i<edge.unused_edges; i++) */
342 
343 
344  /* random decision of the possible candidates to use */
345  rand_decision = geqo_randint(root, minimum_count - 1, 0);
346 
347 
348  for (i = 0; i < edge.unused_edges; i++)
349  {
350  friend = (Gene) edge.edge_list[i];
351 
352  /* return the chosen candidate point */
353  if (edge_table[(int) friend].unused_edges == minimum_edges)
354  {
355  minimum_count--;
356 
357  if (minimum_count == rand_decision)
358  return friend;
359  }
360  }
361 
362  /* ... should never be reached */
363  elog(ERROR, "neither shared nor minimum number nor random edge found");
364  return 0; /* to keep the compiler quiet */
365 }
#define geqo_randint(root, upper, lower)
Definition: geqo_random.h:38
int Gene
Definition: geqo_gene.h:30
#define Abs(x)
Definition: c.h:812
#define ERROR
Definition: elog.h:43
Gene edge_list[4]
int i
#define elog
Definition: elog.h:219
int unused_edges
int gimme_tour ( PlannerInfo root,
Edge edge_table,
Gene new_gene,
int  num_gene 
)

Definition at line 194 of file geqo_erx.c.

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

Referenced by geqo().

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

Definition at line 240 of file geqo_erx.c.

References Abs, Edge::edge_list, i, and Edge::unused_edges.

Referenced by gimme_tour().

241 {
242  int i,
243  j;
244  int possess_edge;
245  int genes_remaining;
246 
247  /*
248  * do for every gene known to have an edge to input gene (i.e. in
249  * edge_list for input edge)
250  */
251 
252  for (i = 0; i < edge.unused_edges; i++)
253  {
254  possess_edge = (int) Abs(edge.edge_list[i]);
255  genes_remaining = edge_table[possess_edge].unused_edges;
256 
257  /* find the input gene in all edge_lists and delete it */
258  for (j = 0; j < genes_remaining; j++)
259  {
260 
261  if ((Gene) Abs(edge_table[possess_edge].edge_list[j]) == gene)
262  {
263 
264  edge_table[possess_edge].unused_edges--;
265 
266  edge_table[possess_edge].edge_list[j] =
267  edge_table[possess_edge].edge_list[genes_remaining - 1];
268 
269  break;
270  }
271  }
272  }
273 }
int Gene
Definition: geqo_gene.h:30
#define Abs(x)
Definition: c.h:812
Gene edge_list[4]
int i
int unused_edges