From 65983bfff91b6d49b6039d70ab6ef6b92a845e4c Mon Sep 17 00:00:00 2001 From: Sebastian Buchwald Date: Sat, 4 Oct 2008 22:05:38 +0000 Subject: [PATCH] - fixed some bugs concerning vector addition - added solving of trivial nodes - added back propagation for RI rule - enabled html dumping for trivial solving and back propagation [r22484] --- heuristical.c | 90 ++++++++++++++++++++++++++++++++++++++++++++++++--- heuristical.h | 2 ++ html_dumper.c | 4 +-- kaps.c | 2 +- pbqp_node.c | 3 +- pbqp_node.h | 2 +- pbqp_node_t.h | 1 + vector.c | 84 +++++++++++++++++++++++++++++++++++++++++++++-- vector.h | 5 +++ 9 files changed, 182 insertions(+), 11 deletions(-) diff --git a/heuristical.c b/heuristical.c index c320764fd..378a57a0a 100644 --- a/heuristical.c +++ b/heuristical.c @@ -14,12 +14,14 @@ static pbqp_edge **edge_bucket; static pbqp_node **node_buckets[4]; +static pbqp_node **reduced_bucket; static void init_buckets(void) { int i; edge_bucket = NEW_ARR_F(pbqp_edge *, 0); + reduced_bucket = NEW_ARR_F(pbqp_node *, 0); for (i = 0; i < 4; ++i) { node_buckets[i] = NEW_ARR_F(pbqp_node *, 0); @@ -91,7 +93,7 @@ static void normalize_towards_source(pbqp *pbqp, pbqp_edge *edge) if (min != 0) { pbqp_matrix_sub_row_value(mat, src_index, tgt_vec, min); - vector_add_value(src_vec, min); + src_vec->entries[src_index].data += min; // TODO add to edge_list if inf } @@ -135,7 +137,7 @@ static void normalize_towards_target(pbqp *pbqp, pbqp_edge *edge) if (min != 0) { pbqp_matrix_sub_col_value(mat, tgt_index, src_vec, min); - vector_add_value(tgt_vec, min); + tgt_vec->entries[tgt_index].data += min; // TODO add to edge_list if inf } @@ -287,8 +289,51 @@ void solve_pbqp_heuristical(pbqp *pbqp) } else if (ARR_LEN(node_buckets[3]) > 0) { panic("Please implement RN simplification"); } else { - panic("Please implement back propagation"); - // break; + 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 += node->costs->entries[node->solution].data; + if (pbqp->dump_file) { + fprintf(pbqp->dump_file, "node n%d is set to %d
\n", node->index, node->solution); + dump_node(pbqp, node->index); + } + } + + 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: + panic("Please implement back propagation for RII"); + break; + default: + panic("Only nodes with degree one or two should be in this bucket"); + break; } } } @@ -331,6 +376,7 @@ void applyRI(pbqp *pbqp) } else { pbqp_node *src_node = get_node(pbqp, edge->src); pbqp_matrix_add_to_all_rows(mat, node->costs); + dump_edge(pbqp, edge); normalize_towards_source(pbqp, edge); disconnect_edge(src_node, edge); } @@ -340,6 +386,42 @@ void applyRI(pbqp *pbqp) dump_node(pbqp, other_index); } + /* Remove node from bucket... */ ARR_SHRINKLEN(bucket, (int)bucket_len - 1); reorder_node(get_node(pbqp, other_index)); + + /* ...and add it to back propagation list. */ + ARR_APP1(pbqp_node *, reduced_bucket, node); +} + +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 = get_node(pbqp, edge->src) == node; + vec = node->costs; + + if (is_src) { + other = get_node(pbqp, edge->tgt); + assert(other); + vector_add_matrix_col(vec, mat, other->solution); + } else { + other = get_node(pbqp, edge->src); + assert(other); + vector_add_matrix_row(vec, mat, other->solution); + } + + node->solution = vector_get_min_index(vec); + if (pbqp->dump_file) { + fprintf(pbqp->dump_file, "node n%d is set to %d
\n", node->index, node->solution); + } } diff --git a/heuristical.h b/heuristical.h index 85e13d985..bb61474a3 100644 --- a/heuristical.h +++ b/heuristical.h @@ -7,4 +7,6 @@ void solve_pbqp_heuristical(pbqp *pbqp); void applyRI(pbqp *pbqp); +void back_propagate_RI(pbqp *pbqp, pbqp_node *node); + #endif /* KAPS_HEURISTICAL_H */ diff --git a/html_dumper.c b/html_dumper.c index 8f834a0b3..0ec8f2c3d 100644 --- a/html_dumper.c +++ b/html_dumper.c @@ -19,7 +19,7 @@ static void dump_vector(FILE *f, vector *vec) for (index = 0; index < len; ++index) { #if EXT_GRS_DEBUG if (vec->entries[index].data == INF_COSTS) { - fprintf(f, "inf", + fprintf(f, " inf ", vec->entries[index].name); } else { fprintf(f, "%6d", @@ -27,7 +27,7 @@ static void dump_vector(FILE *f, vector *vec) } #else if (vec->entries[index].data == INF_COSTS) { - fputs("inf", f); + fputs(" inf ", f); } else { fprintf(f, "%6d", vec->entries[index].data); } diff --git a/kaps.c b/kaps.c index 7a819e498..a33180361 100644 --- a/kaps.c +++ b/kaps.c @@ -63,7 +63,7 @@ void add_node_costs(pbqp *pbqp, unsigned node_index, vector *costs) pbqp_node *node = get_node(pbqp, node_index); if (node == NULL) { - node = alloc_node(pbqp, costs); + node = alloc_node(pbqp, node_index, costs); pbqp->nodes[node_index] = node; } else { vector_add(node->costs, costs); diff --git a/pbqp_node.c b/pbqp_node.c index 51a224801..eed9aa9c2 100644 --- a/pbqp_node.c +++ b/pbqp_node.c @@ -6,7 +6,7 @@ #include "pbqp_node_t.h" #include "vector.h" -pbqp_node *alloc_node(pbqp *pbqp, vector *costs) +pbqp_node *alloc_node(pbqp *pbqp, unsigned node_index, vector *costs) { pbqp_node *node = obstack_alloc(&pbqp->obstack, sizeof(*node)); assert(node); @@ -15,6 +15,7 @@ pbqp_node *alloc_node(pbqp *pbqp, vector *costs) node->costs = vector_copy(pbqp, costs); node->bucket_index = UINT_MAX; node->solution = UINT_MAX; + node->index = node_index; return node; } diff --git a/pbqp_node.h b/pbqp_node.h index 6e3b2c85a..047c86860 100644 --- a/pbqp_node.h +++ b/pbqp_node.h @@ -3,7 +3,7 @@ #include "pbqp_t.h" -pbqp_node *alloc_node(pbqp *pbqp, vector *costs); +pbqp_node *alloc_node(pbqp *pbqp, unsigned node_index, vector *costs); void disconnect_edge(pbqp_node *node, pbqp_edge *edge); diff --git a/pbqp_node_t.h b/pbqp_node_t.h index 836a2c6d0..ba3e4810a 100644 --- a/pbqp_node_t.h +++ b/pbqp_node_t.h @@ -8,6 +8,7 @@ struct pbqp_node { vector *costs; unsigned bucket_index; unsigned solution; + unsigned index; }; #endif /* KAPS_PBQP_NODE_T_H */ diff --git a/vector.c b/vector.c index 8ea8d1ea2..30991e252 100644 --- a/vector.c +++ b/vector.c @@ -38,7 +38,13 @@ void vector_add(vector *sum, vector *summand) len = sum->len; for (i = 0; i < len; ++i) { - sum->entries[i].data += summand->entries[i].data; + if (sum->entries[i].data == INF_COSTS) continue; + + if (summand->entries[i].data == INF_COSTS) { + sum->entries[i].data = INF_COSTS; + } else { + sum->entries[i].data += summand->entries[i].data; + } } } @@ -68,6 +74,80 @@ void vector_add_value(vector *vec, num value) for (index = 0; index < len; ++index) { if (vec->entries[index].data == INF_COSTS) continue; - vec->entries[index].data += value; + if (value == INF_COSTS) { + vec->entries[index].data = INF_COSTS; + } else { + vec->entries[index].data += value; + } + } +} + +void vector_add_matrix_col(vector *vec, pbqp_matrix *mat, unsigned col_index) +{ + unsigned index; + unsigned len; + + assert(vec); + assert(mat); + assert(vec->len == mat->rows); + assert(col_index < mat->cols); + + len = vec->len; + + for (index = 0; index < len; ++index) { + if (vec->entries[index].data == INF_COSTS) continue; + + if (mat->entries[index * mat->cols + col_index] == INF_COSTS) { + vec->entries[index].data = INF_COSTS; + } else { + vec->entries[index].data += mat->entries[index * mat->cols + col_index]; + } } } + +void vector_add_matrix_row(vector *vec, pbqp_matrix *mat, unsigned row_index) +{ + unsigned index; + unsigned len; + + assert(vec); + assert(mat); + assert(vec->len == mat->cols); + assert(row_index < mat->rows); + + len = vec->len; + + for (index = 0; index < len; ++index) { + if (vec->entries[index].data == INF_COSTS) continue; + + if (mat->entries[row_index * mat->cols + index] == INF_COSTS) { + vec->entries[index].data = INF_COSTS; + } else { + vec->entries[index].data += mat->entries[row_index * mat->cols + index]; + } + } +} + +unsigned vector_get_min_index(vector *vec) +{ + unsigned index; + unsigned len; + unsigned min_index = 0; + num min = INF_COSTS; + + assert(vec); + + len = vec->len; + assert(len > 0); + + for (index = 0; index < len; ++index) { + num elem = vec->entries[index].data; + + if (elem < min) { + min = elem; + min_index = index; + } + } + + return min_index; +} diff --git a/vector.h b/vector.h index 4346a46f7..80433a06c 100644 --- a/vector.h +++ b/vector.h @@ -19,4 +19,9 @@ void vector_set_description(vector *vec, unsigned index, char *name); void vector_add_value(vector *vec, num value); +void vector_add_matrix_col(vector *vec, pbqp_matrix *mat, unsigned col_index); +void vector_add_matrix_row(vector *vec, pbqp_matrix *mat, unsigned row_index); + +unsigned vector_get_min_index(vector *vec); + #endif /* KAPS_VECTOR_H */ -- 2.20.1