2 * This file is part of libFirm.
3 * Copyright (C) 2012 University of Karlsruhe.
8 * @brief Optimal reductions and helper functions.
10 * @author Sebastian Buchwald
14 #include "adt/array.h"
20 #include "html_dumper.h"
25 #include "pbqp_edge.h"
26 #include "pbqp_edge_t.h"
27 #include "pbqp_node.h"
28 #include "pbqp_node_t.h"
34 pbqp_edge_t **edge_bucket;
35 static pbqp_edge_t **rm_bucket;
36 pbqp_node_t **node_buckets[4];
37 pbqp_node_t **reduced_bucket = NULL;
38 pbqp_node_t *merged_node = NULL;
39 static int buckets_filled = 0;
41 static void insert_into_edge_bucket(pbqp_edge_t *edge)
43 if (edge_bucket_contains(edge_bucket, edge)) {
44 /* Edge is already inserted. */
48 edge_bucket_insert(&edge_bucket, edge);
51 static void insert_into_rm_bucket(pbqp_edge_t *edge)
53 if (edge_bucket_contains(rm_bucket, edge)) {
54 /* Edge is already inserted. */
58 edge_bucket_insert(&rm_bucket, edge);
61 static void init_buckets(void)
65 edge_bucket_init(&edge_bucket);
66 edge_bucket_init(&rm_bucket);
67 node_bucket_init(&reduced_bucket);
69 for (i = 0; i < 4; ++i) {
70 node_bucket_init(&node_buckets[i]);
74 void free_buckets(void)
78 for (i = 0; i < 4; ++i) {
79 node_bucket_free(&node_buckets[i]);
82 edge_bucket_free(&edge_bucket);
83 edge_bucket_free(&rm_bucket);
84 node_bucket_free(&reduced_bucket);
89 void fill_node_buckets(pbqp_t *pbqp)
94 node_len = pbqp->num_nodes;
97 ir_timer_t *t_fill_buckets = ir_timer_new();
98 ir_timer_start(t_fill_buckets);
101 for (node_index = 0; node_index < node_len; ++node_index) {
103 pbqp_node_t *node = get_node(pbqp, node_index);
107 degree = pbqp_node_get_degree(node);
109 /* We have only one bucket for nodes with arity >= 3. */
114 node_bucket_insert(&node_buckets[degree], node);
120 ir_timer_stop(t_fill_buckets);
121 printf("PBQP Fill Nodes into buckets: %10.3lf msec\n", (double)ir_timer_elapsed_usec(t_fill_buckets) / 1000.0);
125 static void normalize_towards_source(pbqp_edge_t *edge)
128 pbqp_node_t *src_node;
129 pbqp_node_t *tgt_node;
135 unsigned new_infinity = 0;
137 src_node = edge->src;
138 tgt_node = edge->tgt;
140 src_vec = src_node->costs;
141 tgt_vec = tgt_node->costs;
143 src_len = src_vec->len;
144 tgt_len = tgt_vec->len;
150 /* Normalize towards source node. */
151 for (src_index = 0; src_index < src_len; ++src_index) {
152 num min = pbqp_matrix_get_row_min(mat, src_index, tgt_vec);
155 if (src_vec->entries[src_index].data == INF_COSTS) {
156 pbqp_matrix_set_row_value(mat, src_index, 0);
160 pbqp_matrix_sub_row_value(mat, src_index, tgt_vec, min);
161 src_vec->entries[src_index].data = pbqp_add(
162 src_vec->entries[src_index].data, min);
164 if (min == INF_COSTS) {
172 unsigned edge_len = pbqp_node_get_degree(src_node);
174 for (edge_index = 0; edge_index < edge_len; ++edge_index) {
175 pbqp_edge_t *edge_candidate = src_node->edges[edge_index];
177 if (edge_candidate != edge) {
178 insert_into_edge_bucket(edge_candidate);
184 static void normalize_towards_target(pbqp_edge_t *edge)
187 pbqp_node_t *src_node;
188 pbqp_node_t *tgt_node;
194 unsigned new_infinity = 0;
196 src_node = edge->src;
197 tgt_node = edge->tgt;
199 src_vec = src_node->costs;
200 tgt_vec = tgt_node->costs;
202 src_len = src_vec->len;
203 tgt_len = tgt_vec->len;
209 /* Normalize towards target node. */
210 for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
211 num min = pbqp_matrix_get_col_min(mat, tgt_index, src_vec);
214 if (tgt_vec->entries[tgt_index].data == INF_COSTS) {
215 pbqp_matrix_set_col_value(mat, tgt_index, 0);
219 pbqp_matrix_sub_col_value(mat, tgt_index, src_vec, min);
220 tgt_vec->entries[tgt_index].data = pbqp_add(
221 tgt_vec->entries[tgt_index].data, min);
223 if (min == INF_COSTS) {
231 unsigned edge_len = pbqp_node_get_degree(tgt_node);
233 for (edge_index = 0; edge_index < edge_len; ++edge_index) {
234 pbqp_edge_t *edge_candidate = tgt_node->edges[edge_index];
236 if (edge_candidate != edge) {
237 insert_into_edge_bucket(edge_candidate);
244 * Tries to apply RM for the source node of the given edge.
246 * Checks whether the source node of edge can be merged into the target node of
247 * edge, and performs the merge, if possible.
249 static void merge_source_into_target(pbqp_t *pbqp, pbqp_edge_t *edge)
252 pbqp_node_t *src_node;
253 pbqp_node_t *tgt_node;
263 src_node = edge->src;
264 tgt_node = edge->tgt;
266 src_vec = src_node->costs;
267 tgt_vec = tgt_node->costs;
269 src_len = src_vec->len;
270 tgt_len = tgt_vec->len;
272 /* Matrizes are normalized. */
278 mapping = NEW_ARR_F(unsigned, tgt_len);
280 /* Check that each column has at most one zero entry. */
281 for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
282 unsigned onlyOneZero = 0;
285 if (tgt_vec->entries[tgt_index].data == INF_COSTS)
288 for (src_index = 0; src_index < src_len; ++src_index) {
289 if (src_vec->entries[src_index].data == INF_COSTS)
292 if (mat->entries[src_index * tgt_len + tgt_index] == INF_COSTS)
295 /* Matrix entry is finite. */
302 mapping[tgt_index] = src_index;
306 /* We know that we can merge the source node into the target node. */
307 edge_len = pbqp_node_get_degree(src_node);
314 if (pbqp->dump_file) {
316 sprintf(txt, "Merging n%d into n%d", src_node->index, tgt_node->index);
317 pbqp_dump_section(pbqp->dump_file, 3, txt);
321 /* Reconnect the source's edges with the target node. */
322 for (edge_index = 0; edge_index < edge_len; ++edge_index) {
323 pbqp_edge_t *old_edge = src_node->edges[edge_index];
324 pbqp_edge_t *new_edge;
325 pbqp_matrix_t *old_matrix;
326 pbqp_matrix_t *new_matrix;
327 pbqp_node_t *other_node;
330 unsigned other_index;
333 if (old_edge == edge)
336 old_matrix = old_edge->costs;
338 if (old_edge->tgt == src_node) {
339 other_node = old_edge->src;
340 other_len = old_matrix->rows;
343 other_node = old_edge->tgt;
344 other_len = old_matrix->cols;
346 other_vec = other_node->costs;
348 new_matrix = pbqp_matrix_alloc(pbqp, tgt_len, other_len);
350 /* Source node selects the column of the old_matrix. */
351 if (old_edge->tgt == src_node) {
352 for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
353 unsigned src_index = mapping[tgt_index];
355 if (tgt_vec->entries[tgt_index].data == INF_COSTS)
358 for (other_index = 0; other_index < other_len; ++other_index) {
359 if (other_vec->entries[other_index].data == INF_COSTS)
362 new_matrix->entries[tgt_index*other_len+other_index] = old_matrix->entries[other_index*src_len+src_index];
366 /* Source node selects the row of the old_matrix. */
368 for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
369 unsigned src_index = mapping[tgt_index];
371 if (tgt_vec->entries[tgt_index].data == INF_COSTS)
374 for (other_index = 0; other_index < other_len; ++other_index) {
375 if (other_vec->entries[other_index].data == INF_COSTS)
378 new_matrix->entries[tgt_index*other_len+other_index] = old_matrix->entries[src_index*other_len+other_index];
383 new_edge = get_edge(pbqp, tgt_node->index, other_node->index);
385 add_edge_costs(pbqp, tgt_node->index, other_node->index, new_matrix);
387 if (new_edge == NULL) {
388 reorder_node_after_edge_insertion(tgt_node);
389 reorder_node_after_edge_insertion(other_node);
392 delete_edge(old_edge);
394 new_edge = get_edge(pbqp, tgt_node->index, other_node->index);
395 simplify_edge(pbqp, new_edge);
397 insert_into_rm_bucket(new_edge);
406 * Tries to apply RM for the target node of the given edge.
408 * Checks whether the target node of edge can be merged into the source node of
409 * edge, and performs the merge, if possible.
411 static void merge_target_into_source(pbqp_t *pbqp, pbqp_edge_t *edge)
414 pbqp_node_t *src_node;
415 pbqp_node_t *tgt_node;
425 src_node = edge->src;
426 tgt_node = edge->tgt;
428 src_vec = src_node->costs;
429 tgt_vec = tgt_node->costs;
431 src_len = src_vec->len;
432 tgt_len = tgt_vec->len;
434 /* Matrizes are normalized. */
440 mapping = NEW_ARR_F(unsigned, src_len);
442 /* Check that each row has at most one zero entry. */
443 for (src_index = 0; src_index < src_len; ++src_index) {
444 unsigned onlyOneZero = 0;
447 if (src_vec->entries[src_index].data == INF_COSTS)
450 for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
451 if (tgt_vec->entries[tgt_index].data == INF_COSTS)
454 if (mat->entries[src_index * tgt_len + tgt_index] == INF_COSTS)
457 /* Matrix entry is finite. */
464 mapping[src_index] = tgt_index;
468 /* We know that we can merge the target node into the source node. */
469 edge_len = pbqp_node_get_degree(tgt_node);
476 if (pbqp->dump_file) {
478 sprintf(txt, "Merging n%d into n%d", tgt_node->index, src_node->index);
479 pbqp_dump_section(pbqp->dump_file, 3, txt);
483 /* Reconnect the target's edges with the source node. */
484 for (edge_index = 0; edge_index < edge_len; ++edge_index) {
485 pbqp_edge_t *old_edge = tgt_node->edges[edge_index];
486 pbqp_edge_t *new_edge;
487 pbqp_matrix_t *old_matrix;
488 pbqp_matrix_t *new_matrix;
489 pbqp_node_t *other_node;
492 unsigned other_index;
496 if (old_edge == edge)
499 old_matrix = old_edge->costs;
501 if (old_edge->tgt == tgt_node) {
502 other_node = old_edge->src;
503 other_len = old_matrix->rows;
506 other_node = old_edge->tgt;
507 other_len = old_matrix->cols;
509 other_vec = other_node->costs;
511 new_matrix = pbqp_matrix_alloc(pbqp, src_len, other_len);
513 /* Target node selects the column of the old_matrix. */
514 if (old_edge->tgt == tgt_node) {
515 for (src_index = 0; src_index < src_len; ++src_index) {
516 unsigned tgt_index = mapping[src_index];
518 if (src_vec->entries[src_index].data == INF_COSTS)
521 for (other_index = 0; other_index < other_len; ++other_index) {
522 if (other_vec->entries[other_index].data == INF_COSTS)
525 new_matrix->entries[src_index*other_len+other_index] = old_matrix->entries[other_index*tgt_len+tgt_index];
529 /* Source node selects the row of the old_matrix. */
531 for (src_index = 0; src_index < src_len; ++src_index) {
532 unsigned tgt_index = mapping[src_index];
534 if (src_vec->entries[src_index].data == INF_COSTS)
537 for (other_index = 0; other_index < other_len; ++other_index) {
538 if (other_vec->entries[other_index].data == INF_COSTS)
541 new_matrix->entries[src_index*other_len+other_index] = old_matrix->entries[tgt_index*other_len+other_index];
546 new_edge = get_edge(pbqp, src_node->index, other_node->index);
548 add_edge_costs(pbqp, src_node->index, other_node->index, new_matrix);
550 if (new_edge == NULL) {
551 reorder_node_after_edge_insertion(src_node);
552 reorder_node_after_edge_insertion(other_node);
555 delete_edge(old_edge);
557 new_edge = get_edge(pbqp, src_node->index, other_node->index);
558 simplify_edge(pbqp, new_edge);
560 insert_into_rm_bucket(new_edge);
569 * Merge neighbors into the given node.
571 void apply_RM(pbqp_t *pbqp, pbqp_node_t *node)
578 edge_len = pbqp_node_get_degree(node);
580 /* Check all incident edges. */
581 for (edge_index = 0; edge_index < edge_len; ++edge_index) {
582 pbqp_edge_t *edge = edges[edge_index];
584 insert_into_rm_bucket(edge);
587 /* ALAP: Merge neighbors into given node. */
588 while(edge_bucket_get_length(rm_bucket) > 0) {
589 pbqp_edge_t *edge = edge_bucket_pop(&rm_bucket);
591 /* If the edge is not deleted: Try a merge. */
592 if (edge->src == node)
593 merge_target_into_source(pbqp, edge);
594 else if (edge->tgt == node)
595 merge_source_into_target(pbqp, edge);
601 void reorder_node_after_edge_deletion(pbqp_node_t *node)
603 unsigned degree = pbqp_node_get_degree(node);
604 /* Assume node lost one incident edge. */
605 unsigned old_degree = degree + 1;
607 if (!buckets_filled) return;
609 /* Same bucket as before */
610 if (degree > 2) return;
612 /* Delete node from old bucket... */
613 node_bucket_remove(&node_buckets[old_degree], node);
615 /* ..and add to new one. */
616 node_bucket_insert(&node_buckets[degree], node);
619 void reorder_node_after_edge_insertion(pbqp_node_t *node)
621 unsigned degree = pbqp_node_get_degree(node);
622 /* Assume node lost one incident edge. */
623 unsigned old_degree = degree - 1;
625 if (!buckets_filled) return;
627 /* Same bucket as before */
628 if (old_degree > 2) return;
630 /* Delete node from old bucket... */
631 node_bucket_remove(&node_buckets[old_degree], node);
633 /* ..and add to new one. */
634 node_bucket_insert(&node_buckets[degree], node);
637 void simplify_edge(pbqp_t *pbqp, pbqp_edge_t *edge)
640 pbqp_node_t *src_node;
641 pbqp_node_t *tgt_node;
649 src_node = edge->src;
650 tgt_node = edge->tgt;
654 /* If edge are already deleted, we have nothing to do. */
655 if (is_deleted(edge))
659 if (pbqp->dump_file) {
661 sprintf(txt, "Simplification of Edge n%d-n%d", src_node->index, tgt_node->index);
662 pbqp_dump_section(pbqp->dump_file, 3, txt);
666 src_vec = src_node->costs;
667 tgt_vec = tgt_node->costs;
669 src_len = src_vec->len;
670 tgt_len = tgt_vec->len;
677 if (pbqp->dump_file) {
678 fputs("Input:<br>\n", pbqp->dump_file);
679 pbqp_dump_simplifyedge(pbqp, edge);
683 normalize_towards_source(edge);
684 normalize_towards_target(edge);
687 if (pbqp->dump_file) {
688 fputs("<br>\nOutput:<br>\n", pbqp->dump_file);
689 pbqp_dump_simplifyedge(pbqp, edge);
693 if (pbqp_matrix_is_zero(mat, src_vec, tgt_vec)) {
695 if (pbqp->dump_file) {
696 fputs("edge has been eliminated<br>\n", pbqp->dump_file);
708 void initial_simplify_edges(pbqp_t *pbqp)
714 ir_timer_t *t_int_simpl = ir_timer_new();
715 ir_timer_start(t_int_simpl);
719 if (pbqp->dump_file) {
720 pbqp_dump_input(pbqp);
721 pbqp_dump_section(pbqp->dump_file, 1, "2. Simplification of Cost Matrices");
725 node_len = pbqp->num_nodes;
729 /* First simplify all edges. */
730 for (node_index = 0; node_index < node_len; ++node_index) {
732 pbqp_node_t *node = get_node(pbqp, node_index);
739 edge_len = pbqp_node_get_degree(node);
741 for (edge_index = 0; edge_index < edge_len; ++edge_index) {
742 pbqp_edge_t *edge = edges[edge_index];
744 /* Simplify only once per edge. */
745 if (node != edge->src) continue;
747 simplify_edge(pbqp, edge);
752 ir_timer_stop(t_int_simpl);
753 printf("PBQP Initial simplify edges: %10.3lf msec\n", (double)ir_timer_elapsed_usec(t_int_simpl) / 1000.0);
757 num determine_solution(pbqp_t *pbqp)
764 ir_timer_t *t_det_solution = ir_timer_new();
765 ir_timer_reset_and_start(t_det_solution);
775 file = pbqp->dump_file;
778 pbqp_dump_section(file, 1, "4. Determine Solution/Minimum");
779 pbqp_dump_section(file, 2, "4.1. Trivial Solution");
783 /* Solve trivial nodes and calculate solution. */
784 node_len = node_bucket_get_length(node_buckets[0]);
787 pbqp->num_r0 = node_len;
790 for (node_index = 0; node_index < node_len; ++node_index) {
791 pbqp_node_t *node = node_buckets[0][node_index];
793 node->solution = vector_get_min_index(node->costs);
794 solution = pbqp_add(solution,
795 node->costs->entries[node->solution].data);
799 fprintf(file, "node n%d is set to %d<br>\n", node->index, node->solution);
800 pbqp_dump_node(file, node);
807 pbqp_dump_section(file, 2, "Minimum");
808 #if KAPS_USE_UNSIGNED
809 fprintf(file, "Minimum is equal to %u.", solution);
811 fprintf(file, "Minimum is equal to %lld.", solution);
817 ir_timer_stop(t_det_solution);
818 printf("PBQP Determine Solution: %10.3lf msec\n", (double)ir_timer_elapsed_usec(t_det_solution) / 1000.0);
824 static void back_propagate_RI(pbqp_t *pbqp, pbqp_node_t *node)
833 edge = node->edges[0];
835 is_src = edge->src == node;
840 node->solution = pbqp_matrix_get_col_min_index(mat, other->solution, vec);
843 node->solution = pbqp_matrix_get_row_min_index(mat, other->solution, vec);
847 if (pbqp->dump_file) {
848 fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
853 static void back_propagate_RII(pbqp_t *pbqp, pbqp_node_t *node)
855 pbqp_edge_t *src_edge = node->edges[0];
856 pbqp_edge_t *tgt_edge = node->edges[1];
857 int src_is_src = src_edge->src == node;
858 int tgt_is_src = tgt_edge->src == node;
859 pbqp_matrix_t *src_mat;
860 pbqp_matrix_t *tgt_mat;
861 pbqp_node_t *src_node;
862 pbqp_node_t *tgt_node;
869 src_node = src_edge->tgt;
871 src_node = src_edge->src;
875 tgt_node = tgt_edge->tgt;
877 tgt_node = tgt_edge->src;
880 /* Swap nodes if necessary. */
881 if (tgt_node->index < src_node->index) {
882 pbqp_node_t *tmp_node;
883 pbqp_edge_t *tmp_edge;
893 src_is_src = src_edge->src == node;
894 tgt_is_src = tgt_edge->src == node;
897 src_mat = src_edge->costs;
898 tgt_mat = tgt_edge->costs;
900 node_vec = node->costs;
902 row_index = src_node->solution;
903 col_index = tgt_node->solution;
905 vec = vector_copy(pbqp, node_vec);
908 vector_add_matrix_col(vec, src_mat, row_index);
910 vector_add_matrix_row(vec, src_mat, row_index);
914 vector_add_matrix_col(vec, tgt_mat, col_index);
916 vector_add_matrix_row(vec, tgt_mat, col_index);
919 node->solution = vector_get_min_index(vec);
922 if (pbqp->dump_file) {
923 fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
927 obstack_free(&pbqp->obstack, vec);
930 void back_propagate(pbqp_t *pbqp)
933 unsigned node_len = node_bucket_get_length(reduced_bucket);
936 if (pbqp->dump_file) {
937 pbqp_dump_section(pbqp->dump_file, 2, "Back Propagation");
941 for (node_index = node_len; node_index > 0; --node_index) {
942 pbqp_node_t *node = reduced_bucket[node_index - 1];
944 switch (pbqp_node_get_degree(node)) {
946 back_propagate_RI(pbqp, node);
949 back_propagate_RII(pbqp, node);
952 panic("Only nodes with degree one or two should be in this bucket");
957 void apply_edge(pbqp_t *pbqp)
959 pbqp_edge_t *edge = edge_bucket_pop(&edge_bucket);
961 simplify_edge(pbqp, edge);
964 void apply_RI(pbqp_t *pbqp)
966 pbqp_node_t *node = node_bucket_pop(&node_buckets[1]);
967 pbqp_edge_t *edge = node->edges[0];
968 pbqp_matrix_t *mat = edge->costs;
969 int is_src = edge->src == node;
970 pbqp_node_t *other_node;
973 assert(pbqp_node_get_degree(node) == 1);
976 other_node = edge->tgt;
978 other_node = edge->src;
982 if (pbqp->dump_file) {
984 sprintf(txt, "RI-Reduction of Node n%d", node->index);
985 pbqp_dump_section(pbqp->dump_file, 2, txt);
986 pbqp_dump_graph(pbqp);
987 fputs("<br>\nBefore reduction:<br>\n", pbqp->dump_file);
988 pbqp_dump_node(pbqp->dump_file, node);
989 pbqp_dump_node(pbqp->dump_file, other_node);
990 pbqp_dump_edge(pbqp->dump_file, edge);
995 pbqp_matrix_add_to_all_cols(mat, node->costs);
996 normalize_towards_target(edge);
998 pbqp_matrix_add_to_all_rows(mat, node->costs);
999 normalize_towards_source(edge);
1001 disconnect_edge(other_node, edge);
1004 if (pbqp->dump_file) {
1005 fputs("<br>\nAfter reduction:<br>\n", pbqp->dump_file);
1006 pbqp_dump_node(pbqp->dump_file, other_node);
1010 reorder_node_after_edge_deletion(other_node);
1016 /* Add node to back propagation list. */
1017 node_bucket_insert(&reduced_bucket, node);
1020 void apply_RII(pbqp_t *pbqp)
1022 pbqp_node_t *node = node_bucket_pop(&node_buckets[2]);
1023 pbqp_edge_t *src_edge = node->edges[0];
1024 pbqp_edge_t *tgt_edge = node->edges[1];
1025 int src_is_src = src_edge->src == node;
1026 int tgt_is_src = tgt_edge->src == node;
1027 pbqp_matrix_t *src_mat;
1028 pbqp_matrix_t *tgt_mat;
1029 pbqp_node_t *src_node;
1030 pbqp_node_t *tgt_node;
1042 assert(pbqp_node_get_degree(node) == 2);
1045 src_node = src_edge->tgt;
1047 src_node = src_edge->src;
1051 tgt_node = tgt_edge->tgt;
1053 tgt_node = tgt_edge->src;
1056 /* Swap nodes if necessary. */
1057 if (tgt_node->index < src_node->index) {
1058 pbqp_node_t *tmp_node;
1059 pbqp_edge_t *tmp_edge;
1061 tmp_node = src_node;
1062 src_node = tgt_node;
1063 tgt_node = tmp_node;
1065 tmp_edge = src_edge;
1066 src_edge = tgt_edge;
1067 tgt_edge = tmp_edge;
1069 src_is_src = src_edge->src == node;
1070 tgt_is_src = tgt_edge->src == node;
1074 if (pbqp->dump_file) {
1076 sprintf(txt, "RII-Reduction of Node n%d", node->index);
1077 pbqp_dump_section(pbqp->dump_file, 2, txt);
1078 pbqp_dump_graph(pbqp);
1079 fputs("<br>\nBefore reduction:<br>\n", pbqp->dump_file);
1080 pbqp_dump_node(pbqp->dump_file, src_node);
1081 pbqp_dump_edge(pbqp->dump_file, src_edge);
1082 pbqp_dump_node(pbqp->dump_file, node);
1083 pbqp_dump_edge(pbqp->dump_file, tgt_edge);
1084 pbqp_dump_node(pbqp->dump_file, tgt_node);
1088 src_mat = src_edge->costs;
1089 tgt_mat = tgt_edge->costs;
1091 src_vec = src_node->costs;
1092 tgt_vec = tgt_node->costs;
1093 node_vec = node->costs;
1095 row_len = src_vec->len;
1096 col_len = tgt_vec->len;
1098 mat = pbqp_matrix_alloc(pbqp, row_len, col_len);
1100 for (row_index = 0; row_index < row_len; ++row_index) {
1101 for (col_index = 0; col_index < col_len; ++col_index) {
1102 vec = vector_copy(pbqp, node_vec);
1105 vector_add_matrix_col(vec, src_mat, row_index);
1107 vector_add_matrix_row(vec, src_mat, row_index);
1111 vector_add_matrix_col(vec, tgt_mat, col_index);
1113 vector_add_matrix_row(vec, tgt_mat, col_index);
1116 mat->entries[row_index * col_len + col_index] = vector_get_min(vec);
1118 obstack_free(&pbqp->obstack, vec);
1122 edge = get_edge(pbqp, src_node->index, tgt_node->index);
1124 /* Disconnect node. */
1125 disconnect_edge(src_node, src_edge);
1126 disconnect_edge(tgt_node, tgt_edge);
1132 /* Add node to back propagation list. */
1133 node_bucket_insert(&reduced_bucket, node);
1136 edge = alloc_edge(pbqp, src_node->index, tgt_node->index, mat);
1139 pbqp_matrix_add(edge->costs, mat);
1141 /* Free local matrix. */
1142 obstack_free(&pbqp->obstack, mat);
1144 reorder_node_after_edge_deletion(src_node);
1145 reorder_node_after_edge_deletion(tgt_node);
1149 if (pbqp->dump_file) {
1150 fputs("<br>\nAfter reduction:<br>\n", pbqp->dump_file);
1151 pbqp_dump_edge(pbqp->dump_file, edge);
1155 /* Edge has changed so we simplify it. */
1156 simplify_edge(pbqp, edge);
1159 static void select_column(pbqp_edge_t *edge, unsigned col_index)
1162 pbqp_node_t *src_node;
1163 pbqp_node_t *tgt_node;
1169 unsigned new_infinity = 0;
1171 src_node = edge->src;
1172 tgt_node = edge->tgt;
1174 src_vec = src_node->costs;
1175 tgt_vec = tgt_node->costs;
1177 src_len = src_vec->len;
1178 tgt_len = tgt_vec->len;
1179 assert(src_len > 0);
1180 assert(tgt_len > 0);
1184 for (src_index = 0; src_index < src_len; ++src_index) {
1185 num elem = mat->entries[src_index * tgt_len + col_index];
1188 if (elem == INF_COSTS && src_vec->entries[src_index].data != INF_COSTS)
1191 src_vec->entries[src_index].data = pbqp_add(
1192 src_vec->entries[src_index].data, elem);
1197 unsigned edge_index;
1198 unsigned edge_len = pbqp_node_get_degree(src_node);
1200 for (edge_index = 0; edge_index < edge_len; ++edge_index) {
1201 pbqp_edge_t *edge_candidate = src_node->edges[edge_index];
1203 if (edge_candidate != edge) {
1204 insert_into_edge_bucket(edge_candidate);
1212 static void select_row(pbqp_edge_t *edge, unsigned row_index)
1215 pbqp_node_t *tgt_node;
1219 unsigned new_infinity = 0;
1221 tgt_node = edge->tgt;
1223 tgt_vec = tgt_node->costs;
1225 tgt_len = tgt_vec->len;
1226 assert(tgt_len > 0);
1230 for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
1231 num elem = mat->entries[row_index * tgt_len + tgt_index];
1234 if (elem == INF_COSTS && tgt_vec->entries[tgt_index].data != INF_COSTS)
1237 tgt_vec->entries[tgt_index].data = pbqp_add(
1238 tgt_vec->entries[tgt_index].data, elem);
1243 unsigned edge_index;
1244 unsigned edge_len = pbqp_node_get_degree(tgt_node);
1246 for (edge_index = 0; edge_index < edge_len; ++edge_index) {
1247 pbqp_edge_t *edge_candidate = tgt_node->edges[edge_index];
1249 if (edge_candidate != edge) {
1250 insert_into_edge_bucket(edge_candidate);
1258 void select_alternative(pbqp_node_t *node, unsigned selected_index)
1260 unsigned edge_index;
1261 unsigned node_index;
1264 unsigned max_degree = pbqp_node_get_degree(node);
1266 node->solution = selected_index;
1267 node_vec = node->costs;
1268 node_len = node_vec->len;
1269 assert(selected_index < node_len);
1271 /* Set all other costs to infinity. */
1272 for (node_index = 0; node_index < node_len; ++node_index) {
1273 if (node_index != selected_index) {
1274 node_vec->entries[node_index].data = INF_COSTS;
1278 /* Select corresponding row/column for incident edges. */
1279 for (edge_index = 0; edge_index < max_degree; ++edge_index) {
1280 pbqp_edge_t *edge = node->edges[edge_index];
1282 if (edge->src == node)
1283 select_row(edge, selected_index);
1285 select_column(edge, selected_index);
1289 pbqp_node_t *get_node_with_max_degree(void)
1291 pbqp_node_t **bucket = node_buckets[3];
1292 unsigned bucket_len = node_bucket_get_length(bucket);
1293 unsigned bucket_index;
1294 unsigned max_degree = 0;
1295 pbqp_node_t *result = NULL;
1297 for (bucket_index = 0; bucket_index < bucket_len; ++bucket_index) {
1298 pbqp_node_t *candidate = bucket[bucket_index];
1299 unsigned degree = pbqp_node_get_degree(candidate);
1301 if (degree > max_degree) {
1303 max_degree = degree;
1310 unsigned get_local_minimal_alternative(pbqp_t *pbqp, pbqp_node_t *node)
1316 unsigned edge_index;
1317 unsigned max_degree;
1318 unsigned node_index;
1320 unsigned min_index = 0;
1321 num min = INF_COSTS;
1324 node_vec = node->costs;
1325 node_len = node_vec->len;
1326 max_degree = pbqp_node_get_degree(node);
1328 for (node_index = 0; node_index < node_len; ++node_index) {
1329 num value = node_vec->entries[node_index].data;
1331 for (edge_index = 0; edge_index < max_degree; ++edge_index) {
1332 edge = node->edges[edge_index];
1334 is_src = edge->src == node;
1337 vec = vector_copy(pbqp, edge->tgt->costs);
1338 vector_add_matrix_row(vec, mat, node_index);
1340 vec = vector_copy(pbqp, edge->src->costs);
1341 vector_add_matrix_col(vec, mat, node_index);
1344 value = pbqp_add(value, vector_get_min(vec));
1346 obstack_free(&pbqp->obstack, vec);
1351 min_index = node_index;
1358 int node_is_reduced(pbqp_node_t *node)
1360 if (!reduced_bucket) return 0;
1362 if (pbqp_node_get_degree(node) == 0) return 1;
1364 return node_bucket_contains(reduced_bucket, node);