diff options
| -rw-r--r-- | algos.c | 25 | ||||
| -rw-r--r-- | graph.h | 8 | ||||
| -rw-r--r-- | main.c | 10 | ||||
| -rw-r--r-- | set_bitsets.c | 19 | ||||
| -rw-r--r-- | set_test.c | 12 |
5 files changed, 51 insertions, 23 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); @@ -30,15 +30,15 @@ #include "sets.h" struct graph_descriptor { - int N; // number of nodes - set *neighbour; // set of neighbours for each node + int N; // nombre de noeuds + set *neighbour; // ensemble des voisins de chaque noeuds }; typedef struct graph_descriptor *graph; -graph load_graph(FILE *stream); // format specified in README file -graph load_graph_dimacs(FILE *stream); // again, see README +graph load_graph(FILE *stream); // spécification du format dans le fichier README +graph load_graph_dimacs(FILE *stream); // cf README const set graph_neighbours(const graph g, int n); void dump_graphviz(const graph g, FILE *stream); void delete_graph(graph g); @@ -13,16 +13,6 @@ #include "graph.h" #include "algos.h" -/* - max_clique calculates the maximum clique in a graph. Arguments : - - g : the graph where the clique is looked for - - k : the clique we are currently examining - - c : the graph nodes we can potentially add to the clique - - a : the nodes we can actually add to the clique - - mc : a pointer to the set containing the maximum clique found until now - Returns nothing (result is in *mc). -*/ - // Driver diff --git a/set_bitsets.c b/set_bitsets.c index 4ac8462..5578620 100644 --- a/set_bitsets.c +++ b/set_bitsets.c @@ -51,9 +51,9 @@ set empty_set(int n){ res.size = malloc(sizeof(int)); *(res.size) = 0; int NC = nbCells(n); - res.tab = malloc(SCOD*NC/8); + res.tab = malloc((SCOD*NC)/8); for(i = 0; i < NC; i++) - res.tab[i] = 0; + res.tab[i] = (unsigned long long) (0); return res; } @@ -117,6 +117,18 @@ bool is_set_empty(const set s){ return (*(s.size) == 0); } +bool sets_equal(const set a, const set b){ + if(a.N != b.N) + return false; + int i, NC = nbCells(a.N); + for(i = 0; i < NC; i++){ + if(a.tab[i] != b.tab[i]) + return false; + } + assert(*(a.size) == *(b.size)); + return true; +} + inline bool set_mem(int x, const set s){ unsigned long long ux = x; if (!(x < s.N && x >= 0)) { @@ -163,6 +175,7 @@ int elt_of_set_heur(const set s, int h){ } void set_add_ip(int x, set s){ + assert(x < s.N); unsigned long long ux = x; if(! set_mem(ux, s)){ s.tab[ux/SCOD] = s.tab[ux/SCOD] | (unsigned long long)(1)<<(ux%SCOD); @@ -192,7 +205,7 @@ set full_set(int n) { *(r.size) = n; int NC=nbCells(n), i; for(i=0; i< NC; i++) - r.tab[i]=-1; + r.tab[i]=0xFFFFFFFFFFFFFFFF; r.tab[NC-1] = ( r.tab[NC-1]>>( (SCOD-(n%SCOD))%SCOD ) ); assert((n%SCOD == 0) || (r.tab[NC-1]>>(n%SCOD)) == 0); return r; @@ -14,15 +14,15 @@ int fails = 0; #define ASSERT(x) if (!(x)) { fprintf(stderr, "Assert fail: %s\n", #x); fails++; } int main() { - set empty = empty_set(1000); - - set s = empty_set(1000); + set empty = empty_set(200); + int i; + set s = empty_set(200); dump_set(s); set_add_ip(42, s); dump_set(s); - set k = singleton(1000, 12); + set k = singleton(200, 12); dump_set(k); set_add_ip(126, k); @@ -42,6 +42,8 @@ int main() { set_remove_ip(42, s); ASSERT(!set_mem(42, s)); ASSERT(is_set_empty(s)); + dump_set(s); + dump_set(r); ASSERT(sets_equal(s, r)); set_add_ip(4, r); @@ -50,7 +52,7 @@ int main() { set_add_ip(6, r); printf("A: "); dump_set(r); - set x = empty_set(1000); + set x = empty_set(200); set_union_ip(x, r); printf("A(copy): "); dump_set(x); |