diff options
author | Mendes Oulamara <oulamara@clipper.ens.fr> | 2013-12-06 18:08:37 +0100 |
---|---|---|
committer | Mendes Oulamara <oulamara@clipper.ens.fr> | 2013-12-06 18:08:37 +0100 |
commit | 3c8b380b98b8fd5dcbaa3a254ab71ac20a485099 (patch) | |
tree | d294b3ec1ea86de96e57dcf50125a0cb7552b0e7 /algos.c | |
parent | 50b5699f9b6d887c31e546168d9e588b36e3f876 (diff) | |
download | AlgoProg-Projet-3c8b380b98b8fd5dcbaa3a254ab71ac20a485099.tar.gz AlgoProg-Projet-3c8b380b98b8fd5dcbaa3a254ab71ac20a485099.zip |
Addition of sets_equal to bitsets
Diffstat (limited to 'algos.c')
-rw-r--r-- | algos.c | 25 |
1 files changed, 24 insertions, 1 deletions
@@ -1,5 +1,12 @@ #include "algos.h" + +/*Premier algorithme naïf. + * g : graphe où on cherche les cliques + * k : clique actuelle + * c : noeuds candidats à l'ajout + * mc : clique maximale actuelle +*/ void max_clique_a(const graph g, set k, set c, set *mc) { if (is_set_empty(c)) { if (set_size(k) > set_size(*mc)) { @@ -23,6 +30,14 @@ void max_clique_a(const graph g, set k, set c, set *mc) { } } +/** Algorithme avec l'optimisation : on évite d'énumérer plusieurs fois + * la même clique. + * g : graphe où on cherche les cliques + * k : clique actuelle + * c : noeuds candidats à l'ajout + * a : noeuds que l'on s'autorise à ajouter + * mc : clique maximale actuelle + * */ // 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)) { @@ -48,6 +63,14 @@ void max_clique_b(const graph g, set k, set c, set a, set *mc) { } } +/** Algorithme avec la méthode du pivot + * la même clique. + * g : graphe où on cherche les cliques + * k : clique actuelle + * c : noeuds candidats à l'ajout + * a : noeuds que l'on s'autorise à ajouter + * mc : clique maximale actuelle + * */ // 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'à @@ -56,7 +79,7 @@ void max_clique_c(const graph g, set k, set c, set a, set *mc) { if (set_size(k) + set_size(c) <= set_size(*mc)) return; if (is_set_empty(c)) { - if (set_size(k) > set_size(*mc)) { // useless condition + 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); |