diff options
Diffstat (limited to 'algos.c')
| -rw-r--r-- | algos.c | 13 |
1 files changed, 9 insertions, 4 deletions
@@ -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); |