From 1283da4c4ed446a9474d403d7b3b9b9d69578fee Mon Sep 17 00:00:00 2001
From: Thomas Bersch <bersch@ipd.info.uni-karlsruhe.de>
Date: Fri, 18 Sep 2009 12:36:49 +0000
Subject: [PATCH] solve function which follows a reverse perfect elimination
 order

[r26546]
---
 heuristical.c | 110 ++++++++++++++++++++++++++++++++++++++++++++++++++
 heuristical.h |   4 ++
 2 files changed, 114 insertions(+)

diff --git a/heuristical.c b/heuristical.c
index 98e7c4b2a..e054c00c1 100644
--- a/heuristical.c
+++ b/heuristical.c
@@ -15,6 +15,8 @@
 #include "pbqp_node_t.h"
 #include "vector.h"
 
+#include "plist.h"
+
 static pbqp_edge **edge_bucket;
 static pbqp_node **node_buckets[4];
 static pbqp_node **reduced_bucket = NULL;
@@ -555,6 +557,25 @@ static void apply_heuristic_reductions(pbqp *pbqp)
 	}
 }
 
+static void apply_heuristic_reductions_co(pbqp *pbqp, plist_t *rpeo)
+{
+	for (;;) {
+		if (edge_bucket_get_length(edge_bucket) > 0) {
+			apply_edge(pbqp);
+		} else if (node_bucket_get_length(node_buckets[1]) > 0) {
+			apply_RI(pbqp);
+//			apply_RN_co(pbqp, rpeo);
+		} else if (node_bucket_get_length(node_buckets[2]) > 0) {
+			apply_RII(pbqp);
+//			apply_RN_co(pbqp, rpeo);
+		} else if (node_bucket_get_length(node_buckets[3]) > 0) {
+			apply_RN_co(pbqp, rpeo);
+		} else {
+			return;
+		}
+	}
+}
+
 void solve_pbqp_heuristical(pbqp *pbqp)
 {
 	/* Reduce nodes degree ... */
@@ -587,6 +608,37 @@ void solve_pbqp_heuristical(pbqp *pbqp)
 	free_buckets();
 }
 
+void solve_pbqp_heuristical_co(pbqp *pbqp, plist_t *rpeo) {
+	/* Reduce nodes degree ... */
+		initial_simplify_edges(pbqp);
+
+		/* ... and put node into bucket representing their degree. */
+		fill_node_buckets(pbqp);
+
+	#if KAPS_STATISTIC
+		FILE *fh = fopen("solutions.pb", "a");
+		fprintf(fh, "Solution");
+		fclose(fh);
+	#endif
+
+		apply_heuristic_reductions_co(pbqp, rpeo);
+
+		pbqp->solution = determine_solution(pbqp);
+
+	#if KAPS_STATISTIC
+		fh = fopen("solutions.pb", "a");
+		fprintf(fh, ": %lld RE:%u R0:%u R1:%u R2:%u RN/BF:%u\n", pbqp->solution,
+					pbqp->num_edges, pbqp->num_r0, pbqp->num_r1, pbqp->num_r2,
+					pbqp->num_rn);
+		fclose(fh);
+	#endif
+
+		/* Solve reduced nodes. */
+		back_propagate(pbqp);
+
+		free_buckets();
+}
+
 void apply_edge(pbqp *pbqp)
 {
 	pbqp_edge *edge = edge_bucket_pop(&edge_bucket);
@@ -892,6 +944,8 @@ static unsigned get_local_minimal_alternative(pbqp *pbqp, pbqp_node *node)
 
 void apply_RN(pbqp *pbqp)
 {
+//	printf("### ---- RN\n");
+
 	pbqp_node   *node         = NULL;
 	unsigned     min_index    = 0;
 
@@ -933,6 +987,62 @@ void apply_RN(pbqp *pbqp)
 	select_alternative(node, min_index);
 }
 
+void apply_RN_co(pbqp *pbqp, plist_t *rpeo)
+{
+//	printf("### ---- RN\n");
+
+	pbqp_node   *node         = NULL;
+	unsigned     min_index    = 0;
+
+	assert(pbqp);
+
+	/* We want to reduce the first node in reverse perfect elimination order. */
+	do {
+		/* get first element from reverse perfect elimination order */
+		node = plist_first(rpeo)->data;
+		/* remove element from reverse perfect elimination order */
+		plist_erase(rpeo, plist_first(rpeo));
+	} while(node_is_reduced(node));
+
+//	node = plist_first(rpeo)->data;
+//	plist_erase(rpeo, plist_first(rpeo));
+
+	assert(node);
+	assert(pbqp_node_get_degree(node) > 2);
+
+#if	KAPS_DUMP
+	if (pbqp->dump_file) {
+		char     txt[100];
+		sprintf(txt, "RN-Reduction of Node n%d", node->index);
+		dump_section(pbqp->dump_file, 2, txt);
+		pbqp_dump_graph(pbqp);
+	}
+#endif
+
+	min_index = get_local_minimal_alternative(pbqp, node);
+
+#if	KAPS_DUMP
+	if (pbqp->dump_file) {
+		fprintf(pbqp->dump_file, "node n%d is set to %d<br><br>\n",
+					node->index, min_index);
+	}
+#endif
+
+#if KAPS_STATISTIC
+	if (dump == 0) {
+		FILE *fh = fopen("solutions.pb", "a");
+		fprintf(fh, "[%u]", min_index);
+		fclose(fh);
+		pbqp->num_rn++;
+	}
+#endif
+
+	/* Now that we found the local minimum set all other costs to infinity. */
+	select_alternative(node, min_index);
+
+
+}
+
 static void apply_brute_force_reductions(pbqp *pbqp)
 {
 	for (;;) {
diff --git a/heuristical.h b/heuristical.h
index 8cc9ab691..195ad23e1 100644
--- a/heuristical.h
+++ b/heuristical.h
@@ -3,7 +3,10 @@
 
 #include "pbqp_t.h"
 
+#include "plist.h"
+
 void solve_pbqp_heuristical(pbqp *pbqp);
+void solve_pbqp_heuristical_co(pbqp *pbqp, plist_t *rpeo);
 void solve_pbqp_brute_force(pbqp *pbqp);
 
 void apply_edge(pbqp *pbqp);
@@ -11,6 +14,7 @@ void apply_edge(pbqp *pbqp);
 void apply_RI(pbqp *pbqp);
 void apply_RII(pbqp *pbqp);
 void apply_RN(pbqp *pbqp);
+void apply_RN_co(pbqp *pbqp, plist_t *rpeo);
 
 void back_propagate_RI(pbqp *pbqp, pbqp_node *node);
 void back_propagate_RII(pbqp *pbqp, pbqp_node *node);
-- 
2.20.1