From 77db931b94870a8f28eef482091924471cd18d64 Mon Sep 17 00:00:00 2001 From: Alex Auvolat--bernstein Date: Wed, 4 Dec 2013 16:34:15 +0100 Subject: Algorithm B works. --- Makefile | 4 +-- algos.c | 62 ++++++++++++++++++++++++++++++++++++++++++++ algos.h | 11 ++++++++ main.c | 82 +++++++++++++++++++++-------------------------------------- set_bitsets.c | 9 ++++--- 5 files changed, 109 insertions(+), 59 deletions(-) create mode 100644 algos.c create mode 100644 algos.h diff --git a/Makefile b/Makefile index 2f7927c..b81992e 100644 --- a/Makefile +++ b/Makefile @@ -1,5 +1,5 @@ -COMMON_C=main.c sets.c graph.c -COMMON_H=graph.h sets.h +COMMON_C=main.c sets.c graph.c algos.c +COMMON_H=graph.h sets.h algos.h all : exe_ll exe_bs exe_tr exe_ll_test diff --git a/algos.c b/algos.c new file mode 100644 index 0000000..07c667a --- /dev/null +++ b/algos.c @@ -0,0 +1,62 @@ +#include "algos.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); + printf("Found new max clique: "); dump_set(*mc); fflush(stdout); + } + } 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); + } + delete_set(cc); + } +} + +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)) { + delete_set(*mc); + *mc = copy_set(k); + 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); + + set k2 = set_add(x, k); + set c2 = set_inter(c, graph_neighbours(g, x)); + set a2 = set_inter(at, graph_neighbours(g, x)); + + max_clique_b(g,k2, c2, a2, mc); + delete_set(k2); + delete_set(c2); + delete_set(a2); + } + delete_set(at); + } +} + +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)) { + delete_set(*mc); + *mc = copy_set(k); + printf("Found new max clique: "); dump_set(*mc); fflush(stdout); + } + } else { + //TODO + } +} diff --git a/algos.h b/algos.h new file mode 100644 index 0000000..4f20639 --- /dev/null +++ b/algos.h @@ -0,0 +1,11 @@ +#ifndef DEF_ALGOS_H +#define DEF_ALGOS_H + +#include "graph.h" + +void max_clique_a(const graph g, set k, set c, set *mc); +void max_clique_b(const graph g, set k, set c, set a, set *mc); +void max_clique_c(const graph g, set k, set c, set a, set *mc); + +#endif + diff --git a/main.c b/main.c index 4960dcb..4eb0f5d 100644 --- a/main.c +++ b/main.c @@ -11,6 +11,7 @@ #include "sets.h" #include "graph.h" +#include "algos.h" /* max_clique calculates the maximum clique in a graph. Arguments : @@ -21,55 +22,7 @@ - mc : a pointer to the set containing the maximum clique found until now Returns nothing (result is in *mc). */ -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); - printf("Found new max clique: "); dump_set(*mc); fflush(stdout); - } - } 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); - } - delete_set(cc); - } -} - -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)) { - delete_set(*mc); - *mc = copy_set(k); - printf("Found new max clique: "); dump_set(*mc); fflush(stdout); - } - } else { - set at = copy_set a; - while (!(is_set_empty(a2))) { - int x = elt_of_set(at); - set_remove_ip(x, at); - - set k2 = set_add(x, k); - set c2 = set_inter(c, graph_neighbours(g, x)); - set a2 = set_inter(at, graph_neighbours(g, x)); - - max_clique_a(g,k2, c2, a2, mc); - delete_set(k2); - delete_set(c2); - delete_set(a2); - } - delete_set(at); - } -} // Driver @@ -77,6 +30,8 @@ void usage(char *pname) { printf("\nUsage:\n\t%s [options] []\n\n", pname); printf("Available options:\n"); printf("\n -d\n\tRead input in DIMACS format\n"); + printf("\n -b\n\tUse algorithm B\n"); + printf("\n -c\n\tUse algorithm C\n"); printf("\n -o \n\tDump graph in graphwiz .dot format\n"); printf("\n -h, --help\n\tShow this help page\n"); exit(1); @@ -87,6 +42,7 @@ int main(int argc, char **argv) { int dimacs = 0; char *filename = "-"; char *dump = NULL; + int algo = 0; for (i = 1; i < argc; i++) { if (!strcmp(argv[i], "-d")) { @@ -94,6 +50,10 @@ 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], "-b")) { + algo = 1; + } else if (!strcmp(argv[i], "-c")) { + algo = 2; } else if (argv[i][0] == '-') { usage(argv[0]); } else { @@ -127,11 +87,27 @@ int main(int argc, char **argv) { } // 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); + if (algo == 0) { + 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); + } else if (algo == 1) { + set max_clique = empty_set(g->N); + set init_c = full_set(g->N); + set init_a = full_set(g->N); + set init_k = empty_set(g->N); + max_clique_b(g, init_k, init_c, init_a, &max_clique); + printf("Max clique: "); dump_set(max_clique); + } else if (algo == 2) { + set max_clique = empty_set(g->N); + set init_c = full_set(g->N); + set init_a = full_set(g->N); + set init_k = empty_set(g->N); + max_clique_c(g, init_k, init_c, init_a, &max_clique); + printf("Max clique: "); dump_set(max_clique); + } delete_graph(g); return 0; diff --git a/set_bitsets.c b/set_bitsets.c index 6645e0e..30e4dc9 100644 --- a/set_bitsets.c +++ b/set_bitsets.c @@ -48,7 +48,7 @@ set empty_set(int n){ set copy_set(const set s){ set res = empty_set(s.N); *(res.size) = *(s.size); - int NC = nbCells(*(s.size)), i; + int NC = nbCells(s.N), i; for(i = 0; i < NC; i++) res.tab[i] = s.tab[i]; return res; @@ -64,7 +64,7 @@ void set_union_ip(set a, const set b){ printf("Union failed : the sets don't have the same size\n"); assert(a.N == b.N); } - int NC = nbCells(*(a.size)), i; + int NC = nbCells(a.N), i; *(a.size)=0; for(i = 0; i < NC; i++) { a.tab[i] = a.tab[i]|b.tab[i]; @@ -77,7 +77,7 @@ void set_inter_ip(set a, const set b){ printf("Intersection failed : the sets don't have the same size\n"); assert(a.N == b.N); } - int NC = nbCells(*(a.size)), i; + int NC = nbCells(a.N), i; *(a.size)=0; for(i = 0; i < NC; i++){ a.tab[i] = a.tab[i]&b.tab[i]; @@ -91,7 +91,7 @@ void set_diff_ip(set a, const set b){ printf("Difference failed : the sets don't have the same size\n"); assert(a.N == b.N); } - int NC = nbCells(*(a.size)), i; + int NC = nbCells(a.N), i; for(i = 0; i < NC; i++) { a.tab[i] = a.tab[i] & (~b.tab[i]); *(a.size) += nb_one(a.tab[i]); @@ -125,6 +125,7 @@ int elt_of_set(const set s){ return i*SCOD+dyadic_val(s.tab[i]); printf("No element in an empty set!\n"); + dump_set(s); assert(false); } -- cgit v1.2.3