From 8211bf815dbcf193439fc3f0927a5e9de1bce3bc Mon Sep 17 00:00:00 2001 From: Alex AUVOLAT Date: Sun, 24 Nov 2013 21:56:36 +0100 Subject: Implemented basic algorithm for finding maximum clique... no optimizations. --- main.c | 33 +++++++++++++++++++++++++++++++++ 1 file changed, 33 insertions(+) (limited to 'main.c') diff --git a/main.c b/main.c index 66202c1..ad07324 100644 --- a/main.c +++ b/main.c @@ -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; } -- cgit v1.2.3