From 3f0043d05660dd51108f9cd2fcd06975cd8014cf Mon Sep 17 00:00:00 2001
From: Alex AUVOLAT <alex.auvolat@ens.fr>
Date: Sun, 8 Dec 2013 11:10:20 +0100
Subject: Reindent algorithm C, find new max_clique at every possible occasion.

---
 algos.c | 89 ++++++++++++++++++++++++++++++++++-------------------------------
 1 file changed, 47 insertions(+), 42 deletions(-)

diff --git a/algos.c b/algos.c
index 3d24558..1595676 100644
--- a/algos.c
+++ b/algos.c
@@ -53,59 +53,64 @@ void max_clique_b(const graph g, set k, set c, set a, set *mc) {
 // Il est donc de la responsabilité de l'appellant de vérifier qu'à
 // chaque appel les sets sont utilisables et cohérents
 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;
 
-	if (is_set_empty(c)) {
-		if (set_size(k) > set_size(*mc)) { // useless condition
-			delete_set(*mc);
-			*mc = copy_set(k);
-			printf("Found new max clique: "); dump_set(*mc); fflush(stdout);
-		}
-	} else {
-		set c_it = copy_set(c);
-		int u = elt_of_set(c_it), n = 0;
-		set_remove_ip(u, c_it);
+	// 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);
+	}
 
-		{	set temp = set_inter(c, graph_neighbours(g, u));
-			n = set_size(temp);
-			delete_set(temp);
-		}
+	// If we have no possibility to explore, return
+	if (is_set_empty(c)) return;
 
-		int heur = u;
-		while (!is_set_empty(c_it)) {
-			int uprime = elt_of_set_heur(c_it, heur);
-			heur = uprime;
+	// 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);
+	}
 
-			set_remove_ip(uprime, c_it);
+	// 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);
+		set temp = set_inter(c, graph_neighbours(g, uprime));
+		if (set_size(temp) > n) {
+			n = set_size(temp);
+			u = uprime;
 		}
-		delete_set(c_it);
+		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 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 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));
-		}
+		set_remove_ip(x, a);
 		delete_set(t);
+		t = set_diff(a, graph_neighbours(g, u));
 	}
+	delete_set(t);
 }
+
-- 
cgit v1.2.3