From cb064ca96c3af233db91eded8fad3903085bc75f Mon Sep 17 00:00:00 2001 From: Sebastian Buchwald Date: Sun, 5 Oct 2008 17:07:08 +0000 Subject: [PATCH] PBQP edges now have pointers to their incident node, instead of only their index in the node array. [r22502] --- heuristical.c | 58 +++++++++++++++++++++++---------------------------- html_dumper.c | 13 ++++++------ html_dumper.h | 2 +- kaps.c | 2 +- pbqp_edge.c | 10 ++++----- pbqp_edge.h | 2 +- pbqp_edge_t.h | 6 +++--- 7 files changed, 43 insertions(+), 50 deletions(-) diff --git a/heuristical.c b/heuristical.c index 378a57a0a..1011d3e5d 100644 --- a/heuristical.c +++ b/heuristical.c @@ -69,8 +69,8 @@ static void normalize_towards_source(pbqp *pbqp, pbqp_edge *edge) assert(pbqp); assert(edge); - src_node = get_node(pbqp, edge->src); - tgt_node = get_node(pbqp, edge->tgt); + src_node = edge->src; + tgt_node = edge->tgt; assert(src_node); assert(tgt_node); @@ -114,8 +114,8 @@ static void normalize_towards_target(pbqp *pbqp, pbqp_edge *edge) assert(pbqp); assert(edge); - src_node = get_node(pbqp, edge->src); - tgt_node = get_node(pbqp, edge->tgt); + src_node = edge->src; + tgt_node = edge->tgt; assert(src_node); assert(tgt_node); @@ -157,17 +157,17 @@ static void simplify_edge(pbqp *pbqp, pbqp_edge *edge) assert(pbqp); assert(edge); + src_node = edge->src; + tgt_node = edge->tgt; + assert(src_node); + assert(tgt_node); + if(pbqp->dump_file) { char txt[100]; - sprintf(txt, "Simplification of Edge n%d-n%d", edge->src, edge->tgt); + sprintf(txt, "Simplification of Edge n%d-n%d", src_node->index, tgt_node->index); 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); @@ -198,7 +198,7 @@ static void simplify_edge(pbqp *pbqp, pbqp_edge *edge) if (pbqp->dump_file) { fputs("edge has been eliminated", pbqp->dump_file); - delete_edge(pbqp, edge); + delete_edge(edge); } } } @@ -270,7 +270,7 @@ void solve_pbqp_heuristical(pbqp *pbqp) pbqp_edge *edge = edges[edge_index]; /* Simplify only once per edge. */ - if (node_index != edge->src) continue; + if (node_index != edge->src->index) continue; simplify_edge(pbqp, edge); } @@ -308,7 +308,7 @@ void solve_pbqp_heuristical(pbqp *pbqp) 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); + dump_node(pbqp, node); } } @@ -345,50 +345,44 @@ void applyRI(pbqp *pbqp) 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; + int is_src = edge->src == node; + pbqp_node *other_node; if (is_src) { - my_index = edge->src; - other_index = edge->tgt; + other_node = edge->tgt; } else { - my_index = edge->tgt; - other_index = edge->src; + other_node = edge->src; } if (pbqp->dump_file) { char txt[100]; - sprintf(txt, "RI-Reduktion of Node n%d", my_index); + sprintf(txt, "RI-Reduktion of Node n%d", node->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_node(pbqp, node); + dump_node(pbqp, other_node); 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); dump_edge(pbqp, edge); normalize_towards_source(pbqp, edge); - disconnect_edge(src_node, edge); } + disconnect_edge(other_node, edge); if (pbqp->dump_file) { fputs("
\nAfter reduction:
\n", pbqp->dump_file); - dump_node(pbqp, other_index); + dump_node(pbqp, other_node); } /* Remove node from bucket... */ ARR_SHRINKLEN(bucket, (int)bucket_len - 1); - reorder_node(get_node(pbqp, other_index)); + reorder_node(other_node); /* ...and add it to back propagation list. */ ARR_APP1(pbqp_node *, reduced_bucket, node); @@ -407,15 +401,15 @@ void back_propagate_RI(pbqp *pbqp, pbqp_node *node) edge = node->edges[0]; mat = edge->costs; - is_src = get_node(pbqp, edge->src) == node; + is_src = edge->src == node; vec = node->costs; if (is_src) { - other = get_node(pbqp, edge->tgt); + other = edge->tgt; assert(other); vector_add_matrix_col(vec, mat, other->solution); } else { - other = get_node(pbqp, edge->src); + other = edge->src; assert(other); vector_add_matrix_row(vec, mat, other->solution); } diff --git a/html_dumper.c b/html_dumper.c index 0ec8f2c3d..bfa6dbd29 100644 --- a/html_dumper.c +++ b/html_dumper.c @@ -70,7 +70,7 @@ void dump_edge(pbqp *pbqp, pbqp_edge *edge) { fputs("\n", pbqp->dump_file); fprintf(pbqp->dump_file, "\t\\overline\n{C}_{%d,%d}=\n", - edge->src, edge->tgt); + edge->src->index, edge->tgt->index); dump_matrix(pbqp->dump_file, edge->costs); fputs("
", pbqp->dump_file); } @@ -93,7 +93,7 @@ static void dump_edge_costs(pbqp *pbqp) unsigned len = ARR_LEN(src_node->edges); for (edge_index = 0; edge_index < len; ++edge_index) { pbqp_edge *edge = src_node->edges[edge_index]; - unsigned tgt_index = edge->tgt; + unsigned tgt_index = edge->tgt->index; if (src_index < tgt_index) { dump_edge(pbqp, edge); } @@ -102,14 +102,13 @@ static void dump_edge_costs(pbqp *pbqp) fputs("

", pbqp->dump_file); } -void dump_node(pbqp *pbqp, unsigned index) +void dump_node(pbqp *pbqp, pbqp_node *node) { assert(pbqp); assert(pbqp->dump_file); - pbqp_node *node = get_node(pbqp, index); if (node) { - fprintf(pbqp->dump_file, "\tc%d = ", index); + fprintf(pbqp->dump_file, "\tc%d = ", node->index); dump_vector(pbqp->dump_file, node->costs); fputs("
\n", pbqp->dump_file); } @@ -125,7 +124,7 @@ static void dump_node_costs(pbqp *pbqp) /* dump node costs */ fputs("

", pbqp->dump_file); for (index = 0; index < pbqp->num_nodes; ++index) { - dump_node(pbqp, index); + dump_node(pbqp, get_node(pbqp, index)); } fputs("

", pbqp->dump_file); } @@ -161,7 +160,7 @@ void pbqp_dump_graph(pbqp *pbqp) unsigned len = ARR_LEN(node->edges); unsigned edge_index; for (edge_index = 0; edge_index < len; ++edge_index) { - unsigned tgt_index = node->edges[edge_index]->tgt; + unsigned tgt_index = node->edges[edge_index]->tgt->index; if (src_index < tgt_index) { fprintf(pbqp->dump_file, "\t n%d -- n%d;\n", src_index, diff --git a/html_dumper.h b/html_dumper.h index ef8b23c8a..dccb817b2 100644 --- a/html_dumper.h +++ b/html_dumper.h @@ -11,7 +11,7 @@ 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_node(pbqp *pbqp, pbqp_node *node); void dump_edge(pbqp *pbqp, pbqp_edge *edge); #endif /* KAPS_HTML_DUMPER_H */ diff --git a/kaps.c b/kaps.c index a33180361..3162c2413 100644 --- a/kaps.c +++ b/kaps.c @@ -30,7 +30,7 @@ pbqp_edge *get_edge(pbqp *pbqp, unsigned src_index, unsigned tgt_index) for (i = 0; i < len; ++i) { pbqp_edge *cur_edge = src_node->edges[i]; - if (cur_edge->tgt == tgt_index) { + if (cur_edge->tgt->index == tgt_index) { return cur_edge; } } diff --git a/pbqp_edge.c b/pbqp_edge.c index 754c5d8af..f12e2f0e6 100644 --- a/pbqp_edge.c +++ b/pbqp_edge.c @@ -41,22 +41,22 @@ pbqp_edge *alloc_edge(pbqp *pbqp, int src_index, int tgt_index, pbqp_matrix *cos * that it don't appear in the edge lists of the nodes. */ ARR_APP1(pbqp_edge *, src_node->edges, edge); - edge->src = src_index; + edge->src = src_node; ARR_APP1(pbqp_edge *, tgt_node->edges, edge); - edge->tgt = tgt_index; + edge->tgt = tgt_node; return edge; } -void delete_edge(pbqp *pbqp, pbqp_edge *edge) +void delete_edge(pbqp_edge *edge) { pbqp_node *src_node; pbqp_node *tgt_node; assert(edge); - src_node = get_node(pbqp, edge->src); - tgt_node = get_node(pbqp, edge->tgt); + src_node = edge->src; + tgt_node = edge->tgt; assert(src_node); assert(tgt_node); diff --git a/pbqp_edge.h b/pbqp_edge.h index 1ec4fb303..c10643584 100644 --- a/pbqp_edge.h +++ b/pbqp_edge.h @@ -5,6 +5,6 @@ pbqp_edge *alloc_edge(pbqp *pbqp, int src_index, int tgt_index, pbqp_matrix *costs); -void delete_edge(pbqp *pbqp, pbqp_edge *edge); +void delete_edge(pbqp_edge *edge); #endif /* KAPS_PBQP_EDGE_H */ diff --git a/pbqp_edge_t.h b/pbqp_edge_t.h index 4f1b3fdd3..0e043219f 100644 --- a/pbqp_edge_t.h +++ b/pbqp_edge_t.h @@ -4,9 +4,9 @@ #include "pbqp_t.h" struct pbqp_edge { - unsigned src; /* Source index. */ - unsigned tgt; /* Target index. */ - pbqp_matrix *costs; /* Cost matrix. */ + pbqp_node *src; /* Source index. */ + pbqp_node *tgt; /* Target index. */ + pbqp_matrix *costs; /* Cost matrix. */ }; #endif /* KAPS_PBQP_EDGE_T_H */ -- 2.20.1