From a9432653be2d89b257422ac8cb48d98bc8f2d376 Mon Sep 17 00:00:00 2001
From: Sebastian Buchwald <Sebastian.Buchwald@kit.edu>
Date: Mon, 1 Dec 2008 23:10:40 +0000
Subject: [PATCH] Started first attempt for brute force solver.

[r24212]
---
 bucket.c      | 16 +++++++++++
 heuristical.c | 75 +++++++++++++++++++++++++++++++++++++++++++++++++++
 pbqp_edge.c   |  5 ++++
 pbqp_node.c   | 19 +++++++++++++
 pbqp_node.h   |  2 ++
 5 files changed, 117 insertions(+)

diff --git a/bucket.c b/bucket.c
index 5d82275db..90e180f91 100644
--- a/bucket.c
+++ b/bucket.c
@@ -113,3 +113,19 @@ void node_bucket_remove(pbqp_node_bucket *bucket, pbqp_node *node)
 	ARR_SHRINKLEN(*bucket, (int)bucket_len - 1);
 	node->bucket_index = UINT_MAX;
 }
+
+pbqp_node_bucket *node_bucket_deep_copy(pbqp_node_bucket bucket)
+{
+	pbqp_node_bucket *copy;
+	unsigned          bucket_index;
+	unsigned          bucket_length;
+
+	node_bucket_init(copy);
+	bucket_length = node_bucket_get_length(bucket);
+
+	for (bucket_index = 0; bucket_index < bucket_length; ++bucket_index) {
+		node_bucket_insert(copy, pbqp_node_deep_copy(bucket[bucket_index]));
+	}
+
+	return copy;
+}
diff --git a/heuristical.c b/heuristical.c
index 97471439f..060315729 100644
--- a/heuristical.c
+++ b/heuristical.c
@@ -764,6 +764,81 @@ void apply_RN(pbqp *pbqp)
 	}
 }
 
+void apply_Brute_Force(pbqp *pbqp)
+{
+	pbqp_node  **bucket       = node_buckets[3];
+	unsigned     bucket_len   = node_bucket_get_length(bucket);
+	unsigned     bucket_index;
+	pbqp_node   *node         = NULL;
+	pbqp_edge   *edge;
+	vector      *node_vec;
+	vector      *vec;
+	pbqp_matrix *mat;
+	unsigned     edge_index;
+	unsigned     max_degree   = 0;
+	unsigned     node_index;
+	unsigned     node_len;
+	unsigned     min_index    = 0;
+	num          min          = INF_COSTS;
+	int          is_src;
+
+	assert(pbqp);
+
+	/* Search for node with maximum degree. */
+	for (bucket_index = 0; bucket_index < bucket_len; ++bucket_index) {
+		pbqp_node *candidate = bucket[bucket_index];
+		unsigned   degree    = pbqp_node_get_degree(candidate);
+
+		if (degree > max_degree) {
+			node = candidate;
+			max_degree = degree;
+		}
+	}
+	assert(node);
+	node_vec = node->costs;
+	node_len = node_vec->len;
+
+	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);
+	}
+
+	for (node_index = 0; node_index < node_len; ++node_index) {
+		num value = node_vec->entries[node_index].data;
+
+		/* TODO Copy PBQP */
+
+
+		if (value < min) {
+			min = value;
+			min_index = node_index;
+		}
+	}
+
+	if (pbqp->dump_file) {
+		fprintf(pbqp->dump_file, "node n%d is set to %d<br><br>\n",
+					node->index, min_index);
+		fprintf(pbqp->dump_file, "Minimal cost of RN reduction: %lld<br>\n",
+							min);
+	}
+
+	node->solution = min_index;
+
+	/* Now that we found the local minimum set all other costs to infinity. */
+	for (node_index = 0; node_index < node_len; ++node_index) {
+		if (node_index != min_index) {
+			node_vec->entries[node_index].data = INF_COSTS;
+		}
+	}
+
+	/* Add all incident edges to edge bucket, since they are now independent. */
+	for (edge_index = 0; edge_index < max_degree; ++edge_index) {
+		insert_into_edge_bucket(node->edges[edge_index]);
+	}
+}
+
 void back_propagate_RI(pbqp *pbqp, pbqp_node *node)
 {
 	pbqp_edge   *edge;
diff --git a/pbqp_edge.c b/pbqp_edge.c
index 610b53c0c..aeb4608b9 100644
--- a/pbqp_edge.c
+++ b/pbqp_edge.c
@@ -64,3 +64,8 @@ void delete_edge(pbqp_edge *edge)
 	disconnect_edge(src_node, edge);
 	disconnect_edge(tgt_node, edge);
 }
+
+pbqp_edge *pbqp_edge_deep_copy(pbqp *pbqp, pbqp_edge *edge)
+{
+	return alloc_edge(pbqp, edge->src->index, edge->tgt->index, edge->costs);
+}
diff --git a/pbqp_node.c b/pbqp_node.c
index 8716a7839..b4aaae67b 100644
--- a/pbqp_node.c
+++ b/pbqp_node.c
@@ -69,3 +69,22 @@ unsigned pbqp_node_get_degree(pbqp_node *node)
 	assert(node);
 	return ARR_LEN(node->edges);
 }
+
+pbqp_node *pbqp_node_deep_copy(pbqp *pbqp, pbqp_node *node)
+{
+	unsigned   edge_index;
+	unsigned   edge_length = pbqp_node_get_degree(node);
+	pbqp_node *copy        = obstack_alloc(&pbqp->obstack, sizeof(*node));
+	assert(copy);
+
+	for (edge_index = 0; edge_index < edge_length; ++edge_index) {
+		copy->edges[edge_index] = pbqp_edge_deep_copy(node->edges[edge_index]);
+	}
+	copy->edges        = NEW_ARR_F(pbqp_edge *, 0);
+	copy->costs        = vector_copy(pbqp, node->costs);
+	copy->bucket_index = node->bucket_index;
+	copy->solution     = node->solution;
+	copy->index   = node->index;
+
+	return node;
+}
diff --git a/pbqp_node.h b/pbqp_node.h
index af3aec2cd..29939dac1 100644
--- a/pbqp_node.h
+++ b/pbqp_node.h
@@ -11,4 +11,6 @@ int is_connected(pbqp_node *node, pbqp_edge *edge);
 
 unsigned pbqp_node_get_degree(pbqp_node *node);
 
+pbqp_node *pbqp_node_deep_copy(pbqp *pbqp, pbqp_node *node);
+
 #endif /* KAPS_PBQP_NODE_H */
-- 
2.20.1