From fbd599cd8453b43d1e1aded3d29fd5e1d7023539 Mon Sep 17 00:00:00 2001
From: Sebastian Hack <hack@ipd.info.uni-karlsruhe.de>
Date: Fri, 27 Jan 2006 17:20:29 +0000
Subject: [PATCH] Added bipartite graphs

[r7281]
---
 ir/adt/bipartite.c | 134 +++++++++++++++++++++++++++++++++++++++++++++
 ir/adt/bipartite.h |  25 +++++++++
 2 files changed, 159 insertions(+)
 create mode 100644 ir/adt/bipartite.c
 create mode 100644 ir/adt/bipartite.h

diff --git a/ir/adt/bipartite.c b/ir/adt/bipartite.c
new file mode 100644
index 000000000..a633154ef
--- /dev/null
+++ b/ir/adt/bipartite.c
@@ -0,0 +1,134 @@
+
+#include <stdio.h>
+#include <assert.h>
+
+#include "bitset.h"
+#include "bipartite.h"
+
+struct _bipartite_t {
+	int n_left, n_right;
+	bitset_t **adj;
+};
+
+bipartite_t *bipartite_new(int n_left, int n_right)
+{
+	int i;
+	bipartite_t *gr = malloc(sizeof(*gr));
+	memset(gr, 0, sizeof(*gr));
+
+	gr->n_left = n_left;
+	gr->n_right = n_right;
+	gr->adj = malloc(n_left * sizeof(void *));
+
+	for(i = 0; i < n_left; ++i)
+		gr->adj[i] = bitset_malloc(n_right);
+
+	return gr;
+}
+
+void bipartite_free(bipartite_t *gr)
+{
+	int i;
+	for(i = 0; i < gr->n_left; ++i)
+		bitset_free(gr->adj[i]);
+
+	free(gr->adj);
+	free(gr);
+}
+
+void bipartite_add(bipartite_t *gr, int i, int j)
+{
+	assert(i < gr->n_left && j < gr->n_right);
+	bitset_set(gr->adj[i], j);
+}
+
+void bipartite_remv(bipartite_t *gr, int i, int j)
+{
+	assert(i < gr->n_left && j < gr->n_right);
+	bitset_clear(gr->adj[i], j);
+}
+
+int bipartite_adj(const bipartite_t *gr, int i, int j)
+{
+	assert(i < gr->n_left && j < gr->n_right);
+	return bitset_is_set(gr->adj[i], j);
+}
+
+static int apply_alternating_path(const bipartite_t *gr, int *matching,
+		bitset_t *matched_left, bitset_t *matched_right)
+{
+	int left, right;
+	int done_something = 0;
+	bitset_t *tmp = bitset_malloc(gr->n_left);
+
+	for(left = 0; left < gr->n_left; ++left) {
+		bitset_t *left_adj = gr->adj[left];
+		int i;
+
+		bitset_copy(tmp, left_adj);
+
+		if(matching[left] >= 0) {
+			int old_right = matching[left];
+
+			/* Check of all neighbors of the left node are already matched.
+			 * We cannot improve this edge then. */
+			if(bitset_contains(left_adj, matched_right))
+				continue;
+
+			bitset_andnot(tmp, matched_right);
+			right = bitset_next_set(tmp, 0);
+
+			assert(right != -1);
+
+			/* We have to find another left node which has the old right
+			 * one as a neighbor. */
+			for(i = 0; i < gr->n_left; ++i)
+				if(i != left && bitset_is_set(gr->adj[i], old_right))
+					break;
+
+			/* If no such node can be found, exit. */
+			if(i >= gr->n_left)
+				continue;
+
+			/* Else, we can improve this edge. */
+			matching[left] = right;
+			matching[i] = old_right;
+			bitset_set(matched_left, i);
+			bitset_set(matched_right, right);
+			done_something = 1;
+		}
+
+
+		/* We have to create a new single edge */
+		else {
+			assert(!bitset_is_set(matched_left, left));
+
+			bitset_andnot(tmp, matched_right);
+			if(bitset_popcnt(tmp) == 0)
+				continue;
+
+			right = bitset_min(tmp);
+			assert(!bitset_is_set(matched_right, right));
+			matching[left] = right;
+			bitset_set(matched_left, left);
+			bitset_set(matched_right, right);
+			done_something = 1;
+		}
+	}
+
+	bitset_free(tmp);
+
+	return done_something;
+}
+
+void bipartite_matching(const bipartite_t *gr, int *matching)
+{
+	bitset_t *matched_left = bitset_malloc(gr->n_left);
+	bitset_t *matched_right = bitset_malloc(gr->n_right);
+
+	memset(matching, -1, gr->n_left * sizeof(int));
+	while(apply_alternating_path(gr, matching, matched_left, matched_right));
+
+	bitset_free(matched_left);
+	bitset_free(matched_right);
+}
diff --git a/ir/adt/bipartite.h b/ir/adt/bipartite.h
new file mode 100644
index 000000000..993650231
--- /dev/null
+++ b/ir/adt/bipartite.h
@@ -0,0 +1,25 @@
+/**
+ * @file   bipartite.h
+ * @date   26.01.2006
+ * @author Sebastian Hack
+ *
+ * Copyright (C) 2006 Universitaet Karlsruhe
+ * Released under the GPL
+ *
+ * Implements bipartite matchings.
+ *
+ */
+
+#ifndef _BIPARTITE_H
+#define _BIPARTITE_H
+
+typedef struct _bipartite_t bipartite_t;
+
+bipartite_t *bipartite_new(int n_left, int n_right);
+void bipartite_free(bipartite_t *gr);
+void bipartite_add(bipartite_t *gr, int i, int j);
+void bipartite_remv(bipartite_t *gr, int i, int j);
+int bipartite_adj(const bipartite_t *gr, int i, int j);
+void bipartite_matching(const bipartite_t *gr, int *matching);
+
+#endif /* _BIPARTITE_H */
-- 
2.20.1