Implemented basic algorithm for finding maximum clique... no optimizations.

8 files changed, 203 insertions, 8 deletions

diff --git a/Makefile b/Makefile
index 269ccff..266a909 100644
--- a/Makefile
+++ b/Makefile
@@ -1,20 +1,23 @@
+COMMON_C=main.c sets.c graph.c
+COMMON_H=graph.h sets.h
+
 all : exe_ll exe_bs exe_tr exe_ll_test
 
-exe_ll : main.c sets.h set_linked_lists.c sets.c
-	gcc -o exe_ll main.c set_linked_lists.c sets.c -DLINKEDLISTS -g
+exe_ll : set_linked_lists.c	$(COMMON_C) $(COMMON_H) 
+	gcc -o exe_ll set_linked_lists.c $(COMMON_C) -DLINKEDLISTS -g
 
 exe_ll_test : set_test.c sets.h set_linked_lists.c sets.c
 	gcc -o exe_ll_test set_test.c set_linked_lists.c sets.c -DLINKEDLISTS -g
 
-exe_bs : main.c sets.h set_bitsets.c sets.c
-	gcc -o exe_bs main.c set_bitsets.c sets.c -DBITSETS -g
+exe_bs : set_bitsets.c $(COMMON_C) $(COMMON_H)
+	gcc -o exe_bs set_bitsets.c $(COMMON_C) -DBITSETS -g
 
 exe_bs_test : set_test.c sets.h set_bitsets.c sets.c
-	gcc -o exe_ll_test set_test.c set_bitsets.c sets.c -DBITSETS -g
+	gcc -o exe_ll_test set_test.c set_bitsets.c sets.c graphc. -DBITSETS -g
 
 
-exe_tr : main.c sets.h set_treaps.c sets.c
-	# gcc -o exe_tr main.c set_treaps.c sets.c -DTREAPS -g
+exe_tr : set_treaps.c $(COMMON_C) $(COMMON_H)
+	# gcc -o exe_tr set_treaps.c $(COMMON_C) -DTREAPS -g
 
 
 clean : 
diff --git a/README b/README
index 699f8f2..cda0355 100644
--- a/README
+++ b/README
@@ -4,3 +4,15 @@ Alex AUVOLAT, Mendes OULAMARA
 
 Sujet : Algorithme de Bron-Kerbosch pour Maximum-Clique
 (cf maxclique.pdf)
+
+
+Format de fichier pour les graphes
+----------------------------------
+
+Format susceptible d'être modifié (on implémentera le format standard
+utilisé dans les graphes du DIMACS).
+
+<nombre de sommets> <nombre d'arêtes>
+[pour chaque arête :
+	<noeud 1> <noeud 2>]
+
diff --git a/g1.graph b/g1.graph
new file mode 100644
index 0000000..bb6eecf
--- /dev/null
+++ b/g1.graph
@@ -0,0 +1,9 @@
+6 7
+1 2
+1 3
+2 3
+3 0
+3 5
+3 4
+5 1
+
diff --git a/graph.c b/graph.c
new file mode 100644
index 0000000..e6be1c1
--- /dev/null
+++ b/graph.c
@@ -0,0 +1,63 @@
+/*
+	Projet d'algorithmique et programmation 2013-2014
+	(cours de C.Matthieu et J.Stern)
+	Alex AUVOLAT, Mendes OULAMARA
+
+	Fonctions pour la manipulation de graphes.
+*/
+
+#include <stdlib.h>
+
+#include "graph.h"
+
+graph load_graph(FILE *stream) {
+	int i, r, a, b;
+
+	graph k = malloc(sizeof(struct graph_descriptor));
+
+	fscanf(stream, "%d ", &k->N);	// read node count
+	k->neighbour = malloc(k->N * sizeof(set));
+	for (i = 0; i < k->N; i++) k->neighbour[i] = empty_set(k->N);
+	
+	fscanf(stream, "%d ", &r);
+	for (i = 0; i < r; i++) {
+		fscanf(stream, "%d %d ", &a, &b);
+		set_add_ip(b, k->neighbour[a]);
+		set_add_ip(a, k->neighbour[b]);
+	}
+
+	return k;
+}
+
+const set graph_neighbours(const graph g, int n) {
+	return g->neighbour[n];
+}
+
+void dump_graphviz(const graph g, FILE *stream) {
+	int i = 0;
+	fprintf(stream, "graph A {\n");
+
+	for (i = 0; i < g->N; i++) {
+		fprintf(stream, "  \"%d\" []\n", i);
+	}
+
+	for (i = 0; i < g->N; i++) {
+		set n = copy_set(graph_neighbours(g, i));
+		while (!(is_set_empty(n))) {
+			int j = elt_of_set(n);
+			if (j >= i) fprintf(stream, "  \"%d\" -- \"%d\"\n", i, j);
+			set_remove_ip(j, n);
+		}
+	}
+	fprintf(stream, "}\n");
+}
+
+void delete_graph(graph g) {
+	int i;
+	for (i = 0; i < g->N; i++) {
+		delete_set(g->neighbour[i]);
+	}
+	free(g->neighbour);
+	free(g);
+}
+
diff --git a/graph.h b/graph.h
new file mode 100644
index 0000000..3b4aec0
--- /dev/null
+++ b/graph.h
@@ -0,0 +1,45 @@
+/*
+	Projet d'algorithmique et programmation 2013-2014
+	(cours de C.Matthieu et J.Stern)
+	Alex AUVOLAT, Mendes OULAMARA
+
+	Fonctions pour la manipulation de graphes.
+	Remarque : un graphe utilise les ensembles de set_*.c, donc si on utilise
+	l'implémentation sous forme de bitset cela donne l'équivalent d'une matrice
+	d'adjacence, alors que l'utilisation de l'implémentation sous forme de liste
+	liée est plus adaptée pour un graphe peu rempli.
+
+	Dans l'ensemble du projet on travaille sur des graphes  non orientées,
+	c'est-à-dire que la matrice d'adjacence est symmétrique.
+
+	La structure donnée ici permet très facilement d'accéder à l'ensemble
+	des voisins d'un sommet, mais il est un peu plus compliqué d'énumérer
+	toutes les arêtes du graphe.
+
+	Il est recommandé d'utiliser la fonction graph_neighbours(int s) pour
+	accéder aux voisins d'un noeud, car celle-ci renvoie un const set et
+	non un simple set, ce qui évite d'accidentelles modifications des
+	données du graphe.
+*/
+
+#ifndef DEF_GRAPH_H
+#define DEF_GRAPH_H
+
+#include <stdio.h>
+
+#include "sets.h"
+
+struct graph_descriptor {
+	int N;					// number of nodes
+	set *neighbour;			// set of neighbours for each node
+};
+
+typedef struct graph_descriptor *graph;
+
+
+graph load_graph(FILE *stream);		// format specified in README file
+const set graph_neighbours(const graph g, int n);
+void dump_graphviz(const graph g, FILE *stream);
+void delete_graph(graph g);
+
+#endif
diff --git a/main.c b/main.c
index 66202c1..ad07324 100644
--- a/main.c
+++ b/main.c
@@ -8,7 +8,40 @@
 */
 
 #include "sets.h"
+#include "graph.h"
+
+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)) {
+			delete_set(*mc);
+			*mc = copy_set(k);
+		}
+	} else {
+		set cc = copy_set(c);
+		while (!(is_set_empty(cc))) {
+			int x = elt_of_set(cc);
+			set_remove_ip(x, cc);
+
+			set k2 = set_add(x, k);
+			set c2 = set_inter(c, graph_neighbours(g, x));
+			max_clique_a(g,k2, c2, mc);
+			delete_set(k2);
+			delete_set(c2);
+		}
+	}
+}
 
 int main() {
+	graph g = load_graph(stdin);
+	dump_graphviz(g, stdout);
+
+	// do stuff with graph
+	set max_clique = empty_set(g->N);
+	set init_s = full_set(g->N);
+	set init_k = empty_set(g->N);
+	max_clique_a(g, init_k, init_s, &max_clique);
+	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 d7ea499..8cc77c4 100644
--- a/set_linked_lists.c
+++ b/set_linked_lists.c
@@ -51,11 +51,33 @@ typedef struct set_elt *element;
 
 set empty_set(int n) {
 	set k = malloc(sizeof(t_set_descriptor));
+	k->N = n;
 	k->first = k->last = NULL;
 	k->size = 0;
 	return k;
 }
 
+set full_set(int n) {
+	int i;
+	set k = malloc(sizeof(t_set_descriptor));
+	k->N = n;
+
+	element prev = NULL;
+	for (i = 0; i < n; i++) {
+		element e = malloc(sizeof(struct set_elt));
+		e->value = i;
+		if (prev == NULL) {
+			k->first = e;
+		} else {
+			prev->next = e;
+		}
+		k->last = prev = e;
+	}
+
+	k->size = n;
+	return k;
+}
+
 set copy_set(const set s) {
 	element iter, prev;
 
@@ -63,7 +85,7 @@ set copy_set(const set s) {
 	t->size = s->size;
 
 	t->first = NULL;
-	if (s->size) {
+	if (s->size > 0) {
 		prev = malloc(sizeof(struct set_elt));
 		prev->value = s->first->value;
 		t->first = prev;
@@ -96,6 +118,10 @@ void delete_set(set s) {
 	free(s);
 }
 
+int set_size(const set s) {
+	return s->size;
+}
+
 void set_union_ip(set a, const set b) {
 	if (b->size == 0) return;
 
diff --git a/sets.h b/sets.h
index 9465043..ffdf82d 100644
--- a/sets.h
+++ b/sets.h
@@ -25,6 +25,7 @@ struct set_elt {
     struct set_elt *next;
 };
 typedef struct {
+	int N;		// range for elements (0 to N-1)
     struct set_elt *first, *last;
 	int size;	// number of elements
 } t_set_descriptor;
@@ -39,10 +40,13 @@ typedef void* set;
 
 
 set empty_set(int size);
+set full_set(int size);		// set containing all elements from 0 to n-1
 set singleton(int size, int x);
 set copy_set(const set s);
 void delete_set(set a);
 
+int set_size(const set s);
+
 void set_union_ip(set a, const set b); 
 void set_inter_ip(set a, const set b);
 void set_diff_ip(set a, const set b);