diff options
| -rw-r--r-- | algos.c | 22 | ||||
| -rw-r--r-- | algos.h | 2 | ||||
| -rw-r--r-- | main.c | 4 |
3 files changed, 19 insertions, 9 deletions
@@ -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); @@ -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); @@ -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); |