Nouvelle condition de coloriage

1 files changed, 9 insertions, 4 deletions

diff --git a/algos.c b/algos.c
index b329f0c..3563903 100644
--- a/algos.c
+++ b/algos.c
@@ -1,6 +1,6 @@
 #include <assert.h>
 #include <stdbool.h>
-
+#include <stdlib.h>
 
 #include "algos.h"
 
@@ -169,7 +169,10 @@ void max_clique_b(const graph g, set k, set c, set a, set *mc) {
 // 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) {
+int blabla = 0;
+void max_clique_c(const graph g, set k, set c, set a, set *mc, int prev_size) {
+	blabla++;
+	//if (blabla % 100 == 0) printf("%d\n", blabla);
 	// If we have no chance of improving our max clique, exit
 	if (set_size(k) + set_size(c) <= set_size(*mc)) return;
 
@@ -183,7 +186,9 @@ void max_clique_c(const graph g, set k, set c, set a, set *mc) {
 	// If we have no possibility to explore, return
 	if (is_set_empty(c)) return;
 
-	if (set_size(c) == g->N / 2) {
+	if (set_size(c) <= prev_size / 2 && set_size(c) >= g->N / 30) {
+	//if (rand() % 7919 == 0 && set_size(c) >= 20 ) {
+		prev_size = set_size(c);
 		// Color graph : we may have no possibility
 		set c_copy = copy_set(c);
 		int color_count = color_subgraph(g, c_copy);
@@ -228,7 +233,7 @@ void max_clique_c(const graph g, set k, set c, set a, set *mc) {
 		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);
+		max_clique_c(g, k2, c2, a2, mc, prev_size);
 		delete_set(a2);
 		delete_set(c2);
 		delete_set(k2);