1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
|
#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);
}
}
// Voir notice de convention ci-dessous
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 {
while (!(is_set_empty(a))) {
int x = elt_of_set(a);
set_remove_ip(x, a);
set k2 = set_add(x, k);
set c2 = set_inter(c, graph_neighbours(g, x));
set a2 = set_inter(a, graph_neighbours(g, x));
max_clique_b(g,k2, c2, a2, mc);
delete_set(k2);
delete_set(c2);
delete_set(a2);
}
}
}
// Convention : lors d'un appel de fonction, les set donnés en
// argument peuvent être modifiés à la guise de l'algorithme
// Il est donc de la responsabilité de l'appellant de vérifier qu'à
// chaque appel les sets sont utilisables et cohérents
void max_clique_c(const graph g, set k, set c, set a, set *mc) {
// If we have no chance of improving our max clique, exit
if (set_size(k) + set_size(c) <= set_size(*mc)) return;
// If we have improved our clique, great
if (set_size(k) > set_size(*mc)) {
delete_set(*mc);
*mc = copy_set(k);
printf("Found new max clique: "); dump_set(*mc); fflush(stdout);
}
// If we have no possibility to explore, return
if (is_set_empty(c)) return;
// Find u that maximises |C inter Gamma(u)|
set c_it = copy_set(c);
int u = elt_of_set(c_it), n = 0;
set_remove_ip(u, c_it);
{ set temp = set_inter(c, graph_neighbours(g, u));
n = set_size(temp);
delete_set(temp);
}
// Explore possibilites
int heur = u;
while (!is_set_empty(c_it)) {
int uprime = elt_of_set_heur(c_it, heur);
set_remove_ip(uprime, c_it);
heur = uprime;
set temp = set_inter(c, graph_neighbours(g, uprime));
if (set_size(temp) > n) {
n = set_size(temp);
u = uprime;
}
delete_set(temp);
}
delete_set(c_it);
set t = set_diff(a, graph_neighbours(g, u));
heur = u;
while (!is_set_empty(t)) {
int x = elt_of_set_heur(t, heur);
heur = x;
set k2 = set_add(x, k);
set c2 = set_inter(c, graph_neighbours(g, x));
set a2 = set_inter(a, graph_neighbours(g, x));
max_clique_c(g, k2, c2, a2, mc);
delete_set(a2);
delete_set(c2);
delete_set(k2);
set_remove_ip(x, a);
delete_set(t);
t = set_diff(a, graph_neighbours(g, u));
}
delete_set(t);
}
|
