summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--algos.c73
-rw-r--r--algos.h3
-rw-r--r--main.c26
-rw-r--r--media/2013-12-09-132452_1366x768_scrot.pngbin0 -> 230311 bytes
4 files changed, 82 insertions, 20 deletions
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] [<graph file>]\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 <file.dot>\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
--- /dev/null
+++ b/media/2013-12-09-132452_1366x768_scrot.png
Binary files differ
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-21 13:08:55 +0000