Adding upstream version 14.5.upstream/14.5upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 471 insertions, 0 deletions

diff --git a/src/backend/optimizer/geqo/geqo_erx.c b/src/backend/optimizer/geqo/geqo_erx.c
new file mode 100644
index 0000000..3b92f42
--- /dev/null
+++ b/src/backend/optimizer/geqo/geqo_erx.c
@@ -0,0 +1,471 @@
+/*------------------------------------------------------------------------
+*
+* 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_random.h"
+#include "optimizer/geqo_recombination.h"
+
+#if defined(ERX)
+
+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 = (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;
+			}
+		}
+	}
+}
+
+/* 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) */