PostgreSQL Source Code git master
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
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

◆ 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().

◆ edge_failure()

static Gene edge_failure ( PlannerInfo root,
Gene gene,
int  index,
Edge edge_table,
int  num_gene 
)
static

Definition at line 372 of file geqo_erx.c.

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

References elog, ERROR, geqo_randint(), i, LOG, and root.

Referenced by gimme_tour().

◆ 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()

static int gimme_edge ( PlannerInfo root,
Gene  gene1,
Gene  gene2,
Edge edge_table 
)
static

Definition at line 154 of file geqo_erx.c.

155{
156 int i;
157 int edges;
158 int city1 = (int) gene1;
159 int city2 = (int) gene2;
160
161
162 /* check whether edge city1->city2 already exists */
163 edges = edge_table[city1].total_edges;
164
165 for (i = 0; i < edges; i++)
166 {
167 if ((Gene) abs(edge_table[city1].edge_list[i]) == city2)
168 {
169
170 /* mark shared edges as negative */
171 edge_table[city1].edge_list[i] = 0 - city2;
172
173 return 0;
174 }
175 }
176
177 /* add city1->city2; */
178 edge_table[city1].edge_list[edges] = city2;
179
180 /* increment the number of edges from city1 */
181 edge_table[city1].total_edges++;
182 edge_table[city1].unused_edges++;
183
184 return 1;
185}
int unused_edges
Gene edge_list[4]
int total_edges

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

Referenced by gimme_edge_table().

◆ 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

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

Referenced by geqo().

◆ gimme_gene()

static Gene gimme_gene ( PlannerInfo root,
Edge  edge,
Edge edge_table 
)
static

Definition at line 282 of file geqo_erx.c.

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 } /* for (i=0; i<edge.unused_edges; i++) */
341
342
343 /* random decision of the possible candidates to use */
344 rand_decision = geqo_randint(root, minimum_count - 1, 0);
345
346
347 for (i = 0; i < edge.unused_edges; i++)
348 {
349 friend = (Gene) edge.edge_list[i];
350
351 /* return the chosen candidate point */
352 if (edge_table[(int) friend].unused_edges == minimum_edges)
353 {
354 minimum_count--;
355
356 if (minimum_count == rand_decision)
357 return friend;
358 }
359 }
360
361 /* ... should never be reached */
362 elog(ERROR, "neither shared nor minimum number nor random edge found");
363 return 0; /* to keep the compiler quiet */
364}
if(TABLE==NULL||TABLE_index==NULL)
Definition: isn.c:76

References Edge::edge_list, elog, ERROR, geqo_randint(), i, if(), root, and Edge::unused_edges.

Referenced by gimme_tour().

◆ 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

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

Referenced by geqo().

◆ remove_gene()

static void remove_gene ( PlannerInfo root,
Gene  gene,
Edge  edge,
Edge edge_table 
)
static

Definition at line 240 of file geqo_erx.c.

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 = 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 j
Definition: isn.c:73

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

Referenced by gimme_tour().