nsz Git - libfirm/blob - heuristical.c

   1 /*
   2  * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief   Heuristic PBQP solver.
  23  * @date    02.10.2008
  24  * @author  Sebastian Buchwald
  25  * @version $Id$
  26  */
  27 #include "config.h"
  28
  29 #include "adt/array.h"
  30 #include "assert.h"
  31 #include "error.h"
  32
  33 #include "bucket.h"
  34 #include "heuristical.h"
  35 #if     KAPS_DUMP
  36 #include "html_dumper.h"
  37 #endif
  38 #include "kaps.h"
  39 #include "matrix.h"
  40 #include "pbqp_edge.h"
  41 #include "pbqp_edge_t.h"
  42 #include "pbqp_node.h"
  43 #include "pbqp_node_t.h"
  44 #include "vector.h"
  45
  46 #include "plist.h"
  47 #include "timing.h"
  48
  49 static pbqp_edge **edge_bucket;
  50 static pbqp_node **node_buckets[4];
  51 static pbqp_node **reduced_bucket = NULL;
  52 static int         buckets_filled = 0;
  53
  54 #if KAPS_STATISTIC
  55 static int dump = 0;
  56 #endif
  57
  58 /* Forward declarations. */
  59 static void apply_Brute_Force(pbqp *pbqp);
  60
  61 static void insert_into_edge_bucket(pbqp_edge *edge)
  62 {
  63         if (edge_bucket_contains(edge_bucket, edge)) {
  64                 /* Edge is already inserted. */
  65                 return;
  66         }
  67
  68         edge_bucket_insert(&edge_bucket, edge);
  69 }
  70
  71 static void init_buckets(void)
  72 {
  73         int i;
  74
  75         edge_bucket_init(&edge_bucket);
  76         node_bucket_init(&reduced_bucket);
  77
  78         for (i = 0; i < 4; ++i) {
  79                 node_bucket_init(&node_buckets[i]);
  80         }
  81 }
  82
  83 static void free_buckets(void)
  84 {
  85         int i;
  86
  87         for (i = 0; i < 4; ++i) {
  88                 node_bucket_free(&node_buckets[i]);
  89         }
  90
  91         edge_bucket_free(&edge_bucket);
  92         node_bucket_free(&reduced_bucket);
  93
  94         buckets_filled = 0;
  95 }
  96
  97 static void fill_node_buckets(pbqp *pbqp)
  98 {
  99         unsigned node_index;
 100         unsigned node_len;
 101
 102         assert(pbqp);
 103         node_len = pbqp->num_nodes;
 104
 105         #if KAPS_TIMING
 106                 ir_timer_t *t_fill_buckets = ir_timer_register("be_pbqp_fill_buckets", "PBQP Fill Nodes into buckets");
 107                 ir_timer_reset_and_start(t_fill_buckets);
 108         #endif
 109
 110         for (node_index = 0; node_index < node_len; ++node_index) {
 111                 unsigned   degree;
 112                 pbqp_node *node = get_node(pbqp, node_index);
 113
 114                 if (!node) continue;
 115
 116                 degree = pbqp_node_get_degree(node);
 117
 118                 /* We have only one bucket for nodes with arity >= 3. */
 119                 if (degree > 3) {
 120                         degree = 3;
 121                 }
 122
 123                 node_bucket_insert(&node_buckets[degree], node);
 124         }
 125
 126         buckets_filled = 1;
 127
 128         #if KAPS_TIMING
 129                 ir_timer_stop(t_fill_buckets);
 130                 printf("%-20s: %8.3lf msec\n", ir_timer_get_description(t_fill_buckets), (double)ir_timer_elapsed_usec(t_fill_buckets) / 1000.0);
 131         #endif
 132 }
 133
 134 static void normalize_towards_source(pbqp *pbqp, pbqp_edge *edge)
 135 {
 136         pbqp_matrix    *mat;
 137         pbqp_node      *src_node;
 138         pbqp_node      *tgt_node;
 139         vector         *src_vec;
 140         vector         *tgt_vec;
 141         int             src_len;
 142         int             tgt_len;
 143         int             src_index;
 144
 145         assert(pbqp);
 146         assert(edge);
 147
 148         src_node = edge->src;
 149         tgt_node = edge->tgt;
 150         assert(src_node);
 151         assert(tgt_node);
 152
 153         src_vec = src_node->costs;
 154         tgt_vec = tgt_node->costs;
 155         assert(src_vec);
 156         assert(tgt_vec);
 157
 158         src_len = src_vec->len;
 159         tgt_len = tgt_vec->len;
 160         assert(src_len > 0);
 161         assert(tgt_len > 0);
 162
 163         mat = edge->costs;
 164         assert(mat);
 165
 166         /* Normalize towards source node. */
 167         for (src_index = 0; src_index < src_len; ++src_index) {
 168                 num min = pbqp_matrix_get_row_min(mat, src_index, tgt_vec);
 169
 170                 if (min != 0) {
 171                         if (src_vec->entries[src_index].data == INF_COSTS) {
 172                                 pbqp_matrix_set_row_value(mat, src_index, 0);
 173                         } else {
 174                                 pbqp_matrix_sub_row_value(mat, src_index, tgt_vec, min);
 175                         }
 176                         src_vec->entries[src_index].data = pbqp_add(
 177                                         src_vec->entries[src_index].data, min);
 178
 179                         if (min == INF_COSTS) {
 180                                 unsigned edge_index;
 181                                 unsigned edge_len = pbqp_node_get_degree(src_node);
 182
 183                                 for (edge_index = 0; edge_index < edge_len; ++edge_index) {
 184                                         pbqp_edge *edge_candidate = src_node->edges[edge_index];
 185                                         if (edge_candidate != edge) {
 186                                                 insert_into_edge_bucket(edge_candidate);
 187                                         }
 188                                 }
 189                         }
 190                 }
 191         }
 192 }
 193
 194 static void normalize_towards_target(pbqp *pbqp, pbqp_edge *edge)
 195 {
 196         pbqp_matrix    *mat;
 197         pbqp_node      *src_node;
 198         pbqp_node      *tgt_node;
 199         vector         *src_vec;
 200         vector         *tgt_vec;
 201         int             src_len;
 202         int             tgt_len;
 203         int             tgt_index;
 204
 205         assert(pbqp);
 206         assert(edge);
 207
 208         src_node = edge->src;
 209         tgt_node = edge->tgt;
 210         assert(src_node);
 211         assert(tgt_node);
 212
 213         src_vec = src_node->costs;
 214         tgt_vec = tgt_node->costs;
 215         assert(src_vec);
 216         assert(tgt_vec);
 217
 218         src_len = src_vec->len;
 219         tgt_len = tgt_vec->len;
 220         assert(src_len > 0);
 221         assert(tgt_len > 0);
 222
 223         mat = edge->costs;
 224         assert(mat);
 225
 226         for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
 227                 num min = pbqp_matrix_get_col_min(mat, tgt_index, src_vec);
 228
 229                 if (min != 0) {
 230                         if (tgt_vec->entries[tgt_index].data == INF_COSTS) {
 231                                 pbqp_matrix_set_col_value(mat, tgt_index, 0);
 232                         } else {
 233                                 pbqp_matrix_sub_col_value(mat, tgt_index, src_vec, min);
 234                         }
 235                         tgt_vec->entries[tgt_index].data = pbqp_add(
 236                                         tgt_vec->entries[tgt_index].data, min);
 237
 238                         if (min == INF_COSTS) {
 239                                 unsigned edge_index;
 240                                 unsigned edge_len = pbqp_node_get_degree(tgt_node);
 241
 242                                 for (edge_index = 0; edge_index < edge_len; ++edge_index) {
 243                                         pbqp_edge *edge_candidate = tgt_node->edges[edge_index];
 244                                         if (edge_candidate != edge) {
 245                                                 insert_into_edge_bucket(edge_candidate);
 246                                         }
 247                                 }
 248                         }
 249                 }
 250         }
 251 }
 252
 253 static void reorder_node(pbqp_node *node)
 254 {
 255         unsigned    degree     = pbqp_node_get_degree(node);
 256         /* Assume node lost one incident edge. */
 257         unsigned    old_degree = degree + 1;
 258
 259         if (!buckets_filled) return;
 260
 261         /* Same bucket as before */
 262         if (degree > 2) return;
 263
 264         if (!node_bucket_contains(node_buckets[old_degree], node)) {
 265                 /* Old arity is new arity, so we have nothing to do. */
 266                 assert(node_bucket_contains(node_buckets[degree], node));
 267                 return;
 268         }
 269
 270         /* Delete node from old bucket... */
 271         node_bucket_remove(&node_buckets[old_degree], node);
 272
 273         /* ..and add to new one. */
 274         node_bucket_insert(&node_buckets[degree], node);
 275 }
 276
 277 #if 0
 278 static void check_melting_possibility(pbqp *pbqp, pbqp_edge *edge)
 279 {
 280         pbqp_matrix    *mat;
 281         pbqp_node      *src_node;
 282         pbqp_node      *tgt_node;
 283         vector         *src_vec;
 284         vector         *tgt_vec;
 285         int             src_len;
 286         int             tgt_len;
 287         int             src_index;
 288         int             tgt_index;
 289
 290         assert(pbqp);
 291         assert(edge);
 292
 293         src_node = edge->src;
 294         tgt_node = edge->tgt;
 295         assert(src_node);
 296         assert(tgt_node);
 297
 298         src_vec = src_node->costs;
 299         tgt_vec = tgt_node->costs;
 300         assert(src_vec);
 301         assert(tgt_vec);
 302
 303         src_len = src_vec->len;
 304         tgt_len = tgt_vec->len;
 305         assert(src_len > 0);
 306         assert(tgt_len > 0);
 307
 308         mat = edge->costs;
 309         assert(mat);
 310
 311         if (src_len == 1 && tgt_len == 1) {
 312                 //panic("Something is wrong");
 313         }
 314
 315         int allRowsOk = 1;
 316         for (src_index = 0; src_index < src_len; ++src_index) {
 317                 int onlyOneZero = 0;
 318                 if (src_vec->entries[src_index].data == INF_COSTS) {
 319                         continue;
 320                 }
 321                 for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
 322                         if (tgt_vec->entries[tgt_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                 allRowsOk &= onlyOneZero;
 341         }
 342
 343         int allColsOk = 1;
 344         for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
 345                 int onlyOneZero = 0;
 346                 if (tgt_vec->entries[tgt_index].data == INF_COSTS) {
 347                         continue;
 348                 }
 349                 for (src_index = 0; src_index < src_len; ++src_index) {
 350                         if (src_vec->entries[src_index].data == INF_COSTS) {
 351                                 continue;
 352                         }
 353                         if (mat->entries[src_index * tgt_len + tgt_index] == 0) {
 354                                 if (onlyOneZero) {
 355                                         onlyOneZero = 0;
 356                                         break;
 357                                 } else {
 358                                         onlyOneZero = 1;
 359                                         continue;
 360                                 }
 361                         }
 362                         if (mat->entries[src_index * tgt_len + tgt_index] == INF_COSTS) {
 363                                 continue;
 364                         }
 365                         onlyOneZero = 0;
 366                         break;
 367                 }
 368                 allColsOk &= onlyOneZero;
 369         }
 370
 371         if (allRowsOk && allColsOk) {
 372                 panic("Hurray");
 373         }
 374 }
 375 #endif
 376
 377 static void simplify_edge(pbqp *pbqp, pbqp_edge *edge)
 378 {
 379         pbqp_matrix    *mat;
 380         pbqp_node      *src_node;
 381         pbqp_node      *tgt_node;
 382         vector         *src_vec;
 383         vector         *tgt_vec;
 384         int             src_len;
 385         int             tgt_len;
 386
 387         assert(pbqp);
 388         assert(edge);
 389
 390         src_node = edge->src;
 391         tgt_node = edge->tgt;
 392         assert(src_node);
 393         assert(tgt_node);
 394
 395         /* If edge are already deleted, we have nothing to do. */
 396         if (!is_connected(src_node, edge) || !is_connected(tgt_node, edge))
 397                 return;
 398
 399 #if     KAPS_DUMP
 400         if (pbqp->dump_file) {
 401                 char txt[100];
 402                 sprintf(txt, "Simplification of Edge n%d-n%d", src_node->index, tgt_node->index);
 403                 dump_section(pbqp->dump_file, 3, txt);
 404         }
 405 #endif
 406
 407         src_vec = src_node->costs;
 408         tgt_vec = tgt_node->costs;
 409         assert(src_vec);
 410         assert(tgt_vec);
 411
 412         src_len = src_vec->len;
 413         tgt_len = tgt_vec->len;
 414         assert(src_len > 0);
 415         assert(tgt_len > 0);
 416
 417         mat = edge->costs;
 418         assert(mat);
 419
 420 #if     KAPS_DUMP
 421         if (pbqp->dump_file) {
 422                 fputs("Input:<br>\n", pbqp->dump_file);
 423                 dump_simplifyedge(pbqp, edge);
 424         }
 425 #endif
 426
 427         normalize_towards_source(pbqp, edge);
 428         normalize_towards_target(pbqp, edge);
 429
 430 #if     KAPS_DUMP
 431         if (pbqp->dump_file) {
 432                 fputs("<br>\nOutput:<br>\n", pbqp->dump_file);
 433                 dump_simplifyedge(pbqp, edge);
 434         }
 435 #endif
 436
 437         if (pbqp_matrix_is_zero(mat, src_vec, tgt_vec)) {
 438 #if     KAPS_DUMP
 439                 if (pbqp->dump_file) {
 440                         fputs("edge has been eliminated<br>\n", pbqp->dump_file);
 441                 }
 442 #endif
 443
 444 #if KAPS_STATISTIC
 445                 if (dump == 0) {
 446                         pbqp->num_edges++;
 447                 }
 448 #endif
 449
 450                 delete_edge(edge);
 451                 reorder_node(src_node);
 452                 reorder_node(tgt_node);
 453         }
 454 }
 455
 456 static void initial_simplify_edges(pbqp *pbqp)
 457 {
 458         unsigned node_index;
 459         unsigned node_len;
 460
 461         assert(pbqp);
 462
 463         #if KAPS_TIMING
 464                 ir_timer_t *t_int_simpl = ir_timer_register("be_pbqp_init_simp", "PBQP Initial simplify edges");
 465                 ir_timer_reset_and_start(t_int_simpl);
 466         #endif
 467
 468 #if     KAPS_DUMP
 469         if (pbqp->dump_file) {
 470                 pbqp_dump_input(pbqp);
 471                 dump_section(pbqp->dump_file, 1, "2. Simplification of Cost Matrices");
 472         }
 473 #endif
 474
 475         node_len = pbqp->num_nodes;
 476
 477         init_buckets();
 478
 479         /* First simplify all edges. */
 480         for (node_index = 0; node_index < node_len; ++node_index) {
 481                 unsigned    edge_index;
 482                 pbqp_node  *node = get_node(pbqp, node_index);
 483                 pbqp_edge **edges;
 484                 unsigned    edge_len;
 485
 486                 if (!node) continue;
 487
 488                 edges = node->edges;
 489                 edge_len = pbqp_node_get_degree(node);
 490
 491                 for (edge_index = 0; edge_index < edge_len; ++edge_index) {
 492                         pbqp_edge *edge = edges[edge_index];
 493
 494                         /* Simplify only once per edge. */
 495                         if (node != edge->src) continue;
 496
 497                         simplify_edge(pbqp, edge);
 498                 }
 499         }
 500
 501         #if KAPS_TIMING
 502                 ir_timer_stop(t_int_simpl);
 503                 printf("%-20s: %8.3lf msec\n", ir_timer_get_description(t_int_simpl), (double)ir_timer_elapsed_usec(t_int_simpl) / 1000.0);
 504         #endif
 505 }
 506
 507 static num determine_solution(pbqp *pbqp)
 508 {
 509         unsigned node_index;
 510         unsigned node_len;
 511         num      solution   = 0;
 512
 513         #if KAPS_TIMING
 514                 ir_timer_t *t_det_solution = ir_timer_register("be_det_solution", "PBQP Determine Solution");
 515                 ir_timer_reset_and_start(t_det_solution);
 516         #endif
 517
 518 #if     KAPS_DUMP
 519         FILE     *file;
 520 #endif
 521
 522         assert(pbqp);
 523
 524 #if     KAPS_DUMP
 525         file = pbqp->dump_file;
 526
 527         if (file) {
 528                 dump_section(file, 1, "4. Determine Solution/Minimum");
 529                 dump_section(file, 2, "4.1. Trivial Solution");
 530         }
 531 #endif
 532
 533         /* Solve trivial nodes and calculate solution. */
 534         node_len = node_bucket_get_length(node_buckets[0]);
 535
 536 #if KAPS_STATISTIC
 537         if (dump == 0) {
 538                 pbqp->num_r0 = node_len;
 539         }
 540 #endif
 541
 542         for (node_index = 0; node_index < node_len; ++node_index) {
 543                 pbqp_node *node = node_buckets[0][node_index];
 544                 assert(node);
 545
 546                 node->solution = vector_get_min_index(node->costs);
 547                 solution       = pbqp_add(solution,
 548                                 node->costs->entries[node->solution].data);
 549
 550 #if     KAPS_DUMP
 551                 if (file) {
 552                         fprintf(file, "node n%d is set to %d<br>\n", node->index, node->solution);
 553                         dump_node(file, node);
 554                 }
 555 #endif
 556         }
 557
 558 #if     KAPS_DUMP
 559         if (file) {
 560                 dump_section(file, 2, "Minimum");
 561 #if KAPS_USE_UNSIGNED
 562                 fprintf(file, "Minimum is equal to %u.", solution);
 563 #else
 564                 fprintf(file, "Minimum is equal to %lld.", solution);
 565 #endif
 566         }
 567 #endif
 568
 569         #if KAPS_TIMING
 570                 ir_timer_stop(t_det_solution);
 571                 printf("%-20s: %8.3lf msec\n", ir_timer_get_description(t_det_solution), (double)ir_timer_elapsed_usec(t_det_solution) / 1000.0);
 572         #endif
 573
 574         return solution;
 575 }
 576
 577 static void back_propagate(pbqp *pbqp)
 578 {
 579         unsigned node_index;
 580         unsigned node_len   = node_bucket_get_length(reduced_bucket);
 581
 582         assert(pbqp);
 583
 584 #if     KAPS_DUMP
 585         if (pbqp->dump_file) {
 586                 dump_section(pbqp->dump_file, 2, "Back Propagation");
 587         }
 588 #endif
 589
 590         for (node_index = node_len; node_index > 0; --node_index) {
 591                 pbqp_node *node = reduced_bucket[node_index - 1];
 592
 593                 switch (pbqp_node_get_degree(node)) {
 594                         case 1:
 595                                 back_propagate_RI(pbqp, node);
 596                                 break;
 597                         case 2:
 598                                 back_propagate_RII(pbqp, node);
 599                                 break;
 600                         default:
 601                                 panic("Only nodes with degree one or two should be in this bucket");
 602                                 break;
 603                 }
 604         }
 605 }
 606
 607 static void apply_heuristic_reductions(pbqp *pbqp)
 608 {
 609         for (;;) {
 610                 if (edge_bucket_get_length(edge_bucket) > 0) {
 611                         apply_edge(pbqp);
 612                 } else if (node_bucket_get_length(node_buckets[1]) > 0) {
 613                         apply_RI(pbqp);
 614                 } else if (node_bucket_get_length(node_buckets[2]) > 0) {
 615                         apply_RII(pbqp);
 616                 } else if (node_bucket_get_length(node_buckets[3]) > 0) {
 617                         apply_RN(pbqp);
 618                 } else {
 619                         return;
 620                 }
 621         }
 622 }
 623
 624 static void apply_heuristic_reductions_co(pbqp *pbqp, plist_t *rpeo)
 625 {
 626         #if KAPS_TIMING
 627                 /* create timers */
 628                 ir_timer_t *t_edge = ir_timer_register("be_pbqp_edges", "pbqp reduce independent edges");
 629                 ir_timer_t *t_r0 = ir_timer_register("be_pbqp_r0", "pbqp R0 reductions");
 630                 ir_timer_t *t_r1 = ir_timer_register("be_pbqp_r1", "pbqp R1 reductions");
 631                 ir_timer_t *t_r2 = ir_timer_register("be_pbqp_r2", "pbqp R2 reductions");
 632                 ir_timer_t *t_rn = ir_timer_register("be_pbqp_rN", "pbqp RN reductions");
 633
 634                 /* reset timers */
 635                 ir_timer_reset(t_edge);
 636                 ir_timer_reset(t_r0);
 637                 ir_timer_reset(t_r1);
 638                 ir_timer_reset(t_r2);
 639                 ir_timer_reset(t_rn);
 640         #endif
 641
 642         for (;;) {
 643                 if (edge_bucket_get_length(edge_bucket) > 0) {
 644                         #if KAPS_TIMING
 645                                 ir_timer_start(t_r0);
 646                         #endif
 647
 648                         apply_edge(pbqp);
 649
 650                         #if KAPS_TIMING
 651                                 ir_timer_stop(t_r0);
 652                         #endif
 653                 } else if (node_bucket_get_length(node_buckets[1]) > 0) {
 654                         #if KAPS_TIMING
 655                                 ir_timer_start(t_r1);
 656                         #endif
 657
 658                         apply_RI(pbqp);
 659
 660                         #if KAPS_TIMING
 661                                 ir_timer_stop(t_r1);
 662                         #endif
 663                 } else if (node_bucket_get_length(node_buckets[2]) > 0) {
 664                         #if KAPS_TIMING
 665                                 ir_timer_start(t_r2);
 666                         #endif
 667
 668                         apply_RII(pbqp);
 669
 670                         #if KAPS_TIMING
 671                                 ir_timer_stop(t_r2);
 672                         #endif
 673                 } else if (node_bucket_get_length(node_buckets[3]) > 0) {
 674                         #if KAPS_TIMING
 675                                 ir_timer_start(t_rn);
 676                         #endif
 677
 678                         apply_RN_co(pbqp, rpeo);
 679
 680                         #if KAPS_TIMING
 681                                 ir_timer_stop(t_rn);
 682                         #endif
 683                 } else {
 684                         #if KAPS_TIMING
 685                                 printf("%-20s: %8.3lf msec\n", ir_timer_get_description(t_edge), (double)ir_timer_elapsed_usec(t_edge) / 1000.0);
 686                                 printf("%-20s: %8.3lf msec\n", ir_timer_get_description(t_r0), (double)ir_timer_elapsed_usec(t_r0) / 1000.0);
 687                                 printf("%-20s: %8.3lf msec\n", ir_timer_get_description(t_r1), (double)ir_timer_elapsed_usec(t_r1) / 1000.0);
 688                                 printf("%-20s: %8.3lf msec\n", ir_timer_get_description(t_r2), (double)ir_timer_elapsed_usec(t_r2) / 1000.0);
 689                                 printf("%-20s: %8.3lf msec\n", ir_timer_get_description(t_rn), (double)ir_timer_elapsed_usec(t_rn) / 1000.0);
 690                         #endif
 691
 692                         return;
 693                 }
 694         }
 695 }
 696
 697 void solve_pbqp_heuristical(pbqp *pbqp)
 698 {
 699         /* Reduce nodes degree ... */
 700         initial_simplify_edges(pbqp);
 701
 702         /* ... and put node into bucket representing their degree. */
 703         fill_node_buckets(pbqp);
 704
 705 #if KAPS_STATISTIC
 706         FILE *fh = fopen("solutions.pb", "a");
 707         fprintf(fh, "Solution");
 708         fclose(fh);
 709 #endif
 710
 711         apply_heuristic_reductions(pbqp);
 712
 713         pbqp->solution = determine_solution(pbqp);
 714
 715 #if KAPS_STATISTIC
 716         fh = fopen("solutions.pb", "a");
 717         fprintf(fh, ": %lld RE:%u R0:%u R1:%u R2:%u RN/BF:%u\n", pbqp->solution,
 718                                 pbqp->num_edges, pbqp->num_r0, pbqp->num_r1, pbqp->num_r2,
 719                                 pbqp->num_rn);
 720         fclose(fh);
 721 #endif
 722
 723         /* Solve reduced nodes. */
 724         back_propagate(pbqp);
 725
 726         free_buckets();
 727 }
 728
 729 void solve_pbqp_heuristical_co(pbqp *pbqp, plist_t *rpeo)
 730 {
 731         /* Reduce nodes degree ... */
 732         initial_simplify_edges(pbqp);
 733
 734         /* ... and put node into bucket representing their degree. */
 735         fill_node_buckets(pbqp);
 736
 737         #if KAPS_STATISTIC
 738                 FILE *fh = fopen("solutions.pb", "a");
 739                 fprintf(fh, "Solution");
 740                 fclose(fh);
 741         #endif
 742
 743         apply_heuristic_reductions_co(pbqp, rpeo);
 744
 745         pbqp->solution = determine_solution(pbqp);
 746
 747         #if KAPS_STATISTIC
 748                 fh = fopen("solutions.pb", "a");
 749                 fprintf(fh, ": %lld RE:%u R0:%u R1:%u R2:%u RN/BF:%u\n", pbqp->solution,
 750                                         pbqp->num_edges, pbqp->num_r0, pbqp->num_r1, pbqp->num_r2,
 751                                         pbqp->num_rn);
 752                 fclose(fh);
 753         #endif
 754
 755         /* Solve reduced nodes. */
 756         back_propagate(pbqp);
 757
 758         free_buckets();
 759 }
 760
 761 void apply_edge(pbqp *pbqp)
 762 {
 763         pbqp_edge *edge = edge_bucket_pop(&edge_bucket);
 764
 765         simplify_edge(pbqp, edge);
 766 }
 767
 768 void apply_RI(pbqp *pbqp)
 769 {
 770         pbqp_node   *node       = node_bucket_pop(&node_buckets[1]);
 771         pbqp_edge   *edge       = node->edges[0];
 772         pbqp_matrix *mat        = edge->costs;
 773         int          is_src     = edge->src == node;
 774         pbqp_node   *other_node;
 775
 776         assert(pbqp_node_get_degree(node) == 1);
 777
 778         if (is_src) {
 779                 other_node = edge->tgt;
 780         } else {
 781                 other_node = edge->src;
 782         }
 783
 784 #if     KAPS_DUMP
 785         if (pbqp->dump_file) {
 786                 char     txt[100];
 787                 sprintf(txt, "RI-Reduction of Node n%d", node->index);
 788                 dump_section(pbqp->dump_file, 2, txt);
 789                 pbqp_dump_graph(pbqp);
 790                 fputs("<br>\nBefore reduction:<br>\n", pbqp->dump_file);
 791                 dump_node(pbqp->dump_file, node);
 792                 dump_node(pbqp->dump_file, other_node);
 793                 dump_edge(pbqp->dump_file, edge);
 794         }
 795 #endif
 796
 797         if (is_src) {
 798                 pbqp_matrix_add_to_all_cols(mat, node->costs);
 799                 normalize_towards_target(pbqp, edge);
 800         } else {
 801                 pbqp_matrix_add_to_all_rows(mat, node->costs);
 802                 normalize_towards_source(pbqp, edge);
 803         }
 804         disconnect_edge(other_node, edge);
 805
 806 #if     KAPS_DUMP
 807         if (pbqp->dump_file) {
 808                 fputs("<br>\nAfter reduction:<br>\n", pbqp->dump_file);
 809                 dump_node(pbqp->dump_file, other_node);
 810         }
 811 #endif
 812
 813         reorder_node(other_node);
 814
 815 #if KAPS_STATISTIC
 816         if (dump == 0) {
 817                 pbqp->num_r1++;
 818         }
 819 #endif
 820
 821         /* Add node to back propagation list. */
 822         node_bucket_insert(&reduced_bucket, node);
 823 }
 824
 825 void apply_RII(pbqp *pbqp)
 826 {
 827         pbqp_node   *node       = node_bucket_pop(&node_buckets[2]);
 828         pbqp_edge   *src_edge   = node->edges[0];
 829         pbqp_edge   *tgt_edge   = node->edges[1];
 830         int          src_is_src = src_edge->src == node;
 831         int          tgt_is_src = tgt_edge->src == node;
 832         pbqp_matrix *src_mat;
 833         pbqp_matrix *tgt_mat;
 834         pbqp_node   *src_node;
 835         pbqp_node   *tgt_node;
 836         pbqp_matrix *mat;
 837         vector      *vec;
 838         vector      *node_vec;
 839         vector      *src_vec;
 840         vector      *tgt_vec;
 841         unsigned     col_index;
 842         unsigned     col_len;
 843         unsigned     row_index;
 844         unsigned     row_len;
 845         unsigned     node_len;
 846
 847         assert(pbqp);
 848         assert(pbqp_node_get_degree(node) == 2);
 849
 850         if (src_is_src) {
 851                 src_node = src_edge->tgt;
 852         } else {
 853                 src_node = src_edge->src;
 854         }
 855
 856         if (tgt_is_src) {
 857                 tgt_node = tgt_edge->tgt;
 858         } else {
 859                 tgt_node = tgt_edge->src;
 860         }
 861
 862         /* Swap nodes if necessary. */
 863         if (tgt_node->index < src_node->index) {
 864                 pbqp_node *tmp_node;
 865                 pbqp_edge *tmp_edge;
 866
 867                 tmp_node = src_node;
 868                 src_node = tgt_node;
 869                 tgt_node = tmp_node;
 870
 871                 tmp_edge = src_edge;
 872                 src_edge = tgt_edge;
 873                 tgt_edge = tmp_edge;
 874
 875                 src_is_src = src_edge->src == node;
 876                 tgt_is_src = tgt_edge->src == node;
 877         }
 878
 879 #if     KAPS_DUMP
 880         if (pbqp->dump_file) {
 881                 char     txt[100];
 882                 sprintf(txt, "RII-Reduction of Node n%d", node->index);
 883                 dump_section(pbqp->dump_file, 2, txt);
 884                 pbqp_dump_graph(pbqp);
 885                 fputs("<br>\nBefore reduction:<br>\n", pbqp->dump_file);
 886                 dump_node(pbqp->dump_file, src_node);
 887                 dump_edge(pbqp->dump_file, src_edge);
 888                 dump_node(pbqp->dump_file, node);
 889                 dump_edge(pbqp->dump_file, tgt_edge);
 890                 dump_node(pbqp->dump_file, tgt_node);
 891         }
 892 #endif
 893
 894         src_mat = src_edge->costs;
 895         tgt_mat = tgt_edge->costs;
 896
 897         src_vec  = src_node->costs;
 898         tgt_vec  = tgt_node->costs;
 899         node_vec = node->costs;
 900
 901         row_len  = src_vec->len;
 902         col_len  = tgt_vec->len;
 903         node_len = node_vec->len;
 904
 905         mat = pbqp_matrix_alloc(pbqp, row_len, col_len);
 906
 907         for (row_index = 0; row_index < row_len; ++row_index) {
 908                 for (col_index = 0; col_index < col_len; ++col_index) {
 909                         vec = vector_copy(pbqp, node_vec);
 910
 911                         if (src_is_src) {
 912                                 vector_add_matrix_col(vec, src_mat, row_index);
 913                         } else {
 914                                 vector_add_matrix_row(vec, src_mat, row_index);
 915                         }
 916
 917                         if (tgt_is_src) {
 918                                 vector_add_matrix_col(vec, tgt_mat, col_index);
 919                         } else {
 920                                 vector_add_matrix_row(vec, tgt_mat, col_index);
 921                         }
 922
 923                         mat->entries[row_index * col_len + col_index] = vector_get_min(vec);
 924
 925                         obstack_free(&pbqp->obstack, vec);
 926                 }
 927         }
 928
 929         pbqp_edge *edge = get_edge(pbqp, src_node->index, tgt_node->index);
 930
 931         /* Disconnect node. */
 932         disconnect_edge(src_node, src_edge);
 933         disconnect_edge(tgt_node, tgt_edge);
 934
 935 #if KAPS_STATISTIC
 936         if (dump == 0) {
 937                 pbqp->num_r2++;
 938         }
 939 #endif
 940
 941         /* Add node to back propagation list. */
 942         node_bucket_insert(&reduced_bucket, node);
 943
 944         if (edge == NULL) {
 945                 edge = alloc_edge(pbqp, src_node->index, tgt_node->index, mat);
 946         } else {
 947                 // matrix
 948                 pbqp_matrix_add(edge->costs, mat);
 949
 950                 /* Free local matrix. */
 951                 obstack_free(&pbqp->obstack, mat);
 952
 953                 reorder_node(src_node);
 954                 reorder_node(tgt_node);
 955         }
 956
 957 #if     KAPS_DUMP
 958         if (pbqp->dump_file) {
 959                 fputs("<br>\nAfter reduction:<br>\n", pbqp->dump_file);
 960                 dump_edge(pbqp->dump_file, edge);
 961         }
 962 #endif
 963
 964         /* Edge has changed so we simplify it. */
 965         simplify_edge(pbqp, edge);
 966 }
 967
 968 static void select_alternative(pbqp_node *node, unsigned selected_index)
 969 {
 970         unsigned  edge_index;
 971         unsigned  node_index;
 972         unsigned  node_len;
 973         vector   *node_vec;
 974         unsigned  max_degree = pbqp_node_get_degree(node);
 975
 976         assert(node);
 977         node->solution = selected_index;
 978         node_vec = node->costs;
 979         node_len = node_vec->len;
 980         assert(selected_index < node_len);
 981
 982         /* Set all other costs to infinity. */
 983         for (node_index = 0; node_index < node_len; ++node_index) {
 984                 if (node_index != selected_index) {
 985                         node_vec->entries[node_index].data = INF_COSTS;
 986                 }
 987         }
 988
 989         /* Add all incident edges to edge bucket, since they are now independent. */
 990         for (edge_index = 0; edge_index < max_degree; ++edge_index) {
 991                 insert_into_edge_bucket(node->edges[edge_index]);
 992         }
 993 }
 994
 995 static pbqp_node *get_node_with_max_degree(void)
 996 {
 997         pbqp_node  **bucket       = node_buckets[3];
 998         unsigned     bucket_len   = node_bucket_get_length(bucket);
 999         unsigned     bucket_index;
1000         unsigned     max_degree   = 0;
1001         pbqp_node   *result       = NULL;
1002
1003         for (bucket_index = 0; bucket_index < bucket_len; ++bucket_index) {
1004                 pbqp_node *candidate = bucket[bucket_index];
1005                 unsigned   degree    = pbqp_node_get_degree(candidate);
1006
1007                 if (degree > max_degree) {
1008                         result = candidate;
1009                         max_degree = degree;
1010                 }
1011         }
1012
1013         return result;
1014 }
1015
1016 static unsigned get_local_minimal_alternative(pbqp *pbqp, pbqp_node *node)
1017 {
1018         pbqp_edge   *edge;
1019         vector      *node_vec;
1020         vector      *vec;
1021         pbqp_matrix *mat;
1022         unsigned     edge_index;
1023         unsigned     max_degree   = 0;
1024         unsigned     node_index;
1025         unsigned     node_len;
1026         unsigned     min_index    = 0;
1027         num          min          = INF_COSTS;
1028         int          is_src;
1029
1030         assert(pbqp);
1031         assert(node);
1032         node_vec = node->costs;
1033         node_len = node_vec->len;
1034
1035         for (node_index = 0; node_index < node_len; ++node_index) {
1036                 num value = node_vec->entries[node_index].data;
1037
1038                 for (edge_index = 0; edge_index < max_degree; ++edge_index) {
1039                         edge   = node->edges[edge_index];
1040                         mat    = edge->costs;
1041                         is_src = edge->src == node;
1042
1043                         if (is_src) {
1044                                 vec = vector_copy(pbqp, edge->tgt->costs);
1045                                 vector_add_matrix_row(vec, mat, node_index);
1046                         } else {
1047                                 vec = vector_copy(pbqp, edge->src->costs);
1048                                 vector_add_matrix_col(vec, mat, node_index);
1049                         }
1050
1051                         value = pbqp_add(value, vector_get_min(vec));
1052
1053                         obstack_free(&pbqp->obstack, vec);
1054                 }
1055
1056                 if (value < min) {
1057                         min = value;
1058                         min_index = node_index;
1059                 }
1060         }
1061
1062         return min_index;
1063 }
1064
1065 void apply_RN(pbqp *pbqp)
1066 {
1067         pbqp_node   *node         = NULL;
1068         unsigned     min_index    = 0;
1069
1070         assert(pbqp);
1071
1072         /* We want to reduce a node with maximum degree. */
1073         node = get_node_with_max_degree();
1074         assert(node);
1075         assert(pbqp_node_get_degree(node) > 2);
1076
1077 #if     KAPS_DUMP
1078         if (pbqp->dump_file) {
1079                 char     txt[100];
1080                 sprintf(txt, "RN-Reduction of Node n%d", node->index);
1081                 dump_section(pbqp->dump_file, 2, txt);
1082                 pbqp_dump_graph(pbqp);
1083         }
1084 #endif
1085
1086         min_index = get_local_minimal_alternative(pbqp, node);
1087
1088 #if     KAPS_DUMP
1089         if (pbqp->dump_file) {
1090                 fprintf(pbqp->dump_file, "node n%d is set to %d<br><br>\n",
1091                                         node->index, min_index);
1092         }
1093 #endif
1094
1095 #if KAPS_STATISTIC
1096         if (dump == 0) {
1097                 FILE *fh = fopen("solutions.pb", "a");
1098                 fprintf(fh, "[%u]", min_index);
1099                 fclose(fh);
1100                 pbqp->num_rn++;
1101         }
1102 #endif
1103
1104         /* Now that we found the local minimum set all other costs to infinity. */
1105         select_alternative(node, min_index);
1106 }
1107
1108 void apply_RN_co(pbqp *pbqp, plist_t *rpeo)
1109 {
1110         pbqp_node   *node         = NULL;
1111         unsigned     min_index    = 0;
1112
1113         assert(pbqp);
1114
1115         /* We want to reduce the first node in reverse perfect elimination order. */
1116         do {
1117                 /* get first element from reverse perfect elimination order */
1118                 node = plist_first(rpeo)->data;
1119                 /* remove element from reverse perfect elimination order */
1120                 plist_erase(rpeo, plist_first(rpeo));
1121                 /* insert node at the end of rpeo so the rpeo already exits after pbqp solving */
1122                 plist_insert_back(rpeo, node);
1123         } while(node_is_reduced(node));
1124
1125         assert(node);
1126         assert(pbqp_node_get_degree(node) > 2);
1127
1128 #if     KAPS_DUMP
1129         if (pbqp->dump_file) {
1130                 char     txt[100];
1131                 sprintf(txt, "RN-Reduction of Node n%d", node->index);
1132                 dump_section(pbqp->dump_file, 2, txt);
1133                 pbqp_dump_graph(pbqp);
1134         }
1135 #endif
1136
1137         min_index = get_local_minimal_alternative(pbqp, node);
1138
1139 #if     KAPS_DUMP
1140         if (pbqp->dump_file) {
1141                 fprintf(pbqp->dump_file, "node n%d is set to %d<br><br>\n",
1142                                         node->index, min_index);
1143         }
1144 #endif
1145
1146 #if KAPS_STATISTIC
1147         if (dump == 0) {
1148                 FILE *fh = fopen("solutions.pb", "a");
1149                 fprintf(fh, "[%u]", min_index);
1150                 fclose(fh);
1151                 pbqp->num_rn++;
1152         }
1153 #endif
1154
1155         /* Now that we found the local minimum set all other costs to infinity. */
1156         select_alternative(node, min_index);
1157
1158
1159 }
1160
1161 static void apply_brute_force_reductions(pbqp *pbqp)
1162 {
1163         for (;;) {
1164                 if (edge_bucket_get_length(edge_bucket) > 0) {
1165                         apply_edge(pbqp);
1166                 } else if (node_bucket_get_length(node_buckets[1]) > 0) {
1167                         apply_RI(pbqp);
1168                 } else if (node_bucket_get_length(node_buckets[2]) > 0) {
1169                         apply_RII(pbqp);
1170                 } else if (node_bucket_get_length(node_buckets[3]) > 0) {
1171                         apply_Brute_Force(pbqp);
1172                 } else {
1173                         return;
1174                 }
1175         }
1176 }
1177
1178 static unsigned get_minimal_alternative(pbqp *pbqp, pbqp_node *node)
1179 {
1180         vector      *node_vec;
1181         unsigned     node_index;
1182         unsigned     node_len;
1183         unsigned     min_index    = 0;
1184         num          min          = INF_COSTS;
1185         unsigned     bucket_index;
1186
1187         assert(pbqp);
1188         assert(node);
1189         node_vec     = node->costs;
1190         node_len     = node_vec->len;
1191         bucket_index = node->bucket_index;
1192
1193         for (node_index = 0; node_index < node_len; ++node_index) {
1194                 pbqp_node_bucket bucket_deg3;
1195                 num              value;
1196                 unsigned         bucket_0_length;
1197                 unsigned         bucket_red_length;
1198
1199                 char *tmp = obstack_finish(&pbqp->obstack);
1200
1201                 node_bucket_init(&bucket_deg3);
1202
1203                 /* Some node buckets and the edge bucket should be empty. */
1204                 assert(node_bucket_get_length(node_buckets[1]) == 0);
1205                 assert(node_bucket_get_length(node_buckets[2]) == 0);
1206                 assert(edge_bucket_get_length(edge_bucket)     == 0);
1207
1208                 /* char *tmp = obstack_finish(&pbqp->obstack); */
1209
1210                 /* Save current PBQP state. */
1211                 node_bucket_copy(&bucket_deg3, node_buckets[3]);
1212                 node_bucket_shrink(&node_buckets[3], 0);
1213                 node_bucket_deep_copy(pbqp, &node_buckets[3], bucket_deg3);
1214                 node_bucket_update(pbqp, node_buckets[3]);
1215                 bucket_0_length   = node_bucket_get_length(node_buckets[0]);
1216                 bucket_red_length = node_bucket_get_length(reduced_bucket);
1217
1218                 /* Select alternative and solve PBQP recursively. */
1219                 select_alternative(node_buckets[3][bucket_index], node_index);
1220                 apply_brute_force_reductions(pbqp);
1221
1222                 value = determine_solution(pbqp);
1223
1224                 if (value < min) {
1225                         min = value;
1226                         min_index = node_index;
1227                 }
1228
1229                 /* Some node buckets and the edge bucket should still be empty. */
1230                 assert(node_bucket_get_length(node_buckets[1]) == 0);
1231                 assert(node_bucket_get_length(node_buckets[2]) == 0);
1232                 assert(edge_bucket_get_length(edge_bucket)     == 0);
1233
1234                 /* Clear modified buckets... */
1235                 node_bucket_shrink(&node_buckets[3], 0);
1236
1237                 /* ... and restore old PBQP state. */
1238                 node_bucket_shrink(&node_buckets[0], bucket_0_length);
1239                 node_bucket_shrink(&reduced_bucket, bucket_red_length);
1240                 node_bucket_copy(&node_buckets[3], bucket_deg3);
1241                 node_bucket_update(pbqp, node_buckets[3]);
1242
1243                 /* Free copies. */
1244                 /* obstack_free(&pbqp->obstack, tmp); */
1245                 node_bucket_free(&bucket_deg3);
1246
1247                 obstack_free(&pbqp->obstack, tmp);
1248         }
1249
1250         return min_index;
1251 }
1252
1253 void apply_Brute_Force(pbqp *pbqp)
1254 {
1255         pbqp_node   *node         = NULL;
1256         unsigned     min_index    = 0;
1257
1258         assert(pbqp);
1259
1260         /* We want to reduce a node with maximum degree. */
1261         node = get_node_with_max_degree();
1262         assert(node);
1263         assert(pbqp_node_get_degree(node) > 2);
1264
1265 #if     KAPS_DUMP
1266         if (pbqp->dump_file) {
1267                 char     txt[100];
1268                 sprintf(txt, "BF-Reduction of Node n%d", node->index);
1269                 dump_section(pbqp->dump_file, 2, txt);
1270                 pbqp_dump_graph(pbqp);
1271         }
1272 #endif
1273
1274 #if KAPS_STATISTIC
1275         dump++;
1276 #endif
1277
1278         min_index = get_minimal_alternative(pbqp, node);
1279         node = pbqp->nodes[node->index];
1280
1281 #if     KAPS_DUMP
1282         if (pbqp->dump_file) {
1283                 fprintf(pbqp->dump_file, "node n%d is set to %d<br><br>\n",
1284                                         node->index, min_index);
1285         }
1286 #endif
1287
1288 #if KAPS_STATISTIC
1289         dump--;
1290         if (dump == 0) {
1291                 FILE *fh = fopen("solutions.pb", "a");
1292                 fprintf(fh, "[%u]", min_index);
1293                 fclose(fh);
1294                 pbqp->num_bf++;
1295         }
1296 #endif
1297
1298         /* Now that we found the minimum set all other costs to infinity. */
1299         select_alternative(node, min_index);
1300 }
1301
1302 void solve_pbqp_brute_force(pbqp *pbqp)
1303 {
1304         /* Reduce nodes degree ... */
1305         initial_simplify_edges(pbqp);
1306
1307         /* ... and put node into bucket representing their degree. */
1308         fill_node_buckets(pbqp);
1309
1310 #if KAPS_STATISTIC
1311         FILE *fh = fopen("solutions.pb", "a");
1312         fprintf(fh, "Solution");
1313         fclose(fh);
1314 #endif
1315
1316         apply_brute_force_reductions(pbqp);
1317
1318         pbqp->solution = determine_solution(pbqp);
1319
1320 #if KAPS_STATISTIC
1321         fh = fopen("solutions.pb", "a");
1322         fprintf(fh, ": %lld RE:%u R0:%u R1:%u R2:%u RN/BF:%u\n", pbqp->solution,
1323                         pbqp->num_edges, pbqp->num_r0, pbqp->num_r1, pbqp->num_r2,
1324                         pbqp->num_bf);
1325         fclose(fh);
1326 #endif
1327
1328         /* Solve reduced nodes. */
1329         back_propagate(pbqp);
1330
1331         free_buckets();
1332 }
1333
1334 void back_propagate_RI(pbqp *pbqp, pbqp_node *node)
1335 {
1336         pbqp_edge   *edge;
1337         pbqp_node   *other;
1338         pbqp_matrix *mat;
1339         vector      *vec;
1340         int          is_src;
1341
1342         assert(pbqp);
1343         assert(node);
1344
1345         edge = node->edges[0];
1346         mat = edge->costs;
1347         is_src = edge->src == node;
1348         vec = node->costs;
1349
1350         if (is_src) {
1351                 other = edge->tgt;
1352                 assert(other);
1353
1354                 /* Update pointer for brute force solver. */
1355                 other = pbqp->nodes[other->index];
1356
1357                 node->solution = pbqp_matrix_get_col_min_index(mat, other->solution, vec);
1358         } else {
1359                 other = edge->src;
1360                 assert(other);
1361
1362                 /* Update pointer for brute force solver. */
1363                 other = pbqp->nodes[other->index];
1364
1365                 node->solution = pbqp_matrix_get_row_min_index(mat, other->solution, vec);
1366         }
1367
1368 #if     KAPS_DUMP
1369         if (pbqp->dump_file) {
1370                 fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
1371         }
1372 #endif
1373 }
1374
1375 void back_propagate_RII(pbqp *pbqp, pbqp_node *node)
1376 {
1377         pbqp_edge   *src_edge   = node->edges[0];
1378         pbqp_edge   *tgt_edge   = node->edges[1];
1379         int          src_is_src = src_edge->src == node;
1380         int          tgt_is_src = tgt_edge->src == node;
1381         pbqp_matrix *src_mat;
1382         pbqp_matrix *tgt_mat;
1383         pbqp_node   *src_node;
1384         pbqp_node   *tgt_node;
1385         vector      *vec;
1386         vector      *node_vec;
1387         unsigned     col_index;
1388         unsigned     row_index;
1389
1390         assert(pbqp);
1391
1392         if (src_is_src) {
1393                 src_node = src_edge->tgt;
1394         } else {
1395                 src_node = src_edge->src;
1396         }
1397
1398         if (tgt_is_src) {
1399                 tgt_node = tgt_edge->tgt;
1400         } else {
1401                 tgt_node = tgt_edge->src;
1402         }
1403
1404         /* Swap nodes if necessary. */
1405         if (tgt_node->index < src_node->index) {
1406                 pbqp_node *tmp_node;
1407                 pbqp_edge *tmp_edge;
1408
1409                 tmp_node = src_node;
1410                 src_node = tgt_node;
1411                 tgt_node = tmp_node;
1412
1413                 tmp_edge = src_edge;
1414                 src_edge = tgt_edge;
1415                 tgt_edge = tmp_edge;
1416
1417                 src_is_src = src_edge->src == node;
1418                 tgt_is_src = tgt_edge->src == node;
1419         }
1420
1421         /* Update pointer for brute force solver. */
1422         src_node = pbqp->nodes[src_node->index];
1423         tgt_node = pbqp->nodes[tgt_node->index];
1424
1425         src_mat = src_edge->costs;
1426         tgt_mat = tgt_edge->costs;
1427
1428         node_vec = node->costs;
1429
1430         row_index = src_node->solution;
1431         col_index = tgt_node->solution;
1432
1433         vec = vector_copy(pbqp, node_vec);
1434
1435         if (src_is_src) {
1436                 vector_add_matrix_col(vec, src_mat, row_index);
1437         } else {
1438                 vector_add_matrix_row(vec, src_mat, row_index);
1439         }
1440
1441         if (tgt_is_src) {
1442                 vector_add_matrix_col(vec, tgt_mat, col_index);
1443         } else {
1444                 vector_add_matrix_row(vec, tgt_mat, col_index);
1445         }
1446
1447         node->solution = vector_get_min_index(vec);
1448
1449 #if     KAPS_DUMP
1450         if (pbqp->dump_file) {
1451                 fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
1452         }
1453 #endif
1454
1455         obstack_free(&pbqp->obstack, vec);
1456 }
1457
1458 int node_is_reduced(pbqp_node *node)
1459 {
1460         if (!reduced_bucket) return 0;
1461
1462         if (pbqp_node_get_degree(node) == 0) return 1;
1463
1464         return node_bucket_contains(reduced_bucket, node);
1465 }