5 #include "heuristical.h"
6 #include "html_dumper.h"
10 #include "pbqp_edge_t.h"
11 #include "pbqp_node.h"
12 #include "pbqp_node_t.h"
15 static pbqp_edge **edge_bucket;
16 static pbqp_node **node_buckets[4];
18 static void init_buckets(void)
22 edge_bucket = NEW_ARR_F(pbqp_edge *, 0);
24 for (i = 0; i < 4; ++i) {
25 node_buckets[i] = NEW_ARR_F(pbqp_node *, 0);
29 static void fill_node_buckets(pbqp *pbqp)
35 node_len = pbqp->num_nodes;
37 for (node_index = 0; node_index < node_len; ++node_index) {
39 pbqp_node *node = get_node(pbqp, node_index);
43 arity = ARR_LEN(node->edges);
45 /* We have only one bucket for nodes with arity >= 3. */
50 node->bucket_index = ARR_LEN(node_buckets[arity]);
52 ARR_APP1(pbqp_node *, node_buckets[arity], node);
56 static void normalize_towards_source(pbqp *pbqp, pbqp_edge *edge)
70 src_node = get_node(pbqp, edge->src);
71 tgt_node = get_node(pbqp, edge->tgt);
75 src_vec = src_node->costs;
76 tgt_vec = tgt_node->costs;
80 src_len = src_vec->len;
81 tgt_len = tgt_vec->len;
88 /* Normalize towards source node. */
89 for (src_index = 0; src_index < src_len; ++src_index) {
90 num min = pbqp_matrix_get_row_min(mat, src_index, tgt_vec);
93 pbqp_matrix_sub_row_value(mat, src_index, tgt_vec, min);
94 vector_add_value(src_vec, min);
96 // TODO add to edge_list if inf
101 static void normalize_towards_target(pbqp *pbqp, pbqp_edge *edge)
115 src_node = get_node(pbqp, edge->src);
116 tgt_node = get_node(pbqp, edge->tgt);
120 src_vec = src_node->costs;
121 tgt_vec = tgt_node->costs;
125 src_len = src_vec->len;
126 tgt_len = tgt_vec->len;
133 for (tgt_index = 0; tgt_index < tgt_len; ++tgt_index) {
134 num min = pbqp_matrix_get_col_min(mat, tgt_index, src_vec);
137 pbqp_matrix_sub_col_value(mat, tgt_index, src_vec, min);
138 vector_add_value(tgt_vec, min);
140 // TODO add to edge_list if inf
145 static void simplify_edge(pbqp *pbqp, pbqp_edge *edge)
158 if(pbqp->dump_file) {
160 sprintf(txt, "Simplification of Edge n%d-n%d", edge->src, edge->tgt);
161 dump_section(pbqp->dump_file, 3, txt);
164 src_node = get_node(pbqp, edge->src);
165 tgt_node = get_node(pbqp, edge->tgt);
169 src_vec = src_node->costs;
170 tgt_vec = tgt_node->costs;
174 src_len = src_vec->len;
175 tgt_len = tgt_vec->len;
182 if (pbqp->dump_file) {
183 fputs("Input:<br>\n", pbqp->dump_file);
184 dump_simplifyedge(pbqp, edge);
187 normalize_towards_source(pbqp, edge);
188 normalize_towards_target(pbqp, edge);
190 if (pbqp->dump_file) {
191 fputs("<br>\nOutput:<br>\n", pbqp->dump_file);
192 dump_simplifyedge(pbqp, edge);
195 if (pbqp_matrix_is_zero(mat, src_vec, tgt_vec)) {
196 if (pbqp->dump_file) {
197 fputs("edge has been eliminated", pbqp->dump_file);
199 delete_edge(pbqp, edge);
204 static void reorder_node(pbqp_node *node)
208 unsigned old_bucket_len;
212 arity = ARR_LEN(node->edges);
214 /* Equal bucket as before */
215 if (arity > 2) return;
217 /* Assume node lost one incident edge. */
218 old_arity = arity + 1;
220 if (ARR_LEN(node_buckets[old_arity]) <= (int)node->bucket_index
221 || node_buckets[old_arity][node->bucket_index] != node) {
222 /* Old arity is new arity, so we have nothing to do. */
226 old_bucket_len = ARR_LEN(node_buckets[old_arity]);
227 assert (node_buckets[old_arity][node->bucket_index] == node);
229 /* Delete node from old bucket... */
230 node_buckets[old_arity][node->bucket_index]
231 = node_buckets[old_arity][old_bucket_len - 1];
232 ARR_SHRINKLEN(node_buckets[old_arity], (int)old_bucket_len - 1);
234 /* ..and add to new one. */
235 ARR_APP1(pbqp_node *, node_buckets[arity], node);
238 void solve_pbqp_heuristical(pbqp *pbqp)
245 if (pbqp->dump_file) {
246 pbqp_dump_input(pbqp);
247 dump_section(pbqp->dump_file, 1, "2. Simplification of Cost Matrices");
250 node_len = pbqp->num_nodes;
254 /* First simplify all edges. */
255 for (node_index = 0; node_index < node_len; ++node_index) {
257 pbqp_node *node = get_node(pbqp, node_index);
264 edge_len = ARR_LEN(edges);
266 for (edge_index = 0; edge_index < edge_len; ++edge_index) {
267 pbqp_edge *edge = edges[edge_index];
269 /* Simplify only once per edge. */
270 if (node_index != edge->src) continue;
272 simplify_edge(pbqp, edge);
276 /* Put node into bucket representing their arity. */
277 fill_node_buckets(pbqp);
280 if (ARR_LEN(edge_bucket) > 0) {
281 panic("Please implement edge simplification");
282 } else if (ARR_LEN(node_buckets[1]) > 0) {
284 } else if (ARR_LEN(node_buckets[2]) > 0) {
285 panic("Please implement RII simplification");
286 } else if (ARR_LEN(node_buckets[3]) > 0) {
287 panic("Please implement RN simplification");
289 panic("Please implement back propagation");
295 void applyRI(pbqp *pbqp)
297 pbqp_node **bucket = node_buckets[1];
298 unsigned bucket_len = ARR_LEN(bucket);
299 pbqp_node *node = bucket[bucket_len - 1];
300 pbqp_edge *edge = node->edges[0];
301 pbqp_matrix *mat = edge->costs;
302 int is_src = get_node(pbqp, edge->src) == node;
304 unsigned other_index;
307 my_index = edge->src;
308 other_index = edge->tgt;
310 my_index = edge->tgt;
311 other_index = edge->src;
314 if (pbqp->dump_file) {
316 sprintf(txt, "RI-Reduktion of Node n%d", my_index);
317 dump_section(pbqp->dump_file, 2, txt);
318 pbqp_dump_graph(pbqp);
319 fputs("<br>\nBefore reduction:<br>\n", pbqp->dump_file);
320 dump_node(pbqp, my_index);
321 dump_node(pbqp, other_index);
322 dump_edge(pbqp, edge);
326 pbqp_node *tgt_node = get_node(pbqp, edge->tgt);
327 pbqp_matrix_add_to_all_cols(mat, node->costs);
328 normalize_towards_target(pbqp, edge);
329 disconnect_edge(tgt_node, edge);
331 pbqp_node *src_node = get_node(pbqp, edge->src);
332 pbqp_matrix_add_to_all_rows(mat, node->costs);
333 normalize_towards_source(pbqp, edge);
334 disconnect_edge(src_node, edge);
337 if (pbqp->dump_file) {
338 fputs("<br>\nAfter reduction:<br>\n", pbqp->dump_file);
339 dump_node(pbqp, other_index);
342 ARR_SHRINKLEN(bucket, (int)bucket_len - 1);
343 reorder_node(get_node(pbqp, other_index));