labeller.c

   1 #include <ucw/lib.h>
   2 #include <ucw/gary.h>
   3 #include <ucw/mempool.h>
   4 #include <ucw/eltpool.h>
   5
   6 #include "leo.h"
   7 #include "sym.h"
   8 #include "labeller.h"
   9
  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
  14 #define HASH_WANT_NEW
  15 #include <ucw/hashtable.h>
  16
  17 #include <stdio.h>
  18 #include <stdlib.h>
  19 #include <math.h>
  20
  21 #define BLOCK_SIZE 4096
  22
  23 //struct mempool *mpool_requests;
  24
  25 static struct request_point *requests_point;
  26 static struct request_line *requests_line;
  27 static struct request_area *requests_area;
  28
  29 static struct graph_edge *bfs_queue;
  30 static struct longline *longlines; int num_longlines;
  31 static struct buffer_line *buffer_line;
  32 static struct buffer_linelabel *buffer_linelabel;
  33
  34 struct eltpool *ep_individuals;
  35
  36 struct individual **population1;
  37 struct individual **population2;
  38
  39 int conf_pop_size = 50;
  40
  41 int conf_penalty_bound = 0;
  42 int conf_stagnation_bound = 0;
  43 int conf_iteration_limit = 5;
  44
  45 int conf_term_cond = TERM_COND_ITERATIONS;
  46
  47 int conf_breed_rbest_perc = 80;
  48 int conf_breed_pop_size_perc = 20;
  49 int conf_breed_perc = 50;
  50
  51 bool conf_mutate_children = 1;
  52 int conf_mutate_children_prob = 0.3;
  53
  54 int conf_mutate_rbest_perc = 60;
  55 int conf_mutate_pop_size_perc = 20;
  56
  57 int conf_mutate_move_bound = 0.2;
  58 int conf_mutate_regen_bound = 0.1;
  59 int conf_mutate_chvar_bound = 0.1;
  60
  61 int conf_elite_perc = 5;
  62
  63 int old_best = 0; // FIXME: Shall be int max
  64 int iteration = 0;
  65 int pop2_ind;
  66
  67 int conf_part_size = 50;
  68
  69 int move_min = 0;
  70 int move_max = 1;
  71
  72 int num_requests = 0;
  73
  74 void labeller_init(void)
  75 {
  76 //  mpool_requests = mp_new(BLOCK_SIZE);
  77   GARY_INIT(requests_point, 0);
  78   GARY_INIT(requests_area, 0);
  79   GARY_INIT(buffer_line, 0);
  80   GARY_INIT(buffer_linelabel, 0);
  81   ep_individuals = ep_new(sizeof(struct individual), 1);
  82 }
  83
  84 void make_bitmap_icon(struct point_variant *v, struct sym_icon *si)
  85 {
  86   v->width = si->sir.icon->width;
  87   v->height = si->sir.icon->height;
  88 }
  89
  90 void make_bitmap_point(struct point_variant *v, struct sym_point *sp)
  91 {
  92   v->width = v->height = sp->size;
  93   v->bitmap = malloc(sp->size*sp->size * sizeof(bool));
  94   // FIXME: Okay, memset would be much nicer here
  95   for (int i=0; i<sp->size*sp->size; i++) v->bitmap[i] = 1;
  96 }
  97
  98 void make_bitmap_label(struct point_variant *v UNUSED, struct sym_text *text UNUSED)
  99 {
 100 }
 101
 102 void labeller_add_point(struct symbol *sym, struct osm_object *object, z_index_t zindex)
 103 {
 104 /* FIXME
 105    What does correct check look like?
 106   if (object->type != OSM_TYPE_NODE)
 107   {
 108     // FIXME
 109     return;
 110   }
 111 */
 112
 113   struct request_point *r = GARY_PUSH(requests_point);
 114   r->sym = sym;
 115   r->object = object;
 116   r->zindex = zindex;
 117   ((struct request *)r)->ind = num_requests++;
 118
 119   struct osm_node *n = (struct osm_node *) object;
 120   r->x = n->x;
 121   r->y = n->y;
 122
 123   r->offset_x = 0;
 124   r->offset_y = 0;
 125
 126   r->num_variants = 1;
 127   GARY_INIT(r->variants, 0);
 128
 129   struct point_variant *v = GARY_PUSH(r->variants);
 130
 131   if (sym->type == SYMBOLIZER_ICON)
 132   switch (sym->type)
 133   {
 134     case SYMBOLIZER_ICON:
 135       make_bitmap_icon(v, (struct sym_icon *) sym);
 136       break;
 137     case SYMBOLIZER_POINT:
 138       make_bitmap_point(v, (struct sym_point *) sym);
 139       break;
 140     default:
 141       // Oops :)
 142       // FIXME
 143       return;
 144   }
 145
 146   sym_plan(sym, zindex); // TEMPORARY
 147 }
 148
 149 void labeller_add_line(struct symbol *sym, z_index_t zindex)
 150 {
 151   struct buffer_line *b = GARY_PUSH(buffer_line);
 152   b->line = (struct sym_line *) sym;
 153   b->zindex = zindex;
 154   sym_plan(sym, zindex);
 155 }
 156
 157 void labeller_add_arealabel(struct symbol *sym UNUSED, struct osm_object *o, z_index_t zindex)
 158 {
 159   struct request_area *r = GARY_PUSH(requests_area);
 160   r->o = (struct osm_multipolygon *) o;
 161   r->zindex = zindex;
 162   ((struct request *)r)->ind = num_requests++;
 163 }
 164
 165 void make_graph(void)
 166 {
 167   hash_init();
 168   struct mempool *mp_edges = mp_new(BLOCK_SIZE);
 169
 170   printf("Extracting nodes, will iterate over %lld ways\n", GARY_SIZE(buffer_line));
 171   for (uns i=0; i<GARY_SIZE(buffer_line); i++)
 172   {
 173     struct osm_way *way = (struct osm_way *) buffer_line[i].line->s.o;
 174     struct graph_node *prev = NULL;
 175     struct osm_node *prev_node = NULL;
 176     CLIST_FOR_EACH(struct osm_ref *, ref, way->nodes)
 177     {
 178       // FIXME: Shall osm_object's type be checked here?
 179       struct osm_node *node = (struct osm_node *) ref->o;
 180
 181       struct graph_node *n = hash_find(ref->o->id);
 182       if (!n)
 183       {
 184         n = hash_new(ref->o->id);
 185         GARY_INIT(n->edges, 0);
 186       }
 187
 188       if (! prev)
 189       {
 190         prev = n;
 191         prev_node = node;
 192         continue;
 193       }
 194
 195       struct graph_edge *e = (struct graph_edge *) mp_alloc(mp_edges, sizeof(struct graph_edge));
 196       e->id = buffer_line[i].line->s.o->id;
 197       e->color = buffer_line[i].line->color;
 198       e->length = hypot(abs(prev_node->x - node->x), abs(prev_node->y - node->y));
 199       e->visited = 0;
 200       e->prev = NULL;
 201       e->next = NULL;
 202       e->n1 = prev;
 203       e->n2 = n;
 204       e->longline = -1;
 205       e->text = NULL;
 206       e->sym = buffer_line[i].line;
 207
 208       struct graph_edge **edge = GARY_PUSH(prev->edges);
 209       *edge = e;
 210       edge = GARY_PUSH(n->edges);
 211       *edge = e;
 212     }
 213   }
 214 }
 215
 216 void label_graph(void)
 217 {
 218   for (uns i=0; i<GARY_SIZE(buffer_linelabel); i++)
 219   {
 220     CLIST_FOR_EACH(struct osm_ref *, ref, buffer_linelabel[i].way->nodes)
 221     {
 222       struct graph_node *n = hash_find(ref->o->id);
 223       if (n == NULL)
 224       {
 225         // FIXME: What shall be done?
 226       }
 227       else
 228       {
 229         for (uns j=0; j<GARY_SIZE(n->edges); j++)
 230         {
 231           if (n->edges[j]->id == ((struct osm_object *) buffer_linelabel[i].way)->id)
 232           {
 233             n->edges[j]->text = buffer_linelabel[i].text;
 234           }
 235         }
 236       }
 237     }
 238   }
 239 }
 240
 241 void join_edge(struct graph_edge *e, int dir)
 242 {
 243   struct graph_node *other_node = NULL;
 244   switch (dir)
 245   {
 246     case 1:
 247       other_node = e->n2;
 248       break;
 249     case 2:
 250       other_node = e->n1;
 251       break;
 252     // FIXME: default?
 253   }
 254
 255   struct graph_edge *candidate = NULL;
 256   for (uns i=0; i<GARY_SIZE(other_node->edges); i++)
 257   {
 258     struct graph_edge *other = other_node->edges[i];
 259     if (! other->visited)
 260     {
 261     struct graph_edge **new = GARY_PUSH(bfs_queue);
 262     *new = other_node->edges[i];
 263     }
 264
 265     //if (1) // FIXME: same labels but not the same edge
 266     if ((!other->visited) && (e->text) && (other->text) && (e->text->text == other->text->text))
 267     {
 268       if (e->color == other_node->edges[i]->color)
 269       {
 270         if ((!candidate) || (candidate->length < other->length))
 271         {
 272           candidate = other;
 273         }
 274       }
 275       else
 276       {
 277         // Beware: Name conflict here
 278       }
 279     }
 280   }
 281
 282   if (candidate)
 283   {
 284     candidate->longline = e->longline;
 285     if (dir == 1)
 286     {
 287       if (candidate->n2 != e->n1)
 288       {
 289         candidate->n1 = candidate->n2;
 290         candidate->n2 = e->n1;
 291       }
 292       e->prev = candidate;
 293       candidate->next = e;
 294
 295       longlines[e->longline].first = candidate;
 296     }
 297     else
 298     {
 299       if (candidate->n1 != e->n2)
 300       {
 301         candidate->n2 = candidate->n1;
 302         candidate->n1 = e->n2;
 303       }
 304       e->next = candidate;
 305       candidate->prev = e;
 306     }
 307   }
 308 }
 309
 310 void labeller_add_linelabel(struct symbol *sym, struct osm_object *o, z_index_t zindex)
 311 {
 312   struct buffer_linelabel *ll = GARY_PUSH(buffer_linelabel);
 313   ll->way = (struct osm_way *) o;
 314   ll->text = (struct sym_text *) sym;
 315   ll->zindex = zindex;
 316 }
 317
 318 void bfs(void)
 319 {
 320   GARY_INIT(bfs_queue, 0);
 321   GARY_INIT(longlines, 0);
 322
 323   HASH_FOR_ALL(hash, node)
 324   {
 325     for (uns i=0; i<GARY_SIZE(node->edges); i++)
 326     {
 327       struct graph_edge *e = node->edges[i];
 328
 329       if (e->visited) HASH_CONTINUE;
 330       if (e->longline == (uns) -1)
 331       {
 332         GARY_PUSH(longlines);
 333         e->longline = num_longlines++;
 334         longlines[e->longline].first = e;
 335       }
 336
 337       e->visited = 1;
 338
 339       if (! e->prev)
 340       {
 341         join_edge(e, 1);
 342       }
 343       if (! e->next)
 344       {
 345         join_edge(e, 2);
 346       }
 347     }
 348   }
 349   HASH_END_FOR;
 350
 351   GARY_FREE(bfs_queue);
 352 }
 353
 354 void make_segments(void)
 355 {
 356   GARY_INIT(requests_line, 0);
 357
 358   for (uns i=0; i<GARY_SIZE(longlines); i++)
 359   {
 360     struct request_line *request = GARY_PUSH(requests_line);
 361     GARY_INIT(request->segments, 0);
 362     struct graph_edge *e = longlines[i].first;
 363     if (! e) printf("Oops\n");
 364     while (e)
 365     {
 366       struct request_segment *r = GARY_PUSH(request->segments);
 367       request->num_segments++;
 368       r->x1 = ((struct osm_node *) e->n1)->x;
 369       r->y1 = ((struct osm_node *) e->n1)->y;
 370       r->x2 = ((struct osm_node *) e->n2)->x;
 371       r->y2 = ((struct osm_node *) e->n2)->y;
 372       r->sym = e->sym;
 373       r->k = abs(r->x2 - r->x1) / (abs(r->y2 - r->y1) + 0.001); // FIXME: Hack to prevent floating point exception when y2 = y1
 374       r->variant = malloc(sizeof(struct point_variant)); // FIXME
 375       ((struct request *)r)->ind = num_requests++;
 376       make_bitmap_label(r->variant, e->text);
 377
 378       e = e->next;
 379     }
 380   }
 381 }
 382
 383 void labeller_label(void)
 384 {
 385   make_graph();
 386   label_graph();
 387   bfs();
 388   make_segments();
 389
 390   make_population();
 391
 392   while (! shall_terminate())
 393   {
 394     // sort population by fitness
 395     // alloc new population
 396     breed();
 397     mutate();
 398     elite();
 399     rank_population();
 400   }
 401 }
 402
 403 void make_population(void)
 404 {
 405   GARY_INIT(population1, 0);
 406   for (int i=0; i<conf_pop_size; i++)
 407   {
 408     struct individual *individual = ep_alloc(ep_individuals);
 409     struct individual **ind = GARY_PUSH(population1);
 410     *ind = individual;
 411     GARY_INIT(individual->map, 0);
 412     GARY_INIT(individual->placements, 0);
 413
 414     for (uns j=0; j<GARY_SIZE(requests_point); j++)
 415     {
 416       struct placement *p = GARY_PUSH(individual->placements);
 417       init_placement(p, (struct request *) &requests_point[i]);
 418     }
 419     for (uns j=0; j<GARY_SIZE(requests_line); j++)
 420     {
 421       struct placement *p = GARY_PUSH(individual->placements);
 422       init_placement(p, (struct request *) &requests_line[i]);
 423     }
 424     for (uns j=0; j<GARY_SIZE(requests_area); j++)
 425     {
 426       struct placement *p = GARY_PUSH(individual->placements);
 427       init_placement(p, (struct request *) &requests_area[i]);
 428     }
 429   }
 430 }
 431
 432 bool shall_terminate(void)
 433 {
 434   switch (conf_term_cond)
 435   {
 436     case TERM_COND_PENALTY:
 437       return (population1[0]->penalty < conf_penalty_bound);
 438     case TERM_COND_STAGNATION:
 439       return (abs(old_best - population1[0]->penalty) < conf_stagnation_bound);
 440     case TERM_COND_ITERATIONS:
 441       return (iteration >= conf_iteration_limit);
 442     default:
 443       // FIXME: Warn the user that no condition is set
 444       return 1;
 445   }
 446 }
 447
 448 void breed(void)
 449 {
 450   int acc = 0;
 451   int i=0;
 452   printf("%.2f\n", ((double) conf_breed_pop_size_perc/100));
 453   int conf_breed_pop_size = ((double) conf_breed_pop_size_perc/100) * conf_pop_size;
 454   struct individual **breed_buffer;
 455   while (i < conf_breed_rbest_perc * conf_pop_size)
 456   {
 457     int parent1 = randint(1, conf_breed_pop_size);
 458     int parent2 = randint(1, conf_breed_pop_size);
 459     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);
 460     breed_buffer = perform_crossover(population1[parent1], population1[parent2]);
 461     population2[2*i] = breed_buffer[0];
 462     population2[2*i+1] = breed_buffer[1];
 463     free(breed_buffer);
 464   }
 465
 466   acc += conf_breed_rbest_perc;
 467
 468   int remaining = (1 - acc) * (conf_pop_size * conf_breed_perc);
 469   int step = remaining / conf_pop_size;
 470   for (; i<conf_pop_size; i += 2)
 471   {
 472     breed_buffer = perform_crossover(population1[i*step], population1[i*(step+1)]);
 473     population2[2*i] = breed_buffer[0];
 474     population2[2*i+1] = breed_buffer[1];
 475   }
 476
 477   // FIXME: Could there be one missing individual?
 478 }
 479
 480 struct individual **perform_crossover(struct individual *parent1, struct individual *parent2)
 481 {
 482   struct individual **buffer = malloc(2*sizeof(struct individual));
 483   struct individual *child1 = ep_alloc(ep_individuals);
 484   struct individual *child2 = ep_alloc(ep_individuals);
 485   GARY_INIT(child1->placements, 0);
 486   GARY_INIT(child2->placements, 0);
 487
 488   printf("Performing crossover\n");
 489
 490   for (uns i=0; i<GARY_SIZE(parent1->placements); i++)
 491   {
 492     printf("%dth placement\n", i);
 493     if (! parent1->placements[i].processed)
 494     {
 495       struct placement **clos_symbols;
 496       GARY_INIT(clos_symbols, 0);
 497       get_closure(clos_symbols, &(parent1->placements[i]), parent1, parent2);
 498       int x = randint(1, 2);
 499
 500       if (x == 1)
 501       {
 502         copy_symbols(clos_symbols, parent1, child1);
 503         copy_symbols(clos_symbols, parent2, child2);
 504       }
 505       else
 506       {
 507         copy_symbols(clos_symbols, parent2, child1);
 508         copy_symbols(clos_symbols, parent1, child2);
 509       }
 510       printf("%lld\n", GARY_SIZE(clos_symbols));
 511       GARY_FREE(clos_symbols);
 512     }
 513
 514     if (conf_mutate_children)
 515     {
 516       if (randint(1, 1000) < conf_mutate_children_prob * 1000) perform_mutation(child1);
 517       if (randint(1, 1000) < conf_mutate_children_prob * 1000) perform_mutation(child2);
 518     }
 519   }
 520
 521   buffer[0] = child1;
 522   buffer[1] = child2;
 523   return buffer;
 524 }
 525
 526 void mutate(void)
 527 {
 528   int i = 0;
 529   int conf_mutate_pop_size = conf_mutate_pop_size_perc * conf_pop_size;
 530   while (i < conf_mutate_rbest_perc * conf_pop_size)
 531   {
 532     int ind = randint(1, conf_mutate_pop_size);
 533     population2[pop2_ind] = population1[ind];
 534     perform_mutation(population2[pop2_ind]);
 535   }
 536 }
 537
 538 void perform_mutation(struct individual *individual)
 539 {
 540   for (uns i=0; i<GARY_SIZE(individual->placements); i++)
 541   {
 542     int x = randint(1, 1000);
 543     int acc = 0;
 544
 545     if (x <= acc + conf_mutate_move_bound)
 546     {
 547       move_symbol(&(individual->placements[i]));
 548       continue;
 549     }
 550     acc += conf_mutate_move_bound;
 551
 552     if (x <= acc + conf_mutate_regen_bound)
 553     {
 554       gen_coords(&(individual->placements[i]));
 555       continue;
 556     }
 557     acc += conf_mutate_regen_bound;
 558
 559     if (x <= acc + conf_mutate_chvar_bound)
 560     {
 561       if (0) // if num_variants > 1
 562       {
 563         // FIXME: assign new variant
 564       }
 565     }
 566   }
 567 }
 568
 569 void elite(void)
 570 {
 571   for (int i=0; i<conf_elite_perc * conf_pop_size; i++)
 572   {
 573     population2[pop2_ind] = population1[0];
 574   }
 575 }
 576
 577 void rank_population(void)
 578 {
 579   // FIXME
 580 }
 581
 582 void gen_coords(struct placement *p)
 583 {
 584   switch(p->request->type)
 585   {
 586     case REQUEST_POINT:
 587       gen_coords_point(p);
 588   }
 589 }
 590
 591 void gen_coords_point(struct placement *p UNUSED)
 592 {
 593   // FIXME
 594 }
 595
 596 struct map_part **get_parts(struct placement *symbol, struct individual *individual)
 597 {
 598   struct map_part **buffer;
 599   GARY_INIT(buffer, 0);
 600   int x_min = symbol->x / conf_part_size;
 601   int x_max = (symbol->x /*+ symbol->bitmap->width*/ + conf_part_size - 1) / conf_part_size;
 602   int y_min = symbol->y / conf_part_size;
 603   int y_max = (symbol->y /*+ symbol->bitmap->height*/ + conf_part_size - 1) / conf_part_size;
 604
 605   for (int x=x_min; x < x_max; x++)
 606     for (int y=y_min; y < y_max; y++)
 607     {
 608       struct map_part *m = GARY_PUSH(buffer);
 609       *m = individual->map[x][y];
 610     }
 611
 612   return buffer;
 613 }
 614
 615 int randint(int min, int max)
 616 {
 617   int r = random();
 618   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)));
 619   return min + (r % (max - min));
 620   return (r * (max - min));
 621 }
 622
 623 void get_closure(struct placement **closure UNUSED, struct placement *placement UNUSED, struct individual *parent1 UNUSED, struct individual *parent2 UNUSED)
 624 {
 625   printf("Getting closure\n");
 626   bool *chosen = malloc(GARY_SIZE(parent1->placements) * sizeof(bool));
 627   chosen[placement->request->ind] = 1;
 628
 629   struct placement **p = GARY_PUSH(closure); *p = placement;
 630
 631   uns first = 0;
 632   while (first < GARY_SIZE(closure))
 633   {
 634     printf("Iterating, first is %d\n", first);
 635     struct placement **overlapping = get_overlapping(placement);
 636     filter(overlapping, chosen);
 637     for (uns j=0; j<GARY_SIZE(overlapping); j++)
 638     {
 639       p = GARY_PUSH(closure); *p = overlapping[j];
 640       chosen[overlapping[j]->request->ind] = 1;
 641     }
 642     GARY_FREE(overlapping);
 643     first++;
 644   }
 645 }
 646
 647 void copy_symbols(struct placement **closure, struct individual *parent, struct individual *child)
 648 {
 649   printf("%.2f\n", child->penalty);
 650   for (uns i=0; i<GARY_SIZE(closure); i++)
 651   {
 652     int ind = closure[i]->request->ind;
 653     child->placements[ind] = parent->placements[ind];
 654   }
 655 }
 656
 657 void move_symbol(struct placement *p)
 658 {
 659   switch (p->request->type)
 660   {
 661     case REQUEST_POINT:
 662       move_symbol_point(p);
 663   }
 664 }
 665
 666 void move_symbol_point(struct placement *p)
 667 {
 668   p->x += (double) (move_min + randdouble()) * flip(1, -1);
 669   p->y += (double) (move_min + randdouble()) * flip(1, -1);
 670 }
 671
 672 void init_placement(struct placement *p, struct request *r)
 673 {
 674   // FIXME
 675   p->request = r;
 676   p->processed = 0;
 677 }
 678
 679 struct placement **get_overlapping(struct placement *p UNUSED)
 680 {
 681   struct placement **buffer;
 682   GARY_INIT(buffer, 0);
 683 return buffer; }
 684
 685 void filter(struct placement **list UNUSED, bool *pred UNUSED)
 686 {
 687   // FIXME
 688 }
 689
 690 int flip(int a, int b)
 691 {
 692   return (random() % 2 ? a : b);
 693 }
 694
 695 double randdouble(void)
 696 {
 697   // FIXME: How the hell shall double in range <0, 1> be generated? O:)
 698   return 0.5;
 699 }