From cbec036a66960eea2ff1f1cda1f1e07f39461eb9 Mon Sep 17 00:00:00 2001 From: Alex Auvolat--bernstein Date: Wed, 4 Dec 2013 16:49:31 +0100 Subject: Added algorithm C (does not work) --- algos.c | 34 +++++++++++++++++++++++++++------- main.c | 4 +++- set_linked_lists.c | 3 +++ 3 files changed, 33 insertions(+), 8 deletions(-) diff --git a/algos.c b/algos.c index 07c667a..542c8a5 100644 --- a/algos.c +++ b/algos.c @@ -23,6 +23,7 @@ void max_clique_a(const graph g, set k, set c, set *mc) { } } +// 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)) { if (set_size(k) > set_size(*mc)) { @@ -31,24 +32,26 @@ void max_clique_b(const graph g, set k, set c, set a, set *mc) { printf("Found new max clique: "); dump_set(*mc); fflush(stdout); } } else { - set at = copy_set (a); - while (!(is_set_empty(at))) { - int x = elt_of_set(at); - set_remove_ip(x, at); + while (!(is_set_empty(a))) { + int x = elt_of_set(a); + set_remove_ip(x, a); set k2 = set_add(x, k); set c2 = set_inter(c, graph_neighbours(g, x)); - set a2 = set_inter(at, graph_neighbours(g, x)); + set a2 = set_inter(a, graph_neighbours(g, x)); max_clique_b(g,k2, c2, a2, mc); delete_set(k2); delete_set(c2); delete_set(a2); } - delete_set(at); } } +// 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'à +// 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 (is_set_empty(c)) { if (set_size(k) > set_size(*mc)) { @@ -57,6 +60,23 @@ void max_clique_c(const graph g, set k, set c, set a, set *mc) { printf("Found new max clique: "); dump_set(*mc); fflush(stdout); } } else { - //TODO + int u = elt_of_set(c); // TODO maximiser C inter Gamma(u) + set t = set_diff(a, graph_neighbours(g, u)); + while (!is_set_empty(t)) { + int x = elt_of_set(t); + + set k2 = set_add(x, k); + set c2 = set_inter(c, graph_neighbours(g, x)); + set a2 = set_inter(a, graph_neighbours(g, x)); + max_clique_c(g, k2, c2, a2, mc); + delete_set(a2); + delete_set(c2); + delete_set(k2); + + set_remove_ip(x, a); + delete_set(t); + t = set_diff(a, graph_neighbours(g, u)); + } + delete_set(t); } } diff --git a/main.c b/main.c index 4eb0f5d..e5b3efc 100644 --- a/main.c +++ b/main.c @@ -30,6 +30,7 @@ void usage(char *pname) { printf("\nUsage:\n\t%s [options] []\n\n", pname); printf("Available options:\n"); printf("\n -d\n\tRead input in DIMACS format\n"); + printf("\n -a\n\tUse algorithm A\n"); printf("\n -b\n\tUse algorithm B\n"); printf("\n -c\n\tUse algorithm C\n"); printf("\n -o \n\tDump graph in graphwiz .dot format\n"); @@ -50,6 +51,8 @@ int main(int argc, char **argv) { } else if (!strcmp(argv[i], "-o")) { if (++i == argc) usage(argv[0]); dump = argv[i]; + } else if (!strcmp(argv[i], "-a")) { + algo = 0; } else if (!strcmp(argv[i], "-b")) { algo = 1; } else if (!strcmp(argv[i], "-c")) { @@ -109,6 +112,5 @@ int main(int argc, char **argv) { printf("Max clique: "); dump_set(max_clique); } - delete_graph(g); return 0; } diff --git a/set_linked_lists.c b/set_linked_lists.c index 8cc77c4..ee0a021 100644 --- a/set_linked_lists.c +++ b/set_linked_lists.c @@ -9,6 +9,8 @@ #include #include +#include + #include "sets.h" /* Question théorique pertinente : @@ -92,6 +94,7 @@ set copy_set(const set s) { for (iter = s->first->next; iter != NULL; iter = iter->next) { element e = malloc(sizeof(struct set_elt)); + assert(e != NULL); e->value = iter->value; prev->next = e; prev = e; -- cgit v1.2.3 From 71094b2d48ac784e60d454609064d20e83c017be Mon Sep 17 00:00:00 2001 From: Alex Auvolat--bernstein Date: Wed, 4 Dec 2013 17:26:06 +0100 Subject: Finished implementation for algorithm C, and corrected bitset bugs. --- algos.c | 29 ++++++++++++++++++++++++++++- set_bitsets.c | 20 ++++++++++++++------ set_linked_lists.c | 5 ++++- sets.h | 3 ++- 4 files changed, 48 insertions(+), 9 deletions(-) diff --git a/algos.c b/algos.c index 542c8a5..60e94fa 100644 --- a/algos.c +++ b/algos.c @@ -60,10 +60,37 @@ void max_clique_c(const graph g, set k, set c, set a, set *mc) { printf("Found new max clique: "); dump_set(*mc); fflush(stdout); } } else { - int u = elt_of_set(c); // TODO maximiser C inter Gamma(u) + set c_it = copy_set(c); + int u = elt_of_set(c_it), n = 0; + set_remove_ip(u, c_it); + + { set temp = set_inter(c, graph_neighbours(g, u)); + n = set_size(temp); + delete_set(temp); + } + + int heur = u; + while (!is_set_empty(c_it)) { + int uprime = elt_of_set(c_it); + heur = uprime; + + set_remove_ip(uprime, c_it); + + set temp = set_inter(c, graph_neighbours(g, uprime)); + if (set_size(temp) > n) { + n = set_size(temp); + u = uprime; + } + delete_set(temp); + } + delete_set(c_it); + + set t = set_diff(a, graph_neighbours(g, u)); + heur = u; while (!is_set_empty(t)) { int x = elt_of_set(t); + heur = x; set k2 = set_add(x, k); set c2 = set_inter(c, graph_neighbours(g, x)); diff --git a/set_bitsets.c b/set_bitsets.c index 53af83a..fda7085 100644 --- a/set_bitsets.c +++ b/set_bitsets.c @@ -83,6 +83,7 @@ void set_inter_ip(set a, const set b){ a.tab[i] = a.tab[i]&b.tab[i]; *(a.size) += nb_one(a.tab[i]); } + assert((a.N%SCOD == 0) || (a.tab[NC-1]>>(a.N%SCOD)) == 0); } @@ -92,10 +93,12 @@ void set_diff_ip(set a, const set b){ assert(a.N == b.N); } int NC = nbCells(a.N), i; + *(a.size)=0; for(i = 0; i < NC; i++) { a.tab[i] = a.tab[i] & (~b.tab[i]); *(a.size) += nb_one(a.tab[i]); } + assert((a.N%SCOD == 0) || (a.tab[NC-1]>>(a.N%SCOD)) == 0); } bool is_set_empty(const set s){ @@ -103,18 +106,21 @@ bool is_set_empty(const set s){ } inline bool set_mem(int x, const set s){ - unsigned long long ux = x; + unsigned long long ux = x; + if (!(x < s.N && x >= 0)) { + printf("Invalid argument for set_mem : %d\n", x); assert(x < s.N && x >= 0); + } return (s.tab[ux/SCOD]>>(ux%SCOD))&1; } int dyadic_val(unsigned long long x){ - if(x == 0){ + if(x == 0) { printf("Infinite valuation\n"); assert(false); } - int i; - for(i=0; ((x>>i)&1) == 0; i++); + int i = 0; + while (((x>>i)&1) == 0) i++; return i; } @@ -122,7 +128,7 @@ int elt_of_set(const set s){ int N=nbCells(s.N), i; for(i=0; i>( (SCOD-(n%SCOD))%SCOD ) ); + assert((n%SCOD == 0) || (r.tab[NC-1]>>(n%SCOD)) == 0); return r; } diff --git a/set_linked_lists.c b/set_linked_lists.c index 86a53b3..004e55a 100644 --- a/set_linked_lists.c +++ b/set_linked_lists.c @@ -239,7 +239,10 @@ bool sets_equal(const set a, const set b) { int elt_of_set(const set s) { if (s->first != NULL) return s->first->value; - return -1; // should raise exception... hope this will be handled properly + + fprintf(stderr, "No element in empty set...\n"); + dump_set(s); + assert(false); } int elt_of_set_heur(const set s, int h) { diff --git a/sets.h b/sets.h index cbb37b8..c161e03 100644 --- a/sets.h +++ b/sets.h @@ -14,7 +14,8 @@ #ifdef BITSETS typedef struct { - int N, *size; + int N; // Capacity of set (range of possible elements : 0..N-1) + int *size; // Number of elements actually in the set unsigned long long* tab; } set; #endif -- cgit v1.2.3