From f1464f81cdd2b841781474c05d8ce8dd4bf9bf4f Mon Sep 17 00:00:00 2001
From: Ali Gholami Rudi <ali@rudi.ir>
Date: Wed, 17 Oct 2012 19:25:05 +0330
Subject: [PATCH] rangi: skip roots without nsub colors in their neighborhood

---
 rangi.c | 43 ++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 42 insertions(+), 1 deletion(-)

diff --git a/rangi.c b/rangi.c
index 4f8cf1d..a4060fb 100644
--- a/rangi.c
+++ b/rangi.c
@@ -148,6 +148,7 @@ static int goodroot(int u, int crank)
 
 static int kavosh_enum(int v, int *used, int nsub);
 static int fanmod_enum(int v, int *used, int nsub);
+static int reachable(int v, int *used, int nsub);
 
 /* generate all subgraphs of size nsub with all possible root vertices */
 static int gensubs(int nsub)
@@ -161,7 +162,8 @@ static int gensubs(int nsub)
 		if (!doheur || goodroot(S[i], crank)) {
 			used[S[i]] = 1;
 			if (!ownroot(nsub, i))
-				found += x_enum(S[i], used, nsub);
+				if (!doheur || reachable(S[i], used, nsub))
+					found += x_enum(S[i], used, nsub);
 		}
 	}
 	return found;
@@ -664,3 +666,42 @@ static int fanmod_enum(int v, int *used, int nsub)
 	fanmod_addext(sub_map, ext_map, ext, used, v);
 	return fanmod_fill(used, sub, sub_map, ext, ext_map, nsub - 1);
 }
+
+
+/* count the number of reachable colors from a vertex */
+
+static int reachable_bfs(int v, int depth, int nsub, int nclrs, int *mark, int *used, int *clrs)
+{
+	int q[NNODES];
+	int nq = 0;
+	int added = 0;
+	int i;
+	for (i = 0; C[v][i] >= 0; i++) {
+		if (!clrs[C[v][i]]) {
+			clrs[C[v][i]] = 1;
+			added++;
+		}
+	}
+	if (depth >= nsub - 1)
+		return added;
+	for (i = 0; N[v][i] >= 0; i++) {
+		int u = N[v][i];
+		if (!mark[u] && !used[u]) {
+			q[nq++] = u;
+			mark[u] = 1;
+		}
+	}
+	for (i = 0; i < nq; i++) {
+		if (nclrs + added >= nsub)
+			break;
+		added += reachable_bfs(q[i], depth + 1, nsub, nclrs + added, mark, used, clrs);
+	}
+	return added;
+}
+
+static int reachable(int v, int *used, int nsub)
+{
+	int mark[NNODES] = {0};
+	int clrs[NCOLORS] = {0};
+	return reachable_bfs(v, 0, nsub, 0, mark, used, clrs) >= nsub;
+}
-- 
2.11.4.GIT