Algorithm B works.

1 files changed, 29 insertions, 53 deletions

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;