From 100be058261bc725a0356dd76e07145ae6c3181f Mon Sep 17 00:00:00 2001 From: Alex AUVOLAT Date: Sun, 8 Dec 2013 19:07:27 +0100 Subject: Nouvelle condition de coloriage --- algos.c | 13 +++++++++---- 1 file changed, 9 insertions(+), 4 deletions(-) (limited to 'algos.c') diff --git a/algos.c b/algos.c index b329f0c..3563903 100644 --- a/algos.c +++ b/algos.c @@ -1,6 +1,6 @@ #include #include - +#include #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); -- cgit v1.2.3