Ajout de l'heuristique de coloriage.

1 files changed, 103 insertions, 0 deletions

diff --git a/algos.c b/algos.c
index 35f1dfd..b329f0c 100644
--- a/algos.c
+++ b/algos.c
@@ -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;