From 71094b2d48ac784e60d454609064d20e83c017be Mon Sep 17 00:00:00 2001
From: Alex Auvolat--bernstein <auvolat@clipper.ens.fr>
Date: Wed, 4 Dec 2013 17:26:06 +0100
Subject: Finished implementation for algorithm C, and corrected bitset bugs.

---
 algos.c            | 29 ++++++++++++++++++++++++++++-
 set_bitsets.c      | 20 ++++++++++++++------
 set_linked_lists.c |  5 ++++-
 sets.h             |  3 ++-
 4 files changed, 48 insertions(+), 9 deletions(-)

diff --git a/algos.c b/algos.c
index 542c8a5..60e94fa 100644
--- a/algos.c
+++ b/algos.c
@@ -60,10 +60,37 @@ void max_clique_c(const graph g, set k, set c, set a, set *mc) {
 			printf("Found new max clique: "); dump_set(*mc); fflush(stdout);
 		}
 	} else {
-		int u = elt_of_set(c);	// TODO maximiser C inter Gamma(u)
+		set c_it = copy_set(c);
+		int u = elt_of_set(c_it), n = 0;
+		set_remove_ip(u, c_it);
+
+		{	set temp = set_inter(c, graph_neighbours(g, u));
+			n = set_size(temp);
+			delete_set(temp);
+		}
+
+		int heur = u;
+		while (!is_set_empty(c_it)) {
+			int uprime = elt_of_set(c_it);
+			heur = uprime;
+
+			set_remove_ip(uprime, c_it);
+
+			set temp = set_inter(c, graph_neighbours(g, uprime));
+			if (set_size(temp) > n) {
+				n = set_size(temp);
+				u = uprime;
+			}
+			delete_set(temp);
+		}
+		delete_set(c_it);
+
+
 		set t = set_diff(a, graph_neighbours(g, u));
+		heur = u;
 		while (!is_set_empty(t)) {
 			int x = elt_of_set(t);
+			heur = x;
 
 			set k2 = set_add(x, k);
 			set c2 = set_inter(c, graph_neighbours(g, x));
diff --git a/set_bitsets.c b/set_bitsets.c
index 53af83a..fda7085 100644
--- a/set_bitsets.c
+++ b/set_bitsets.c
@@ -83,6 +83,7 @@ void set_inter_ip(set a, const set b){
 		a.tab[i] = a.tab[i]&b.tab[i];
 		*(a.size) += nb_one(a.tab[i]);
 	}
+	assert((a.N%SCOD == 0) || (a.tab[NC-1]>>(a.N%SCOD)) == 0);
 }
 
 
@@ -92,10 +93,12 @@ void set_diff_ip(set a, const set b){
 		assert(a.N == b.N);
 	}
 	int NC = nbCells(a.N), i;
+	*(a.size)=0;
 	for(i = 0; i < NC; i++) { 
 		a.tab[i] = a.tab[i] & (~b.tab[i]);
 		*(a.size) += nb_one(a.tab[i]);
 	}
+	assert((a.N%SCOD == 0) || (a.tab[NC-1]>>(a.N%SCOD)) == 0);
 }
 
 bool is_set_empty(const set s){
@@ -103,18 +106,21 @@ bool is_set_empty(const set s){
 }
 
 inline bool set_mem(int x, const set s){
-    	unsigned long long ux = x;
+    unsigned long long ux = x;
+	if (!(x < s.N && x >= 0)) {
+		printf("Invalid argument for set_mem : %d\n", x);
     	assert(x < s.N && x >= 0);
+	}
 	return  (s.tab[ux/SCOD]>>(ux%SCOD))&1;
 }
 
 int dyadic_val(unsigned long long x){
-	if(x == 0){
+	if(x == 0) {
 		printf("Infinite valuation\n");
 		assert(false);
 	}
-	int i;
-	for(i=0; ((x>>i)&1) == 0; i++);
+	int i = 0;
+	while (((x>>i)&1) == 0) i++;
 	return i;
 }
 
@@ -122,7 +128,7 @@ int elt_of_set(const set s){
 	int N=nbCells(s.N), i;
 	for(i=0; i<N; i++)
 		if(s.tab[i] != 0)
-		    return i*SCOD+dyadic_val(s.tab[i]);
+		    return i*SCOD + dyadic_val(s.tab[i]);
 
 	printf("No element in an empty set!\n");
 	dump_set(s);
@@ -174,7 +180,9 @@ set full_set(int n) {
     *(r.size) = n;
     int NC=nbCells(n), i;
     for(i=0; i< NC; i++)
-	r.tab[i]=-1;
+		r.tab[i]=-1;
+	r.tab[NC-1] = ( r.tab[NC-1]>>( (SCOD-(n%SCOD))%SCOD ) );
+	assert((n%SCOD == 0) || (r.tab[NC-1]>>(n%SCOD)) == 0);
     return r;
 }
 
diff --git a/set_linked_lists.c b/set_linked_lists.c
index 86a53b3..004e55a 100644
--- a/set_linked_lists.c
+++ b/set_linked_lists.c
@@ -239,7 +239,10 @@ bool sets_equal(const set a, const set b) {
 
 int elt_of_set(const set s) {
 	if (s->first != NULL) return s->first->value;
-	return -1;		// should raise exception... hope this will be handled properly
+
+	fprintf(stderr, "No element in empty set...\n");
+	dump_set(s);
+	assert(false);
 }
 
 int elt_of_set_heur(const set s, int h) {
diff --git a/sets.h b/sets.h
index cbb37b8..c161e03 100644
--- a/sets.h
+++ b/sets.h
@@ -14,7 +14,8 @@
 
 #ifdef BITSETS
 typedef struct {
-    int N, *size;
+    int N;			// Capacity of set (range of possible elements : 0..N-1)
+   	int *size;		// Number of elements actually in the set
     unsigned long long* tab;
 } set;
 #endif
-- 
cgit v1.2.3