From d01193ed5f4474a0f51b2b8dd809f5b39ac9b722 Mon Sep 17 00:00:00 2001
From: Sebastian Buchwald <Sebastian.Buchwald@kit.edu>
Date: Thu, 2 Oct 2008 18:41:41 +0000
Subject: [PATCH] Started implementing a new PBQP solver, which should solve
 PBQPs and the problems/bugs of the Scholz solver.

[r22420]
---
 heuristical.c |  0
 heuristical.h | 16 ++++++++++++++++
 kaps.c        | 35 +++++++++++++++++++++++++++++++++++
 kaps.h        | 26 ++++++++++++++++++++++++++
 matrix.c      |  0
 matrix.h      |  0
 matrix_t.h    | 13 +++++++++++++
 pbqp_edge.c   |  0
 pbqp_edge.h   |  0
 pbqp_edge_t.h | 12 ++++++++++++
 pbqp_node.c   | 18 ++++++++++++++++++
 pbqp_node.h   |  8 ++++++++
 pbqp_node_t.h | 11 +++++++++++
 pbqp_t.h      | 23 +++++++++++++++++++++++
 vector.c      | 36 ++++++++++++++++++++++++++++++++++++
 vector.h      | 10 ++++++++++
 vector_t.h    | 12 ++++++++++++
 17 files changed, 220 insertions(+)
 create mode 100644 heuristical.c
 create mode 100644 heuristical.h
 create mode 100644 kaps.c
 create mode 100644 kaps.h
 create mode 100644 matrix.c
 create mode 100644 matrix.h
 create mode 100644 matrix_t.h
 create mode 100644 pbqp_edge.c
 create mode 100644 pbqp_edge.h
 create mode 100644 pbqp_edge_t.h
 create mode 100644 pbqp_node.c
 create mode 100644 pbqp_node.h
 create mode 100644 pbqp_node_t.h
 create mode 100644 pbqp_t.h
 create mode 100644 vector.c
 create mode 100644 vector.h
 create mode 100644 vector_t.h

diff --git a/heuristical.c b/heuristical.c
new file mode 100644
index 000000000..e69de29bb
diff --git a/heuristical.h b/heuristical.h
new file mode 100644
index 000000000..5ff812d11
--- /dev/null
+++ b/heuristical.h
@@ -0,0 +1,16 @@
+#ifndef KAPS_HEURISTICAL_H
+#define KAPS_HEURISTICAL_H
+
+#include "pbqp_t.h"
+
+/**
+ * Create an empty PBQP instance with the given number of nodes.
+ */
+pbqp* alloc_pbqp(int number_nodes);
+
+/**
+ * Free the given PBQP.
+ */
+void free_pbqp(pbqp *pbqp);
+
+#endif /* KAPS_HEURISTICAL_H */
diff --git a/kaps.c b/kaps.c
new file mode 100644
index 000000000..0729fbe67
--- /dev/null
+++ b/kaps.c
@@ -0,0 +1,35 @@
+#include "kaps.h"
+
+static pbqp_node *get_node(pbqp *pbqp, int index)
+{
+	return pbqp->nodes[index];
+}
+
+pbqp *alloc_pbqp(int number_nodes)
+{
+	pbqp* pbqp = xmalloc(sizeof(*pbqp));
+
+	obstack_init(&pbqp->obstack);
+
+	pbqp->solution = 0;
+	pbqp->num_nodes = number_nodes;
+	pbqp->nodes = obstack_alloc(&pbqp->obstack, number_nodes
+			* sizeof(*pbqp->nodes));
+}
+
+void free_pbqp(pbqp *pbqp)
+{
+	obstack_free(&pbqp->obstack, NULL);
+	xfree(pbqp);
+}
+
+void add_node_costs(pbqp *pbqp, int node_index, vector *costs)
+{
+	pbqp_node *node = get_node(pbqp, node_index);
+
+	if (node == NULL) {
+		node = alloc_node(pbqp, costs);
+	} else {
+		vector_add(node->costs, costs);
+	}
+}
diff --git a/kaps.h b/kaps.h
new file mode 100644
index 000000000..ac50f08ef
--- /dev/null
+++ b/kaps.h
@@ -0,0 +1,26 @@
+#ifndef KAPS_KAPS_H
+#define KAPS_KAPS_H
+
+#include "pbqp_t.h"
+
+/**
+ * Create an empty PBQP instance with the given number of nodes.
+ */
+pbqp* alloc_pbqp(int number_nodes);
+
+/**
+ * Free the given PBQP.
+ */
+void free_pbqp(pbqp *pbqp);
+
+/**
+ * Add costs vector to given node.
+ */
+void add_node_costs(pbqp *pbqp, int node_index, vector *costs);
+
+/**
+ * Add costs matrix between given nodes.
+ */
+void add_edge_costs(pbqp *pbqp, int src_index, int tgt_index, matrix *costs);
+
+#endif /* KAPS_KAPS_H */
diff --git a/matrix.c b/matrix.c
new file mode 100644
index 000000000..e69de29bb
diff --git a/matrix.h b/matrix.h
new file mode 100644
index 000000000..e69de29bb
diff --git a/matrix_t.h b/matrix_t.h
new file mode 100644
index 000000000..38ee3b84a
--- /dev/null
+++ b/matrix_t.h
@@ -0,0 +1,13 @@
+#ifndef KAPS_MATRIX_T_H
+#define KAPS_MATRIX_T_H
+
+struct matrix;
+typedef struct matrix matrix;
+
+struct matrix {
+	int rows;
+	int cols;
+	num entries[];
+};
+
+#endif /* KAPS_MATRIX_T_H */
diff --git a/pbqp_edge.c b/pbqp_edge.c
new file mode 100644
index 000000000..e69de29bb
diff --git a/pbqp_edge.h b/pbqp_edge.h
new file mode 100644
index 000000000..e69de29bb
diff --git a/pbqp_edge_t.h b/pbqp_edge_t.h
new file mode 100644
index 000000000..955774238
--- /dev/null
+++ b/pbqp_edge_t.h
@@ -0,0 +1,12 @@
+#ifndef KAPS_PBQP_EDGE_T_H
+#define KAPS_PBQP_EDGE_T_H
+
+#include "pbqp_t.h"
+
+struct pbqp_edge {
+	pbqp_node *src;                    /* Source node. */
+	pbqp_node *tgt;                    /* Target node. */
+	matrix *costs;                     /* Cost matrix. */
+};
+
+#endif /* KAPS_PBQP_EDGE_T_H */
diff --git a/pbqp_node.c b/pbqp_node.c
new file mode 100644
index 000000000..4b6a3bedc
--- /dev/null
+++ b/pbqp_node.c
@@ -0,0 +1,18 @@
+#include "adt/array.h"
+
+#include "assert.h"
+
+#include "pbqp_node.h"
+#include "pbqp_node_t.h"
+#include "vector.h"
+
+pbqp_node *alloc_node(pbqp *pbqp, vector *costs)
+{
+	pbqp_node *node = obstack_alloc(&pbqp->obstack, sizeof(*node));
+	assert(node);
+
+	node->edges = NEW_ARR_F(pbqp_edge *, 0);
+	node->costs = vector_copy(costs);
+
+	return node;
+}
diff --git a/pbqp_node.h b/pbqp_node.h
new file mode 100644
index 000000000..4c82ddb1b
--- /dev/null
+++ b/pbqp_node.h
@@ -0,0 +1,8 @@
+#ifndef KAPS_PBQP_NODE_H
+#define KAPS_PBQP_NODE_H
+
+#include "pbqp_t.h"
+
+pbqp_node *alloc_node(pbqp *pbqp, vector *costs);
+
+#endif /* KAPS_PBQP_NODE_H */
diff --git a/pbqp_node_t.h b/pbqp_node_t.h
new file mode 100644
index 000000000..40b17de86
--- /dev/null
+++ b/pbqp_node_t.h
@@ -0,0 +1,11 @@
+#ifndef KAPS_PBQP_NODE_T_H
+#define KAPS_PBQP_NODE_T_H
+
+#include "pbqp_t.h"
+
+struct pbqp_node {
+	pbqp_edge **edges;
+	vector *costs;
+};
+
+#endif /* KAPS_PBQP_NODE_T_H */
diff --git a/pbqp_t.h b/pbqp_t.h
new file mode 100644
index 000000000..bb8a34c9c
--- /dev/null
+++ b/pbqp_t.h
@@ -0,0 +1,23 @@
+#ifndef KAPS_PBQP_T_H
+#define KAPS_PBQP_T_H
+
+#include <limits.h>
+
+#include "matrix_t.h"
+#include "vector_t.h"
+
+typedef int num;
+
+typedef struct pbqp_edge pbqp_edge;
+typedef struct pbqp_node pbqp_node;
+
+static const num INF_COST = INT_MAX;
+
+struct pbqp {
+	struct obstack obstack;            /* Obstack. */
+	num            solution;           /* Computed solution. */
+	size_t         num_nodes;          /* Number of PBQP nodes. */
+	pbqp_node    **nodes;              /* Nodes of PBQP. */
+};
+
+#endif /* KAPS_PBQP_T_H */
diff --git a/vector.c b/vector.c
new file mode 100644
index 000000000..e4456a82d
--- /dev/null
+++ b/vector.c
@@ -0,0 +1,36 @@
+#include "adt/array.h"
+
+#include "vector.h"
+
+vector *vector_copy(pbqp *pbqp, vector *v)
+{
+	int i;
+	int len;
+	vector *copy = obstack_alloc(pbqp->obstack, sizeof(*copy));
+
+	assert(copy);
+
+	len = v->len;
+
+	for (i = 0; i < len; ++i) {
+		copy->entries[i] = v->entries[i];
+	}
+
+	return copy;
+}
+
+void vector_add(vector *sum, vector *summand)
+{
+	int i;
+	int len;
+
+	assert(sum);
+	assert(summand);
+	assert(sum->len == summand->len);
+
+	len = sum->len;
+
+	for (i = 0; i < len; ++i) {
+		sum->entries[i] += summand->entries[i];
+	}
+}
diff --git a/vector.h b/vector.h
new file mode 100644
index 000000000..05855d8e2
--- /dev/null
+++ b/vector.h
@@ -0,0 +1,10 @@
+#ifndef KAPS_VECTOR_H
+#define KAPS_VECTOR_H
+
+/* Copy the given vector. */
+vector *vector_copy(vector *v);
+
+/* sum += summand */
+void vector_add(vector *sum, vector *summand);
+
+#endif KAPS_VECTOR_H
diff --git a/vector_t.h b/vector_t.h
new file mode 100644
index 000000000..9d6a93c51
--- /dev/null
+++ b/vector_t.h
@@ -0,0 +1,12 @@
+#ifndef KAPS_VECTOR_T_H
+#define KAPS_VECTOR_T_H
+
+struct vector;
+typedef struct vector vector;
+
+struct vector {
+	int len;
+	num entries[];
+};
+
+#endif /* KAPS_VECTOR_T_H */
-- 
2.20.1