Merge branch 'master' of /users/13/info/oulamara/Work/../../auvolat/boulot/AlgoProg-Projet

1 files changed, 54 insertions, 7 deletions

diff --git a/algos.c b/algos.c
index 07c667a..60e94fa 100644
--- a/algos.c
+++ b/algos.c
@@ -23,6 +23,7 @@ void max_clique_a(const graph g, set k, set c, set *mc) {
 	}
 }
 
+// Voir notice de convention ci-dessous
 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)) {
@@ -31,24 +32,26 @@ void max_clique_b(const graph g, set k, set c, set a, set *mc) {
 			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);
+		while (!(is_set_empty(a))) {
+			int x = elt_of_set(a);
+			set_remove_ip(x, a);
 
 			set k2 = set_add(x, k);
 			set c2 = set_inter(c, graph_neighbours(g, x));
-			set a2 = set_inter(at,  graph_neighbours(g, x));
+			set a2 = set_inter(a,  graph_neighbours(g, x));
 			
 			max_clique_b(g,k2, c2, a2, mc);
 			delete_set(k2);
 			delete_set(c2);
 			delete_set(a2);
 		}
-		delete_set(at);
 	}
 }
 
+// Convention : lors d'un appel de fonction, les set donnés en
+// argument peuvent être modifiés à la guise de l'algorithme
+// Il est donc de la responsabilité de l'appellant de vérifier qu'à
+// chaque appel les sets sont utilisables et cohérents
 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)) {
@@ -57,6 +60,50 @@ 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 {
-		//TODO
+		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));
+			set a2 = set_inter(a, graph_neighbours(g, x));
+			max_clique_c(g, k2, c2, a2, mc);
+			delete_set(a2);
+			delete_set(c2);
+			delete_set(k2);
+
+			set_remove_ip(x, a);
+			delete_set(t);
+			t = set_diff(a, graph_neighbours(g, u));
+		}
+		delete_set(t);
 	}
 }