diff options
Diffstat (limited to 'algos.c')
| -rw-r--r-- | algos.c | 34 |
1 files changed, 27 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,23 @@ 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 + int u = elt_of_set(c); // TODO maximiser C inter Gamma(u) + set t = set_diff(a, graph_neighbours(g, u)); + while (!is_set_empty(t)) { + int x = elt_of_set(t); + + 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); } } |