From c4e66752adf068b2b55cca81c018966b65d2c0bd Mon Sep 17 00:00:00 2001
From: Alex AUVOLAT <alex.auvolat@ens.fr>
Date: Sun, 8 Dec 2013 19:33:04 +0100
Subject: Improved coloring

---
 algos.c | 42 +++++++++++++++++++++++++++---------------
 1 file changed, 27 insertions(+), 15 deletions(-)

diff --git a/algos.c b/algos.c
index 34a1e15..fdf7243 100644
--- a/algos.c
+++ b/algos.c
@@ -13,7 +13,7 @@
  * 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) {
+void color_subgraph_aux(const graph g, int *colors, int *v, int *nneigh, const int n) {
 	int i, j, t;
 
 	if (n == 0) return;
@@ -24,15 +24,9 @@ void color_subgraph_aux(const graph g, int *colors, int *v, const int n) {
 	}
 
 	// 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;
-		}
+	int x = 0;
+	for (i = 1; i < n; i++) {
+		if (nneigh[i] < nneigh[x]) x = i;
 	}
 
 	// Put that element at the beginning of vector v, so that the remaining subgraph is defined by v[1..]
@@ -40,10 +34,19 @@ void color_subgraph_aux(const graph g, int *colors, int *v, const int n) {
 		t = v[x];
 		v[x] = v[0];
 		v[0] = t;
+
+		t = nneigh[x];
+		nneigh[x] = nneigh[0];
+		nneigh[0] = t;
+	}
+
+	// update nneigh
+	for (i = 1; i < n; i++) {
+		if (set_mem(v[i], graph_neighbours(g, v[0]))) nneigh[i]--;
 	}
 
 	// Color remaining subgraph (v[1..])
-	color_subgraph_aux(g, colors + 1, v + 1, n - 1);
+	color_subgraph_aux(g, colors + 1, v + 1, nneigh + 1, n - 1);
 
 	// Find free color
 	colors[0] = -1;
@@ -63,12 +66,12 @@ void color_subgraph_aux(const graph g, int *colors, int *v, const int n) {
 }
 
 int color_subgraph(const graph g, set s, int dump_colors) {
-	int i, m;
+	int i, j, m;
 
 	const int n = set_size(s);
 	if (n == 0) return 0;
 
-	int colors[n], vertices[n];
+	int colors[n], vertices[n], nneigh[n];
 	for (i = 0; i < n; i++)
 		colors[i] = -1;
 	
@@ -83,8 +86,17 @@ int color_subgraph(const graph g, set s, int dump_colors) {
 	}
 	assert(i == n);
 
+	// Calculate neighbour count for all nodes
+	for (i = 0; i < n; i++) nneigh[i] = 0;
+	for (i = 0; i < n; i++) {
+		for (j = 0; j < n; j++) {
+			if (set_mem(vertices[i], graph_neighbours(g, vertices[j])))
+				nneigh[i]++;
+		}
+	}
+
 	// Color graph
-	color_subgraph_aux(g, colors, vertices, n);
+	color_subgraph_aux(g, colors, vertices, nneigh, n);
 
 	// Count colors
 	m = -1;
@@ -190,7 +202,7 @@ 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 / 10) {
+	if (set_size(c) <= prev_size / 2 && set_size(c) >= g->N / 20) {
 		prev_size = set_size(c);
 		// Color graph : we may have no possibility
 		set c_copy = copy_set(c);
-- 
cgit v1.2.3