From 5c0bf0e1f8bf2cd1d309e443c9632423ca96589a Mon Sep 17 00:00:00 2001
From: Alex AUVOLAT <alex.auvolat@ens.fr>
Date: Sun, 8 Dec 2013 19:23:25 +0100
Subject: Rien du tout, on a juste un coloriage correct maintenant.

---
 algos.c | 22 +++++++++++++---------
 algos.h |  2 ++
 main.c  |  4 ++++
 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);
-- 
cgit v1.2.3