Algorithm B works.

5 files changed, 109 insertions, 59 deletions

diff --git a/Makefile b/Makefile
index 2f7927c..b81992e 100644
--- a/Makefile
+++ b/Makefile
@@ -1,5 +1,5 @@
-COMMON_C=main.c sets.c graph.c
-COMMON_H=graph.h sets.h
+COMMON_C=main.c sets.c graph.c algos.c
+COMMON_H=graph.h sets.h algos.h
 
 all : exe_ll exe_bs exe_tr exe_ll_test
 
diff --git a/algos.c b/algos.c
new file mode 100644
index 0000000..07c667a
--- /dev/null
+++ b/algos.c
@@ -0,0 +1,62 @@
+#include "algos.h"
+
+void max_clique_a(const graph g, set k, set c, set *mc) {
+	if (is_set_empty(c)) {
+		if (set_size(k) > set_size(*mc)) {
+			delete_set(*mc);
+			*mc = copy_set(k);
+			printf("Found new max clique: "); dump_set(*mc); fflush(stdout);
+		}
+	} else {
+		set cc = copy_set(c);
+		while (!(is_set_empty(cc))) {
+			int x = elt_of_set(cc);
+			set_remove_ip(x, cc);
+
+			set k2 = set_add(x, k);
+			set c2 = set_inter(c, graph_neighbours(g, x));
+			max_clique_a(g,k2, c2, mc);
+			delete_set(k2);
+			delete_set(c2);
+		}
+		delete_set(cc);
+	}
+}
+
+void max_clique_b(const graph g, set k, set c, set a, set *mc) {
+	if (is_set_empty(c)) {
+		if (set_size(k) > set_size(*mc)) {
+			delete_set(*mc);
+			*mc = copy_set(k);
+			printf("Found new max clique: "); dump_set(*mc); fflush(stdout);
+		}
+	} else {
+	    set at = copy_set (a);
+		while (!(is_set_empty(at))) {
+			int x = elt_of_set(at);
+			set_remove_ip(x, at);
+
+			set k2 = set_add(x, k);
+			set c2 = set_inter(c, graph_neighbours(g, x));
+			set a2 = set_inter(at,  graph_neighbours(g, x));
+			
+			max_clique_b(g,k2, c2, a2, mc);
+			delete_set(k2);
+			delete_set(c2);
+			delete_set(a2);
+		}
+		delete_set(at);
+	}
+}
+
+void max_clique_c(const graph g, set k, set c, set a, set *mc) {
+	if (is_set_empty(c)) {
+		if (set_size(k) > set_size(*mc)) {
+			delete_set(*mc);
+			*mc = copy_set(k);
+			printf("Found new max clique: "); dump_set(*mc); fflush(stdout);
+		}
+	} else {
+		//TODO
+	}
+}
diff --git a/algos.h b/algos.h
new file mode 100644
index 0000000..4f20639
--- /dev/null
+++ b/algos.h
@@ -0,0 +1,11 @@
+#ifndef DEF_ALGOS_H
+#define DEF_ALGOS_H
+
+#include "graph.h"
+
+void max_clique_a(const graph g, set k, set c, set *mc);
+void max_clique_b(const graph g, set k, set c, set a, set *mc);
+void max_clique_c(const graph g, set k, set c, set a, set *mc);
+
+#endif
+
diff --git a/main.c b/main.c
index 4960dcb..4eb0f5d 100644
--- a/main.c
+++ b/main.c
@@ -11,6 +11,7 @@
 
 #include "sets.h"
 #include "graph.h"
+#include "algos.h"
 
 /*
 	max_clique calculates the maximum clique in a graph. Arguments :
@@ -21,55 +22,7 @@
 	- mc : a pointer to the set containing the maximum clique found until now
 	Returns nothing (result is in *mc).
 */
-void max_clique_a(const graph g, set k, set c, set *mc) {
-	if (is_set_empty(c)) {
-		if (set_size(k) > set_size(*mc)) {
-			delete_set(*mc);
-			*mc = copy_set(k);
-			printf("Found new max clique: "); dump_set(*mc); fflush(stdout);
-		}
-	} else {
-		set cc = copy_set(c);
-		while (!(is_set_empty(cc))) {
-			int x = elt_of_set(cc);
-			set_remove_ip(x, cc);
-
-			set k2 = set_add(x, k);
-			set c2 = set_inter(c, graph_neighbours(g, x));
-			max_clique_a(g,k2, c2, mc);
-			delete_set(k2);
-			delete_set(c2);
-		}
-		delete_set(cc);
-	}
-}
-
 
-void max_clique_b(const graph g, set k, set c, set a, set *mc) {
-	if (is_set_empty(c)) {
-		if (set_size(k) > set_size(*mc)) {
-			delete_set(*mc);
-			*mc = copy_set(k);
-			printf("Found new max clique: "); dump_set(*mc); fflush(stdout);
-		}
-	} else {
-	    	set at = copy_set a;
-		while (!(is_set_empty(a2))) {
-			int x = elt_of_set(at);
-			set_remove_ip(x, at);
-
-			set k2 = set_add(x, k);
-			set c2 = set_inter(c, graph_neighbours(g, x));
-			set a2 = set_inter(at,  graph_neighbours(g, x));
-			
-			max_clique_a(g,k2, c2, a2, mc);
-			delete_set(k2);
-			delete_set(c2);
-			delete_set(a2);
-		}
-		delete_set(at);
-	}
-}
 
 // Driver
 
@@ -77,6 +30,8 @@ void usage(char *pname) {
 	printf("\nUsage:\n\t%s [options] [<graph file>]\n\n", pname);
 	printf("Available options:\n");
 	printf("\n    -d\n\tRead input in DIMACS format\n");
+	printf("\n    -b\n\tUse algorithm B\n");
+	printf("\n    -c\n\tUse algorithm C\n");
 	printf("\n    -o <file.dot>\n\tDump graph in graphwiz .dot format\n");
 	printf("\n    -h, --help\n\tShow this help page\n");
 	exit(1);
@@ -87,6 +42,7 @@ int main(int argc, char **argv) {
 	int dimacs = 0;
 	char *filename = "-";
 	char *dump = NULL;
+	int algo = 0;
 
 	for (i = 1; i < argc; i++) {
 		if (!strcmp(argv[i], "-d")) {
@@ -94,6 +50,10 @@ int main(int argc, char **argv) {
 		} else if (!strcmp(argv[i], "-o")) {
 			if (++i == argc) usage(argv[0]);
 			dump = argv[i];
+		} else if (!strcmp(argv[i], "-b")) {
+			algo = 1;
+		} else if (!strcmp(argv[i], "-c")) {
+			algo = 2;
 		} else if (argv[i][0] == '-') {
 			usage(argv[0]);
 		} else {
@@ -127,11 +87,27 @@ int main(int argc, char **argv) {
 	}
 
 	// do stuff with graph
-	set max_clique = empty_set(g->N);
-	set init_s = full_set(g->N);
-	set init_k = empty_set(g->N);
-	max_clique_a(g, init_k, init_s, &max_clique);
-	printf("Max clique: "); dump_set(max_clique);
+	if (algo == 0) {
+		set max_clique = empty_set(g->N);
+		set init_s = full_set(g->N);
+		set init_k = empty_set(g->N);
+		max_clique_a(g, init_k, init_s, &max_clique);
+		printf("Max clique: "); dump_set(max_clique);
+	} else if (algo == 1) {
+		set max_clique = empty_set(g->N);
+		set init_c = full_set(g->N);
+		set init_a = full_set(g->N);
+		set init_k = empty_set(g->N);
+		max_clique_b(g, init_k, init_c, init_a, &max_clique);
+		printf("Max clique: "); dump_set(max_clique);
+	} else if (algo == 2) {
+		set max_clique = empty_set(g->N);
+		set init_c = full_set(g->N);
+		set init_a = full_set(g->N);
+		set init_k = empty_set(g->N);
+		max_clique_c(g, init_k, init_c, init_a, &max_clique);
+		printf("Max clique: "); dump_set(max_clique);
+	}
 
 	delete_graph(g);
 	return 0;
diff --git a/set_bitsets.c b/set_bitsets.c
index 6645e0e..30e4dc9 100644
--- a/set_bitsets.c
+++ b/set_bitsets.c
@@ -48,7 +48,7 @@ set empty_set(int n){
 set copy_set(const set s){
 	set res = empty_set(s.N);
 	*(res.size) = *(s.size);
-	int NC = nbCells(*(s.size)), i;
+	int NC = nbCells(s.N), i;
 	for(i = 0; i < NC; i++) 
 		res.tab[i] = s.tab[i];
 	return res;
@@ -64,7 +64,7 @@ void set_union_ip(set a, const set b){
 		printf("Union failed : the sets don't have the same size\n");
 		assert(a.N == b.N);
 	}
-	int NC = nbCells(*(a.size)), i;
+	int NC = nbCells(a.N), i;
 	*(a.size)=0;
 	for(i = 0; i < NC; i++) {
 		a.tab[i] = a.tab[i]|b.tab[i];
@@ -77,7 +77,7 @@ void set_inter_ip(set a, const set b){
 		printf("Intersection failed : the sets don't have the same size\n");
 		assert(a.N == b.N);
 	}
-	int NC = nbCells(*(a.size)), i;
+	int NC = nbCells(a.N), i;
 	*(a.size)=0;
 	for(i = 0; i < NC; i++){ 
 		a.tab[i] = a.tab[i]&b.tab[i];
@@ -91,7 +91,7 @@ void set_diff_ip(set a, const set b){
 		printf("Difference failed : the sets don't have the same size\n");
 		assert(a.N == b.N);
 	}
-	int NC = nbCells(*(a.size)), i;
+	int NC = nbCells(a.N), i;
 	for(i = 0; i < NC; i++) { 
 		a.tab[i] = a.tab[i] & (~b.tab[i]);
 		*(a.size) += nb_one(a.tab[i]);
@@ -125,6 +125,7 @@ int elt_of_set(const set s){
 		    return i*SCOD+dyadic_val(s.tab[i]);
 
 	printf("No element in an empty set!\n");
+	dump_set(s);
 	assert(false);
 }