From 3a1b146a5761db20d243ae5224a962eeca19b506 Mon Sep 17 00:00:00 2001 From: Alex AUVOLAT Date: Tue, 10 Dec 2013 10:26:12 +0100 Subject: Code reorganization --- algos.c | 73 +++++++++++++++++++++++++---- algos.h | 3 +- main.c | 26 +++++----- media/2013-12-09-132452_1366x768_scrot.png | Bin 0 -> 230311 bytes 4 files changed, 82 insertions(+), 20 deletions(-) create mode 100644 media/2013-12-09-132452_1366x768_scrot.png diff --git a/algos.c b/algos.c index 95fd1aa..3da67af 100644 --- a/algos.c +++ b/algos.c @@ -82,7 +82,6 @@ int color_subgraph(const graph g, set s, int dump_colors) { set_remove_ip(vertices[i], s); i++; } - assert(i == n); // Calculate neighbour count for all nodes for (i = 0; i < n; i++) nneigh[i] = 0; @@ -183,10 +182,7 @@ void max_clique_b(const graph g, set k, set c, set a, set *mc) { // 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 -int blabla = 0; -void max_clique_c(const graph g, set k, set c, set a, set *mc, int prev_size) { - blabla++; - //if (blabla % 100 == 0) printf("%d\n", blabla); +void max_clique_c(const graph g, set k, set c, set a, set *mc) { // If we have no chance of improving our max clique, exit if (set_size(k) + set_size(c) <= set_size(*mc)) return; @@ -200,7 +196,69 @@ void max_clique_c(const graph g, set k, set c, set a, set *mc, int prev_size) { // If we have no possibility to explore, return if (is_set_empty(c)) return; - if (set_size(c) <= prev_size / 2 && set_size(c) >= g->N / 20) { + // Find u that maximises |C inter Gamma(u)| + set c_it = copy_set(c); + int u = elt_of_set(c_it), n = 0; + set_remove_ip(u, c_it); + + { set temp = set_inter(c, graph_neighbours(g, u)); + n = set_size(temp); + delete_set(temp); + } + + // Explore possibilites + int heur = u; + while (!is_set_empty(c_it)) { + int uprime = elt_of_set_heur(c_it, heur); + set_remove_ip(uprime, c_it); + heur = uprime; + + set temp = set_inter(c, graph_neighbours(g, uprime)); + if (set_size(temp) > n) { + n = set_size(temp); + u = uprime; + } + delete_set(temp); + } + delete_set(c_it); + + + set t = set_diff(a, graph_neighbours(g, u)); + heur = u; + while (!is_set_empty(t)) { + int x = elt_of_set_heur(t, heur); + heur = x; + + 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); +} + +void max_clique_c_color(const graph g, set k, set c, set a, set *mc, int prev_size) { + // If we have no chance of improving our max clique, exit + if (set_size(k) + set_size(c) <= set_size(*mc)) return; + + // If we have improved our clique, great + if (set_size(k) > set_size(*mc)) { + delete_set(*mc); + *mc = copy_set(k); + printf("Found new max clique: "); dump_set(*mc); fflush(stdout); + } + + // If we have no possibility to explore, return + if (is_set_empty(c)) return; + + if (set_size(c) <= prev_size / 2 && (set_size(c) >= 20 || set_size(c) >= g->N / 24)) { prev_size = set_size(c); // Color graph : we may have no possibility set c_copy = copy_set(c); @@ -246,8 +304,7 @@ void max_clique_c(const graph g, set k, set c, set a, set *mc, int prev_size) { set k2 = set_add(x, k); set c2 = set_inter(c, graph_neighbours(g, x)); set a2 = set_inter(a, graph_neighbours(g, x)); - assert(!set_mem(x, c2)); - max_clique_c(g, k2, c2, a2, mc, prev_size); + max_clique_c_color(g, k2, c2, a2, mc, prev_size); delete_set(a2); delete_set(c2); delete_set(k2); diff --git a/algos.h b/algos.h index c86c70a..1edefcb 100644 --- a/algos.h +++ b/algos.h @@ -7,7 +7,8 @@ int color_subgraph(const graph g, set s, int dump_colors); 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, int prev_size); +void max_clique_c(const graph g, set k, set c, set a, set *mc); +void max_clique_c_color(const graph g, set k, set c, set a, set *mc, int prev_size); #endif diff --git a/main.c b/main.c index 549a406..7e6d749 100644 --- a/main.c +++ b/main.c @@ -19,10 +19,11 @@ 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 -x\n\tRead input in custom format instead of 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 -cc\n\tUse algorithm C with coloring\n"); printf("\n -o \n\tDump graph in graphwiz .dot format\n"); printf("\n -h, --help\n\tShow this help page\n"); exit(1); @@ -30,14 +31,14 @@ void usage(char *pname) { int main(int argc, char **argv) { int i; - int dimacs = 0; + int dimacs = 1; char *filename = "-"; char *dump = NULL; int algo = 0; for (i = 1; i < argc; i++) { - if (!strcmp(argv[i], "-d")) { - dimacs = 1; + if (!strcmp(argv[i], "-x")) { + dimacs = 0; } else if (!strcmp(argv[i], "-o")) { if (++i == argc) usage(argv[0]); dump = argv[i]; @@ -47,6 +48,8 @@ int main(int argc, char **argv) { algo = 1; } else if (!strcmp(argv[i], "-c")) { algo = 2; + } else if (!strcmp(argv[i], "-cc")) { + algo = 3; } else if (argv[i][0] == '-') { usage(argv[0]); } else { @@ -80,32 +83,33 @@ int main(int argc, char **argv) { } // do stuff with graph + set max_clique = empty_set(g->N); 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 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); + } else if (algo == 3) { set k = full_set(g->N); int clique_upper_bound = color_subgraph(g, k, 0); delete_set(k); printf("Upper bound on max clique size: %d\n", clique_upper_bound); - 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, g->N); - printf("Max clique: "); dump_set(max_clique); + max_clique_c_color(g, init_k, init_c, init_a, &max_clique, g->N); } + printf("Max clique: "); dump_set(max_clique); return 0; } diff --git a/media/2013-12-09-132452_1366x768_scrot.png b/media/2013-12-09-132452_1366x768_scrot.png new file mode 100644 index 0000000..b3e5564 Binary files /dev/null and b/media/2013-12-09-132452_1366x768_scrot.png differ -- cgit v1.2.3