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