From ef0bfb331d2e274f35d1cbc36bd0e7dabcdc83bd Mon Sep 17 00:00:00 2001
From: Sebastian Buchwald <Sebastian.Buchwald@kit.edu>
Date: Sun, 25 Jul 2010 19:30:43 +0000
Subject: [PATCH] RM should work now, theoretically.

[r27810]
---
 heuristical_co.c | 10 ++++-----
 optimal.c        | 55 ++++++++++++++++++++++++++++++++++++++++++++++++
 optimal.h        |  1 +
 3 files changed, 61 insertions(+), 5 deletions(-)

diff --git a/heuristical_co.c b/heuristical_co.c
index d5eb0f401..b1db7936b 100644
--- a/heuristical_co.c
+++ b/heuristical_co.c
@@ -75,12 +75,12 @@ static void apply_RN_co(pbqp *pbqp, plist_t *rpeo)
 		pbqp_dump_graph(pbqp);
 	}
 #endif
-#if KAPS_STATISTIC
 	/* Check whether we can merge a neighbor into the current node. */
-	for (min_index = 0; min_index < pbqp_node_get_degree(node); ++min_index) {
-		check_melting_possibility(pbqp, node->edges[min_index]);
-	}
-#endif
+	apply_RM(pbqp, node);
+
+	/* Apply optimal solution for the given node, if possible. */
+	if (pbqp_node_get_degree(node) < 3)
+		return;
 
 	min_index = get_local_minimal_alternative(pbqp, node);
 
diff --git a/optimal.c b/optimal.c
index c4af9aabd..cb4ef75fe 100644
--- a/optimal.c
+++ b/optimal.c
@@ -47,6 +47,7 @@
 #include "timing.h"
 
 pbqp_edge **edge_bucket;
+pbqp_edge **rm_bucket;
 pbqp_node **node_buckets[4];
 pbqp_node **reduced_bucket = NULL;
 static int         buckets_filled = 0;
@@ -61,11 +62,22 @@ static void insert_into_edge_bucket(pbqp_edge *edge)
 	edge_bucket_insert(&edge_bucket, edge);
 }
 
+static void insert_into_rm_bucket(pbqp_edge *edge)
+{
+	if (edge_bucket_contains(rm_bucket, edge)) {
+		/* Edge is already inserted. */
+		return;
+	}
+
+	edge_bucket_insert(&rm_bucket, edge);
+}
+
 static void init_buckets(void)
 {
 	int i;
 
 	edge_bucket_init(&edge_bucket);
+	edge_bucket_init(&rm_bucket);
 	node_bucket_init(&reduced_bucket);
 
 	for (i = 0; i < 4; ++i) {
@@ -82,6 +94,7 @@ void free_buckets(void)
 	}
 
 	edge_bucket_free(&edge_bucket);
+	edge_bucket_free(&rm_bucket);
 	node_bucket_free(&reduced_bucket);
 
 	buckets_filled = 0;
@@ -322,6 +335,7 @@ static void merge_source_into_target(pbqp *pbqp, pbqp_edge *edge)
 	/* Reconnect the source's edges with the target node. */
 	for (edge_index = 0; edge_index < edge_len; ++edge_index) {
 		pbqp_edge   *old_edge = src_node->edges[edge_index];
+		pbqp_edge   *new_edge;
 		pbqp_matrix *old_matrix;
 		pbqp_matrix *new_matrix;
 		pbqp_node   *other_node;
@@ -374,6 +388,9 @@ static void merge_source_into_target(pbqp *pbqp, pbqp_edge *edge)
 
 		disconnect_edge(src_node, old_edge);
 		disconnect_edge(other_node, old_edge);
+
+		new_edge = get_edge(pbqp, tgt_node->index, other_node->index);
+		insert_into_rm_bucket(new_edge);
 	}
 
 	/* Reduce the remaining source node via RI. */
@@ -461,6 +478,7 @@ static void merge_target_into_source(pbqp *pbqp, pbqp_edge *edge)
 	/* Reconnect the target's edges with the source node. */
 	for (edge_index = 0; edge_index < edge_len; ++edge_index) {
 		pbqp_edge   *old_edge = tgt_node->edges[edge_index];
+		pbqp_edge   *new_edge;
 		pbqp_matrix *old_matrix;
 		pbqp_matrix *new_matrix;
 		pbqp_node   *other_node;
@@ -513,12 +531,49 @@ static void merge_target_into_source(pbqp *pbqp, pbqp_edge *edge)
 
 		disconnect_edge(tgt_node, old_edge);
 		disconnect_edge(other_node, old_edge);
+
+		new_edge = get_edge(pbqp, src_node->index, other_node->index);
+		insert_into_rm_bucket(new_edge);
 	}
 
 	/* Reduce the remaining source node via RI. */
 	apply_RI(pbqp);
 }
 
+/**
+ * Merge neighbors into the given node.
+ */
+void apply_RM(pbqp *pbqp, pbqp_node *node)
+{
+	pbqp_edge **edges;
+	unsigned    edge_index;
+	unsigned    edge_len;
+
+	assert(node);
+	assert(pbqp);
+
+	edges    = node->edges;
+	edge_len = pbqp_node_get_degree(node);
+
+	/* Check all incident edges. */
+	for (edge_index = 0; edge_index < edge_len; ++edge_index) {
+		pbqp_edge *edge = edges[edge_index];
+
+		insert_into_rm_bucket(edge);
+	}
+
+	/* ALAP: Merge neighbors into given node. */
+	while(edge_bucket_get_length(rm_bucket) > 0) {
+		pbqp_edge *edge = edge_bucket_pop(&rm_bucket);
+		assert(edge);
+
+		if (edge->src == node)
+			merge_target_into_source(pbqp, edge);
+		else
+			merge_source_into_target(pbqp, edge);
+	}
+}
+
 void reorder_node(pbqp_node *node)
 {
 	unsigned    degree     = pbqp_node_get_degree(node);
diff --git a/optimal.h b/optimal.h
index db4f4f5f7..3d130427c 100644
--- a/optimal.h
+++ b/optimal.h
@@ -37,6 +37,7 @@ void apply_edge(pbqp *pbqp);
 
 void apply_RI(pbqp *pbqp);
 void apply_RII(pbqp *pbqp);
+void apply_RM(pbqp *pbqp, pbqp_node *node);
 
 void back_propagate(pbqp *pbqp);
 num determine_solution(pbqp *pbqp);
-- 
2.20.1