diff options
| -rw-r--r-- | algos.c | 34 | ||||
| -rw-r--r-- | main.c | 4 | ||||
| -rw-r--r-- | set_linked_lists.c | 3 |
3 files changed, 33 insertions, 8 deletions
@@ -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,23 @@ 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 + int u = elt_of_set(c); // TODO maximiser C inter Gamma(u) + set t = set_diff(a, graph_neighbours(g, u)); + while (!is_set_empty(t)) { + int x = elt_of_set(t); + + 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); } } @@ -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_linked_lists.c b/set_linked_lists.c index e865b95..86a53b3 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; |