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