Code reorganization

1 files changed, 65 insertions, 8 deletions

diff --git a/algos.c b/algos.c
index 95fd1aa..3da67af 100644
--- a/algos.c
+++ b/algos.c
@@ -82,7 +82,6 @@ int color_subgraph(const graph g, set s, int dump_colors) {
 		set_remove_ip(vertices[i], s);
 		i++;
 	}
-	assert(i == n);
 
 	// Calculate neighbour count for all nodes
 	for (i = 0; i < n; i++) nneigh[i] = 0;
@@ -183,10 +182,7 @@ void max_clique_b(const graph g, set k, set c, set a, set *mc) {
 // argument peuvent être modifiés à la guise de l'algorithme
 // Il est donc de la responsabilité de l'appellant de vérifier qu'à
 // chaque appel les sets sont utilisables et cohérents
-int blabla = 0;
-void max_clique_c(const graph g, set k, set c, set a, set *mc, int prev_size) {
-	blabla++;
-	//if (blabla % 100 == 0) printf("%d\n", blabla);
+void max_clique_c(const graph g, set k, set c, set a, set *mc) {
 	// If we have no chance of improving our max clique, exit
 	if (set_size(k) + set_size(c) <= set_size(*mc)) return;
 
@@ -200,7 +196,69 @@ 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 / 20) {
+	// Find u that maximises |C inter Gamma(u)|
+	set c_it = copy_set(c);
+	int u = elt_of_set(c_it), n = 0;
+	set_remove_ip(u, c_it);
+
+	{	set temp = set_inter(c, graph_neighbours(g, u));
+		n = set_size(temp);
+		delete_set(temp);
+	}
+
+	// Explore possibilites
+	int heur = u;
+	while (!is_set_empty(c_it)) {
+		int uprime = elt_of_set_heur(c_it, heur);
+		set_remove_ip(uprime, c_it);
+		heur = uprime;
+
+		set temp = set_inter(c, graph_neighbours(g, uprime));
+		if (set_size(temp) > n) {
+			n = set_size(temp);
+			u = uprime;
+		}
+		delete_set(temp);
+	}
+	delete_set(c_it);
+
+
+	set t = set_diff(a, graph_neighbours(g, u));
+	heur = u;
+	while (!is_set_empty(t)) {
+		int x = elt_of_set_heur(t, heur);
+		heur = x;
+
+		set k2 = set_add(x, k);
+		set c2 = set_inter(c, graph_neighbours(g, x));
+		set a2 = set_inter(a, graph_neighbours(g, x));
+		max_clique_c(g, k2, c2, a2, mc);
+		delete_set(a2);
+		delete_set(c2);
+		delete_set(k2);
+
+		set_remove_ip(x, a);
+		delete_set(t);
+		t = set_diff(a, graph_neighbours(g, u));
+	}
+	delete_set(t);
+}
+
+void max_clique_c_color(const graph g, set k, set c, set a, set *mc, int prev_size) {
+	// If we have no chance of improving our max clique, exit
+	if (set_size(k) + set_size(c) <= set_size(*mc)) return;
+
+	// If we have improved our clique, great
+	if (set_size(k) > set_size(*mc)) {
+		delete_set(*mc);
+		*mc = copy_set(k);
+		printf("Found new max clique: "); dump_set(*mc); fflush(stdout);
+	}
+
+	// If we have no possibility to explore, return
+	if (is_set_empty(c)) return;
+
+	if (set_size(c) <= prev_size / 2 && (set_size(c) >= 20 || set_size(c) >= g->N / 24)) {
 		prev_size = set_size(c);
 		// Color graph : we may have no possibility
 		set c_copy = copy_set(c);
@@ -246,8 +304,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);
+		max_clique_c_color(g, k2, c2, a2, mc, prev_size);
 		delete_set(a2);
 		delete_set(c2);
 		delete_set(k2);