From 71094b2d48ac784e60d454609064d20e83c017be Mon Sep 17 00:00:00 2001 From: Alex Auvolat--bernstein Date: Wed, 4 Dec 2013 17:26:06 +0100 Subject: Finished implementation for algorithm C, and corrected bitset bugs. --- algos.c | 29 ++++++++++++++++++++++++++++- 1 file changed, 28 insertions(+), 1 deletion(-) (limited to 'algos.c') diff --git a/algos.c b/algos.c index 542c8a5..60e94fa 100644 --- a/algos.c +++ b/algos.c @@ -60,10 +60,37 @@ void max_clique_c(const graph g, set k, set c, set a, set *mc) { printf("Found new max clique: "); dump_set(*mc); fflush(stdout); } } else { - int u = elt_of_set(c); // TODO maximiser 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); + } + + int heur = u; + while (!is_set_empty(c_it)) { + int uprime = elt_of_set(c_it); + heur = uprime; + + set_remove_ip(uprime, c_it); + + 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(t); + heur = x; set k2 = set_add(x, k); set c2 = set_inter(c, graph_neighbours(g, x)); -- cgit v1.2.3