summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--Makefile4
-rw-r--r--algos.c62
-rw-r--r--algos.h11
-rw-r--r--main.c82
-rw-r--r--set_bitsets.c9
5 files changed, 109 insertions, 59 deletions
diff --git a/Makefile b/Makefile
index 2f7927c..b81992e 100644
--- a/Makefile
+++ b/Makefile
@@ -1,5 +1,5 @@
-COMMON_C=main.c sets.c graph.c
-COMMON_H=graph.h sets.h
+COMMON_C=main.c sets.c graph.c algos.c
+COMMON_H=graph.h sets.h algos.h
all : exe_ll exe_bs exe_tr exe_ll_test
diff --git a/algos.c b/algos.c
new file mode 100644
index 0000000..07c667a
--- /dev/null
+++ b/algos.c
@@ -0,0 +1,62 @@
+#include "algos.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);
+ printf("Found new max clique: "); dump_set(*mc); fflush(stdout);
+ }
+ } 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);
+ }
+ delete_set(cc);
+ }
+}
+
+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(at))) {
+ 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_b(g,k2, c2, a2, mc);
+ delete_set(k2);
+ delete_set(c2);
+ delete_set(a2);
+ }
+ delete_set(at);
+ }
+}
+
+void max_clique_c(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 {
+ //TODO
+ }
+}
diff --git a/algos.h b/algos.h
new file mode 100644
index 0000000..4f20639
--- /dev/null
+++ b/algos.h
@@ -0,0 +1,11 @@
+#ifndef DEF_ALGOS_H
+#define DEF_ALGOS_H
+
+#include "graph.h"
+
+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);
+void max_clique_c(const graph g, set k, set c, set a, set *mc);
+
+#endif
+
diff --git a/main.c b/main.c
index 4960dcb..4eb0f5d 100644
--- a/main.c
+++ b/main.c
@@ -11,6 +11,7 @@
#include "sets.h"
#include "graph.h"
+#include "algos.h"
/*
max_clique calculates the maximum clique in a graph. Arguments :
@@ -21,55 +22,7 @@
- mc : a pointer to the set containing the maximum clique found until now
Returns nothing (result is in *mc).
*/
-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);
- printf("Found new max clique: "); dump_set(*mc); fflush(stdout);
- }
- } 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);
- }
- delete_set(cc);
- }
-}
-
-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
@@ -77,6 +30,8 @@ void usage(char *pname) {
printf("\nUsage:\n\t%s [options] [<graph file>]\n\n", pname);
printf("Available options:\n");
printf("\n -d\n\tRead input in DIMACS format\n");
+ printf("\n -b\n\tUse algorithm B\n");
+ printf("\n -c\n\tUse algorithm C\n");
printf("\n -o <file.dot>\n\tDump graph in graphwiz .dot format\n");
printf("\n -h, --help\n\tShow this help page\n");
exit(1);
@@ -87,6 +42,7 @@ int main(int argc, char **argv) {
int dimacs = 0;
char *filename = "-";
char *dump = NULL;
+ int algo = 0;
for (i = 1; i < argc; i++) {
if (!strcmp(argv[i], "-d")) {
@@ -94,6 +50,10 @@ int main(int argc, char **argv) {
} else if (!strcmp(argv[i], "-o")) {
if (++i == argc) usage(argv[0]);
dump = argv[i];
+ } else if (!strcmp(argv[i], "-b")) {
+ algo = 1;
+ } else if (!strcmp(argv[i], "-c")) {
+ algo = 2;
} else if (argv[i][0] == '-') {
usage(argv[0]);
} else {
@@ -127,11 +87,27 @@ int main(int argc, char **argv) {
}
// 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);
+ if (algo == 0) {
+ 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);
+ } else if (algo == 1) {
+ set max_clique = empty_set(g->N);
+ set init_c = full_set(g->N);
+ set init_a = full_set(g->N);
+ set init_k = empty_set(g->N);
+ max_clique_b(g, init_k, init_c, init_a, &max_clique);
+ printf("Max clique: "); dump_set(max_clique);
+ } else if (algo == 2) {
+ set max_clique = empty_set(g->N);
+ set init_c = full_set(g->N);
+ set init_a = full_set(g->N);
+ set init_k = empty_set(g->N);
+ max_clique_c(g, init_k, init_c, init_a, &max_clique);
+ printf("Max clique: "); dump_set(max_clique);
+ }
delete_graph(g);
return 0;
diff --git a/set_bitsets.c b/set_bitsets.c
index 6645e0e..30e4dc9 100644
--- a/set_bitsets.c
+++ b/set_bitsets.c
@@ -48,7 +48,7 @@ set empty_set(int n){
set copy_set(const set s){
set res = empty_set(s.N);
*(res.size) = *(s.size);
- int NC = nbCells(*(s.size)), i;
+ int NC = nbCells(s.N), i;
for(i = 0; i < NC; i++)
res.tab[i] = s.tab[i];
return res;
@@ -64,7 +64,7 @@ void set_union_ip(set a, const set b){
printf("Union failed : the sets don't have the same size\n");
assert(a.N == b.N);
}
- int NC = nbCells(*(a.size)), i;
+ int NC = nbCells(a.N), i;
*(a.size)=0;
for(i = 0; i < NC; i++) {
a.tab[i] = a.tab[i]|b.tab[i];
@@ -77,7 +77,7 @@ void set_inter_ip(set a, const set b){
printf("Intersection failed : the sets don't have the same size\n");
assert(a.N == b.N);
}
- int NC = nbCells(*(a.size)), i;
+ int NC = nbCells(a.N), i;
*(a.size)=0;
for(i = 0; i < NC; i++){
a.tab[i] = a.tab[i]&b.tab[i];
@@ -91,7 +91,7 @@ void set_diff_ip(set a, const set b){
printf("Difference failed : the sets don't have the same size\n");
assert(a.N == b.N);
}
- int NC = nbCells(*(a.size)), i;
+ int NC = nbCells(a.N), i;
for(i = 0; i < NC; i++) {
a.tab[i] = a.tab[i] & (~b.tab[i]);
*(a.size) += nb_one(a.tab[i]);
@@ -125,6 +125,7 @@ int elt_of_set(const set s){
return i*SCOD+dyadic_val(s.tab[i]);
printf("No element in an empty set!\n");
+ dump_set(s);
assert(false);
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-21 12:25:57 +0000