diff options
| -rw-r--r-- | TODO | 19 | ||||
| -rw-r--r-- | algos.c | 89 |
2 files changed, 66 insertions, 42 deletions
@@ -1,3 +1,22 @@ dichotomie? +Coloriage : + + (On a toujours |K| + |C| > |K_max|, sinon ça sert à rien) + + Lorsque |C| = 10 (par exemple) et |K| < |K_max|, faire un coloriage du + graphe induit par C (ça se fait rapidement... mais ne pas le faire de + manière exacte). Si on a |K| + nb_couleurs <= |K_max|, alors on a perdu + (42). + +Utiliser des bitsets plus simples : + + Faire un typedef bitset_descriptor *set; On peut s'arranger pour faire, lors + de la création d'un bitset, *un seul malloc*, dont la première partie est + utilisée pour le descripteur et la seconde pour le tableau de bits. + +Analyse des cache miss ? + + + @@ -76,59 +76,64 @@ void max_clique_b(const graph g, set k, set c, set a, set *mc) { // 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 we have no chance of improving our max clique, exit if (set_size(k) + set_size(c) <= set_size(*mc)) return; - if (is_set_empty(c)) { - if (set_size(k) > set_size(*mc)) { // condition inutile - delete_set(*mc); - *mc = copy_set(k); - printf("Found new max clique: "); dump_set(*mc); fflush(stdout); - } - } else { - set c_it = copy_set(c); - int u = elt_of_set(c_it), n = 0; - set_remove_ip(u, c_it); + // If we have improved our clique, great + if (set_size(k) > set_size(*mc)) { + delete_set(*mc); + *mc = copy_set(k); + printf("Found new max clique: "); dump_set(*mc); fflush(stdout); + } - { set temp = set_inter(c, graph_neighbours(g, u)); - n = set_size(temp); - delete_set(temp); - } + // If we have no possibility to explore, return + if (is_set_empty(c)) return; - int heur = u; - while (!is_set_empty(c_it)) { - int uprime = elt_of_set_heur(c_it, heur); - heur = uprime; + // Find u that maximises |C inter Gamma(u)| + 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); + } - set_remove_ip(uprime, c_it); + // Explore possibilites + int heur = u; + while (!is_set_empty(c_it)) { + int uprime = elt_of_set_heur(c_it, heur); + set_remove_ip(uprime, c_it); + heur = uprime; - set temp = set_inter(c, graph_neighbours(g, uprime)); - if (set_size(temp) > n) { - n = set_size(temp); - u = uprime; - } - delete_set(temp); + set temp = set_inter(c, graph_neighbours(g, uprime)); + if (set_size(temp) > n) { + n = set_size(temp); + u = uprime; } - delete_set(c_it); + 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_heur(t, heur); - heur = x; + set t = set_diff(a, graph_neighbours(g, u)); + heur = u; + while (!is_set_empty(t)) { + int x = elt_of_set_heur(t, heur); + 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 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)); - } + set_remove_ip(x, a); delete_set(t); + t = set_diff(a, graph_neighbours(g, u)); } + delete_set(t); } + |