diff options
Diffstat (limited to 'main.c')
-rw-r--r-- | main.c | 33 |
1 files changed, 33 insertions, 0 deletions
@@ -8,7 +8,40 @@ */ #include "sets.h" +#include "graph.h" + +void max_clique_a(const graph g, set k, set c, set *mc) { + if (is_set_empty(c)) { + if (set_size(k) > set_size(*mc)) { + delete_set(*mc); + *mc = copy_set(k); + } + } else { + set cc = copy_set(c); + while (!(is_set_empty(cc))) { + int x = elt_of_set(cc); + set_remove_ip(x, cc); + + set k2 = set_add(x, k); + set c2 = set_inter(c, graph_neighbours(g, x)); + max_clique_a(g,k2, c2, mc); + delete_set(k2); + delete_set(c2); + } + } +} int main() { + graph g = load_graph(stdin); + dump_graphviz(g, stdout); + + // do stuff with graph + set max_clique = empty_set(g->N); + set init_s = full_set(g->N); + set init_k = empty_set(g->N); + max_clique_a(g, init_k, init_s, &max_clique); + printf("Max clique: "); dump_set(max_clique); + + delete_graph(g); return 0; } |