#include "bucket.h"
#include "heuristical.h"
+#if KAPS_DUMP
#include "html_dumper.h"
+#endif
#include "kaps.h"
#include "matrix.h"
#include "pbqp_edge.h"
static pbqp_node **reduced_bucket = NULL;
static int buckets_filled = 0;
+#if KAPS_STATISTIC
+static int dump = 0;
+#endif
+
/* Forward declarations. */
static void apply_Brute_Force(pbqp *pbqp);
node_bucket_insert(&node_buckets[degree], node);
}
+#if 0
static void check_melting_possibility(pbqp *pbqp, pbqp_edge *edge)
{
pbqp_matrix *mat;
panic("Hurray");
}
}
+#endif
static void simplify_edge(pbqp *pbqp, pbqp_edge *edge)
{
if (!is_connected(src_node, edge) || !is_connected(tgt_node, edge))
return;
+#if KAPS_DUMP
if (pbqp->dump_file) {
char txt[100];
sprintf(txt, "Simplification of Edge n%d-n%d", src_node->index, tgt_node->index);
dump_section(pbqp->dump_file, 3, txt);
}
+#endif
src_vec = src_node->costs;
tgt_vec = tgt_node->costs;
mat = edge->costs;
assert(mat);
+#if KAPS_DUMP
if (pbqp->dump_file) {
fputs("Input:<br>\n", pbqp->dump_file);
dump_simplifyedge(pbqp, edge);
}
+#endif
normalize_towards_source(pbqp, edge);
normalize_towards_target(pbqp, edge);
+#if KAPS_DUMP
if (pbqp->dump_file) {
fputs("<br>\nOutput:<br>\n", pbqp->dump_file);
dump_simplifyedge(pbqp, edge);
}
+#endif
if (pbqp_matrix_is_zero(mat, src_vec, tgt_vec)) {
+#if KAPS_DUMP
if (pbqp->dump_file) {
fputs("edge has been eliminated<br>\n", pbqp->dump_file);
}
+#endif
+
+#if KAPS_STATISTIC
+ if (dump == 0) {
+ pbqp->num_edges++;
+ }
+#endif
delete_edge(edge);
reorder_node(src_node);
reorder_node(tgt_node);
- } else {
- //check_melting_possibility(pbqp, edge);
}
}
assert(pbqp);
+#if KAPS_DUMP
if (pbqp->dump_file) {
pbqp_dump_input(pbqp);
dump_section(pbqp->dump_file, 1, "2. Simplification of Cost Matrices");
}
+#endif
node_len = pbqp->num_nodes;
}
}
-num determine_solution(FILE *file)
+static num determine_solution(pbqp *pbqp)
{
unsigned node_index;
unsigned node_len;
- num solution;
+ num solution = 0;
+#if KAPS_DUMP
+ FILE *file;
+#endif
+
+ assert(pbqp);
+
+#if KAPS_DUMP
+ file = pbqp->dump_file;
if (file) {
dump_section(file, 1, "4. Determine Solution/Minimum");
dump_section(file, 2, "4.1. Trivial Solution");
}
+#endif
/* Solve trivial nodes and calculate solution. */
node_len = node_bucket_get_length(node_buckets[0]);
+
+#if KAPS_STATISTIC
+ if (dump == 0) {
+ pbqp->num_r0 = node_len;
+ }
+#endif
+
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);
solution = pbqp_add(solution,
node->costs->entries[node->solution].data);
+
+#if KAPS_DUMP
if (file) {
fprintf(file, "node n%d is set to %d<br>\n", node->index, node->solution);
dump_node(file, node);
}
+#endif
}
+#if KAPS_DUMP
if (file) {
dump_section(file, 2, "Minimum");
fprintf(file, "Minimum is equal to %lld.", solution);
}
+#endif
return solution;
}
unsigned node_len = node_bucket_get_length(reduced_bucket);
assert(pbqp);
+
+#if KAPS_DUMP
if (pbqp->dump_file) {
dump_section(pbqp->dump_file, 2, "Back Propagation");
}
+#endif
for (node_index = node_len; node_index > 0; --node_index) {
pbqp_node *node = reduced_bucket[node_index - 1];
/* ... and put node into bucket representing their degree. */
fill_node_buckets(pbqp);
+#if KAPS_STATISTIC
+ FILE *fh = fopen("solutions.pb", "a");
+ fprintf(fh, "Solution");
+ fclose(fh);
+#endif
+
apply_heuristic_reductions(pbqp);
- pbqp->solution = determine_solution(pbqp->dump_file);
+ pbqp->solution = determine_solution(pbqp);
+
+#if KAPS_STATISTIC
+ fh = fopen("solutions.pb", "a");
+ fprintf(fh, ": %lld RE:%u R0:%u R1:%u R2:%u RN/BF:%u\n", pbqp->solution,
+ pbqp->num_edges, pbqp->num_r0, pbqp->num_r1, pbqp->num_r2,
+ pbqp->num_rn);
+ fclose(fh);
+#endif
/* Solve reduced nodes. */
back_propagate(pbqp);
int is_src = edge->src == node;
pbqp_node *other_node;
+ assert(pbqp_node_get_degree(node) == 1);
+
if (is_src) {
other_node = edge->tgt;
} else {
other_node = edge->src;
}
+#if KAPS_DUMP
if (pbqp->dump_file) {
char txt[100];
sprintf(txt, "RI-Reduction of Node n%d", node->index);
dump_node(pbqp->dump_file, other_node);
dump_edge(pbqp->dump_file, edge);
}
+#endif
if (is_src) {
pbqp_matrix_add_to_all_cols(mat, node->costs);
}
disconnect_edge(other_node, edge);
+#if KAPS_DUMP
if (pbqp->dump_file) {
fputs("<br>\nAfter reduction:<br>\n", pbqp->dump_file);
dump_node(pbqp->dump_file, other_node);
}
+#endif
reorder_node(other_node);
+#if KAPS_STATISTIC
+ if (dump == 0) {
+ pbqp->num_r1++;
+ }
+#endif
+
/* Add node to back propagation list. */
node_bucket_insert(&reduced_bucket, node);
}
unsigned node_len;
assert(pbqp);
+ assert(pbqp_node_get_degree(node) == 2);
if (src_is_src) {
src_node = src_edge->tgt;
tgt_is_src = tgt_edge->src == node;
}
+#if KAPS_DUMP
if (pbqp->dump_file) {
char txt[100];
sprintf(txt, "RII-Reduction of Node n%d", node->index);
dump_edge(pbqp->dump_file, tgt_edge);
dump_node(pbqp->dump_file, tgt_node);
}
+#endif
src_mat = src_edge->costs;
tgt_mat = tgt_edge->costs;
disconnect_edge(src_node, src_edge);
disconnect_edge(tgt_node, tgt_edge);
+#if KAPS_STATISTIC
+ if (dump == 0) {
+ pbqp->num_r2++;
+ }
+#endif
+
/* Add node to back propagation list. */
node_bucket_insert(&reduced_bucket, node);
reorder_node(tgt_node);
}
+#if KAPS_DUMP
if (pbqp->dump_file) {
fputs("<br>\nAfter reduction:<br>\n", pbqp->dump_file);
dump_edge(pbqp->dump_file, edge);
}
+#endif
/* Edge has changed so we simplify it. */
simplify_edge(pbqp, edge);
vector *node_vec;
unsigned max_degree = pbqp_node_get_degree(node);
- assert(selected_index < max_degree);
assert(node);
node->solution = selected_index;
node_vec = node->costs;
node_len = node_vec->len;
+ assert(selected_index < node_len);
/* Set all other costs to infinity. */
for (node_index = 0; node_index < node_len; ++node_index) {
/* We want to reduce a node with maximum degree. */
node = get_node_with_max_degree();
assert(node);
+ assert(pbqp_node_get_degree(node) > 2);
+#if KAPS_DUMP
if (pbqp->dump_file) {
char txt[100];
sprintf(txt, "RN-Reduction of Node n%d", node->index);
dump_section(pbqp->dump_file, 2, txt);
pbqp_dump_graph(pbqp);
}
+#endif
min_index = get_local_minimal_alternative(pbqp, node);
+#if KAPS_DUMP
if (pbqp->dump_file) {
fprintf(pbqp->dump_file, "node n%d is set to %d<br><br>\n",
node->index, min_index);
}
+#endif
+
+#if KAPS_STATISTIC
+ if (dump == 0) {
+ FILE *fh = fopen("solutions.pb", "a");
+ fprintf(fh, "[%u]", min_index);
+ fclose(fh);
+ pbqp->num_rn++;
+ }
+#endif
/* Now that we found the local minimum set all other costs to infinity. */
select_alternative(node, min_index);
unsigned node_len;
unsigned min_index = 0;
num min = INF_COSTS;
+ unsigned bucket_index;
assert(pbqp);
assert(node);
- node_vec = node->costs;
- node_len = node_vec->len;
+ node_vec = node->costs;
+ node_len = node_vec->len;
+ bucket_index = node->bucket_index;
for (node_index = 0; node_index < node_len; ++node_index) {
- num value;
+ pbqp_node_bucket bucket_deg3;
+ num value;
+ unsigned bucket_0_length;
+ unsigned bucket_red_length;
+
+ char *tmp = obstack_finish(&pbqp->obstack);
+
+ node_bucket_init(&bucket_deg3);
/* Some node buckets and the edge bucket should be empty. */
assert(node_bucket_get_length(node_buckets[1]) == 0);
assert(node_bucket_get_length(node_buckets[2]) == 0);
assert(edge_bucket_get_length(edge_bucket) == 0);
+ /* char *tmp = obstack_finish(&pbqp->obstack); */
+
/* Save current PBQP state. */
- pbqp_node_bucket *bucket_deg0 = node_bucket_deep_copy(node_buckets[0]);
- pbqp_node_bucket *bucket_deg3 = node_bucket_deep_copy(node_buckets[3]);
- pbqp_node_bucket *bucket_red = node_bucket_deep_copy(reduced_bucket);
+ node_bucket_copy(&bucket_deg3, node_buckets[3]);
+ node_bucket_shrink(&node_buckets[3], 0);
+ node_bucket_deep_copy(pbqp, &node_buckets[3], bucket_deg3);
+ node_bucket_update(pbqp, node_buckets[3]);
+ bucket_0_length = node_bucket_get_length(node_buckets[0]);
+ bucket_red_length = node_bucket_get_length(reduced_bucket);
/* Select alternative and solve PBQP recursively. */
- select_alternative(node, node_index);
+ select_alternative(node_buckets[3][bucket_index], node_index);
apply_brute_force_reductions(pbqp);
- value = determine_solution(pbqp->dump_file);
+ value = determine_solution(pbqp);
if (value < min) {
min = value;
assert(node_bucket_get_length(node_buckets[2]) == 0);
assert(edge_bucket_get_length(edge_bucket) == 0);
- /* TODO Restore old PBQP state. */
+ /* Clear modified buckets... */
+ node_bucket_shrink(&node_buckets[3], 0);
+
+ /* ... and restore old PBQP state. */
+ node_bucket_shrink(&node_buckets[0], bucket_0_length);
+ node_bucket_shrink(&reduced_bucket, bucket_red_length);
+ node_bucket_copy(&node_buckets[3], bucket_deg3);
+ node_bucket_update(pbqp, node_buckets[3]);
+
+ /* Free copies. */
+ /* obstack_free(&pbqp->obstack, tmp); */
+ node_bucket_free(&bucket_deg3);
+ obstack_free(&pbqp->obstack, tmp);
}
return min_index;
/* We want to reduce a node with maximum degree. */
node = get_node_with_max_degree();
assert(node);
+ assert(pbqp_node_get_degree(node) > 2);
+#if KAPS_DUMP
if (pbqp->dump_file) {
char txt[100];
sprintf(txt, "BF-Reduction of Node n%d", node->index);
dump_section(pbqp->dump_file, 2, txt);
pbqp_dump_graph(pbqp);
}
+#endif
+
+#if KAPS_STATISTIC
+ dump++;
+#endif
min_index = get_minimal_alternative(pbqp, node);
+ node = pbqp->nodes[node->index];
+#if KAPS_DUMP
if (pbqp->dump_file) {
fprintf(pbqp->dump_file, "node n%d is set to %d<br><br>\n",
node->index, min_index);
}
+#endif
+
+#if KAPS_STATISTIC
+ dump--;
+ if (dump == 0) {
+ FILE *fh = fopen("solutions.pb", "a");
+ fprintf(fh, "[%u]", min_index);
+ fclose(fh);
+ pbqp->num_bf++;
+ }
+#endif
/* Now that we found the minimum set all other costs to infinity. */
select_alternative(node, min_index);
/* ... and put node into bucket representing their degree. */
fill_node_buckets(pbqp);
+#if KAPS_STATISTIC
+ FILE *fh = fopen("solutions.pb", "a");
+ fprintf(fh, "Solution");
+ fclose(fh);
+#endif
+
apply_brute_force_reductions(pbqp);
- pbqp->solution = determine_solution(pbqp->dump_file);
+ pbqp->solution = determine_solution(pbqp);
+
+#if KAPS_STATISTIC
+ fh = fopen("solutions.pb", "a");
+ fprintf(fh, ": %lld RE:%u R0:%u R1:%u R2:%u RN/BF:%u\n", pbqp->solution,
+ pbqp->num_edges, pbqp->num_r0, pbqp->num_r1, pbqp->num_r2,
+ pbqp->num_bf);
+ fclose(fh);
+#endif
/* Solve reduced nodes. */
back_propagate(pbqp);
if (is_src) {
other = edge->tgt;
assert(other);
- vector_add_matrix_col(vec, mat, other->solution);
+
+ /* Update pointer for brute force solver. */
+ other = pbqp->nodes[other->index];
+
+ node->solution = pbqp_matrix_get_col_min_index(mat, other->solution, vec);
} else {
other = edge->src;
assert(other);
- vector_add_matrix_row(vec, mat, other->solution);
+
+ /* Update pointer for brute force solver. */
+ other = pbqp->nodes[other->index];
+
+ node->solution = pbqp_matrix_get_row_min_index(mat, other->solution, vec);
}
- node->solution = vector_get_min_index(vec);
+#if KAPS_DUMP
if (pbqp->dump_file) {
fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
}
+#endif
}
void back_propagate_RII(pbqp *pbqp, pbqp_node *node)
tgt_is_src = tgt_edge->src == node;
}
+ /* Update pointer for brute force solver. */
+ src_node = pbqp->nodes[src_node->index];
+ tgt_node = pbqp->nodes[tgt_node->index];
+
src_mat = src_edge->costs;
tgt_mat = tgt_edge->costs;
}
node->solution = vector_get_min_index(vec);
+
+#if KAPS_DUMP
if (pbqp->dump_file) {
fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
}
+#endif
obstack_free(&pbqp->obstack, vec);
}