1 /*-------------------------------------------------------------------------
2  *
3  * geqo_recombination.h
4  *	  prototypes for recombination in the genetic query optimizer
5  *
6  * Portions Copyright (c) 1996-2021, PostgreSQL Global Development Group
7  * Portions Copyright (c) 1994, Regents of the University of California
8  *
9  * src/include/optimizer/geqo_recombination.h
10  *
11  *-------------------------------------------------------------------------
12  */
13 
14 /* contributed by:
15    =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
16    *  Martin Utesch				 * Institute of Automatic Control	   *
17    =							 = University of Mining and Technology =
18    *  utesch@aut.tu-freiberg.de  * Freiberg, Germany				   *
19    =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
20  */
21 
22 /* -- parts of this are adapted from D. Whitley's Genitor algorithm -- */
23 
24 #ifndef GEQO_RECOMBINATION_H
25 #define GEQO_RECOMBINATION_H
26 
27 #include "optimizer/geqo.h"
28 
29 
30 extern void init_tour(PlannerInfo *root, Gene *tour, int num_gene);
31 
32 
33 /* edge recombination crossover [ERX] */
34 
35 typedef struct Edge
36 {
37 	Gene		edge_list[4];	/* list of edges */
38 	int			total_edges;
39 	int			unused_edges;
40 } Edge;
41 
42 extern Edge *alloc_edge_table(PlannerInfo *root, int num_gene);
43 extern void free_edge_table(PlannerInfo *root, Edge *edge_table);
44 
45 extern float gimme_edge_table(PlannerInfo *root, Gene *tour1, Gene *tour2,
46 							  int num_gene, Edge *edge_table);
47 
48 extern int	gimme_tour(PlannerInfo *root, Edge *edge_table, Gene *new_gene,
49 					   int num_gene);
50 
51 
52 /* partially matched crossover [PMX] */
53 
54 #define DAD 1					/* indicator for gene from dad */
55 #define MOM 0					/* indicator for gene from mom */
56 
57 extern void pmx(PlannerInfo *root,
58 				Gene *tour1, Gene *tour2,
59 				Gene *offspring, int num_gene);
60 
61 
62 typedef struct City
63 {
64 	int			tour2_position;
65 	int			tour1_position;
66 	int			used;
67 	int			select_list;
68 }			City;
69 
70 extern City * alloc_city_table(PlannerInfo *root, int num_gene);
71 extern void free_city_table(PlannerInfo *root, City * city_table);
72 
73 /* cycle crossover [CX] */
74 extern int	cx(PlannerInfo *root, Gene *tour1, Gene *tour2,
75 			   Gene *offspring, int num_gene, City * city_table);
76 
77 /* position crossover [PX] */
78 extern void px(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring,
79 			   int num_gene, City * city_table);
80 
81 /* order crossover [OX1] according to Davis */
82 extern void ox1(PlannerInfo *root, Gene *mom, Gene *dad, Gene *offspring,
83 				int num_gene, City * city_table);
84 
85 /* order crossover [OX2] according to Syswerda */
86 extern void ox2(PlannerInfo *root, Gene *mom, Gene *dad, Gene *offspring,
87 				int num_gene, City * city_table);
88 
89 #endif							/* GEQO_RECOMBINATION_H */
90