diff options
| -rw-r--r-- | algos.c | 103 |
1 files changed, 103 insertions, 0 deletions
@@ -1,6 +1,100 @@ +#include <assert.h> +#include <stdbool.h> + + #include "algos.h" +/* Heuristique de coloriage + * Trouve un coloriage non-optimal (mais parfois proche) du sous-graphe engendré + * par s dans le graphe g. + * Ne donne pas le coloriage, mais juste le nombre de couleurs d'un coloriage possible (nombre que l'on cherche à minimiser) + * Cet algorithme est assez naif mais il est fait pour tourner sur des graphes de taille petite (de l'ordre de 20), donc un + * algorithme même en n^3 ou n^4 est acceptable (ou pas...) + */ + +void color_subgraph_aux(const graph g, int *colors, int *v, const int n) { + int i, j, t; + + if (n == 0) return; + + if (n == 1) { + colors[0] = 0; + return; + } + + // Find element with smallest neighbours count + int x = -1, m = n + 1; + for (i = 0; i < n; i++) { + t = 0; + for (j = 0; j < n; j++) { + if (set_mem(v[j], graph_neighbours(g, v[i]))) t++; + } + if (t < m) { + x = i; m = t; + } + } + + // 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; + } + + // Color remaining subgraph (v[1..]) + color_subgraph_aux(g, colors + 1, v + 1, n - 1); + + // Find free color + colors[0] = -1; + bool used[n]; + for (i = 0; i < n; i++) used[i] = false; + for (i = 1; i < n; i++) { + if (set_mem(v[i], graph_neighbours(g, v[0]))) + used[colors[i]] = true; + } + for (i = 0; i < n; i++) { + if (used[i] == false) { + colors[0] = i; + break; + } + } + assert(colors[0] != -1); +} + +int color_subgraph(const graph g, set s) { + int i, m; + + const int n = set_size(s); + if (n == 0) return 0; + + int colors[n], vertices[n]; + for (i = 0; i < n; i++) + colors[i] = 0; + + // Put all vertices in vertice vector (order is not important) + vertices[0] = elt_of_set(s); + set_remove_ip(vertices[0], s); + i = 1; + while (!is_set_empty(s)) { + vertices[i] = elt_of_set_heur(s, vertices[i-1]); + set_remove_ip(vertices[i], s); + i++; + } + assert(i == n); + + // Color graph + color_subgraph_aux(g, colors, vertices, n); + + // Count colors + m = colors[0]; + for (i = 1; i < n; i++) + if (colors[i] > m) m = colors[i]; + + return m + 1; +} + + /*Premier algorithme naïf. * g : graphe où on cherche les cliques * k : clique actuelle @@ -89,6 +183,15 @@ void max_clique_c(const graph g, set k, set c, set a, set *mc) { // If we have no possibility to explore, return if (is_set_empty(c)) return; + if (set_size(c) == g->N / 2) { + // Color graph : we may have no possibility + set c_copy = copy_set(c); + int color_count = color_subgraph(g, c_copy); + delete_set(c_copy); + if (set_size(k) + color_count <= set_size(*mc)) return; + } + + // Find u that maximises |C inter Gamma(u)| set c_it = copy_set(c); int u = elt_of_set(c_it), n = 0; |