From f9fc64555b5ffaffe08419ffa69eed6d92732c76 Mon Sep 17 00:00:00 2001 From: Sebastian Buchwald Date: Mon, 28 Dec 2009 10:42:24 +0000 Subject: [PATCH] - brute force solver need own back propagation - clean up a bit [r26850] --- brute_force.c | 160 ++++++++++++++++++++++++++++++++++++++++++++++- heuristical.c | 87 +++++++++++++------------- heuristical.h | 4 -- heuristical_co.c | 102 +++++++++++++++--------------- heuristical_co.h | 2 - optimal.c | 10 --- 6 files changed, 252 insertions(+), 113 deletions(-) diff --git a/brute_force.c b/brute_force.c index d5e15aa6f..e41f46857 100644 --- a/brute_force.c +++ b/brute_force.c @@ -138,7 +138,7 @@ static unsigned get_minimal_alternative(pbqp *pbqp, pbqp_node *node) return min_index; } -void apply_Brute_Force(pbqp *pbqp) +static void apply_Brute_Force(pbqp *pbqp) { pbqp_node *node = NULL; unsigned min_index = 0; @@ -187,6 +187,162 @@ void apply_Brute_Force(pbqp *pbqp) select_alternative(node, min_index); } + + +static void back_propagate_RI(pbqp *pbqp, pbqp_node *node) +{ + pbqp_edge *edge; + pbqp_node *other; + pbqp_matrix *mat; + vector *vec; + int is_src; + + assert(pbqp); + assert(node); + + edge = node->edges[0]; + mat = edge->costs; + is_src = edge->src == node; + vec = node->costs; + + if (is_src) { + other = edge->tgt; + assert(other); + + /* 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); + + /* Update pointer for brute force solver. */ + other = pbqp->nodes[other->index]; + + node->solution = pbqp_matrix_get_row_min_index(mat, other->solution, vec); + } + +#if KAPS_DUMP + if (pbqp->dump_file) { + fprintf(pbqp->dump_file, "node n%d is set to %d
\n", node->index, node->solution); + } +#endif +} + +static void back_propagate_RII(pbqp *pbqp, pbqp_node *node) +{ + 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; + vector *vec; + vector *node_vec; + unsigned col_index; + unsigned row_index; + + 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; + } + + /* 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_vec = node->costs; + + row_index = src_node->solution; + col_index = tgt_node->solution; + + vec = vector_copy(pbqp, node_vec); + + if (src_is_src) { + vector_add_matrix_col(vec, src_mat, row_index); + } else { + vector_add_matrix_row(vec, src_mat, row_index); + } + + if (tgt_is_src) { + vector_add_matrix_col(vec, tgt_mat, col_index); + } else { + vector_add_matrix_row(vec, tgt_mat, col_index); + } + + 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
\n", node->index, node->solution); + } +#endif + + obstack_free(&pbqp->obstack, vec); +} + +static void back_propagate_brute_force(pbqp *pbqp) +{ + unsigned node_index; + 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]; + + switch (pbqp_node_get_degree(node)) { + 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; + } + } +} + void solve_pbqp_brute_force(pbqp *pbqp) { /* Reduce nodes degree ... */ @@ -214,7 +370,7 @@ void solve_pbqp_brute_force(pbqp *pbqp) #endif /* Solve reduced nodes. */ - back_propagate(pbqp); + back_propagate_brute_force(pbqp); free_buckets(); } diff --git a/heuristical.c b/heuristical.c index 04b25b8e7..f202c74e2 100644 --- a/heuristical.c +++ b/heuristical.c @@ -44,9 +44,51 @@ #include "pbqp_node_t.h" #include "vector.h" -#include "plist.h" #include "timing.h" +static void apply_RN(pbqp *pbqp) +{ + pbqp_node *node = NULL; + unsigned min_index = 0; + + assert(pbqp); + + /* 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

\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); +} + static void apply_heuristic_reductions(pbqp *pbqp) { for (;;) { @@ -95,46 +137,3 @@ void solve_pbqp_heuristical(pbqp *pbqp) free_buckets(); } - -void apply_RN(pbqp *pbqp) -{ - pbqp_node *node = NULL; - unsigned min_index = 0; - - assert(pbqp); - - /* 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

\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); -} diff --git a/heuristical.h b/heuristical.h index 215798044..2e0164907 100644 --- a/heuristical.h +++ b/heuristical.h @@ -29,10 +29,6 @@ #include "pbqp_t.h" -#include "plist.h" - void solve_pbqp_heuristical(pbqp *pbqp); -void apply_RN(pbqp *pbqp); - #endif /* KAPS_HEURISTICAL_CO_H */ diff --git a/heuristical_co.c b/heuristical_co.c index f05bdb91a..281bb95e8 100644 --- a/heuristical_co.c +++ b/heuristical_co.c @@ -47,6 +47,57 @@ #include "plist.h" #include "timing.h" +static void apply_RN_co(pbqp *pbqp, plist_t *rpeo) +{ + pbqp_node *node = NULL; + unsigned min_index = 0; + + assert(pbqp); + + /* We want to reduce the first node in reverse perfect elimination order. */ + do { + /* get first element from reverse perfect elimination order */ + node = plist_first(rpeo)->data; + /* remove element from reverse perfect elimination order */ + plist_erase(rpeo, plist_first(rpeo)); + /* insert node at the end of rpeo so the rpeo already exits after pbqp solving */ + plist_insert_back(rpeo, node); + } while(node_is_reduced(node)); + + 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

\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); +} + static void apply_heuristic_reductions_co(pbqp *pbqp, plist_t *rpeo) { #if KAPS_TIMING @@ -151,54 +202,3 @@ void solve_pbqp_heuristical_co(pbqp *pbqp, plist_t *rpeo) free_buckets(); } - -void apply_RN_co(pbqp *pbqp, plist_t *rpeo) -{ - pbqp_node *node = NULL; - unsigned min_index = 0; - - assert(pbqp); - - /* We want to reduce the first node in reverse perfect elimination order. */ - do { - /* get first element from reverse perfect elimination order */ - node = plist_first(rpeo)->data; - /* remove element from reverse perfect elimination order */ - plist_erase(rpeo, plist_first(rpeo)); - /* insert node at the end of rpeo so the rpeo already exits after pbqp solving */ - plist_insert_back(rpeo, node); - } while(node_is_reduced(node)); - - 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

\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); -} diff --git a/heuristical_co.h b/heuristical_co.h index 1b512d88e..9e7dea930 100644 --- a/heuristical_co.h +++ b/heuristical_co.h @@ -33,6 +33,4 @@ void solve_pbqp_heuristical_co(pbqp *pbqp, plist_t *rpeo); -void apply_RN_co(pbqp *pbqp, plist_t *rpeo); - #endif /* KAPS_HEURISTICAL_H */ diff --git a/optimal.c b/optimal.c index e5c6a65bf..6ad5c41c5 100644 --- a/optimal.c +++ b/optimal.c @@ -591,17 +591,11 @@ static void back_propagate_RI(pbqp *pbqp, pbqp_node *node) other = edge->tgt; assert(other); - /* 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); - /* Update pointer for brute force solver. */ - other = pbqp->nodes[other->index]; - node->solution = pbqp_matrix_get_row_min_index(mat, other->solution, vec); } @@ -658,10 +652,6 @@ static 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; -- 2.20.1