From f7022495daa31b714a73d6bdf6640db7494f1f4c Mon Sep 17 00:00:00 2001 From: Alex Auvolat--bernstein Date: Wed, 4 Dec 2013 17:57:00 +0100 Subject: Added optimization to algo C. --- algos.c | 4 +++- graph.c | 1 - 2 files changed, 3 insertions(+), 2 deletions(-) diff --git a/algos.c b/algos.c index 630a719..3d24558 100644 --- a/algos.c +++ b/algos.c @@ -53,8 +53,10 @@ void max_clique_b(const graph g, set k, set c, set a, set *mc) { // 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 (set_size(k) + set_size(c) <= set_size(*mc)) return; + if (is_set_empty(c)) { - if (set_size(k) > set_size(*mc)) { + if (set_size(k) > set_size(*mc)) { // useless condition delete_set(*mc); *mc = copy_set(k); printf("Found new max clique: "); dump_set(*mc); fflush(stdout); diff --git a/graph.c b/graph.c index a957136..4d3ba2a 100644 --- a/graph.c +++ b/graph.c @@ -65,7 +65,6 @@ graph load_graph_dimacs(FILE *stream) { } fscanf(stream, " %d %d\n", &a, &b); - fprintf(stderr, "Edge: (%d, %d)\n", a, b); a--; b--; set_add_ip(b, k->neighbour[a]); set_add_ip(a, k->neighbour[b]); -- cgit v1.2.3 From 3ab1dd7971402fd2d76d464e4e193132b4a9eb89 Mon Sep 17 00:00:00 2001 From: Alex Auvolat--bernstein Date: Wed, 4 Dec 2013 18:07:33 +0100 Subject: Improved hamming weight. --- set_bitsets.c | 20 ++++++++++++++++---- 1 file changed, 16 insertions(+), 4 deletions(-) diff --git a/set_bitsets.c b/set_bitsets.c index 7eddcfd..f59e61e 100644 --- a/set_bitsets.c +++ b/set_bitsets.c @@ -21,10 +21,22 @@ int nbCells(int n){ //the mathematical ceil function } int nb_one(unsigned long long x) { //the hamming weight of x - int cnt = 0, i; - for(i = 0; i < SCOD; i++) - cnt+= ((x>>i)&1); - return cnt; + assert(SCOD==64); + + //1 + x = (x & 0x5555555555555555) + ((x >> 1) & 0x5555555555555555); + //2 + x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333); + //4 + x = (x & 0x0F0F0F0F0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F0F0F0F0F); + //8 + x = (x & 0x00FF00FF00FF00FF) + ((x >> 8) & 0x00FF00FF00FF00FF); + //16 + x = (x & 0x0000FFFF0000FFFF) + ((x >> 16) & 0x0000FFFF0000FFFF); + //32 + x = (x & 0x00000000FFFFFFFF) + ((x >> 32) & 0x00000000FFFFFFFF); + + return x; } int set_size(const set s){ -- cgit v1.2.3 From cbffb4f8d60a8516b23aae1bdf07197787ddce2c Mon Sep 17 00:00:00 2001 From: Alex AUVOLAT Date: Thu, 5 Dec 2013 08:52:04 +0100 Subject: Added comment --- set_bitsets.c | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) diff --git a/set_bitsets.c b/set_bitsets.c index f59e61e..4ac8462 100644 --- a/set_bitsets.c +++ b/set_bitsets.c @@ -24,13 +24,13 @@ int nb_one(unsigned long long x) { //the hamming weight of x assert(SCOD==64); //1 - x = (x & 0x5555555555555555) + ((x >> 1) & 0x5555555555555555); + x = (x & 0x5555555555555555) + ((x >> 1) & 0x5555555555555555); // mask : 0101010101... //2 - x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333); + x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333); // mask : 001100110011... //4 - x = (x & 0x0F0F0F0F0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F0F0F0F0F); + x = (x & 0x0F0F0F0F0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F0F0F0F0F); // mask : 000011110000.... //8 - x = (x & 0x00FF00FF00FF00FF) + ((x >> 8) & 0x00FF00FF00FF00FF); + x = (x & 0x00FF00FF00FF00FF) + ((x >> 8) & 0x00FF00FF00FF00FF); // etc. //16 x = (x & 0x0000FFFF0000FFFF) + ((x >> 16) & 0x0000FFFF0000FFFF); //32 -- cgit v1.2.3