diff options
| -rw-r--r-- | Makefile | 17 | ||||
| -rw-r--r-- | README | 12 | ||||
| -rw-r--r-- | g1.graph | 9 | ||||
| -rw-r--r-- | graph.c | 63 | ||||
| -rw-r--r-- | graph.h | 45 | ||||
| -rw-r--r-- | main.c | 33 | ||||
| -rw-r--r-- | set_linked_lists.c | 28 | ||||
| -rw-r--r-- | sets.h | 4 |
8 files changed, 203 insertions, 8 deletions
@@ -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 : @@ -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 + @@ -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); +} + @@ -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 @@ -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; @@ -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); |