diff options
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); |