geqo_erx.c File Reference

#include "postgres.h"
#include "optimizer/geqo_random.h"
#include "optimizer/geqo_recombination.h"

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

Function Documentation

alloc_edge_table()

Edge* alloc_edge_table	(	PlannerInfo *	root,
		int	num_gene
	)

Definition at line 54 of file geqo_erx.c.

{
    Edge       *edge_table;
 
    /*
     * palloc one extra location so that nodes numbered 1..n can be indexed
     * directly; 0 will not be used
     */
 
    edge_table = (Edge *) palloc((num_gene + 1) * sizeof(Edge));
 
    return edge_table;
}

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 370 of file geqo_erx.c.

{
    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 unused point");
    }
 
 
    /* ... should never be reached */
    elog(ERROR, "no edge found");
    return 0;                   /* to keep the compiler quiet */
}

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

Referenced by gimme_tour().

free_edge_table()

void free_edge_table	(	PlannerInfo *	root,
		Edge *	edge_table
	)

Definition at line 74 of file geqo_erx.c.

{
    pfree(edge_table);
}

References pfree().

Referenced by geqo().

gimme_edge()

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

static

Definition at line 152 of file geqo_erx.c.

{
    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;
}

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 93 of file geqo_erx.c.

{
    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 operation
         * 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);
}

References gimme_edge(), i, 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 280 of file geqo_erx.c.

{
    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 candidate 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 */
}

References Edge::edge_list, elog(), ERROR, geqo_randint(), i, if(), 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 194 of file geqo_erx.c.

{
    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;
}

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

Referenced by geqo().

remove_gene()

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

static

Definition at line 238 of file geqo_erx.c.

{
    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 = 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;
            }
        }
    }
}

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

Referenced by gimme_tour().