nsz Git - libfirm/blob - heuristical.c

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