PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
geqo_cx.c File Reference
Include dependency graph for geqo_cx.c:

Go to the source code of this file.

Functions

int cx (PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring, int num_gene, City *city_table)
 

Function Documentation

int cx ( PlannerInfo root,
Gene tour1,
Gene tour2,
Gene offspring,
int  num_gene,
City city_table 
)

Definition at line 47 of file geqo_cx.c.

References geqo_randint, i, City::tour1_position, City::tour2_position, and City::used.

Referenced by bf_decrypt(), bf_encrypt(), bf_init(), bf_load(), geqo(), intctx_free(), px_find_combo(), rj_decrypt(), rj_encrypt(), rj_init(), and rj_load().

49 {
50  int i,
51  start_pos,
52  curr_pos;
53  int count = 0;
54  int num_diffs = 0;
55 
56  /* initialize city table */
57  for (i = 1; i <= num_gene; i++)
58  {
59  city_table[i].used = 0;
60  city_table[tour2[i - 1]].tour2_position = i - 1;
61  city_table[tour1[i - 1]].tour1_position = i - 1;
62  }
63 
64  /* choose random cycle starting position */
65  start_pos = geqo_randint(root, num_gene - 1, 0);
66 
67  /* child inherits first city */
68  offspring[start_pos] = tour1[start_pos];
69 
70  /* begin cycle with tour1 */
71  curr_pos = start_pos;
72  city_table[(int) tour1[start_pos]].used = 1;
73 
74  count++;
75 
76  /* cx main part */
77 
78 
79 /* STEP 1 */
80 
81  while (tour2[curr_pos] != tour1[start_pos])
82  {
83  city_table[(int) tour2[curr_pos]].used = 1;
84  curr_pos = city_table[(int) tour2[curr_pos]].tour1_position;
85  offspring[curr_pos] = tour1[curr_pos];
86  count++;
87  }
88 
89 
90 /* STEP 2 */
91 
92  /* failed to create a complete tour */
93  if (count < num_gene)
94  {
95  for (i = 1; i <= num_gene; i++)
96  {
97  if (!city_table[i].used)
98  {
99  offspring[city_table[i].tour2_position] =
100  tour2[(int) city_table[i].tour2_position];
101  count++;
102  }
103  }
104  }
105 
106 
107 /* STEP 3 */
108 
109  /* still failed to create a complete tour */
110  if (count < num_gene)
111  {
112 
113  /* count the number of differences between mom and offspring */
114  for (i = 0; i < num_gene; i++)
115  if (tour1[i] != offspring[i])
116  num_diffs++;
117 
118  }
119 
120  return num_diffs;
121 }
#define geqo_randint(root, upper, lower)
Definition: geqo_random.h:38
int tour1_position
int tour2_position
int i