From 777bbb1740045bdbafe1a0e34ff8cc25d148f980 Mon Sep 17 00:00:00 2001 From: Sebastian Buchwald Date: Sat, 4 Oct 2008 19:09:55 +0000 Subject: [PATCH] Implemented RI-Reduction (without back propagation). [r22481] --- heuristical.c | 184 ++++++++++++++++++++++++++++++++++++++++++++++---- heuristical.h | 2 + html_dumper.c | 4 +- html_dumper.h | 5 ++ matrix.c | 50 ++++++++++++++ matrix.h | 3 + pbqp_node.c | 2 + pbqp_node_t.h | 4 +- 8 files changed, 236 insertions(+), 18 deletions(-) diff --git a/heuristical.c b/heuristical.c index 844c87a3d..9ad9b2969 100644 --- a/heuristical.c +++ b/heuristical.c @@ -8,6 +8,7 @@ #include "matrix.h" #include "pbqp_edge.h" #include "pbqp_edge_t.h" +#include "pbqp_node.h" #include "pbqp_node_t.h" #include "vector.h" @@ -46,11 +47,13 @@ static void fill_node_buckets(pbqp *pbqp) arity = 3; } + node->bucket_index = ARR_LEN(node_buckets[arity]); + ARR_APP1(pbqp_node *, node_buckets[arity], node); } } -static void simplify_edge(pbqp *pbqp, pbqp_edge *edge) +static void normalize_towards_source(pbqp *pbqp, pbqp_edge *edge) { pbqp_matrix *mat; pbqp_node *src_node; @@ -60,17 +63,10 @@ static void simplify_edge(pbqp *pbqp, pbqp_edge *edge) int src_len; int tgt_len; int src_index; - int tgt_index; assert(pbqp); assert(edge); - if(pbqp->dump_file) { - char txt[100]; - sprintf(txt, "Simplification of Edge n%d-n%d", edge->src, edge->tgt); - dump_section(pbqp->dump_file, 3, txt); - } - src_node = get_node(pbqp, edge->src); tgt_node = get_node(pbqp, edge->tgt); assert(src_node); @@ -89,11 +85,6 @@ static void simplify_edge(pbqp *pbqp, pbqp_edge *edge) mat = edge->costs; assert(mat); - if (pbqp->dump_file) { - fputs("Input:
\n", pbqp->dump_file); - dump_simplifyedge(pbqp, edge); - } - /* Normalize towards source node. */ for (src_index = 0; src_index < src_len; ++src_index) { num min = pbqp_matrix_get_row_min(mat, src_index, tgt_vec); @@ -105,8 +96,40 @@ static void simplify_edge(pbqp *pbqp, pbqp_edge *edge) // TODO add to edge_list if inf } } +} + +static void normalize_towards_target(pbqp *pbqp, pbqp_edge *edge) +{ + pbqp_matrix *mat; + pbqp_node *src_node; + pbqp_node *tgt_node; + vector *src_vec; + vector *tgt_vec; + int src_len; + int tgt_len; + int tgt_index; + + assert(pbqp); + assert(edge); + + src_node = get_node(pbqp, edge->src); + tgt_node = get_node(pbqp, edge->tgt); + assert(src_node); + assert(tgt_node); + + src_vec = src_node->costs; + tgt_vec = tgt_node->costs; + assert(src_vec); + assert(tgt_vec); + + src_len = src_vec->len; + tgt_len = tgt_vec->len; + assert(src_len > 0); + assert(tgt_len > 0); + + mat = edge->costs; + assert(mat); - /* Normalize towards target node. */ for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) { num min = pbqp_matrix_get_col_min(mat, tgt_index, src_vec); @@ -117,6 +140,52 @@ static void simplify_edge(pbqp *pbqp, pbqp_edge *edge) // TODO add to edge_list if inf } } +} + +static void simplify_edge(pbqp *pbqp, pbqp_edge *edge) +{ + pbqp_matrix *mat; + pbqp_node *src_node; + pbqp_node *tgt_node; + vector *src_vec; + vector *tgt_vec; + int src_len; + int tgt_len; + + assert(pbqp); + assert(edge); + + if(pbqp->dump_file) { + char txt[100]; + sprintf(txt, "Simplification of Edge n%d-n%d", edge->src, edge->tgt); + dump_section(pbqp->dump_file, 3, txt); + } + + src_node = get_node(pbqp, edge->src); + tgt_node = get_node(pbqp, edge->tgt); + assert(src_node); + assert(tgt_node); + + src_vec = src_node->costs; + tgt_vec = tgt_node->costs; + assert(src_vec); + assert(tgt_vec); + + src_len = src_vec->len; + tgt_len = tgt_vec->len; + assert(src_len > 0); + assert(tgt_len > 0); + + mat = edge->costs; + assert(mat); + + if (pbqp->dump_file) { + fputs("Input:
\n", pbqp->dump_file); + dump_simplifyedge(pbqp, edge); + } + + normalize_towards_source(pbqp, edge); + normalize_towards_target(pbqp, edge); if (pbqp->dump_file) { fputs("
\nOutput:
\n", pbqp->dump_file); @@ -132,6 +201,40 @@ static void simplify_edge(pbqp *pbqp, pbqp_edge *edge) } } +static void reorder_node(pbqp_node *node) +{ + unsigned arity; + unsigned old_arity; + unsigned old_bucket_len; + + assert(node); + + arity = ARR_LEN(node->edges); + + /* Equal bucket as before */ + if (arity > 2) return; + + /* Assume node lost one incident edge. */ + old_arity = arity + 1; + + if (ARR_LEN(node_buckets[old_arity]) <= (int)node->bucket_index + || node_buckets[old_arity][node->bucket_index] != node) { + /* Old arity is new arity, so we have nothing to do. */ + return; + } + + old_bucket_len = ARR_LEN(node_buckets[old_arity]); + assert (node_buckets[old_arity][node->bucket_index] == node); + + /* Delete node from old bucket... */ + node_buckets[old_arity][node->bucket_index] + = node_buckets[old_arity][old_bucket_len - 1]; + ARR_SHRINKLEN(node_buckets[old_arity], (int)old_bucket_len - 1); + + /* ..and add to new one. */ + ARR_APP1(pbqp_node *, node_buckets[arity], node); +} + void solve_pbqp_heuristical(pbqp *pbqp) { unsigned node_index; @@ -177,7 +280,7 @@ void solve_pbqp_heuristical(pbqp *pbqp) if (ARR_LEN(edge_bucket) > 0) { panic("Please implement edge simplification"); } else if (ARR_LEN(node_buckets[1]) > 0) { - panic("Please implement RI simplification"); + applyRI(pbqp); } else if (ARR_LEN(node_buckets[2]) > 0) { panic("Please implement RII simplification"); } else if (ARR_LEN(node_buckets[3]) > 0) { @@ -188,3 +291,54 @@ void solve_pbqp_heuristical(pbqp *pbqp) } } } + +void applyRI(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 = get_node(pbqp, edge->src) == node; + unsigned my_index; + unsigned other_index; + + if (is_src) { + my_index = edge->src; + other_index = edge->tgt; + } else { + my_index = edge->tgt; + other_index = edge->src; + } + + if (pbqp->dump_file) { + char txt[100]; + sprintf(txt, "RI-Reduktion of Node n%d", my_index); + dump_section(pbqp->dump_file, 2, txt); + pbqp_dump_graph(pbqp); + fputs("
\nBefore reduction:
\n", pbqp->dump_file); + dump_node(pbqp, my_index); + dump_node(pbqp, other_index); + dump_edge(pbqp, edge); + } + + if (is_src) { + pbqp_node *tgt_node = get_node(pbqp, edge->tgt); + pbqp_matrix_add_to_all_cols(mat, node->costs); + normalize_towards_target(pbqp, edge); + disconnect_edge(tgt_node, edge); + } else { + pbqp_node *src_node = get_node(pbqp, edge->src); + pbqp_matrix_add_to_all_rows(mat, node->costs); + normalize_towards_source(pbqp, edge); + disconnect_edge(src_node, edge); + } + + if (pbqp->dump_file) { + fputs("
\nAfter reduction:
\n", pbqp->dump_file); + dump_node(pbqp, other_index); + } + + ARR_SHRINKLEN(bucket, (int)bucket_len - 1); + reorder_node(get_node(pbqp, other_index)); +} diff --git a/heuristical.h b/heuristical.h index 8d24c2e40..85e13d985 100644 --- a/heuristical.h +++ b/heuristical.h @@ -5,4 +5,6 @@ void solve_pbqp_heuristical(pbqp *pbqp); +void applyRI(pbqp *pbqp); + #endif /* KAPS_HEURISTICAL_H */ diff --git a/html_dumper.c b/html_dumper.c index 68fcb8e42..8f834a0b3 100644 --- a/html_dumper.c +++ b/html_dumper.c @@ -66,7 +66,7 @@ static void dump_matrix(FILE *f, pbqp_matrix *mat) fprintf(f, "\t\\end{pmatrix}\n"); } -static void dump_edge(pbqp *pbqp, pbqp_edge *edge) +void dump_edge(pbqp *pbqp, pbqp_edge *edge) { fputs("\n", pbqp->dump_file); fprintf(pbqp->dump_file, "\t\\overline\n{C}_{%d,%d}=\n", @@ -102,7 +102,7 @@ static void dump_edge_costs(pbqp *pbqp) fputs("

", pbqp->dump_file); } -static void dump_node(pbqp *pbqp, unsigned index) +void dump_node(pbqp *pbqp, unsigned index) { assert(pbqp); assert(pbqp->dump_file); diff --git a/html_dumper.h b/html_dumper.h index f75555739..ef8b23c8a 100644 --- a/html_dumper.h +++ b/html_dumper.h @@ -5,8 +5,13 @@ void pbqp_dump_input(pbqp *pbqp); +void pbqp_dump_graph(pbqp *pbqp); + void dump_simplifyedge(pbqp *pbqp, pbqp_edge *edge); void dump_section(FILE *f, int level, char *txt); +void dump_node(pbqp *pbqp, unsigned index); +void dump_edge(pbqp *pbqp, pbqp_edge *edge); + #endif /* KAPS_HTML_DUMPER_H */ diff --git a/matrix.c b/matrix.c index 9d6ec93d0..b25c71ac0 100644 --- a/matrix.c +++ b/matrix.c @@ -199,3 +199,53 @@ int pbqp_matrix_is_zero(pbqp_matrix *mat, vector *src_vec, vector *tgt_vec) return 1; } + +void pbqp_matrix_add_to_all_cols(pbqp_matrix *mat, vector *vec) +{ + unsigned col_index; + unsigned col_len; + unsigned row_index; + unsigned row_len; + + assert(mat); + assert(vec); + assert(mat->rows == vec->len); + + col_len = mat->cols; + row_len = mat->rows; + + for (row_index = 0; row_index < row_len; ++row_index) { + num value = vec->entries[row_index].data; + for (col_index = 0; col_index < col_len; ++col_index) { + if (mat->entries[row_index * col_len + col_index] == INF_COSTS) + continue; + + mat->entries[row_index * col_len + col_index] += value; + } + } +} + +void pbqp_matrix_add_to_all_rows(pbqp_matrix *mat, vector *vec) +{ + unsigned col_index; + unsigned col_len; + unsigned row_index; + unsigned row_len; + + assert(mat); + assert(vec); + assert(mat->cols == vec->len); + + col_len = mat->cols; + row_len = mat->rows; + + for (row_index = 0; row_index < row_len; ++row_index) { + for (col_index = 0; col_index < col_len; ++col_index) { + num value = vec->entries[col_index].data; + if (mat->entries[row_index * col_len + col_index] == INF_COSTS) + continue; + + mat->entries[row_index * col_len + col_index] += value; + } + } +} diff --git a/matrix.h b/matrix.h index a9d26a058..0d45a1514 100644 --- a/matrix.h +++ b/matrix.h @@ -25,4 +25,7 @@ void pbqp_matrix_sub_row_value(pbqp_matrix *matrix, unsigned row_index, int pbqp_matrix_is_zero(pbqp_matrix *mat, vector *src_vec, vector *tgt_vec); +void pbqp_matrix_add_to_all_cols(pbqp_matrix *mat, vector *vec); +void pbqp_matrix_add_to_all_rows(pbqp_matrix *mat, vector *vec); + #endif /* KAPS_MATRIX_H */ diff --git a/pbqp_node.c b/pbqp_node.c index 160425d8c..51a224801 100644 --- a/pbqp_node.c +++ b/pbqp_node.c @@ -13,6 +13,8 @@ pbqp_node *alloc_node(pbqp *pbqp, vector *costs) node->edges = NEW_ARR_F(pbqp_edge *, 0); node->costs = vector_copy(pbqp, costs); + node->bucket_index = UINT_MAX; + node->solution = UINT_MAX; return node; } diff --git a/pbqp_node_t.h b/pbqp_node_t.h index 40b17de86..836a2c6d0 100644 --- a/pbqp_node_t.h +++ b/pbqp_node_t.h @@ -5,7 +5,9 @@ struct pbqp_node { pbqp_edge **edges; - vector *costs; + vector *costs; + unsigned bucket_index; + unsigned solution; }; #endif /* KAPS_PBQP_NODE_T_H */ -- 2.20.1