/src/postgres/src/backend/optimizer/geqo/geqo_erx.c

Source (jump to first uncovered line)
/*------------------------------------------------------------------------
*
* geqo_erx.c
*  edge recombination crossover [ER]
*
* src/backend/optimizer/geqo/geqo_erx.c
*
*-------------------------------------------------------------------------
*/

/* contributed by:
   =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
   *  Martin Utesch        * Institute of Automatic Control    *
   =               = University of Mining and Technology =
   *  utesch@aut.tu-freiberg.de  * Freiberg, Germany           *
   =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
 */

/* the edge recombination algorithm is adopted from Genitor : */
/*************************************************************/
/*                               */
/*  Copyright (c) 1990                     */
/*  Darrell L. Whitley                     */
/*  Computer Science Department                */
/*  Colorado State University                */
/*                               */
/*  Permission is hereby granted to copy all or any part of  */
/*  this program for free distribution.   The author's name  */
/*  and this copyright notice must be included in any copy.  */
/*                               */
/*************************************************************/


#include "postgres.h"
#include "optimizer/geqo.h"

#if defined(ERX)

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

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


/* alloc_edge_table
 *
 *   allocate memory for edge table
 *
 */

Edge *
alloc_edge_table(PlannerInfo *root, int num_gene)
{
  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;
}

/* free_edge_table
 *
 *    deallocate memory of edge table
 *
 */
void
free_edge_table(PlannerInfo *root, Edge *edge_table)
{
  pfree(edge_table);
}

/* gimme_edge_table
 *
 *   fills a data structure which represents the set of explicit
 *   edges between points in the (2) input genes
 *
 *   assumes circular tours and bidirectional edges
 *
 *   gimme_edge() will set "shared" edges to negative values
 *
 *   returns average number edges/city in range 2.0 - 4.0
 *   where 2.0=homogeneous; 4.0=diverse
 *
 */
float
gimme_edge_table(PlannerInfo *root, Gene *tour1, Gene *tour2,
         int num_gene, Edge *edge_table)
{
  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);
}

/* gimme_edge
 *
 *    registers edge from city1 to city2 in input edge table
 *
 *    no assumptions about directionality are made;
 *    therefore it is up to the calling routine to
 *    call gimme_edge twice to make a bi-directional edge
 *    between city1 and city2;
 *    uni-directional edges are possible as well (just call gimme_edge
 *    once with the direction from city1 to city2)
 *
 *    returns 1 if edge was not already registered and was just added;
 *        0 if edge was already registered and edge_table is unchanged
 */
static int
gimme_edge(PlannerInfo *root, Gene gene1, Gene gene2, Edge *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;
}

/* gimme_tour
 *
 *    creates a new tour using edges from the edge table.
 *    priority is given to "shared" edges (i.e. edges which
 *    all parent genes possess and are marked as negative
 *    in the edge table.)
 *
 */
int
gimme_tour(PlannerInfo *root, Edge *edge_table, Gene *new_gene, int num_gene)
{
  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;
}

/* remove_gene
 *
 *   removes input gene from edge_table.
 *   input edge is used
 *   to identify deletion locations within edge table.
 *
 */
static void
remove_gene(PlannerInfo *root, Gene gene, Edge edge, Edge *edge_table)
{
  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;
      }
    }
  }
}

/* gimme_gene
 *
 *    priority is given to "shared" edges
 *    (i.e. edges which both genes possess)
 *
 */
static Gene
gimme_gene(PlannerInfo *root, Edge edge, Edge *edge_table)
{
  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 */
}

/* edge_failure
 *
 *    routine for handling edge failure
 *
 */
static Gene
edge_failure(PlannerInfo *root, Gene *gene, int index, Edge *edge_table, int num_gene)
{
  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 */
}

#endif              /* defined(ERX) */

Coverage Report

Created: 2025-07-03 06:49

Line	Count	Source (jump to first uncovered line)
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.h"
36
37		#if defined(ERX)
38
39		#include "optimizer/geqo_random.h"
40		#include "optimizer/geqo_recombination.h"
41
42		static int gimme_edge(PlannerInfo root, Gene gene1, Gene gene2, Edge edge_table);
43		static void remove_gene(PlannerInfo root, Gene gene, Edge edge, Edge edge_table);
44		static Gene gimme_gene(PlannerInfo root, Edge edge, Edge edge_table);
45
46		static Gene edge_failure(PlannerInfo root, Gene gene, int index, Edge *edge_table, int num_gene);
47
48
49		/* alloc_edge_table
50		*
51		* allocate memory for edge table
52		*
53		*/
54
55		Edge *
56		alloc_edge_table(PlannerInfo *root, int num_gene)
57	0	{
58	0	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	0	edge_table = (Edge ) palloc((num_gene + 1) sizeof(Edge));
66
67	0	return edge_table;
68	0	}
69
70		/* free_edge_table
71		*
72		* deallocate memory of edge table
73		*
74		*/
75		void
76		free_edge_table(PlannerInfo root, Edge edge_table)
77	0	{
78	0	pfree(edge_table);
79	0	}
80
81		/* gimme_edge_table
82		*
83		* fills a data structure which represents the set of explicit
84		* edges between points in the (2) input genes
85		*
86		* assumes circular tours and bidirectional edges
87		*
88		* gimme_edge() will set "shared" edges to negative values
89		*
90		* returns average number edges/city in range 2.0 - 4.0
91		* where 2.0=homogeneous; 4.0=diverse
92		*
93		*/
94		float
95		gimme_edge_table(PlannerInfo root, Gene tour1, Gene *tour2,
96		int num_gene, Edge *edge_table)
97	0	{
98	0	int i,
99	0	index1,
100	0	index2;
101	0	int edge_total; /* total number of unique edges in two genes */
102
103		/* at first clear the edge table's old data */
104	0	for (i = 1; i <= num_gene; i++)
105	0	{
106	0	edge_table[i].total_edges = 0;
107	0	edge_table[i].unused_edges = 0;
108	0	}
109
110		/* fill edge table with new data */
111
112	0	edge_total = 0;
113
114	0	for (index1 = 0; index1 < num_gene; index1++)
115	0	{
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	0	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	0	edge_total += gimme_edge(root, tour1[index1], tour1[index2], edge_table);
129	0	gimme_edge(root, tour1[index2], tour1[index1], edge_table);
130
131	0	edge_total += gimme_edge(root, tour2[index1], tour2[index2], edge_table);
132	0	gimme_edge(root, tour2[index2], tour2[index1], edge_table);
133	0	}
134
135		/* return average number of edges per index */
136	0	return ((float) (edge_total * 2) / (float) num_gene);
137	0	}
138
139		/* gimme_edge
140		*
141		* registers edge from city1 to city2 in input edge table
142		*
143		* no assumptions about directionality are made;
144		* therefore it is up to the calling routine to
145		* call gimme_edge twice to make a bi-directional edge
146		* between city1 and city2;
147		* uni-directional edges are possible as well (just call gimme_edge
148		* once with the direction from city1 to city2)
149		*
150		* returns 1 if edge was not already registered and was just added;
151		* 0 if edge was already registered and edge_table is unchanged
152		*/
153		static int
154		gimme_edge(PlannerInfo root, Gene gene1, Gene gene2, Edge edge_table)
155	0	{
156	0	int i;
157	0	int edges;
158	0	int city1 = (int) gene1;
159	0	int city2 = (int) gene2;
160
161
162		/* check whether edge city1->city2 already exists */
163	0	edges = edge_table[city1].total_edges;
164
165	0	for (i = 0; i < edges; i++)
166	0	{
167	0	if ((Gene) abs(edge_table[city1].edge_list[i]) == city2)
168	0	{
169
170		/* mark shared edges as negative */
171	0	edge_table[city1].edge_list[i] = 0 - city2;
172
173	0	return 0;
174	0	}
175	0	}
176
177		/* add city1->city2; */
178	0	edge_table[city1].edge_list[edges] = city2;
179
180		/* increment the number of edges from city1 */
181	0	edge_table[city1].total_edges++;
182	0	edge_table[city1].unused_edges++;
183
184	0	return 1;
185	0	}
186
187		/* gimme_tour
188		*
189		* creates a new tour using edges from the edge table.
190		* priority is given to "shared" edges (i.e. edges which
191		* all parent genes possess and are marked as negative
192		* in the edge table.)
193		*
194		*/
195		int
196		gimme_tour(PlannerInfo root, Edge edge_table, Gene *new_gene, int num_gene)
197	0	{
198	0	int i;
199	0	int edge_failures = 0;
200
201		/* choose int between 1 and num_gene */
202	0	new_gene[0] = (Gene) geqo_randint(root, num_gene, 1);
203
204	0	for (i = 1; i < num_gene; i++)
205	0	{
206		/*
207		* as each point is entered into the tour, remove it from the edge
208		* table
209		*/
210
211	0	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	0	if (edge_table[new_gene[i - 1]].unused_edges > 0)
216	0	new_gene[i] = gimme_gene(root, edge_table[(int) new_gene[i - 1]], edge_table);
217
218	0	else
219	0	{ /* cope with fault */
220	0	edge_failures++;
221
222	0	new_gene[i] = edge_failure(root, new_gene, i - 1, edge_table, num_gene);
223	0	}
224
225		/* mark this node as incorporated */
226	0	edge_table[(int) new_gene[i - 1]].unused_edges = -1;
227	0	} /* for (i=1; i<num_gene; i++) */
228
229	0	return edge_failures;
230	0	}
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		remove_gene(PlannerInfo root, Gene gene, Edge edge, Edge edge_table)
241	0	{
242	0	int i,
243	0	j;
244	0	int possess_edge;
245	0	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	0	for (i = 0; i < edge.unused_edges; i++)
253	0	{
254	0	possess_edge = abs(edge.edge_list[i]);
255	0	genes_remaining = edge_table[possess_edge].unused_edges;
256
257		/* find the input gene in all edge_lists and delete it */
258	0	for (j = 0; j < genes_remaining; j++)
259	0	{
260
261	0	if ((Gene) abs(edge_table[possess_edge].edge_list[j]) == gene)
262	0	{
263
264	0	edge_table[possess_edge].unused_edges--;
265
266	0	edge_table[possess_edge].edge_list[j] =
267	0	edge_table[possess_edge].edge_list[genes_remaining - 1];
268
269	0	break;
270	0	}
271	0	}
272	0	}
273	0	}
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		gimme_gene(PlannerInfo root, Edge edge, Edge edge_table)
283	0	{
284	0	int i;
285	0	Gene friend;
286	0	int minimum_edges;
287	0	int minimum_count = -1;
288	0	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	0	minimum_edges = 5;
296
297		/* consider candidate destination points in edge list */
298
299	0	for (i = 0; i < edge.unused_edges; i++)
300	0	{
301	0	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	0	if (friend < 0)
312	0	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	0	if (edge_table[(int) friend].unused_edges < minimum_edges)
332	0	{
333	0	minimum_edges = edge_table[(int) friend].unused_edges;
334	0	minimum_count = 1;
335	0	}
336	0	else if (minimum_count == -1)
337	0	elog(ERROR, "minimum_count not set");
338	0	else if (edge_table[(int) friend].unused_edges == minimum_edges)
339	0	minimum_count++;
340	0	} /* for (i=0; i<edge.unused_edges; i++) */
341
342
343		/* random decision of the possible candidates to use */
344	0	rand_decision = geqo_randint(root, minimum_count - 1, 0);
345
346
347	0	for (i = 0; i < edge.unused_edges; i++)
348	0	{
349	0	friend = (Gene) edge.edge_list[i];
350
351		/* return the chosen candidate point */
352	0	if (edge_table[(int) friend].unused_edges == minimum_edges)
353	0	{
354	0	minimum_count--;
355
356	0	if (minimum_count == rand_decision)
357	0	return friend;
358	0	}
359	0	}
360
361		/* ... should never be reached */
362	0	elog(ERROR, "neither shared nor minimum number nor random edge found");
363	0	return 0; /* to keep the compiler quiet */
364	0	}
365
366		/* edge_failure
367		*
368		* routine for handling edge failure
369		*
370		*/
371		static Gene
372		edge_failure(PlannerInfo root, Gene gene, int index, Edge *edge_table, int num_gene)
373	0	{
374	0	int i;
375	0	Gene fail_gene = gene[index];
376	0	int remaining_edges = 0;
377	0	int four_count = 0;
378	0	int rand_decision;
379
380
381		/*
382		* how many edges remain? how many gene with four total (initial) edges
383		* remain?
384		*/
385
386	0	for (i = 1; i <= num_gene; i++)
387	0	{
388	0	if ((edge_table[i].unused_edges != -1) && (i != (int) fail_gene))
389	0	{
390	0	remaining_edges++;
391
392	0	if (edge_table[i].total_edges == 4)
393	0	four_count++;
394	0	}
395	0	}
396
397		/*
398		* random decision of the gene with remaining edges and whose total_edges
399		* == 4
400		*/
401
402	0	if (four_count != 0)
403	0	{
404
405	0	rand_decision = geqo_randint(root, four_count - 1, 0);
406
407	0	for (i = 1; i <= num_gene; i++)
408	0	{
409
410	0	if ((Gene) i != fail_gene &&
411	0	edge_table[i].unused_edges != -1 &&
412	0	edge_table[i].total_edges == 4)
413	0	{
414
415	0	four_count--;
416
417	0	if (rand_decision == four_count)
418	0	return (Gene) i;
419	0	}
420	0	}
421
422	0	elog(LOG, "no edge found via random decision and total_edges == 4");
423	0	}
424	0	else if (remaining_edges != 0)
425	0	{
426		/* random decision of the gene with remaining edges */
427	0	rand_decision = geqo_randint(root, remaining_edges - 1, 0);
428
429	0	for (i = 1; i <= num_gene; i++)
430	0	{
431
432	0	if ((Gene) i != fail_gene &&
433	0	edge_table[i].unused_edges != -1)
434	0	{
435
436	0	remaining_edges--;
437
438	0	if (rand_decision == remaining_edges)
439	0	return i;
440	0	}
441	0	}
442
443	0	elog(LOG, "no edge found via random decision with remaining edges");
444	0	}
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	0	else
453	0	{ /* occurs only at the last point in the tour;
454		* simply look for the point which is not yet
455		* used */
456
457	0	for (i = 1; i <= num_gene; i++)
458	0	if (edge_table[i].unused_edges >= 0)
459	0	return (Gene) i;
460
461	0	elog(LOG, "no edge found via looking for the last unused point");
462	0	}
463
464
465		/* ... should never be reached */
466	0	elog(ERROR, "no edge found");
467	0	return 0; /* to keep the compiler quiet */
468	0	}
469
470		#endif /* defined(ERX) */