diff options
author | Alex Auvolat--bernstein <auvolat@clipper.ens.fr> | 2013-12-04 16:49:31 +0100 |
---|---|---|
committer | Alex Auvolat--bernstein <auvolat@clipper.ens.fr> | 2013-12-04 16:49:31 +0100 |
commit | cbec036a66960eea2ff1f1cda1f1e07f39461eb9 (patch) | |
tree | 7f19c834dede1729c40eb861f78fd2d8d5f137f2 /algos.c | |
parent | 77db931b94870a8f28eef482091924471cd18d64 (diff) | |
download | AlgoProg-Projet-cbec036a66960eea2ff1f1cda1f1e07f39461eb9.tar.gz AlgoProg-Projet-cbec036a66960eea2ff1f1cda1f1e07f39461eb9.zip |
Added algorithm C (does not work)
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); } } |