Implemented basic algorithm for finding maximum clique... no optimizations.

1 files changed, 33 insertions, 0 deletions

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;
 }