+ dump_section(pbqp->dump_file, 1, "2. Simplification of Cost Matrices");
+ }
+
+ node_len = pbqp->num_nodes;
+
+ init_buckets();
+
+ /* First simplify all edges. */
+ for (node_index = 0; node_index < node_len; ++node_index) {
+ unsigned edge_index;
+ pbqp_node *node = get_node(pbqp, node_index);
+ pbqp_edge **edges;
+ unsigned edge_len;
+
+ if (!node) continue;
+
+ edges = node->edges;
+ edge_len = ARR_LEN(edges);
+
+ for (edge_index = 0; edge_index < edge_len; ++edge_index) {
+ pbqp_edge *edge = edges[edge_index];
+
+ /* Simplify only once per edge. */
+ if (node != edge->src) continue;
+
+ simplify_edge(pbqp, edge);
+ }
+ }
+
+ /* Put node into bucket representing their arity. */
+ fill_node_buckets(pbqp);
+
+ for (;;) {
+ if (ARR_LEN(edge_bucket) > 0) {
+ panic("Please implement edge simplification");
+ } else if (ARR_LEN(node_buckets[1]) > 0) {
+ apply_RI(pbqp);
+ } else if (ARR_LEN(node_buckets[2]) > 0) {
+ apply_RII(pbqp);
+ } else if (ARR_LEN(node_buckets[3]) > 0) {
+ panic("Please implement RN simplification");
+ } else {
+ break;
+ }
+ }
+
+ if (pbqp->dump_file) {
+ dump_section(pbqp->dump_file, 1, "4. Determine Solution/Minimum");
+ dump_section(pbqp->dump_file, 2, "4.1. Trivial Solution");
+ }
+
+ /* Solve trivial nodes and calculate solution. */
+ node_len = ARR_LEN(node_buckets[0]);
+ for (node_index = 0; node_index < node_len; ++node_index) {
+ pbqp_node *node = node_buckets[0][node_index];
+ assert(node);
+
+ node->solution = vector_get_min_index(node->costs);
+ pbqp->solution = pbqp_add(pbqp->solution,
+ node->costs->entries[node->solution].data);
+ if (pbqp->dump_file) {
+ fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
+ dump_node(pbqp, node);
+ }
+ }
+
+ if (pbqp->dump_file) {
+ dump_section(pbqp->dump_file, 2, "Minimum");
+ fprintf(pbqp->dump_file, "Minimum is equal to %d.", pbqp->solution);
+ dump_section(pbqp->dump_file, 2, "Back Propagation");
+ }
+
+ /* Solve reduced nodes. */
+ node_len = ARR_LEN(reduced_bucket);
+ for (node_index = node_len; node_index > 0; --node_index) {
+ pbqp_node *node = reduced_bucket[node_index - 1];
+ assert(node);
+
+ switch (ARR_LEN(node->edges)) {
+ case 1:
+ back_propagate_RI(pbqp, node);
+ break;
+ case 2:
+ back_propagate_RII(pbqp, node);
+ break;
+ default:
+ panic("Only nodes with degree one or two should be in this bucket");
+ break;
+ }
+ }
+
+ free_buckets();
+}
+
+void apply_RI(pbqp *pbqp)
+{
+ pbqp_node **bucket = node_buckets[1];
+ unsigned bucket_len = ARR_LEN(bucket);
+ pbqp_node *node = bucket[bucket_len - 1];
+ pbqp_edge *edge = node->edges[0];
+ pbqp_matrix *mat = edge->costs;
+ int is_src = edge->src == node;
+ pbqp_node *other_node;
+
+ if (is_src) {
+ other_node = edge->tgt;
+ } else {
+ other_node = edge->src;
+ }
+
+ if (pbqp->dump_file) {
+ char txt[100];
+ sprintf(txt, "RI-Reduktion of Node n%d", node->index);
+ dump_section(pbqp->dump_file, 2, txt);
+ pbqp_dump_graph(pbqp);
+ fputs("<br>\nBefore reduction:<br>\n", pbqp->dump_file);
+ dump_node(pbqp, node);
+ dump_node(pbqp, other_node);
+ dump_edge(pbqp, edge);
+ }
+
+ if (is_src) {
+ pbqp_matrix_add_to_all_cols(mat, node->costs);
+ normalize_towards_target(pbqp, edge);
+ } else {
+ pbqp_matrix_add_to_all_rows(mat, node->costs);
+ normalize_towards_source(pbqp, edge);
+ }
+ disconnect_edge(other_node, edge);
+
+ if (pbqp->dump_file) {
+ fputs("<br>\nAfter reduction:<br>\n", pbqp->dump_file);
+ dump_node(pbqp, other_node);
+ }
+
+ /* Remove node from bucket... */
+ ARR_SHRINKLEN(bucket, (int)bucket_len - 1);
+ reorder_node(other_node);
+
+ /* ...and add it to back propagation list. */
+ node->bucket_index = ARR_LEN(reduced_bucket);
+ ARR_APP1(pbqp_node *, reduced_bucket, node);
+}
+
+void apply_RII(pbqp *pbqp)
+{
+ pbqp_node **bucket = node_buckets[2];
+ unsigned bucket_len = ARR_LEN(bucket);
+ pbqp_node *node = bucket[bucket_len - 1];
+ pbqp_edge *src_edge = node->edges[0];
+ pbqp_edge *tgt_edge = node->edges[1];
+ int src_is_src = src_edge->src == node;
+ int tgt_is_src = tgt_edge->src == node;
+ pbqp_matrix *src_mat;
+ pbqp_matrix *tgt_mat;
+ pbqp_node *src_node;
+ pbqp_node *tgt_node;
+ pbqp_matrix *mat;
+ vector *vec;
+ vector *node_vec;
+ vector *src_vec;
+ vector *tgt_vec;
+ unsigned col_index;
+ unsigned col_len;
+ unsigned row_index;
+ unsigned row_len;
+ unsigned node_len;
+
+ assert(pbqp);
+
+ if (src_is_src) {
+ src_node = src_edge->tgt;
+ } else {
+ src_node = src_edge->src;
+ }
+
+ if (tgt_is_src) {
+ tgt_node = tgt_edge->tgt;
+ } else {
+ tgt_node = tgt_edge->src;
+ }
+
+ /* Swap nodes if necessary. */
+ if (tgt_node->index < src_node->index) {
+ pbqp_node *tmp_node;
+ pbqp_edge *tmp_edge;
+
+ tmp_node = src_node;
+ src_node = tgt_node;
+ tgt_node = tmp_node;
+
+ tmp_edge = src_edge;
+ src_edge = tgt_edge;
+ tgt_edge = tmp_edge;
+
+ src_is_src = src_edge->src == node;
+ tgt_is_src = tgt_edge->src == node;
+ }
+
+ if (pbqp->dump_file) {
+ char txt[100];
+ sprintf(txt, "RII-Reduktion of Node n%d", node->index);
+ dump_section(pbqp->dump_file, 2, txt);
+ pbqp_dump_graph(pbqp);
+ fputs("<br>\nBefore reduction:<br>\n", pbqp->dump_file);
+ dump_node(pbqp, src_node);
+ dump_edge(pbqp, src_edge);
+ dump_node(pbqp, node);
+ dump_edge(pbqp, tgt_edge);
+ dump_node(pbqp, tgt_node);