summaryrefslogtreecommitdiff
path: root/main.c
diff options
context:
space:
mode:
Diffstat (limited to 'main.c')
-rw-r--r--main.c27
1 files changed, 27 insertions, 0 deletions
diff --git a/main.c b/main.c
index d5ac0e1..4960dcb 100644
--- a/main.c
+++ b/main.c
@@ -17,6 +17,7 @@
- g : the graph where the clique is looked for
- k : the clique we are currently examining
- c : the graph nodes we can potentially add to the clique
+ - a : the nodes we can actually add to the clique
- mc : a pointer to the set containing the maximum clique found until now
Returns nothing (result is in *mc).
*/
@@ -44,6 +45,32 @@ void max_clique_a(const graph g, set k, set c, set *mc) {
}
+void max_clique_b(const graph g, set k, set c, set a, set *mc) {
+ if (is_set_empty(c)) {
+ if (set_size(k) > set_size(*mc)) {
+ delete_set(*mc);
+ *mc = copy_set(k);
+ printf("Found new max clique: "); dump_set(*mc); fflush(stdout);
+ }
+ } else {
+ set at = copy_set a;
+ while (!(is_set_empty(a2))) {
+ int x = elt_of_set(at);
+ set_remove_ip(x, at);
+
+ set k2 = set_add(x, k);
+ set c2 = set_inter(c, graph_neighbours(g, x));
+ set a2 = set_inter(at, graph_neighbours(g, x));
+
+ max_clique_a(g,k2, c2, a2, mc);
+ delete_set(k2);
+ delete_set(c2);
+ delete_set(a2);
+ }
+ delete_set(at);
+ }
+}
+
// Driver
void usage(char *pname) {