From 3c8b380b98b8fd5dcbaa3a254ab71ac20a485099 Mon Sep 17 00:00:00 2001 From: Mendes Oulamara Date: Fri, 6 Dec 2013 18:08:37 +0100 Subject: Addition of sets_equal to bitsets --- algos.c | 25 ++++++++++++++++++++++++- graph.h | 8 ++++---- main.c | 10 ---------- set_bitsets.c | 19 ++++++++++++++++--- set_test.c | 12 +++++++----- 5 files changed, 51 insertions(+), 23 deletions(-) diff --git a/algos.c b/algos.c index 3d24558..e1815c3 100644 --- a/algos.c +++ b/algos.c @@ -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); diff --git a/graph.h b/graph.h index 3c913ba..e85ef90 100644 --- a/graph.h +++ b/graph.h @@ -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); diff --git a/main.c b/main.c index e5b3efc..8a3d113 100644 --- a/main.c +++ b/main.c @@ -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; diff --git a/set_test.c b/set_test.c index a2d49ab..4685bc3 100644 --- a/set_test.c +++ b/set_test.c @@ -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); -- cgit v1.2.3