summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--algos.c61
-rw-r--r--main.c4
-rw-r--r--set_bitsets.c20
-rw-r--r--set_linked_lists.c8
-rw-r--r--sets.h3
5 files changed, 80 insertions, 16 deletions
diff --git a/algos.c b/algos.c
index 07c667a..60e94fa 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,50 @@ 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
+ 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));
+ 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] [<graph file>]\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 <file.dot>\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_bitsets.c b/set_bitsets.c
index 2c85277..7eddcfd 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<N; i++)
if(s.tab[i] != 0)
- return i*SCOD+dyadic_val(s.tab[i]);
+ return i*SCOD + dyadic_val(s.tab[i]);
printf("No element in an empty set!\n");
dump_set(s);
@@ -174,7 +180,9 @@ 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]=-1;
+ 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_linked_lists.c b/set_linked_lists.c
index e865b95..004e55a 100644
--- a/set_linked_lists.c
+++ b/set_linked_lists.c
@@ -9,6 +9,8 @@
#include <stdlib.h>
#include <stdio.h>
+#include <assert.h>
+
#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;
@@ -236,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
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-21 12:31:22 +0000