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