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 node->bucket_index = ARR_LEN(node_buckets[arity]);
236 ARR_APP1(pbqp_node *, node_buckets[arity], node);
239 void solve_pbqp_heuristical(pbqp *pbqp)
246 if (pbqp->dump_file) {
247 pbqp_dump_input(pbqp);
248 dump_section(pbqp->dump_file, 1, "2. Simplification of Cost Matrices");
251 node_len = pbqp->num_nodes;
255 /* First simplify all edges. */
256 for (node_index = 0; node_index < node_len; ++node_index) {
258 pbqp_node *node = get_node(pbqp, node_index);
265 edge_len = ARR_LEN(edges);
267 for (edge_index = 0; edge_index < edge_len; ++edge_index) {
268 pbqp_edge *edge = edges[edge_index];
270 /* Simplify only once per edge. */
271 if (node_index != edge->src) continue;
273 simplify_edge(pbqp, edge);
277 /* Put node into bucket representing their arity. */
278 fill_node_buckets(pbqp);
281 if (ARR_LEN(edge_bucket) > 0) {
282 panic("Please implement edge simplification");
283 } else if (ARR_LEN(node_buckets[1]) > 0) {
285 } else if (ARR_LEN(node_buckets[2]) > 0) {
286 panic("Please implement RII simplification");
287 } else if (ARR_LEN(node_buckets[3]) > 0) {
288 panic("Please implement RN simplification");
290 panic("Please implement back propagation");
296 void applyRI(pbqp *pbqp)
298 pbqp_node **bucket = node_buckets[1];
299 unsigned bucket_len = ARR_LEN(bucket);
300 pbqp_node *node = bucket[bucket_len - 1];
301 pbqp_edge *edge = node->edges[0];
302 pbqp_matrix *mat = edge->costs;
303 int is_src = get_node(pbqp, edge->src) == node;
305 unsigned other_index;
308 my_index = edge->src;
309 other_index = edge->tgt;
311 my_index = edge->tgt;
312 other_index = edge->src;
315 if (pbqp->dump_file) {
317 sprintf(txt, "RI-Reduktion of Node n%d", my_index);
318 dump_section(pbqp->dump_file, 2, txt);
319 pbqp_dump_graph(pbqp);
320 fputs("<br>\nBefore reduction:<br>\n", pbqp->dump_file);
321 dump_node(pbqp, my_index);
322 dump_node(pbqp, other_index);
323 dump_edge(pbqp, edge);
327 pbqp_node *tgt_node = get_node(pbqp, edge->tgt);
328 pbqp_matrix_add_to_all_cols(mat, node->costs);
329 normalize_towards_target(pbqp, edge);
330 disconnect_edge(tgt_node, edge);
332 pbqp_node *src_node = get_node(pbqp, edge->src);
333 pbqp_matrix_add_to_all_rows(mat, node->costs);
334 normalize_towards_source(pbqp, edge);
335 disconnect_edge(src_node, edge);
338 if (pbqp->dump_file) {
339 fputs("<br>\nAfter reduction:<br>\n", pbqp->dump_file);
340 dump_node(pbqp, other_index);
343 ARR_SHRINKLEN(bucket, (int)bucket_len - 1);
344 reorder_node(get_node(pbqp, other_index));