diff options
Diffstat (limited to 'main.c')
| -rw-r--r-- | main.c | 82 |
1 files changed, 29 insertions, 53 deletions
@@ -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] [<graph file>]\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 <file.dot>\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; |