diff options
Diffstat (limited to 'algos.c')
-rw-r--r-- | algos.c | 29 |
1 files changed, 28 insertions, 1 deletions
@@ -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)); |