Header And Logo
|
#include "postgres.h"#include "optimizer/geqo_recombination.h"#include "optimizer/geqo_random.h"
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) |
| Edge * | alloc_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) |
| Edge* alloc_edge_table | ( | PlannerInfo * | root, | |
| int | num_gene | |||
| ) |
| 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.
References elog, ERROR, geqo_randint, i, and LOG.
Referenced by gimme_tour().
{
int i;
Gene fail_gene = gene[index];
int remaining_edges = 0;
int four_count = 0;
int rand_decision;
/*
* how many edges remain? how many gene with four total (initial) edges
* remain?
*/
for (i = 1; i <= num_gene; i++)
{
if ((edge_table[i].unused_edges != -1) && (i != (int) fail_gene))
{
remaining_edges++;
if (edge_table[i].total_edges == 4)
four_count++;
}
}
/*
* random decision of the gene with remaining edges and whose total_edges
* == 4
*/
if (four_count != 0)
{
rand_decision = geqo_randint(root, four_count - 1, 0);
for (i = 1; i <= num_gene; i++)
{
if ((Gene) i != fail_gene &&
edge_table[i].unused_edges != -1 &&
edge_table[i].total_edges == 4)
{
four_count--;
if (rand_decision == four_count)
return (Gene) i;
}
}
elog(LOG, "no edge found via random decision and total_edges == 4");
}
else if (remaining_edges != 0)
{
/* random decision of the gene with remaining edges */
rand_decision = geqo_randint(root, remaining_edges - 1, 0);
for (i = 1; i <= num_gene; i++)
{
if ((Gene) i != fail_gene &&
edge_table[i].unused_edges != -1)
{
remaining_edges--;
if (rand_decision == remaining_edges)
return i;
}
}
elog(LOG, "no edge found via random decision with remaining edges");
}
/*
* edge table seems to be empty; this happens sometimes on the last point
* due to the fact that the first point is removed from the table even
* though only one of its edges has been determined
*/
else
{ /* occurs only at the last point in the tour;
* simply look for the point which is not yet
* used */
for (i = 1; i <= num_gene; i++)
if (edge_table[i].unused_edges >= 0)
return (Gene) i;
elog(LOG, "no edge found via looking for the last ununsed point");
}
/* ... should never be reached */
elog(ERROR, "no edge found");
return 0; /* to keep the compiler quiet */
}
| void free_edge_table | ( | PlannerInfo * | root, | |
| Edge * | edge_table | |||
| ) |
Definition at line 73 of file geqo_erx.c.
References pfree().
Referenced by geqo().
{
pfree(edge_table);
}
| static int gimme_edge | ( | PlannerInfo * | root, | |
| Gene | gene1, | |||
| Gene | gene2, | |||
| Edge * | edge_table | |||
| ) | [static] |
Definition at line 151 of file geqo_erx.c.
References Abs, Edge::edge_list, i, Edge::total_edges, and Edge::unused_edges.
Referenced by gimme_edge_table().
{
int i;
int edges;
int city1 = (int) gene1;
int city2 = (int) gene2;
/* check whether edge city1->city2 already exists */
edges = edge_table[city1].total_edges;
for (i = 0; i < edges; i++)
{
if ((Gene) Abs(edge_table[city1].edge_list[i]) == city2)
{
/* mark shared edges as negative */
edge_table[city1].edge_list[i] = 0 - city2;
return 0;
}
}
/* add city1->city2; */
edge_table[city1].edge_list[edges] = city2;
/* increment the number of edges from city1 */
edge_table[city1].total_edges++;
edge_table[city1].unused_edges++;
return 1;
}
| float gimme_edge_table | ( | PlannerInfo * | root, | |
| Gene * | tour1, | |||
| Gene * | tour2, | |||
| int | num_gene, | |||
| Edge * | edge_table | |||
| ) |
Definition at line 92 of file geqo_erx.c.
References gimme_edge(), i, Edge::total_edges, and Edge::unused_edges.
Referenced by geqo().
{
int i,
index1,
index2;
int edge_total; /* total number of unique edges in two genes */
/* at first clear the edge table's old data */
for (i = 1; i <= num_gene; i++)
{
edge_table[i].total_edges = 0;
edge_table[i].unused_edges = 0;
}
/* fill edge table with new data */
edge_total = 0;
for (index1 = 0; index1 < num_gene; index1++)
{
/*
* presume the tour is circular, i.e. 1->2, 2->3, 3->1 this operaton
* maps n back to 1
*/
index2 = (index1 + 1) % num_gene;
/*
* edges are bidirectional, i.e. 1->2 is same as 2->1 call gimme_edge
* twice per edge
*/
edge_total += gimme_edge(root, tour1[index1], tour1[index2], edge_table);
gimme_edge(root, tour1[index2], tour1[index1], edge_table);
edge_total += gimme_edge(root, tour2[index1], tour2[index2], edge_table);
gimme_edge(root, tour2[index2], tour2[index1], edge_table);
}
/* return average number of edges per index */
return ((float) (edge_total * 2) / (float) num_gene);
}
| static Gene gimme_gene | ( | PlannerInfo * | root, | |
| Edge | edge, | |||
| Edge * | edge_table | |||
| ) | [static] |
Definition at line 281 of file geqo_erx.c.
References Abs, Edge::edge_list, elog, ERROR, geqo_randint, i, and Edge::unused_edges.
Referenced by gimme_tour().
{
int i;
Gene friend;
int minimum_edges;
int minimum_count = -1;
int rand_decision;
/*
* no point has edges to more than 4 other points thus, this contrived
* minimum will be replaced
*/
minimum_edges = 5;
/* consider candidate destination points in edge list */
for (i = 0; i < edge.unused_edges; i++)
{
friend = (Gene) edge.edge_list[i];
/*
* give priority to shared edges that are negative; so return 'em
*/
/*
* negative values are caught here so we need not worry about
* converting to absolute values
*/
if (friend < 0)
return (Gene) Abs(friend);
/*
* give priority to candidates with fewest remaining unused edges;
* find out what the minimum number of unused edges is
* (minimum_edges); if there is more than one cadidate with the
* minimum number of unused edges keep count of this number
* (minimum_count);
*/
/*
* The test for minimum_count can probably be removed at some point
* but comments should probably indicate exactly why it is guaranteed
* that the test will always succeed the first time around. If it can
* fail then the code is in error
*/
if (edge_table[(int) friend].unused_edges < minimum_edges)
{
minimum_edges = edge_table[(int) friend].unused_edges;
minimum_count = 1;
}
else if (minimum_count == -1)
elog(ERROR, "minimum_count not set");
else if (edge_table[(int) friend].unused_edges == minimum_edges)
minimum_count++;
} /* for (i=0; i<edge.unused_edges; i++) */
/* random decision of the possible candidates to use */
rand_decision = geqo_randint(root, minimum_count - 1, 0);
for (i = 0; i < edge.unused_edges; i++)
{
friend = (Gene) edge.edge_list[i];
/* return the chosen candidate point */
if (edge_table[(int) friend].unused_edges == minimum_edges)
{
minimum_count--;
if (minimum_count == rand_decision)
return friend;
}
}
/* ... should never be reached */
elog(ERROR, "neither shared nor minimum number nor random edge found");
return 0; /* to keep the compiler quiet */
}
| int gimme_tour | ( | PlannerInfo * | root, | |
| Edge * | edge_table, | |||
| Gene * | new_gene, | |||
| int | num_gene | |||
| ) |
Definition at line 193 of file geqo_erx.c.
References edge_failure(), geqo_randint, gimme_gene(), i, and remove_gene().
Referenced by geqo().
{
int i;
int edge_failures = 0;
/* choose int between 1 and num_gene */
new_gene[0] = (Gene) geqo_randint(root, num_gene, 1);
for (i = 1; i < num_gene; i++)
{
/*
* as each point is entered into the tour, remove it from the edge
* table
*/
remove_gene(root, new_gene[i - 1], edge_table[(int) new_gene[i - 1]], edge_table);
/* find destination for the newly entered point */
if (edge_table[new_gene[i - 1]].unused_edges > 0)
new_gene[i] = gimme_gene(root, edge_table[(int) new_gene[i - 1]], edge_table);
else
{ /* cope with fault */
edge_failures++;
new_gene[i] = edge_failure(root, new_gene, i - 1, edge_table, num_gene);
}
/* mark this node as incorporated */
edge_table[(int) new_gene[i - 1]].unused_edges = -1;
} /* for (i=1; i<num_gene; i++) */
return edge_failures;
}
| static void remove_gene | ( | PlannerInfo * | root, | |
| Gene | gene, | |||
| Edge | edge, | |||
| Edge * | edge_table | |||
| ) | [static] |
Definition at line 239 of file geqo_erx.c.
References Abs, Edge::edge_list, i, and Edge::unused_edges.
Referenced by gimme_tour().
{
int i,
j;
int possess_edge;
int genes_remaining;
/*
* do for every gene known to have an edge to input gene (i.e. in
* edge_list for input edge)
*/
for (i = 0; i < edge.unused_edges; i++)
{
possess_edge = (int) Abs(edge.edge_list[i]);
genes_remaining = edge_table[possess_edge].unused_edges;
/* find the input gene in all edge_lists and delete it */
for (j = 0; j < genes_remaining; j++)
{
if ((Gene) Abs(edge_table[possess_edge].edge_list[j]) == gene)
{
edge_table[possess_edge].unused_edges--;
edge_table[possess_edge].edge_list[j] =
edge_table[possess_edge].edge_list[genes_remaining - 1];
break;
}
}
}
}
1.7.1