summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--algos.c22
-rw-r--r--algos.h2
-rw-r--r--main.c4
3 files changed, 19 insertions, 9 deletions
diff --git a/algos.c b/algos.c
index 3563903..34a1e15 100644
--- a/algos.c
+++ b/algos.c
@@ -38,8 +38,8 @@ void color_subgraph_aux(const graph g, int *colors, int *v, const int n) {
// Put that element at the beginning of vector v, so that the remaining subgraph is defined by v[1..]
if (x != 0) {
t = v[x];
- v[0] = v[x];
- v[x] = t;
+ v[x] = v[0];
+ v[0] = t;
}
// Color remaining subgraph (v[1..])
@@ -62,7 +62,7 @@ void color_subgraph_aux(const graph g, int *colors, int *v, const int n) {
assert(colors[0] != -1);
}
-int color_subgraph(const graph g, set s) {
+int color_subgraph(const graph g, set s, int dump_colors) {
int i, m;
const int n = set_size(s);
@@ -70,7 +70,7 @@ int color_subgraph(const graph g, set s) {
int colors[n], vertices[n];
for (i = 0; i < n; i++)
- colors[i] = 0;
+ colors[i] = -1;
// Put all vertices in vertice vector (order is not important)
vertices[0] = elt_of_set(s);
@@ -87,9 +87,13 @@ int color_subgraph(const graph g, set s) {
color_subgraph_aux(g, colors, vertices, n);
// Count colors
- m = colors[0];
- for (i = 1; i < n; i++)
+ m = -1;
+ for (i = 0; i < n; i++) {
+ assert(colors[i] != -1);
if (colors[i] > m) m = colors[i];
+ if (dump_colors) printf("%d:%d ", vertices[i], colors[i]);
+ }
+ if (dump_colors) printf("\n");
return m + 1;
}
@@ -186,12 +190,11 @@ 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 / 30) {
- //if (rand() % 7919 == 0 && set_size(c) >= 20 ) {
+ if (set_size(c) <= prev_size / 2 && set_size(c) >= g->N / 10) {
prev_size = set_size(c);
// Color graph : we may have no possibility
set c_copy = copy_set(c);
- int color_count = color_subgraph(g, c_copy);
+ int color_count = color_subgraph(g, c_copy, 0);
delete_set(c_copy);
if (set_size(k) + color_count <= set_size(*mc)) return;
}
@@ -233,6 +236,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);
delete_set(a2);
delete_set(c2);
diff --git a/algos.h b/algos.h
index b8959dd..c86c70a 100644
--- a/algos.h
+++ b/algos.h
@@ -3,6 +3,8 @@
#include "graph.h"
+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);
diff --git a/main.c b/main.c
index 3faf077..febe6a5 100644
--- a/main.c
+++ b/main.c
@@ -94,6 +94,10 @@ int main(int argc, char **argv) {
max_clique_b(g, init_k, init_c, init_a, &max_clique);
printf("Max clique: "); dump_set(max_clique);
} else if (algo == 2) {
+ set k = full_set(g->N);
+ color_subgraph(g, k, 1);
+ delete_set(k);
+
set max_clique = empty_set(g->N);
set init_c = full_set(g->N);
set init_a = full_set(g->N);