3 #include <ucw/mempool.h>
4 #include <ucw/eltpool.h>
10 #define HASH_NODE struct graph_node
11 #define HASH_PREFIX(x) hash_##x
12 #define HASH_KEY_ATOMIC id
13 #define HASH_WANT_FIND
15 #define HASH_WANT_CLEANUP
16 #include <ucw/hashtable.h>
22 #define BLOCK_SIZE 4096
24 //struct mempool *mpool_requests;
26 static struct request_point *requests_point;
27 static struct request_line *requests_line;
28 static struct request_area *requests_area;
30 static struct graph_edge **bfs_queue;
31 static struct longline *longlines; int num_longlines;
32 static struct buffer_line *buffer_line;
33 static struct buffer_linelabel *buffer_linelabel;
35 struct eltpool *ep_individuals;
37 struct individual **population1;
38 struct individual **population2;
45 int conf_pop_size = 50;
47 int conf_penalty_bound = 0;
48 int conf_stagnation_bound = 0;
49 int conf_iteration_limit = 4;
51 int conf_term_cond = TERM_COND_ITERATIONS;
53 int conf_breed_rbest_perc = 80;
54 int conf_breed_pop_size_perc = 20;
55 int conf_breed_perc = 50; // Percentage of new pop created by breeding
57 bool conf_mutate_children = 1;
58 int conf_mutate_children_prob = 0.3;
60 int conf_mutate_rbest_perc = 60;
61 int conf_mutate_pop_size_perc = 20;
63 int conf_mutate_move_bound = 0.2;
64 int conf_mutate_regen_bound = 0.1;
65 int conf_mutate_chvar_bound = 0.1;
67 int conf_elite_perc = 5;
69 int old_best = 0; // FIXME: Shall be int max
73 int conf_part_size = 50;
80 void labeller_init(void)
82 // mpool_requests = mp_new(BLOCK_SIZE);
83 GARY_INIT(requests_point, 0);
84 GARY_INIT(requests_line, 0);
85 GARY_INIT(requests_area, 0);
86 GARY_INIT(buffer_line, 0);
87 GARY_INIT(buffer_linelabel, 0);
88 ep_individuals = ep_new(sizeof(struct individual), 1);
91 void make_bitmap_icon(struct point_variant *v, struct sym_icon *si)
93 v->width = si->sir.icon->width;
94 v->height = si->sir.icon->height;
95 v->bitmap = malloc((int) ceil(v->width * v->height * sizeof(bool)));
96 for (int i=0; i<v->width*v->height; i++) v->bitmap[i] = 1;
99 void make_bitmap_point(struct point_variant *v, struct sym_point *sp)
101 v->width = v->height = sp->size;
102 v->bitmap = malloc(sp->size*sp->size * sizeof(bool));
103 // FIXME: Okay, memset would be much nicer here
104 for (int i=0; i<sp->size*sp->size; i++) v->bitmap[i] = 1;
107 void make_bitmap_label(struct point_variant *v UNUSED, struct sym_text *text UNUSED)
111 void labeller_add_point(struct symbol *sym, struct osm_object *object, z_index_t zindex)
114 What does correct check look like?
115 if (object->type != OSM_TYPE_NODE)
122 struct request_point *r = GARY_PUSH(requests_point);
124 r->request.type = REQUEST_POINT;
125 r->request.ind = num_requests++;
135 GARY_INIT(r->variants, 0);
137 struct point_variant *v = GARY_PUSH(r->variants);
141 case SYMBOLIZER_ICON:
142 make_bitmap_icon(v, (struct sym_icon *) sym);
143 r->x = ((struct sym_icon *)sym)->sir.x;
144 r->y = ((struct sym_icon *)sym)->sir.y;
146 case SYMBOLIZER_POINT:
147 make_bitmap_point(v, (struct sym_point *) sym);
148 struct osm_node *n = (struct osm_node *) object;
158 printf("Inited point to [%.2f; %.2f]\n", r->x, r->y);
161 void labeller_add_line(struct symbol *sym, z_index_t zindex)
163 struct buffer_line *b = GARY_PUSH(buffer_line);
164 b->line = (struct sym_line *) sym;
166 sym_plan(sym, zindex);
169 void labeller_add_linelabel(struct symbol *sym, struct osm_object *o, z_index_t zindex)
171 struct buffer_linelabel *ll = GARY_PUSH(buffer_linelabel);
172 ll->way = (struct osm_way *) o;
173 ll->text = (struct sym_text *) sym;
177 void labeller_add_arealabel(struct symbol *sym UNUSED, struct osm_object *o, z_index_t zindex)
179 struct request_area *r = GARY_PUSH(requests_area);
181 r->request.type = REQUEST_AREALABEL;
182 r->request.ind = num_requests++;
184 r->o = (struct osm_multipolygon *) o;
186 r->sym = (struct sym_text *) sym;
188 GARY_INIT(r->text_variant, 0);
189 struct point_variant *v = GARY_PUSH(r->text_variant);
190 make_bitmap_label(v, r->sym);
193 void make_graph(void)
196 struct mempool *mp_edges = mp_new(BLOCK_SIZE);
198 printf("Extracting nodes, will iterate over %lld ways\n", GARY_SIZE(buffer_line));
199 for (uns i=0; i<GARY_SIZE(buffer_line); i++)
201 struct osm_way *way = (struct osm_way *) buffer_line[i].line->s.o;
202 struct graph_node *g_prev = NULL;
203 struct osm_node *o_prev = NULL;
205 CLIST_FOR_EACH(struct osm_ref *, ref, way->nodes)
207 // FIXME: Shall osm_object's type be checked here?
208 struct osm_node *o_node = (struct osm_node *) ref->o;
210 struct graph_node *g_node = hash_find(ref->o->id);
213 g_node = hash_new(ref->o->id);
214 GARY_INIT(g_node->edges, 0);
216 g_node->id = ref->o->id;
217 g_node->num = num_nodes++;
227 struct graph_edge *e = mp_alloc(mp_edges, sizeof(struct graph_edge)); num_edges_dbg++;
228 e->num = num_edges++;
229 e->id = buffer_line[i].line->s.o->id;
230 e->color = buffer_line[i].line->color;
231 e->length = hypot(abs(o_prev->x - o_node->x), abs(o_prev->y - o_node->y));
237 e->longline = (uns) -1;
239 e->sym = buffer_line[i].line;
242 struct graph_edge **edge = GARY_PUSH(g_prev->edges);
244 edge = GARY_PUSH(g_node->edges);
253 void dump_graph(void)
255 HASH_FOR_ALL(hash, node)
257 printf("* Node: (%d) #%ju [%.2f; %.2f]\n", node->num, node->id, node->o->x, node->o->y);
258 for (uns i=0; i<GARY_SIZE(node->edges); i++)
260 struct graph_edge *e = node->edges[i];
261 printf("\t edge (%d) #%ju to ", e->num, e->id);
262 if (node->edges[i]->n1->id == node->id)
263 printf("(%d) #%ju [%.2f; %.2f]\n", e->n2->num, e->n2->id, e->n2->o->x, e->n2->o->y);
264 else if (node->edges[i]->n2->id == node->id)
265 printf("(%d) #%ju [%.2f; %.2f]\n", e->n1->num, e->n1->id, e->n1->o->x, e->n1->o->y);
267 printf("BEWARE! BEWARE! BEWARE!\n");
270 if (node->edges[i]->text) printf(" labelled %s;", osm_val_decode(node->edges[i]->text->text));
271 printf(" colored %d;", node->edges[i]->color);
272 printf(" length %.2f", node->edges[i]->length);
279 void label_graph(void)
281 printf("There are %u line labels requested\n", GARY_SIZE(buffer_linelabel));
282 for (uns i=0; i<GARY_SIZE(buffer_linelabel); i++)
284 printf("Labelling nodes of way %s\n", osm_val_decode(buffer_linelabel[i].text->text));
285 CLIST_FOR_EACH(struct osm_ref *, ref, buffer_linelabel[i].way->nodes)
287 printf("Looking for node %ju\n", ref->o->id);
288 struct graph_node *n = hash_find(ref->o->id);
291 // FIXME: What shall be done?
295 printf("Searching among %u edges\n", GARY_SIZE(n->edges));
296 for (uns j=0; j<GARY_SIZE(n->edges); j++)
298 if (n->edges[j]->id == buffer_linelabel[i].way->o.id)
300 printf("Labelling node %ju\n", n->id);
301 n->edges[j]->text = buffer_linelabel[i].text;
302 n->edges[j]->zindex = buffer_linelabel[i].zindex;
310 void join_edge(struct graph_edge *e, int dir)
312 struct graph_node *other_node = NULL;
324 struct graph_edge *candidate = NULL;
325 for (uns i=0; i<GARY_SIZE(other_node->edges); i++)
327 struct graph_edge *other = other_node->edges[i];
328 if (! other->visited)
330 struct graph_edge **new = GARY_PUSH(bfs_queue);
331 *new = other_node->edges[i];
334 if ((!other->visited) && (e->text) && (other->text) && (e->text->text == other->text->text))
336 if (e->color == other_node->edges[i]->color)
338 if ((!candidate) || (candidate->length < other->length))
345 // Beware: Name conflict here
352 candidate->longline = e->longline;
355 if (candidate->n2 != e->n1)
357 candidate->n1 = candidate->n2;
358 candidate->n2 = e->n1;
363 longlines[e->longline].first = candidate;
367 if (candidate->n1 != e->n2)
369 candidate->n2 = candidate->n1;
370 candidate->n1 = e->n2;
380 GARY_INIT(bfs_queue, 0);
381 GARY_INIT(longlines, 0);
383 printf("Making longlines from %u causal lines, using %d graph edges\n", GARY_SIZE(buffer_line), num_edges_dbg);
385 HASH_FOR_ALL(hash, node)
387 for (uns i=0; i<GARY_SIZE(node->edges); i++)
389 struct graph_edge *e = node->edges[i];
391 // printf("Examining edge from [%.2f; %.2f] to [%.2f; %.2f]\n",
392 // e->n1->o->x, e->n1->o->y, e->n2->o->x, e->n2->o->y);
394 // if (e->visited) HASH_CONTINUE; // FIXME: Is is correct?
395 if (e->visited) continue;
396 // printf("Continuing\n");
397 if (e->longline == (uns) -1)
399 GARY_PUSH(longlines);
400 e->longline = num_longlines++;
401 longlines[e->longline].first = e;
403 // printf("Longline is %u\n", e->longline);
419 GARY_FREE(bfs_queue);
422 void bfs_edge(struct graph_edge *e, struct graph_node *node, struct graph_node *anode, int dir)
425 struct graph_edge *candidate = NULL;
427 if ((e->num > 31) && (e->num < 48)) printf("Searching for neighbours of %d, in longline %u, BFS dir is %d, edge's dir is %d\n", e->num, e->longline, dir, e->dir);
430 for (uns i=0; i<GARY_SIZE(node->edges); i++)
432 struct graph_edge *other = node->edges[i];
433 printf("Touching %d\n", other->num);
434 if (other->num == 44) printf("Longline of 44 is %u\n", other->longline);
435 if ((other->longline != (uns) -1) && (other->longline != e->longline)) continue;
437 if (! other->visited) {
438 struct graph_edge **e_ptr = GARY_PUSH(bfs_queue);
443 if (((other->n1->id == node->id) && (other->n2->id == anode->id)) ||
444 ((other->n2->id == node->id) && (other->n1->id == anode->id)))
447 if (((other->n1->id == node->id) || (other->n2->id == node->id)) &&
448 (e->text) && (other->text) && (e->text->text == other->text->text))
450 if (! candidate || (other->length > candidate->length))
457 struct graph_edge *other = candidate;
459 other->longline = e->longline;
461 other->anode = (other->n1->id == node->id ? other->n2 : other->n1);
462 other->bnode = (other->n1->id == node->id ? other->n1 : other->n2);
468 longlines[other->longline].first = other;
483 for (uns i=0; i<GARY_SIZE(bfs_queue); i++)
485 struct graph_edge *cur = bfs_queue[i];
486 printf("Exploring new edge, %d\n", cur->num);
487 //ASSERT(! cur->visited);
490 if (cur->longline == (uns) -1)
492 GARY_PUSH(longlines);
493 cur->longline = num_longlines++;
494 longlines[cur->longline].first = cur;
499 bfs_edge(cur, cur->n1, cur->n2, 1);
500 bfs_edge(cur, cur->n2, cur->n1, 2);
504 bfs_edge(cur, cur->anode, cur->bnode, cur->dir);
509 void bfs_wrapper(void)
511 GARY_INIT(bfs_queue, 0);
512 GARY_INIT(longlines, 0);
514 HASH_FOR_ALL(hash, node)
516 for (uns i=0; i<GARY_SIZE(node->edges); i++)
518 if (! node->edges[i]->visited)
520 printf("Running new BFS\n");
521 GARY_RESIZE(bfs_queue, 0);
522 struct graph_edge **e = GARY_PUSH(bfs_queue);
526 printf("Joined %d edges\n", dbg_num_hits); dbg_num_hits = 0;
527 printf("Planned %u edges\n", GARY_SIZE(bfs_queue));
533 GARY_FREE(bfs_queue);
538 printf("Starting outer BFS\n");
539 printf("There are %u buffered lines and %d eges\n", GARY_SIZE(buffer_line), num_edges_dbg);
541 GARY_INIT(bfs_queue, 0);
542 GARY_INIT(longlines, 0);
544 int dbg_bfs_continues = 0;
546 HASH_FOR_ALL(hash, node)
548 // FIXME: Skip if visited node
550 for (uns i=0; i<GARY_SIZE(node->edges); i++)
552 struct graph_edge *e = node->edges[i];
554 if (e->visited) continue;
557 for (uns i1=0; i1<GARY_SIZE(e->n1->edges); i1++)
559 struct graph_edge *other = e->n1->edges[i1];
560 if (other->visited) { dbg_bfs_continues++; continue; }
562 if (((other->n1->id == e->n1->id) || (other->n2->id == e->n1->id)) &&
563 (e->text) && (other->text) && (e->text->text == other->text->text))
569 for (uns i2=0; i2<GARY_SIZE(e->n2->edges); i2++)
571 struct graph_edge *other = e->n2->edges[i2];
572 if (other->visited) {dbg_bfs_continues++; continue; }
574 if (((other->n1->id == e->n2->id) || (other->n2->id == e->n2->id)) &&
575 (e->text) && (other->text) && (e->text->text == other->text->text))
585 printf("Total: %d hits, %d visited edges skipped\n", dbg_num_hits, dbg_bfs_continues);
587 GARY_FREE(bfs_queue);
590 void dump_longlines(void)
592 for (uns i=0; i<GARY_SIZE(longlines); i++)
594 struct graph_edge *e = longlines[i].first;
596 printf("> Longline %u;", i);
597 if (longlines[i].first->text) printf(" labelled %s", osm_val_decode(longlines[i].first->text->text));
601 printf("\t#%ju (%d)", e->id, e->num);
605 printf("[%.2f; %.2f] -- #%u [%.2f; %.2f] (dir %d)\n", e->anode->o->x, e->anode->o->y, e->bnode->o->o.id, e->bnode->o->x, e->bnode->o->y, e->dir);
608 printf("[%.2f; %.2f] -- #%u [%.2f; %.2f] (dir %d)\n", e->bnode->o->x, e->bnode->o->y, e->anode->o->o.id, e->anode->o->x, e->anode->o->y, e->dir);
611 printf("[%.2f; %.2f] -- #%u [%.2f; %.2f] (dir %d)\n", e->n1->o->x, e->n1->o->y, e->n2->o->o.id, e->n2->o->x, e->n2->o->y, e->dir);
614 printf("%d\n", e->dir);
622 void make_segments(void)
624 printf("Analysing %u longlines\n", GARY_SIZE(longlines));
625 for (uns i=0; i<GARY_SIZE(longlines); i++)
627 if (! longlines[i].first->text) continue;
628 // printf("Survived! %s\n", osm_val_decode(longlines[i].first->text->text));
629 printf("New longline\n");
630 struct request_line *request = GARY_PUSH(requests_line);
631 request->request.ind = -1;
632 request->request.type = REQUEST_LINELABEL;
634 GARY_INIT(request->segments, 0);
635 request->num_segments = 0;
637 // ->num_variants FIXME
640 struct graph_edge *e = longlines[i].first;
642 if (! e) printf("Oops\n");
646 if (! e->text) break;
647 struct request_segment *r = GARY_PUSH(request->segments);
648 request->num_segments++;
650 r->request.ind = num_requests++;
651 r->request.type = REQUEST_SEGMENT;
653 struct osm_node *n = e->n1->o;
659 r->k = abs(r->x2 - r->x1) / (abs(r->y2 - r->y1) + 0.001); // FIXME: Hack to prevent floating point exception when y2 = y1
661 //printf("Segment [%.2f; %.2f] -- [%.2f; %.2f]\n", r->x1, r->y1, r->x2, r->y2);
664 r->zindex = e->zindex;
665 r->text = malloc(sizeof(struct sym_text));
666 *(r->text) = *(e->text);
670 r->variant = malloc(sizeof(struct point_variant)); // FIXME
671 make_bitmap_label(r->variant, e->text);
678 void dump_linelabel_requests(void)
680 for (uns i=0; i<GARY_SIZE(requests_line); i++)
682 printf("Longline of %d segments, labelled %s\n", requests_line[i].num_segments, osm_val_decode(requests_line[i].segments[0].text->text));
686 void dump_individual(struct individual *individual)
688 for (uns i=0; i<GARY_SIZE(individual->placements); i++)
690 struct placement *p = &(individual->placements[i]);
692 switch (p->request->type)
695 printf("Point at [%.2f; %.2f]\n", p->x, p->y);
697 case REQUEST_LINELABEL: ;
698 struct request_line *rl = (struct request_line *) p->request;
699 printf("%d-segment longline %s\n", rl->num_segments, osm_val_decode(rl->segments[0].text->text));
701 case REQUEST_AREALABEL: ;
702 struct request_area *ra = (struct request_area *) p->request;
703 printf("Area label %s at [%.2f; %.2f]\n", osm_val_decode(ra->sym->text), p->x, p->y);
706 printf("\nTotal penalty: %d\n", individual->penalty);
709 void labeller_label(void)
717 dump_linelabel_requests();
719 printf("Having %u point requests, %u line requests and %u area requests\n", GARY_SIZE(requests_point), GARY_SIZE(requests_line), GARY_SIZE(requests_area));
721 GARY_INIT(population1, conf_pop_size);
722 GARY_INIT(population2, conf_pop_size);
725 printf("Dealing with %d requests\n", num_requests);
728 while (! shall_terminate())
732 struct individual **swp = population1;
733 population1 = population2;
739 dump_individual(population1[0]);
741 for (uns i=0; i<GARY_SIZE(population1[0]->placements); i++)
743 switch (population1[0]->placements[i].request->type)
745 case REQUEST_POINT: ;
746 struct request_point *rp = (struct request_point *) population1[0]->placements[i].request;
747 switch (rp->sym->type)
749 case SYMBOLIZER_POINT: ;
750 // printf("Moving point to final destination\n");
751 struct sym_point *sp = (struct sym_point *) rp->sym;
752 sp->x = population1[0]->placements[i].x;
753 sp->y = population1[0]->placements[i].y;
754 sym_plan((struct symbol *) sp, rp->zindex);
756 case SYMBOLIZER_ICON: ;
757 // printf("Moving icon to final destination\n");
758 struct sym_icon *si = (struct sym_icon *) rp->sym;
759 si->sir.x = population1[0]->placements[i].x;
760 si->sir.y = population1[0]->placements[i].y;
761 sym_plan((struct symbol *) si, rp->zindex);
767 case REQUEST_AREALABEL: ;
768 struct request_area *ra = (struct request_area *) population1[0]->placements[i].request;
769 sym_plan((struct symbol *) ra->sym, ra->zindex);
772 case REQUEST_LINELABEL: ;
773 struct request_line *rl = (struct request_line *) population1[0]->placements[i].request;
774 for (uns j=0; j<GARY_SIZE(rl->segments); j++)
776 // printf("Planning text %s to [%.2f; %.2f]\n", osm_val_decode(rl->segments[j].text->text), rl->segments[j].text->x, rl->segments[j].text->y);
777 rl->segments[j].text->next_duplicate = NULL;
778 rl->segments[j].text->next_in_tile = NULL;
779 rl->segments[j].text->x = population1[0]->placements[i].x;
780 rl->segments[j].text->y = population1[0]->placements[i].y;
781 sym_plan((struct symbol *) rl->segments[j].text, rl->segments[j].zindex); // FIXME: z-index
785 case REQUEST_SEGMENT: ;
786 struct request_segment *rs = (struct request_segment *) population1[0]->placements[i].request;
787 printf("Segment!\n");
794 while (! shall_terminate())
802 // sort population by fitness
804 struct individual **swp = population1;
805 population1 = population2;
806 printf("Swapped populations\n");
808 // GARY_RESIZE(population2, 0) -- is it needed?
813 void make_population(void)
815 for (int i=0; i<conf_pop_size; i++)
817 struct individual *individual = ep_alloc(ep_individuals); init_individual(individual);
818 population1[i] = individual;
821 for (uns j=0; j<GARY_SIZE(requests_point); j++)
823 init_placement(&(individual->placements[p++]), (struct request *) &requests_point[j]);
825 for (uns j=0; j<GARY_SIZE(requests_line); j++)
827 init_placement(&(individual->placements[p++]), (struct request *) &requests_line[j]);
828 for (uns k=0; k<GARY_SIZE(requests_line[j].segments); k++)
830 init_placement(&(individual->placements[p++]), (struct request *) &requests_line[j].segments[k]);
833 for (uns j=0; j<GARY_SIZE(requests_area); j++)
835 init_placement(&(individual->placements[p++]), (struct request *) &requests_area[j]);
838 ASSERT(p == num_requests);
842 bool shall_terminate(void)
844 switch (conf_term_cond)
846 case TERM_COND_PENALTY:
847 return (population1[0]->penalty < conf_penalty_bound);
848 case TERM_COND_STAGNATION:
849 return (abs(old_best - population1[0]->penalty) < conf_stagnation_bound);
850 case TERM_COND_ITERATIONS:
851 return (iteration >= conf_iteration_limit);
853 // FIXME: Warn the user that no condition is set
862 printf("%.2f\n", ((double) conf_breed_pop_size_perc/100));
863 int conf_breed_pop_size = ((double) conf_breed_pop_size_perc/100) * conf_pop_size;
864 struct individual **breed_buffer;
865 while (i < conf_breed_pop_size)
867 printf("%d < %d, breeding\n", i, conf_breed_pop_size);
868 int parent1 = randint(1, conf_breed_pop_size);
869 int parent2 = randint(1, conf_breed_pop_size);
870 printf("Will breed %d and %d, chosen of %d best of %d population (intended to be %d)\n", parent1, parent2, conf_breed_pop_size, GARY_SIZE(population1), conf_pop_size);
871 breed_buffer = perform_crossover(population1[parent1], population1[parent2]);
872 population2[pop2_ind++] = breed_buffer[0];
873 population2[pop2_ind++] = breed_buffer[1];
878 acc += conf_breed_rbest_perc;
880 return; // FIXME: DEBUG HACK
882 int remaining = (1 - acc) * (conf_pop_size * conf_breed_perc);
883 int step = remaining / conf_pop_size;
884 for (; i<conf_pop_size; i += 2)
886 printf("Asking for %d and %d of %d\n", i*step, i*(step+1), conf_pop_size);
887 breed_buffer = perform_crossover(population1[i*step], population1[i*step+1]);
888 population2[pop2_ind++] = breed_buffer[0];
889 population2[pop2_ind++] = breed_buffer[1];
892 // FIXME: Could there be one missing individual?
895 struct individual **perform_crossover(struct individual *parent1, struct individual *parent2)
897 struct individual **buffer = malloc(2*sizeof(struct individual));
898 struct individual *child1 = ep_alloc(ep_individuals); init_individual(child1);
899 struct individual *child2 = ep_alloc(ep_individuals); init_individual(child2);
901 printf("Performing crossover\n");
903 for (uns i=0; i<GARY_SIZE(parent1->placements); i++)
905 printf("%dth placement out of %d\n", i, num_requests);
906 if (! parent1->placements[i].processed)
908 struct placement **clos_symbols = get_closure(&(parent1->placements[i]), parent1, parent2);
909 int x = randint(1, 2);
913 copy_symbols(clos_symbols, parent1, child1);
914 copy_symbols(clos_symbols, parent2, child2);
918 copy_symbols(clos_symbols, parent2, child1);
919 copy_symbols(clos_symbols, parent1, child2);
921 printf("Symbols copied; %lld\n", GARY_SIZE(clos_symbols));
922 GARY_FREE(clos_symbols);
925 if (conf_mutate_children)
927 if (randint(1, 1000) < conf_mutate_children_prob * 1000) perform_mutation(child1);
928 if (randint(1, 1000) < conf_mutate_children_prob * 1000) perform_mutation(child2);
940 int conf_mutate_pop_size = conf_mutate_pop_size_perc * conf_pop_size;
941 while (i < conf_mutate_rbest_perc * conf_pop_size)
943 int ind = randint(1, conf_mutate_pop_size);
944 copy_individual(population2[pop2_ind], population1[ind]);
945 perform_mutation(population2[pop2_ind]);
950 void perform_mutation(struct individual *individual)
952 for (uns i=0; i<GARY_SIZE(individual->placements); i++)
954 int x = randint(1, 1000);
957 if (x <= acc + conf_mutate_move_bound)
959 move_symbol(&(individual->placements[i]));
962 acc += conf_mutate_move_bound;
964 if (x <= acc + conf_mutate_regen_bound)
966 gen_coords(&(individual->placements[i]));
969 acc += conf_mutate_regen_bound;
971 if (x <= acc + conf_mutate_chvar_bound)
973 if (0) // if num_variants > 1
975 // FIXME: assign new variant
983 for (int i=0; i<conf_elite_perc * conf_pop_size; i++)
985 population2[pop2_ind++] = population1[0];
989 void rank_population(void)
994 void gen_coords(struct placement *p)
996 switch(p->request->type)
1003 void gen_coords_point(struct placement *p UNUSED)
1008 struct map_part **get_parts(struct placement *symbol, struct individual *individual)
1010 struct map_part **buffer;
1011 GARY_INIT(buffer, 0);
1012 int x_min = symbol->x / conf_part_size;
1013 int x_max = (symbol->x /*+ symbol->bitmap->width*/ + conf_part_size - 1) / conf_part_size;
1014 int y_min = symbol->y / conf_part_size;
1015 int y_max = (symbol->y /*+ symbol->bitmap->height*/ + conf_part_size - 1) / conf_part_size;
1017 for (int x=x_min; x < x_max; x++)
1018 for (int y=y_min; y < y_max; y++)
1020 struct map_part *m = GARY_PUSH(buffer);
1021 *m = individual->map[x][y];
1027 int randint(int min, int max)
1030 //printf("Returning %d + (%d %% (%d - %d)) = %d + %d %% %d = %d + %d = %d\n", min, r, max, min, min, r, max-min, min, r%(max-min), min+(r%(max-min)));
1031 return min + (r % (max - min));
1032 return (r * (max - min));
1035 struct placement **get_closure(struct placement *placement, struct individual *parent1, struct individual *parent2 UNUSED)
1037 printf("Getting closure\n");
1038 struct placement **closure;
1039 GARY_INIT(closure, 0);
1040 bool *chosen = malloc(GARY_SIZE(parent1->placements) * sizeof(bool));
1041 chosen[placement->request->ind] = 1;
1043 struct placement **p = GARY_PUSH(closure); *p = placement;
1046 while (first < GARY_SIZE(closure))
1048 printf("Iterating, first is %d\n", first);
1049 struct placement **overlapping = get_overlapping(placement);
1050 filter(overlapping, chosen);
1051 for (uns j=0; j<GARY_SIZE(overlapping); j++)
1053 p = GARY_PUSH(closure); *p = overlapping[j];
1054 chosen[overlapping[j]->request->ind] = 1;
1056 GARY_FREE(overlapping);
1063 void copy_symbols(struct placement **closure, struct individual *parent, struct individual *child)
1065 //printf("%d\n", child->penalty);
1066 //printf("Closure size: %lld\n", GARY_SIZE(closure));
1067 for (uns i=0; i<GARY_SIZE(closure); i++)
1069 int ind = closure[i]->request->ind;
1070 child->placements[ind] = parent->placements[ind];
1071 child->placements[ind].processed = 0;
1075 void move_symbol(struct placement *p)
1077 switch (p->request->type)
1080 move_symbol_point(p);
1084 void move_symbol_point(struct placement *p)
1086 p->x += (double) (move_min + randdouble()) * flip(1, -1);
1087 p->y += (double) (move_min + randdouble()) * flip(1, -1);
1090 void init_placement(struct placement *p, struct request *r)
1097 case REQUEST_POINT: ;
1098 struct request_point *rp = (struct request_point *) r;
1102 case REQUEST_SEGMENT: ;
1103 struct request_segment *rs = (struct request_segment *) r;
1107 case REQUEST_AREALABEL: ;
1108 struct request_area *ra = (struct request_area *) r;
1109 struct sym_text *st = ra->sym;
1115 void init_individual(struct individual *i)
1117 //printf("Initing individual\n");
1118 GARY_INIT(i->placements, num_requests);
1119 GARY_INIT(i->map, 0);
1120 i->penalty = 0; // FIXME
1123 struct placement **get_overlapping(struct placement *p UNUSED)
1125 struct placement **buffer;
1126 GARY_INIT(buffer, 0);
1130 void filter(struct placement **list UNUSED, bool *pred UNUSED)
1135 int flip(int a, int b)
1137 return (random() % 2 ? a : b);
1140 double randdouble(void)
1142 // FIXME: How the hell shall double in range <0, 1> be generated? O:)
1149 GARY_FREE(requests_point);
1150 GARY_FREE(requests_line);
1151 GARY_FREE(requests_area);
1154 void copy_individual(struct individual *src, struct individual *dest)
1156 src->penalty = dest->penalty;
1157 GARY_INIT(dest->placements, GARY_SIZE(src->placements));
1158 for (uns i=0; i<GARY_SIZE(src->placements); i++)
1160 dest->placements[i] = src->placements[i];