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