1 #ifdef _WIN32 2 # include <malloc.h> 3 #else 4 #include <stdlib.h> 5 #endif 6 #include <stdlib.h> 7 #include <assert.h> 8 9 #include "initial.h" 10 #include "lib.h" 11 12 /* generate a random initial schedule where all predecessor 13 * dependencies are fulfilled. we do this by storing a set with all 14 * jobs, their dependency count and how many dependecies are already 15 * scheduled in a linked list sorted by the number of unfillfiled 16 * dependencies. we can then in turn choose one of the jobs where that 17 * number is 0, and then update the list 18 * */ 19 20 struct initial_job { 21 int job_number; 22 int left_deps; 23 struct initial_job **successors; 24 struct initial_job *next; 25 struct initial_job *prev; 26 }; 27 28 /* XXX this could be sped up by not regenrating the structure every single 29 * time this is run */ random_schedule(struct rcps_problem * problem)30int *random_schedule(struct rcps_problem *problem) { 31 int *result; 32 int cproblem; 33 int i, j, c; 34 int zcount; 35 struct initial_job *njob; 36 struct initial_job *cjob; 37 struct initial_job *ojob; 38 struct initial_job *job_list; 39 40 struct initial_job *A; 41 struct initial_job *B; 42 struct initial_job *C; 43 44 /* empty result set */ 45 result = (int*)malloc(sizeof(int) * problem->job_count); 46 cproblem = 0; 47 48 /* init the list */ 49 job_list = NULL; 50 for (i = 0; i < problem->job_count; i++) { 51 /* create new job */ 52 njob = (struct initial_job*)malloc(sizeof(struct initial_job)); 53 njob->job_number = i; 54 njob->left_deps = problem->jobs[i]->predeccessor_count; 55 njob->next = NULL; 56 njob->prev = NULL; 57 if (problem->jobs[i]->successor_count > 0) { 58 njob->successors = (struct initial_job**)malloc(sizeof(struct initial_job *) * 59 problem->jobs[i]->successor_count); 60 } 61 else { 62 njob->successors = NULL; 63 } 64 /* insert into the list */ 65 if (job_list == NULL) { 66 job_list = njob; 67 } 68 else { 69 /* go through the list */ 70 ojob = NULL; 71 cjob = job_list; 72 while ((cjob != NULL) && (cjob->left_deps < njob->left_deps)) { 73 ojob = cjob; 74 cjob = cjob->next; 75 } 76 /* insert */ 77 if (cjob == NULL) { 78 ojob->next = njob; 79 njob->prev = ojob; 80 } 81 else if (ojob == NULL) { 82 njob->next = job_list; 83 job_list = njob; 84 } 85 else { 86 njob->next = cjob; 87 njob->prev = ojob; 88 ojob->next = njob; 89 cjob->prev = njob; 90 } 91 } 92 } 93 /* fix the successors */ 94 cjob = job_list; 95 while (cjob) { 96 for (i = 0; i < problem->jobs[cjob->job_number]->successor_count; i++) { 97 for (j = 0; j < problem->job_count; j++) { 98 if (problem->jobs[j] == 99 problem->jobs[cjob->job_number]->successors[i]) { 100 /* update with successor j */ 101 ojob = job_list; 102 while ((ojob) && (ojob->job_number != j)) { 103 ojob = ojob->next; 104 } 105 cjob->successors[i] = ojob; 106 break; 107 } 108 } 109 } 110 cjob = cjob->next; 111 } 112 /* get the zero count */ 113 cjob = job_list; 114 zcount = 0; 115 while ((cjob) && (cjob->left_deps == 0)) { 116 zcount++; 117 cjob = cjob->next; 118 } 119 /* work your way through the list */ 120 c = 0; 121 while (zcount != 0) { 122 /* choose the proper job */ 123 /* XXX randomly for now, insert heuristics here */ 124 i = irand(zcount); 125 cjob = job_list; 126 while (i > 0) { 127 cjob = cjob->next; 128 i--; 129 } 130 /* remove from list */ 131 if (cjob == job_list) { 132 job_list = cjob->next; 133 if (job_list != NULL) { 134 job_list->prev = NULL; 135 } 136 } 137 else { 138 if (cjob->next != NULL) { 139 cjob->next->prev = cjob->prev; 140 } 141 if (cjob->prev != NULL) { 142 cjob->prev->next = cjob->next; 143 } 144 } 145 zcount--; 146 /* add to result */ 147 result[c] = cjob->job_number; 148 c++; 149 /* update the list */ 150 for (i = 0; i < problem->jobs[cjob->job_number]->successor_count; i++) { 151 ojob = cjob->successors[i]; 152 ojob->left_deps--; 153 /* resort */ 154 while ((ojob->prev != NULL) && (ojob->prev->left_deps > ojob->left_deps)) { 155 /* shift down */ 156 C = ojob->next; 157 B = ojob->prev; 158 A = B->prev; 159 if (C) { 160 C->prev = B; 161 } 162 B->prev = ojob; 163 B->next = C; 164 ojob->next = B; 165 ojob->prev = A; 166 if (A) { 167 A->next = ojob; 168 } 169 else { 170 job_list = ojob; 171 } 172 } 173 /* update zcount */ 174 if (ojob->left_deps == 0) { 175 zcount++; 176 } 177 } 178 /* clean up */ 179 free(cjob->successors); 180 free(cjob); 181 } 182 return result; 183 } 184 initial(struct rcps_problem * problem,struct rcps_genome * genome)185void initial(struct rcps_problem *problem, struct rcps_genome *genome) { 186 int i; 187 /* XXX assert that he structs in the genome are not yet mallocd */ 188 /* the schedule */ 189 genome->schedule = random_schedule(problem); 190 /* the modes */ 191 genome->modes = (int*)malloc(problem->genome_modes * sizeof(int)); 192 for (i = 0; i < problem->genome_modes; i++) { 193 if (problem->modes_max[i] == 0) { 194 /* XXX this should never happen, assert it and remove later */ 195 assert(0 == 1); 196 } 197 else { 198 genome->modes[i] = irand(problem->modes_max[i]); 199 } 200 } 201 /* the alternatives */ 202 genome->alternatives = (int*)malloc(problem->genome_alternatives * 203 sizeof(int)); 204 for (i = 0; i < problem->genome_alternatives; i++) { 205 if (problem->alternatives_max[i] == 0) { 206 /* XXX this should never happen, assert it and remove later */ 207 assert(0 == 1); 208 } 209 else { 210 genome->alternatives[i] = irand(problem->alternatives_max[i]); 211 } 212 } 213 } 214