nsz Git - libfirm/blob - heuristical.c

   1 #include "adt/array.h"
   2 #include "assert.h"
   3 #include "error.h"
   4
   5 #include "bucket.h"
   6 #include "heuristical.h"
   7 #include "html_dumper.h"
   8 #include "kaps.h"
   9 #include "matrix.h"
  10 #include "pbqp_edge.h"
  11 #include "pbqp_edge_t.h"
  12 #include "pbqp_node.h"
  13 #include "pbqp_node_t.h"
  14 #include "vector.h"
  15
  16 static pbqp_edge **edge_bucket;
  17 static pbqp_node **node_buckets[4];
  18 static pbqp_node **reduced_bucket = NULL;
  19 static int         buckets_filled = 0;
  20
  21 static void insert_into_edge_bucket(pbqp_edge *edge)
  22 {
  23         if (edge_bucket_contains(edge_bucket, edge)) {
  24                 /* Edge is already inserted. */
  25                 return;
  26         }
  27
  28         edge_bucket_insert(&edge_bucket, edge);
  29 }
  30
  31 static void init_buckets(void)
  32 {
  33         int i;
  34
  35         edge_bucket_init(&edge_bucket);
  36         node_bucket_init(&reduced_bucket);
  37
  38         for (i = 0; i < 4; ++i) {
  39                 node_bucket_init(&node_buckets[i]);
  40         }
  41 }
  42
  43 static void free_buckets(void)
  44 {
  45         int i;
  46
  47         for (i = 0; i < 4; ++i) {
  48                 node_bucket_free(&node_buckets[i]);
  49         }
  50
  51         edge_bucket_free(&edge_bucket);
  52         node_bucket_free(&reduced_bucket);
  53
  54         buckets_filled = 0;
  55 }
  56
  57 static void fill_node_buckets(pbqp *pbqp)
  58 {
  59         unsigned node_index;
  60         unsigned node_len;
  61
  62         assert(pbqp);
  63         node_len = pbqp->num_nodes;
  64
  65         for (node_index = 0; node_index < node_len; ++node_index) {
  66                 unsigned   arity;
  67                 pbqp_node *node = get_node(pbqp, node_index);
  68
  69                 if (!node) continue;
  70
  71                 arity = ARR_LEN(node->edges);
  72
  73                 /* We have only one bucket for nodes with arity >= 3. */
  74                 if (arity > 3) {
  75                         arity = 3;
  76                 }
  77
  78                 node_bucket_insert(&node_buckets[arity], node);
  79         }
  80
  81         buckets_filled = 1;
  82 }
  83
  84 static void normalize_towards_source(pbqp *pbqp, pbqp_edge *edge)
  85 {
  86         pbqp_matrix    *mat;
  87         pbqp_node      *src_node;
  88         pbqp_node      *tgt_node;
  89         vector         *src_vec;
  90         vector         *tgt_vec;
  91         int             src_len;
  92         int             tgt_len;
  93         int             src_index;
  94
  95         assert(pbqp);
  96         assert(edge);
  97
  98         src_node = edge->src;
  99         tgt_node = edge->tgt;
 100         assert(src_node);
 101         assert(tgt_node);
 102
 103         src_vec = src_node->costs;
 104         tgt_vec = tgt_node->costs;
 105         assert(src_vec);
 106         assert(tgt_vec);
 107
 108         src_len = src_vec->len;
 109         tgt_len = tgt_vec->len;
 110         assert(src_len > 0);
 111         assert(tgt_len > 0);
 112
 113         mat = edge->costs;
 114         assert(mat);
 115
 116         /* Normalize towards source node. */
 117         for (src_index = 0; src_index < src_len; ++src_index) {
 118                 num min = pbqp_matrix_get_row_min(mat, src_index, tgt_vec);
 119
 120                 if (min != 0) {
 121                         if (src_vec->entries[src_index].data == INF_COSTS) {
 122                                 pbqp_matrix_set_row_value(mat, src_index, 0);
 123                         } else {
 124                                 pbqp_matrix_sub_row_value(mat, src_index, tgt_vec, min);
 125                         }
 126                         src_vec->entries[src_index].data = pbqp_add(
 127                                         src_vec->entries[src_index].data, min);
 128
 129                         if (min == INF_COSTS) {
 130                                 unsigned edge_index;
 131                                 unsigned edge_len = ARR_LEN(src_node->edges);
 132
 133                                 for (edge_index = 0; edge_index < edge_len; ++edge_index) {
 134                                         pbqp_edge *edge_candidate = src_node->edges[edge_index];
 135                                         if (edge_candidate != edge) {
 136                                                 insert_into_edge_bucket(edge_candidate);
 137                                         }
 138                                 }
 139                         }
 140                 }
 141         }
 142 }
 143
 144 static void normalize_towards_target(pbqp *pbqp, pbqp_edge *edge)
 145 {
 146         pbqp_matrix    *mat;
 147         pbqp_node      *src_node;
 148         pbqp_node      *tgt_node;
 149         vector         *src_vec;
 150         vector         *tgt_vec;
 151         int             src_len;
 152         int             tgt_len;
 153         int             tgt_index;
 154
 155         assert(pbqp);
 156         assert(edge);
 157
 158         src_node = edge->src;
 159         tgt_node = edge->tgt;
 160         assert(src_node);
 161         assert(tgt_node);
 162
 163         src_vec = src_node->costs;
 164         tgt_vec = tgt_node->costs;
 165         assert(src_vec);
 166         assert(tgt_vec);
 167
 168         src_len = src_vec->len;
 169         tgt_len = tgt_vec->len;
 170         assert(src_len > 0);
 171         assert(tgt_len > 0);
 172
 173         mat = edge->costs;
 174         assert(mat);
 175
 176         for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
 177                 num min = pbqp_matrix_get_col_min(mat, tgt_index, src_vec);
 178
 179                 if (min != 0) {
 180                         if (tgt_vec->entries[tgt_index].data == INF_COSTS) {
 181                                 pbqp_matrix_set_col_value(mat, tgt_index, 0);
 182                         } else {
 183                                 pbqp_matrix_sub_col_value(mat, tgt_index, src_vec, min);
 184                         }
 185                         tgt_vec->entries[tgt_index].data = pbqp_add(
 186                                         tgt_vec->entries[tgt_index].data, min);
 187
 188                         if (min == INF_COSTS) {
 189                                 unsigned edge_index;
 190                                 unsigned edge_len = ARR_LEN(tgt_node->edges);
 191
 192                                 for (edge_index = 0; edge_index < edge_len; ++edge_index) {
 193                                         pbqp_edge *edge_candidate = tgt_node->edges[edge_index];
 194                                         if (edge_candidate != edge) {
 195                                                 insert_into_edge_bucket(edge_candidate);
 196                                         }
 197                                 }
 198                         }
 199                 }
 200         }
 201 }
 202
 203 static void reorder_node(pbqp_node *node)
 204 {
 205         unsigned    arity;
 206         unsigned    old_arity;
 207         unsigned    old_bucket_len;
 208         unsigned    old_bucket_index;
 209         pbqp_node **old_bucket;
 210         pbqp_node  *other;
 211
 212         if (!buckets_filled) return;
 213
 214         assert(node);
 215
 216         arity = ARR_LEN(node->edges);
 217
 218         /* Same bucket as before */
 219         if (arity > 2) return;
 220
 221         /* Assume node lost one incident edge. */
 222         old_arity        = arity + 1;
 223         old_bucket       = node_buckets[old_arity];
 224         old_bucket_len   = node_bucket_get_length(old_bucket);
 225         old_bucket_index = node->bucket_index;
 226
 227         if (old_bucket_len <= old_bucket_index || old_bucket[old_bucket_index]
 228                         != node) {
 229                 unsigned bucket_len = node_bucket_get_length(node_buckets[arity]);
 230
 231                 /* Old arity is new arity, so we have nothing to do. */
 232                 assert(old_bucket_index < bucket_len);
 233                 assert(node_buckets[arity][old_bucket_index] == node);
 234                 return;
 235         }
 236
 237         assert(old_bucket[old_bucket_index] == node);
 238
 239         /* Delete node from old bucket... */
 240         other                        = old_bucket[old_bucket_len - 1];
 241         other->bucket_index          = old_bucket_index;
 242         old_bucket[old_bucket_index] = other;
 243         ARR_SHRINKLEN(node_buckets[old_arity], old_bucket_len - 1);
 244
 245         /* ..and add to new one. */
 246         node->bucket_index = node_bucket_get_length(node_buckets[arity]);
 247         ARR_APP1(pbqp_node*, node_buckets[arity], node);
 248 }
 249
 250 static void check_melting_possibility(pbqp *pbqp, pbqp_edge *edge)
 251 {
 252         pbqp_matrix    *mat;
 253         pbqp_node      *src_node;
 254         pbqp_node      *tgt_node;
 255         vector         *src_vec;
 256         vector         *tgt_vec;
 257         int             src_len;
 258         int             tgt_len;
 259         int             src_index;
 260         int             tgt_index;
 261
 262         assert(pbqp);
 263         assert(edge);
 264
 265         src_node = edge->src;
 266         tgt_node = edge->tgt;
 267         assert(src_node);
 268         assert(tgt_node);
 269
 270         src_vec = src_node->costs;
 271         tgt_vec = tgt_node->costs;
 272         assert(src_vec);
 273         assert(tgt_vec);
 274
 275         src_len = src_vec->len;
 276         tgt_len = tgt_vec->len;
 277         assert(src_len > 0);
 278         assert(tgt_len > 0);
 279
 280         mat = edge->costs;
 281         assert(mat);
 282
 283         if (src_len == 1 && tgt_len == 1) {
 284                 //panic("Something is wrong");
 285         }
 286
 287         int allRowsOk = 1;
 288         for (src_index = 0; src_index < src_len; ++src_index) {
 289                 int onlyOneZero = 0;
 290                 if (src_vec->entries[src_index].data == INF_COSTS) {
 291                         continue;
 292                 }
 293                 for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
 294                         if (tgt_vec->entries[tgt_index].data == INF_COSTS) {
 295                                 continue;
 296                         }
 297                         if (mat->entries[src_index * tgt_len + tgt_index] == 0) {
 298                                 if (onlyOneZero) {
 299                                         onlyOneZero = 0;
 300                                         break;
 301                                 } else {
 302                                         onlyOneZero = 1;
 303                                         continue;
 304                                 }
 305                         }
 306                         if (mat->entries[src_index * tgt_len + tgt_index] == INF_COSTS) {
 307                                 continue;
 308                         }
 309                         onlyOneZero = 0;
 310                         break;
 311                 }
 312                 allRowsOk &= onlyOneZero;
 313         }
 314
 315         int allColsOk = 1;
 316         for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
 317                 int onlyOneZero = 0;
 318                 if (tgt_vec->entries[tgt_index].data == INF_COSTS) {
 319                         continue;
 320                 }
 321                 for (src_index = 0; src_index < src_len; ++src_index) {
 322                         if (src_vec->entries[src_index].data == INF_COSTS) {
 323                                 continue;
 324                         }
 325                         if (mat->entries[src_index * tgt_len + tgt_index] == 0) {
 326                                 if (onlyOneZero) {
 327                                         onlyOneZero = 0;
 328                                         break;
 329                                 } else {
 330                                         onlyOneZero = 1;
 331                                         continue;
 332                                 }
 333                         }
 334                         if (mat->entries[src_index * tgt_len + tgt_index] == INF_COSTS) {
 335                                 continue;
 336                         }
 337                         onlyOneZero = 0;
 338                         break;
 339                 }
 340                 allColsOk &= onlyOneZero;
 341         }
 342
 343         if (allRowsOk && allColsOk) {
 344                 panic("Hurray");
 345         }
 346 }
 347
 348 static void simplify_edge(pbqp *pbqp, pbqp_edge *edge)
 349 {
 350         pbqp_matrix    *mat;
 351         pbqp_node      *src_node;
 352         pbqp_node      *tgt_node;
 353         vector         *src_vec;
 354         vector         *tgt_vec;
 355         int             src_len;
 356         int             tgt_len;
 357
 358         assert(pbqp);
 359         assert(edge);
 360
 361         src_node = edge->src;
 362         tgt_node = edge->tgt;
 363         assert(src_node);
 364         assert(tgt_node);
 365
 366         /* If edge are already deleted, we have nothing to do. */
 367         if (!is_connected(src_node, edge) || !is_connected(tgt_node, edge))
 368                 return;
 369
 370         if (pbqp->dump_file) {
 371                 char txt[100];
 372                 sprintf(txt, "Simplification of Edge n%d-n%d", src_node->index, tgt_node->index);
 373                 dump_section(pbqp->dump_file, 3, txt);
 374         }
 375
 376         src_vec = src_node->costs;
 377         tgt_vec = tgt_node->costs;
 378         assert(src_vec);
 379         assert(tgt_vec);
 380
 381         src_len = src_vec->len;
 382         tgt_len = tgt_vec->len;
 383         assert(src_len > 0);
 384         assert(tgt_len > 0);
 385
 386         mat = edge->costs;
 387         assert(mat);
 388
 389         if (pbqp->dump_file) {
 390                 fputs("Input:<br>\n", pbqp->dump_file);
 391                 dump_simplifyedge(pbqp, edge);
 392         }
 393
 394         normalize_towards_source(pbqp, edge);
 395         normalize_towards_target(pbqp, edge);
 396
 397         if (pbqp->dump_file) {
 398                 fputs("<br>\nOutput:<br>\n", pbqp->dump_file);
 399                 dump_simplifyedge(pbqp, edge);
 400         }
 401
 402         if (pbqp_matrix_is_zero(mat, src_vec, tgt_vec)) {
 403                 if (pbqp->dump_file) {
 404                         fputs("edge has been eliminated<br>\n", pbqp->dump_file);
 405                 }
 406
 407                 delete_edge(edge);
 408                 reorder_node(src_node);
 409                 reorder_node(tgt_node);
 410         } else {
 411                 //check_melting_possibility(pbqp, edge);
 412         }
 413 }
 414
 415 void solve_pbqp_heuristical(pbqp *pbqp)
 416 {
 417         unsigned node_index;
 418         unsigned node_len;
 419
 420         assert(pbqp);
 421
 422         if (pbqp->dump_file) {
 423                 pbqp_dump_input(pbqp);
 424                 dump_section(pbqp->dump_file, 1, "2. Simplification of Cost Matrices");
 425         }
 426
 427         node_len = pbqp->num_nodes;
 428
 429         init_buckets();
 430
 431         /* First simplify all edges. */
 432         for (node_index = 0; node_index < node_len; ++node_index) {
 433                 unsigned    edge_index;
 434                 pbqp_node  *node = get_node(pbqp, node_index);
 435                 pbqp_edge **edges;
 436                 unsigned    edge_len;
 437
 438                 if (!node) continue;
 439
 440                 edges = node->edges;
 441                 edge_len = ARR_LEN(edges);
 442
 443                 for (edge_index = 0; edge_index < edge_len; ++edge_index) {
 444                         pbqp_edge *edge = edges[edge_index];
 445
 446                         /* Simplify only once per edge. */
 447                         if (node != edge->src) continue;
 448
 449                         simplify_edge(pbqp, edge);
 450                 }
 451         }
 452
 453         /* Put node into bucket representing their arity. */
 454         fill_node_buckets(pbqp);
 455
 456         for (;;) {
 457                 if (edge_bucket_get_length(edge_bucket) > 0) {
 458                         apply_edge(pbqp);
 459                 } else if (node_bucket_get_length(node_buckets[1]) > 0) {
 460                         apply_RI(pbqp);
 461                 } else if (node_bucket_get_length(node_buckets[2]) > 0) {
 462                         apply_RII(pbqp);
 463                 } else if (node_bucket_get_length(node_buckets[3]) > 0) {
 464                         apply_RN(pbqp);
 465                 } else {
 466                         break;
 467                 }
 468         }
 469
 470         if (pbqp->dump_file) {
 471                 dump_section(pbqp->dump_file, 1, "4. Determine Solution/Minimum");
 472                 dump_section(pbqp->dump_file, 2, "4.1. Trivial Solution");
 473         }
 474
 475         /* Solve trivial nodes and calculate solution. */
 476         node_len = node_bucket_get_length(node_buckets[0]);
 477         for (node_index = 0; node_index < node_len; ++node_index) {
 478                 pbqp_node *node = node_buckets[0][node_index];
 479                 assert(node);
 480
 481                 node->solution = vector_get_min_index(node->costs);
 482                 pbqp->solution = pbqp_add(pbqp->solution,
 483                                 node->costs->entries[node->solution].data);
 484                 if (pbqp->dump_file) {
 485                         fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
 486                         dump_node(pbqp, node);
 487                 }
 488         }
 489
 490         if (pbqp->dump_file) {
 491                 dump_section(pbqp->dump_file, 2, "Minimum");
 492                 fprintf(pbqp->dump_file, "Minimum is equal to %lld.", pbqp->solution);
 493                 dump_section(pbqp->dump_file, 2, "Back Propagation");
 494         }
 495
 496         /* Solve reduced nodes. */
 497         node_len = node_bucket_get_length(reduced_bucket);
 498         for (node_index = node_len; node_index > 0; --node_index) {
 499                 pbqp_node *node = reduced_bucket[node_index - 1];
 500                 assert(node);
 501
 502                 switch (ARR_LEN(node->edges)) {
 503                         case 1:
 504                                 back_propagate_RI(pbqp, node);
 505                                 break;
 506                         case 2:
 507                                 back_propagate_RII(pbqp, node);
 508                                 break;
 509                         default:
 510                                 panic("Only nodes with degree one or two should be in this bucket");
 511                                 break;
 512                 }
 513         }
 514
 515         free_buckets();
 516 }
 517
 518 void apply_edge(pbqp *pbqp)
 519 {
 520         pbqp_edge *edge = edge_bucket_pop(&edge_bucket);
 521
 522         simplify_edge(pbqp, edge);
 523 }
 524
 525 void apply_RI(pbqp *pbqp)
 526 {
 527         pbqp_node   *node       = node_bucket_pop(&node_buckets[1]);
 528         pbqp_edge   *edge       = node->edges[0];
 529         pbqp_matrix *mat        = edge->costs;
 530         int          is_src     = edge->src == node;
 531         pbqp_node   *other_node;
 532
 533         if (is_src) {
 534                 other_node = edge->tgt;
 535         } else {
 536                 other_node = edge->src;
 537         }
 538
 539         if (pbqp->dump_file) {
 540                 char     txt[100];
 541                 sprintf(txt, "RI-Reduction of Node n%d", node->index);
 542                 dump_section(pbqp->dump_file, 2, txt);
 543                 pbqp_dump_graph(pbqp);
 544                 fputs("<br>\nBefore reduction:<br>\n", pbqp->dump_file);
 545                 dump_node(pbqp, node);
 546                 dump_node(pbqp, other_node);
 547                 dump_edge(pbqp, edge);
 548         }
 549
 550         if (is_src) {
 551                 pbqp_matrix_add_to_all_cols(mat, node->costs);
 552                 normalize_towards_target(pbqp, edge);
 553         } else {
 554                 pbqp_matrix_add_to_all_rows(mat, node->costs);
 555                 normalize_towards_source(pbqp, edge);
 556         }
 557         disconnect_edge(other_node, edge);
 558
 559         if (pbqp->dump_file) {
 560                 fputs("<br>\nAfter reduction:<br>\n", pbqp->dump_file);
 561                 dump_node(pbqp, other_node);
 562         }
 563
 564         reorder_node(other_node);
 565
 566         /* Add node to back propagation list. */
 567         node_bucket_insert(&reduced_bucket, node);
 568 }
 569
 570 void apply_RII(pbqp *pbqp)
 571 {
 572         pbqp_node   *node       = node_bucket_pop(&node_buckets[2]);
 573         pbqp_edge   *src_edge   = node->edges[0];
 574         pbqp_edge   *tgt_edge   = node->edges[1];
 575         int          src_is_src = src_edge->src == node;
 576         int          tgt_is_src = tgt_edge->src == node;
 577         pbqp_matrix *src_mat;
 578         pbqp_matrix *tgt_mat;
 579         pbqp_node   *src_node;
 580         pbqp_node   *tgt_node;
 581         pbqp_matrix *mat;
 582         vector      *vec;
 583         vector      *node_vec;
 584         vector      *src_vec;
 585         vector      *tgt_vec;
 586         unsigned     col_index;
 587         unsigned     col_len;
 588         unsigned     row_index;
 589         unsigned     row_len;
 590         unsigned     node_len;
 591
 592         assert(pbqp);
 593
 594         if (src_is_src) {
 595                 src_node = src_edge->tgt;
 596         } else {
 597                 src_node = src_edge->src;
 598         }
 599
 600         if (tgt_is_src) {
 601                 tgt_node = tgt_edge->tgt;
 602         } else {
 603                 tgt_node = tgt_edge->src;
 604         }
 605
 606         /* Swap nodes if necessary. */
 607         if (tgt_node->index < src_node->index) {
 608                 pbqp_node *tmp_node;
 609                 pbqp_edge *tmp_edge;
 610
 611                 tmp_node = src_node;
 612                 src_node = tgt_node;
 613                 tgt_node = tmp_node;
 614
 615                 tmp_edge = src_edge;
 616                 src_edge = tgt_edge;
 617                 tgt_edge = tmp_edge;
 618
 619                 src_is_src = src_edge->src == node;
 620                 tgt_is_src = tgt_edge->src == node;
 621         }
 622
 623         if (pbqp->dump_file) {
 624                 char     txt[100];
 625                 sprintf(txt, "RII-Reduction of Node n%d", node->index);
 626                 dump_section(pbqp->dump_file, 2, txt);
 627                 pbqp_dump_graph(pbqp);
 628                 fputs("<br>\nBefore reduction:<br>\n", pbqp->dump_file);
 629                 dump_node(pbqp, src_node);
 630                 dump_edge(pbqp, src_edge);
 631                 dump_node(pbqp, node);
 632                 dump_edge(pbqp, tgt_edge);
 633                 dump_node(pbqp, tgt_node);
 634         }
 635
 636         src_mat = src_edge->costs;
 637         tgt_mat = tgt_edge->costs;
 638
 639         src_vec  = src_node->costs;
 640         tgt_vec  = tgt_node->costs;
 641         node_vec = node->costs;
 642
 643         row_len  = src_vec->len;
 644         col_len  = tgt_vec->len;
 645         node_len = node_vec->len;
 646
 647         mat = pbqp_matrix_alloc(pbqp, row_len, col_len);
 648
 649         for (row_index = 0; row_index < row_len; ++row_index) {
 650                 for (col_index = 0; col_index < col_len; ++col_index) {
 651                         vec = vector_copy(pbqp, node_vec);
 652
 653                         if (src_is_src) {
 654                                 vector_add_matrix_col(vec, src_mat, row_index);
 655                         } else {
 656                                 vector_add_matrix_row(vec, src_mat, row_index);
 657                         }
 658
 659                         if (tgt_is_src) {
 660                                 vector_add_matrix_col(vec, tgt_mat, col_index);
 661                         } else {
 662                                 vector_add_matrix_row(vec, tgt_mat, col_index);
 663                         }
 664
 665                         mat->entries[row_index * col_len + col_index] = vector_get_min(vec);
 666
 667                         obstack_free(&pbqp->obstack, vec);
 668                 }
 669         }
 670
 671         pbqp_edge *edge = get_edge(pbqp, src_node->index, tgt_node->index);
 672
 673         /* Disconnect node. */
 674         disconnect_edge(src_node, src_edge);
 675         disconnect_edge(tgt_node, tgt_edge);
 676
 677         /* Add node to back propagation list. */
 678         node_bucket_insert(&reduced_bucket, node);
 679
 680         if (edge == NULL) {
 681                 edge = alloc_edge(pbqp, src_node->index, tgt_node->index, mat);
 682         } else {
 683                 pbqp_matrix_add(edge->costs, mat);
 684
 685                 /* Free local matrix. */
 686                 obstack_free(&pbqp->obstack, mat);
 687
 688                 reorder_node(src_node);
 689                 reorder_node(tgt_node);
 690         }
 691
 692         if (pbqp->dump_file) {
 693                 fputs("<br>\nAfter reduction:<br>\n", pbqp->dump_file);
 694                 dump_edge(pbqp, edge);
 695         }
 696
 697         /* Edge has changed so we simplify it. */
 698         simplify_edge(pbqp, edge);
 699 }
 700
 701 void apply_RN(pbqp *pbqp)
 702 {
 703         pbqp_node  **bucket       = node_buckets[3];
 704         unsigned     bucket_len   = node_bucket_get_length(bucket);
 705         unsigned     bucket_index;
 706         pbqp_node   *node         = NULL;
 707         pbqp_edge   *edge;
 708         vector      *node_vec;
 709         vector      *vec;
 710         pbqp_matrix *mat;
 711         unsigned     edge_index;
 712         unsigned     max_degree   = 0;
 713         unsigned     node_index;
 714         unsigned     node_len;
 715         unsigned     min_index    = 0;
 716         num          min          = INF_COSTS;
 717         int          is_src;
 718
 719         assert(pbqp);
 720
 721         /* Search for node with maximum degree. */
 722         for (bucket_index = 0; bucket_index < bucket_len; ++bucket_index) {
 723                 pbqp_node *candidate = bucket[bucket_index];
 724                 unsigned   degree    = ARR_LEN(candidate->edges);
 725
 726                 if (degree > max_degree) {
 727                         node = candidate;
 728                         max_degree = degree;
 729                 }
 730         }
 731         assert(node);
 732         node_vec = node->costs;
 733         node_len = node_vec->len;
 734
 735         if (pbqp->dump_file) {
 736                 char     txt[100];
 737                 sprintf(txt, "RN-Reduction of Node n%d", node->index);
 738                 dump_section(pbqp->dump_file, 2, txt);
 739                 pbqp_dump_graph(pbqp);
 740         }
 741
 742         for (node_index = 0; node_index < node_len; ++node_index) {
 743                 num value = node_vec->entries[node_index].data;
 744
 745                 for (edge_index = 0; edge_index < max_degree; ++edge_index) {
 746                         edge   = node->edges[edge_index];
 747                         mat    = edge->costs;
 748                         is_src = edge->src == node;
 749
 750                         if (is_src) {
 751                                 vec = vector_copy(pbqp, edge->tgt->costs);
 752                                 vector_add_matrix_row(vec, mat, node_index);
 753                         } else {
 754                                 vec = vector_copy(pbqp, edge->src->costs);
 755                                 vector_add_matrix_col(vec, mat, node_index);
 756                         }
 757
 758                         value = pbqp_add(value, vector_get_min(vec));
 759
 760                         obstack_free(&pbqp->obstack, vec);
 761                 }
 762
 763                 if (value < min) {
 764                         min = value;
 765                         min_index = node_index;
 766                 }
 767         }
 768
 769         if (pbqp->dump_file) {
 770                 fprintf(pbqp->dump_file, "node n%d is set to %d<br><br>\n",
 771                                         node->index, min_index);
 772                 fprintf(pbqp->dump_file, "Minimal cost of RN reduction: %lld<br>\n",
 773                                                         min);
 774         }
 775
 776         node->solution = min_index;
 777
 778         /* Now that we found the local minimum set all other costs to infinity. */
 779         for (node_index = 0; node_index < node_len; ++node_index) {
 780                 if (node_index != min_index) {
 781                         node_vec->entries[node_index].data = INF_COSTS;
 782                 }
 783         }
 784
 785         /* Add all incident edges to edge bucket, since they are now independent. */
 786         for (edge_index = 0; edge_index < max_degree; ++edge_index) {
 787                 insert_into_edge_bucket(node->edges[edge_index]);
 788         }
 789 }
 790
 791 void back_propagate_RI(pbqp *pbqp, pbqp_node *node)
 792 {
 793         pbqp_edge   *edge;
 794         pbqp_node   *other;
 795         pbqp_matrix *mat;
 796         vector      *vec;
 797         int          is_src;
 798
 799         assert(pbqp);
 800         assert(node);
 801
 802         edge = node->edges[0];
 803         mat = edge->costs;
 804         is_src = edge->src == node;
 805         vec = node->costs;
 806
 807         if (is_src) {
 808                 other = edge->tgt;
 809                 assert(other);
 810                 vector_add_matrix_col(vec, mat, other->solution);
 811         } else {
 812                 other = edge->src;
 813                 assert(other);
 814                 vector_add_matrix_row(vec, mat, other->solution);
 815         }
 816
 817         node->solution = vector_get_min_index(vec);
 818         if (pbqp->dump_file) {
 819                 fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
 820         }
 821 }
 822
 823 void back_propagate_RII(pbqp *pbqp, pbqp_node *node)
 824 {
 825         pbqp_edge   *src_edge   = node->edges[0];
 826         pbqp_edge   *tgt_edge   = node->edges[1];
 827         int          src_is_src = src_edge->src == node;
 828         int          tgt_is_src = tgt_edge->src == node;
 829         pbqp_matrix *src_mat;
 830         pbqp_matrix *tgt_mat;
 831         pbqp_node   *src_node;
 832         pbqp_node   *tgt_node;
 833         vector      *vec;
 834         vector      *node_vec;
 835         unsigned     col_index;
 836         unsigned     row_index;
 837
 838         assert(pbqp);
 839
 840         if (src_is_src) {
 841                 src_node = src_edge->tgt;
 842         } else {
 843                 src_node = src_edge->src;
 844         }
 845
 846         if (tgt_is_src) {
 847                 tgt_node = tgt_edge->tgt;
 848         } else {
 849                 tgt_node = tgt_edge->src;
 850         }
 851
 852         /* Swap nodes if necessary. */
 853         if (tgt_node->index < src_node->index) {
 854                 pbqp_node *tmp_node;
 855                 pbqp_edge *tmp_edge;
 856
 857                 tmp_node = src_node;
 858                 src_node = tgt_node;
 859                 tgt_node = tmp_node;
 860
 861                 tmp_edge = src_edge;
 862                 src_edge = tgt_edge;
 863                 tgt_edge = tmp_edge;
 864
 865                 src_is_src = src_edge->src == node;
 866                 tgt_is_src = tgt_edge->src == node;
 867         }
 868
 869         src_mat = src_edge->costs;
 870         tgt_mat = tgt_edge->costs;
 871
 872         node_vec = node->costs;
 873
 874         row_index = src_node->solution;
 875         col_index = tgt_node->solution;
 876
 877         vec = vector_copy(pbqp, node_vec);
 878
 879         if (src_is_src) {
 880                 vector_add_matrix_col(vec, src_mat, row_index);
 881         } else {
 882                 vector_add_matrix_row(vec, src_mat, row_index);
 883         }
 884
 885         if (tgt_is_src) {
 886                 vector_add_matrix_col(vec, tgt_mat, col_index);
 887         } else {
 888                 vector_add_matrix_row(vec, tgt_mat, col_index);
 889         }
 890
 891         node->solution = vector_get_min_index(vec);
 892         if (pbqp->dump_file) {
 893                 fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
 894         }
 895
 896         obstack_free(&pbqp->obstack, vec);
 897 }
 898
 899 int node_is_reduced(pbqp_node *node)
 900 {
 901         if (!reduced_bucket) return 0;
 902
 903         assert(node);
 904         if (ARR_LEN(node->edges) == 0) return 1;
 905
 906         return node_bucket_contains(reduced_bucket, node);
 907 }