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

1 files changed, 63 insertions, 0 deletions

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