LCOV - code coverage report
Current view: top level - src/backend/optimizer/geqo - geqo_erx.c (source / functions) Hit Total Coverage
Test: PostgreSQL 13devel Lines: 70 107 65.4 %
Date: 2019-11-13 21:06:57 Functions: 7 8 87.5 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*------------------------------------------------------------------------
       2             : *
       3             : * geqo_erx.c
       4             : *    edge recombination crossover [ER]
       5             : *
       6             : * src/backend/optimizer/geqo/geqo_erx.c
       7             : *
       8             : *-------------------------------------------------------------------------
       9             : */
      10             : 
      11             : /* contributed by:
      12             :    =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
      13             :    *  Martin Utesch              * Institute of Automatic Control      *
      14             :    =                             = University of Mining and Technology =
      15             :    *  utesch@aut.tu-freiberg.de  * Freiberg, Germany                   *
      16             :    =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
      17             :  */
      18             : 
      19             : /* the edge recombination algorithm is adopted from Genitor : */
      20             : /*************************************************************/
      21             : /*                                                           */
      22             : /*  Copyright (c) 1990                                       */
      23             : /*  Darrell L. Whitley                                       */
      24             : /*  Computer Science Department                              */
      25             : /*  Colorado State University                                */
      26             : /*                                                           */
      27             : /*  Permission is hereby granted to copy all or any part of  */
      28             : /*  this program for free distribution.   The author's name  */
      29             : /*  and this copyright notice must be included in any copy.  */
      30             : /*                                                           */
      31             : /*************************************************************/
      32             : 
      33             : 
      34             : #include "postgres.h"
      35             : #include "optimizer/geqo_random.h"
      36             : #include "optimizer/geqo_recombination.h"
      37             : 
      38             : #if defined(ERX)
      39             : 
      40             : static int  gimme_edge(PlannerInfo *root, Gene gene1, Gene gene2, Edge *edge_table);
      41             : static void remove_gene(PlannerInfo *root, Gene gene, Edge edge, Edge *edge_table);
      42             : static Gene gimme_gene(PlannerInfo *root, Edge edge, Edge *edge_table);
      43             : 
      44             : static Gene edge_failure(PlannerInfo *root, Gene *gene, int index, Edge *edge_table, int num_gene);
      45             : 
      46             : 
      47             : /* alloc_edge_table
      48             :  *
      49             :  *   allocate memory for edge table
      50             :  *
      51             :  */
      52             : 
      53             : Edge *
      54           4 : alloc_edge_table(PlannerInfo *root, int num_gene)
      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           4 :     edge_table = (Edge *) palloc((num_gene + 1) * sizeof(Edge));
      64             : 
      65           4 :     return edge_table;
      66             : }
      67             : 
      68             : /* free_edge_table
      69             :  *
      70             :  *    deallocate memory of edge table
      71             :  *
      72             :  */
      73             : void
      74           4 : free_edge_table(PlannerInfo *root, Edge *edge_table)
      75             : {
      76           4 :     pfree(edge_table);
      77           4 : }
      78             : 
      79             : /* gimme_edge_table
      80             :  *
      81             :  *   fills a data structure which represents the set of explicit
      82             :  *   edges between points in the (2) input genes
      83             :  *
      84             :  *   assumes circular tours and bidirectional edges
      85             :  *
      86             :  *   gimme_edge() will set "shared" edges to negative values
      87             :  *
      88             :  *   returns average number edges/city in range 2.0 - 4.0
      89             :  *   where 2.0=homogeneous; 4.0=diverse
      90             :  *
      91             :  */
      92             : float
      93         256 : gimme_edge_table(PlannerInfo *root, Gene *tour1, Gene *tour2,
      94             :                  int num_gene, Edge *edge_table)
      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        1536 :     for (i = 1; i <= num_gene; i++)
     103             :     {
     104        1280 :         edge_table[i].total_edges = 0;
     105        1280 :         edge_table[i].unused_edges = 0;
     106             :     }
     107             : 
     108             :     /* fill edge table with new data */
     109             : 
     110         256 :     edge_total = 0;
     111             : 
     112        1536 :     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        1280 :         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        1280 :         edge_total += gimme_edge(root, tour1[index1], tour1[index2], edge_table);
     127        1280 :         gimme_edge(root, tour1[index2], tour1[index1], edge_table);
     128             : 
     129        1280 :         edge_total += gimme_edge(root, tour2[index1], tour2[index2], edge_table);
     130        1280 :         gimme_edge(root, tour2[index2], tour2[index1], edge_table);
     131             :     }
     132             : 
     133             :     /* return average number of edges per index */
     134         256 :     return ((float) (edge_total * 2) / (float) num_gene);
     135             : }
     136             : 
     137             : /* gimme_edge
     138             :  *
     139             :  *    registers edge from city1 to city2 in input edge table
     140             :  *
     141             :  *    no assumptions about directionality are made;
     142             :  *    therefore it is up to the calling routine to
     143             :  *    call gimme_edge twice to make a bi-directional edge
     144             :  *    between city1 and city2;
     145             :  *    uni-directional edges are possible as well (just call gimme_edge
     146             :  *    once with the direction from city1 to city2)
     147             :  *
     148             :  *    returns 1 if edge was not already registered and was just added;
     149             :  *            0 if edge was already registered and edge_table is unchanged
     150             :  */
     151             : static int
     152        5120 : gimme_edge(PlannerInfo *root, Gene gene1, Gene gene2, Edge *edge_table)
     153             : {
     154             :     int         i;
     155             :     int         edges;
     156        5120 :     int         city1 = (int) gene1;
     157        5120 :     int         city2 = (int) gene2;
     158             : 
     159             : 
     160             :     /* check whether edge city1->city2 already exists */
     161        5120 :     edges = edge_table[city1].total_edges;
     162             : 
     163        9604 :     for (i = 0; i < edges; i++)
     164             :     {
     165        5932 :         if ((Gene) Abs(edge_table[city1].edge_list[i]) == city2)
     166             :         {
     167             : 
     168             :             /* mark shared edges as negative */
     169        1448 :             edge_table[city1].edge_list[i] = 0 - city2;
     170             : 
     171        1448 :             return 0;
     172             :         }
     173             :     }
     174             : 
     175             :     /* add city1->city2; */
     176        3672 :     edge_table[city1].edge_list[edges] = city2;
     177             : 
     178             :     /* increment the number of edges from city1 */
     179        3672 :     edge_table[city1].total_edges++;
     180        3672 :     edge_table[city1].unused_edges++;
     181             : 
     182        3672 :     return 1;
     183             : }
     184             : 
     185             : /* gimme_tour
     186             :  *
     187             :  *    creates a new tour using edges from the edge table.
     188             :  *    priority is given to "shared" edges (i.e. edges which
     189             :  *    all parent genes possess and are marked as negative
     190             :  *    in the edge table.)
     191             :  *
     192             :  */
     193             : int
     194         256 : gimme_tour(PlannerInfo *root, Edge *edge_table, Gene *new_gene, int num_gene)
     195             : {
     196             :     int         i;
     197         256 :     int         edge_failures = 0;
     198             : 
     199             :     /* choose int between 1 and num_gene */
     200         256 :     new_gene[0] = (Gene) geqo_randint(root, num_gene, 1);
     201             : 
     202        1280 :     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        1024 :         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        1024 :         if (edge_table[new_gene[i - 1]].unused_edges > 0)
     214        1024 :             new_gene[i] = gimme_gene(root, edge_table[(int) new_gene[i - 1]], edge_table);
     215             : 
     216             :         else
     217             :         {                       /* cope with fault */
     218           0 :             edge_failures++;
     219             : 
     220           0 :             new_gene[i] = edge_failure(root, new_gene, i - 1, edge_table, num_gene);
     221             :         }
     222             : 
     223             :         /* mark this node as incorporated */
     224        1024 :         edge_table[(int) new_gene[i - 1]].unused_edges = -1;
     225             : 
     226             :     }                           /* for (i=1; i<num_gene; i++) */
     227             : 
     228         256 :     return edge_failures;
     229             : 
     230             : }
     231             : 
     232             : /* remove_gene
     233             :  *
     234             :  *   removes input gene from edge_table.
     235             :  *   input edge is used
     236             :  *   to identify deletion locations within edge table.
     237             :  *
     238             :  */
     239             : static void
     240        1024 : remove_gene(PlannerInfo *root, Gene gene, Edge edge, Edge *edge_table)
     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        2860 :     for (i = 0; i < edge.unused_edges; i++)
     253             :     {
     254        1836 :         possess_edge = (int) Abs(edge.edge_list[i]);
     255        1836 :         genes_remaining = edge_table[possess_edge].unused_edges;
     256             : 
     257             :         /* find the input gene in all edge_lists and delete it */
     258        3152 :         for (j = 0; j < genes_remaining; j++)
     259             :         {
     260             : 
     261        3152 :             if ((Gene) Abs(edge_table[possess_edge].edge_list[j]) == gene)
     262             :             {
     263             : 
     264        1836 :                 edge_table[possess_edge].unused_edges--;
     265             : 
     266        3672 :                 edge_table[possess_edge].edge_list[j] =
     267        1836 :                     edge_table[possess_edge].edge_list[genes_remaining - 1];
     268             : 
     269        1836 :                 break;
     270             :             }
     271             :         }
     272             :     }
     273        1024 : }
     274             : 
     275             : /* gimme_gene
     276             :  *
     277             :  *    priority is given to "shared" edges
     278             :  *    (i.e. edges which both genes possess)
     279             :  *
     280             :  */
     281             : static Gene
     282        1024 : gimme_gene(PlannerInfo *root, Edge edge, Edge *edge_table)
     283             : {
     284             :     int         i;
     285             :     Gene        friend;
     286             :     int         minimum_edges;
     287        1024 :     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        1024 :     minimum_edges = 5;
     296             : 
     297             :     /* consider candidate destination points in edge list */
     298             : 
     299        1904 :     for (i = 0; i < edge.unused_edges; i++)
     300             :     {
     301        1536 :         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        1536 :         if (friend < 0)
     312         656 :             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         880 :         if (edge_table[(int) friend].unused_edges < minimum_edges)
     332             :         {
     333         532 :             minimum_edges = edge_table[(int) friend].unused_edges;
     334         532 :             minimum_count = 1;
     335             :         }
     336         348 :         else if (minimum_count == -1)
     337           0 :             elog(ERROR, "minimum_count not set");
     338         348 :         else if (edge_table[(int) friend].unused_edges == minimum_edges)
     339         336 :             minimum_count++;
     340             : 
     341             :     }                           /* for (i=0; i<edge.unused_edges; i++) */
     342             : 
     343             : 
     344             :     /* random decision of the possible candidates to use */
     345         368 :     rand_decision = geqo_randint(root, minimum_count - 1, 0);
     346             : 
     347             : 
     348         512 :     for (i = 0; i < edge.unused_edges; i++)
     349             :     {
     350         512 :         friend = (Gene) edge.edge_list[i];
     351             : 
     352             :         /* return the chosen candidate point */
     353         512 :         if (edge_table[(int) friend].unused_edges == minimum_edges)
     354             :         {
     355         512 :             minimum_count--;
     356             : 
     357         512 :             if (minimum_count == rand_decision)
     358         368 :                 return friend;
     359             :         }
     360             :     }
     361             : 
     362             :     /* ... should never be reached */
     363           0 :     elog(ERROR, "neither shared nor minimum number nor random edge found");
     364             :     return 0;                   /* to keep the compiler quiet */
     365             : }
     366             : 
     367             : /* edge_failure
     368             :  *
     369             :  *    routine for handling edge failure
     370             :  *
     371             :  */
     372             : static Gene
     373           0 : edge_failure(PlannerInfo *root, Gene *gene, int index, Edge *edge_table, int num_gene)
     374             : {
     375             :     int         i;
     376           0 :     Gene        fail_gene = gene[index];
     377           0 :     int         remaining_edges = 0;
     378           0 :     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           0 :     for (i = 1; i <= num_gene; i++)
     388             :     {
     389           0 :         if ((edge_table[i].unused_edges != -1) && (i != (int) fail_gene))
     390             :         {
     391           0 :             remaining_edges++;
     392             : 
     393           0 :             if (edge_table[i].total_edges == 4)
     394           0 :                 four_count++;
     395             :         }
     396             :     }
     397             : 
     398             :     /*
     399             :      * random decision of the gene with remaining edges and whose total_edges
     400             :      * == 4
     401             :      */
     402             : 
     403           0 :     if (four_count != 0)
     404             :     {
     405             : 
     406           0 :         rand_decision = geqo_randint(root, four_count - 1, 0);
     407             : 
     408           0 :         for (i = 1; i <= num_gene; i++)
     409             :         {
     410             : 
     411           0 :             if ((Gene) i != fail_gene &&
     412           0 :                 edge_table[i].unused_edges != -1 &&
     413           0 :                 edge_table[i].total_edges == 4)
     414             :             {
     415             : 
     416           0 :                 four_count--;
     417             : 
     418           0 :                 if (rand_decision == four_count)
     419           0 :                     return (Gene) i;
     420             :             }
     421             :         }
     422             : 
     423           0 :         elog(LOG, "no edge found via random decision and total_edges == 4");
     424             :     }
     425           0 :     else if (remaining_edges != 0)
     426             :     {
     427             :         /* random decision of the gene with remaining edges */
     428           0 :         rand_decision = geqo_randint(root, remaining_edges - 1, 0);
     429             : 
     430           0 :         for (i = 1; i <= num_gene; i++)
     431             :         {
     432             : 
     433           0 :             if ((Gene) i != fail_gene &&
     434           0 :                 edge_table[i].unused_edges != -1)
     435             :             {
     436             : 
     437           0 :                 remaining_edges--;
     438             : 
     439           0 :                 if (rand_decision == remaining_edges)
     440           0 :                     return i;
     441             :             }
     442             :         }
     443             : 
     444           0 :         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           0 :         for (i = 1; i <= num_gene; i++)
     459           0 :             if (edge_table[i].unused_edges >= 0)
     460           0 :                 return (Gene) i;
     461             : 
     462           0 :         elog(LOG, "no edge found via looking for the last unused point");
     463             :     }
     464             : 
     465             : 
     466             :     /* ... should never be reached */
     467           0 :     elog(ERROR, "no edge found");
     468             :     return 0;                   /* to keep the compiler quiet */
     469             : }
     470             : 
     471             : #endif                          /* defined(ERX) */

Generated by: LCOV version 1.13