Addition of sets_equal to bitsets

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);