1
2 #include "igraph_error.h"
3 #include "igraph_memory.h"
4 #include "igraph_constants.h"
5
6 #include "core/interruption.h"
7 #include "cliques/cliquer_internal.h"
8 #include "cliques/cliquer/cliquer.h"
9
10 #include "config.h"
11
12 /* Call this to allow for interruption in Cliquer callback functions */
13 #define CLIQUER_ALLOW_INTERRUPTION() \
14 { \
15 if (igraph_i_interruption_handler) \
16 if (igraph_allow_interruption(NULL) != IGRAPH_SUCCESS) { \
17 cliquer_interrupted = 1; \
18 return FALSE; \
19 } \
20 }
21
22 /* Interruptable Cliquer functions must be wrapped in CLIQUER_INTERRUPTABLE when called */
23 #define CLIQUER_INTERRUPTABLE(x) \
24 { \
25 cliquer_interrupted = 0; \
26 x; \
27 if (cliquer_interrupted) return IGRAPH_INTERRUPTED; \
28 }
29
30
31 /* Nonzero value signals interuption from Cliquer callback function */
32 static IGRAPH_THREAD_LOCAL int cliquer_interrupted;
33
34
35 /* For use with IGRAPH_FINALLY */
free_clique_list(igraph_vector_ptr_t * vp)36 static void free_clique_list(igraph_vector_ptr_t *vp) {
37 igraph_integer_t i, len;
38 len = igraph_vector_ptr_size(vp);
39 for (i = 0; i < len; ++i) {
40 igraph_vector_destroy((igraph_vector_t *) VECTOR(*vp)[i]);
41 }
42 igraph_vector_ptr_free_all(vp);
43 }
44
45 /* We shall use this option struct for all calls to Cliquer */
46 static IGRAPH_THREAD_LOCAL clique_options igraph_cliquer_opt = {
47 reorder_by_default, NULL, NULL, NULL, NULL, NULL, NULL, 0
48 };
49
50
51 /* Convert an igraph graph to a Cliquer graph */
igraph_to_cliquer(const igraph_t * ig,graph_t ** cg)52 static void igraph_to_cliquer(const igraph_t *ig, graph_t **cg) {
53 igraph_integer_t vcount, ecount;
54 int i;
55
56 if (igraph_is_directed(ig)) {
57 IGRAPH_WARNING("Edge directions are ignored for clique calculations");
58 }
59
60 vcount = igraph_vcount(ig);
61 ecount = igraph_ecount(ig);
62
63 *cg = graph_new(vcount);
64
65 for (i = 0; i < ecount; ++i) {
66 long s, t;
67 s = IGRAPH_FROM(ig, i);
68 t = IGRAPH_TO(ig, i);
69 if (s != t) {
70 GRAPH_ADD_EDGE(*cg, s, t);
71 }
72 }
73 }
74
75
76 /* Copy weights to a Cliquer graph */
set_weights(const igraph_vector_t * vertex_weights,graph_t * g)77 static int set_weights(const igraph_vector_t *vertex_weights, graph_t *g) {
78 int i;
79
80 IGRAPH_ASSERT(vertex_weights != NULL);
81
82 if (igraph_vector_size(vertex_weights) != g->n) {
83 IGRAPH_ERROR("Invalid vertex weight vector length", IGRAPH_EINVAL);
84 }
85
86 for (i = 0; i < g->n; ++i) {
87 g->weights[i] = VECTOR(*vertex_weights)[i];
88 if (g->weights[i] != VECTOR(*vertex_weights)[i]) {
89 IGRAPH_WARNING("Only integer vertex weights are supported; weights will be truncated to their integer parts");
90 }
91 if (g->weights[i] <= 0) {
92 IGRAPH_ERROR("Vertex weights must be positive", IGRAPH_EINVAL);
93 }
94 }
95
96 return IGRAPH_SUCCESS;
97 }
98
99
100 /* Find all cliques. */
101
collect_cliques_callback(set_t s,graph_t * g,clique_options * opt)102 static boolean collect_cliques_callback(set_t s, graph_t *g, clique_options *opt) {
103 igraph_vector_ptr_t *list;
104 igraph_vector_t *clique;
105 int i, j;
106
107 IGRAPH_UNUSED(g);
108
109 CLIQUER_ALLOW_INTERRUPTION();
110
111 list = (igraph_vector_ptr_t *) opt->user_data;
112 clique = (igraph_vector_t *) malloc(sizeof(igraph_vector_t));
113 igraph_vector_init(clique, set_size(s));
114
115 i = -1; j = 0;
116 while ((i = set_return_next(s, i)) >= 0) {
117 VECTOR(*clique)[j++] = i;
118 }
119
120 igraph_vector_ptr_push_back(list, clique);
121
122 return TRUE;
123 }
124
igraph_i_cliquer_cliques(const igraph_t * graph,igraph_vector_ptr_t * res,igraph_integer_t min_size,igraph_integer_t max_size)125 int igraph_i_cliquer_cliques(const igraph_t *graph, igraph_vector_ptr_t *res,
126 igraph_integer_t min_size, igraph_integer_t max_size) {
127 graph_t *g;
128 igraph_integer_t vcount = igraph_vcount(graph);
129
130 if (vcount == 0) {
131 igraph_vector_ptr_clear(res);
132 return IGRAPH_SUCCESS;
133 }
134
135 if (min_size <= 0) {
136 min_size = 1;
137 }
138 if (max_size <= 0) {
139 max_size = 0;
140 }
141
142 if (max_size > 0 && max_size < min_size) {
143 IGRAPH_ERROR("max_size must not be smaller than min_size", IGRAPH_EINVAL);
144 }
145
146 igraph_to_cliquer(graph, &g);
147 IGRAPH_FINALLY(graph_free, g);
148
149 igraph_vector_ptr_clear(res);
150 igraph_cliquer_opt.user_data = res;
151 igraph_cliquer_opt.user_function = &collect_cliques_callback;
152
153 IGRAPH_FINALLY(free_clique_list, res);
154 CLIQUER_INTERRUPTABLE(clique_unweighted_find_all(g, min_size, max_size, /* maximal= */ FALSE, &igraph_cliquer_opt));
155 IGRAPH_FINALLY_CLEAN(1);
156
157 graph_free(g);
158 IGRAPH_FINALLY_CLEAN(1);
159
160 return IGRAPH_SUCCESS;
161 }
162
163
164 /* Count cliques of each size. */
165
count_cliques_callback(set_t s,graph_t * g,clique_options * opt)166 static boolean count_cliques_callback(set_t s, graph_t *g, clique_options *opt) {
167 igraph_vector_t *hist;
168
169 IGRAPH_UNUSED(g);
170
171 CLIQUER_ALLOW_INTERRUPTION();
172
173 hist = (igraph_vector_t *) opt->user_data;
174 VECTOR(*hist)[set_size(s) - 1] += 1;
175
176 return TRUE;
177 }
178
igraph_i_cliquer_histogram(const igraph_t * graph,igraph_vector_t * hist,igraph_integer_t min_size,igraph_integer_t max_size)179 int igraph_i_cliquer_histogram(const igraph_t *graph, igraph_vector_t *hist,
180 igraph_integer_t min_size, igraph_integer_t max_size) {
181 graph_t *g;
182 int i;
183 igraph_integer_t vcount = igraph_vcount(graph);
184
185 if (vcount == 0) {
186 igraph_vector_clear(hist);
187 return IGRAPH_SUCCESS;
188 }
189
190 if (min_size <= 0) {
191 min_size = 1;
192 }
193 if (max_size <= 0) {
194 max_size = vcount; /* also used for initial hist vector size, do not set to zero */
195 }
196
197 if (max_size < min_size) {
198 IGRAPH_ERRORF("Maximum clique size (%" IGRAPH_PRId ") must not be "
199 "smaller than minimum clique size (%" IGRAPH_PRId ").",
200 IGRAPH_EINVAL, max_size, min_size);
201 }
202
203 igraph_to_cliquer(graph, &g);
204 IGRAPH_FINALLY(graph_free, g);
205
206 igraph_vector_resize(hist, max_size);
207 igraph_vector_null(hist);
208 igraph_cliquer_opt.user_data = hist;
209 igraph_cliquer_opt.user_function = &count_cliques_callback;
210
211 CLIQUER_INTERRUPTABLE(clique_unweighted_find_all(g, min_size, max_size, /* maximal= */ FALSE, &igraph_cliquer_opt));
212
213 for (i = max_size; i > 0; --i)
214 if (VECTOR(*hist)[i - 1] > 0) {
215 break;
216 }
217 igraph_vector_resize(hist, i);
218 igraph_vector_resize_min(hist);
219
220 graph_free(g);
221 IGRAPH_FINALLY_CLEAN(1);
222
223 return IGRAPH_SUCCESS;
224 }
225
226
227 /* Call function for each clique. */
228
229 struct callback_data {
230 igraph_clique_handler_t *handler;
231 void *arg;
232 };
233
callback_callback(set_t s,graph_t * g,clique_options * opt)234 static boolean callback_callback(set_t s, graph_t *g, clique_options *opt) {
235 igraph_vector_t *clique;
236 struct callback_data *cd;
237 int i, j;
238
239 IGRAPH_UNUSED(g);
240
241 CLIQUER_ALLOW_INTERRUPTION();
242
243 cd = (struct callback_data *) opt->user_data;
244
245 clique = (igraph_vector_t *) malloc(sizeof(igraph_vector_t));
246 igraph_vector_init(clique, set_size(s));
247
248 i = -1; j = 0;
249 while ((i = set_return_next(s, i)) >= 0) {
250 VECTOR(*clique)[j++] = i;
251 }
252
253 return (*(cd->handler))(clique, cd->arg);
254 }
255
igraph_i_cliquer_callback(const igraph_t * graph,igraph_integer_t min_size,igraph_integer_t max_size,igraph_clique_handler_t * cliquehandler_fn,void * arg)256 int igraph_i_cliquer_callback(const igraph_t *graph,
257 igraph_integer_t min_size, igraph_integer_t max_size,
258 igraph_clique_handler_t *cliquehandler_fn, void *arg) {
259 graph_t *g;
260 struct callback_data cd;
261 igraph_integer_t vcount = igraph_vcount(graph);
262
263 if (vcount == 0) {
264 return IGRAPH_SUCCESS;
265 }
266
267 if (min_size <= 0) {
268 min_size = 1;
269 }
270 if (max_size <= 0) {
271 max_size = 0;
272 }
273
274 if (max_size > 0 && max_size < min_size) {
275 IGRAPH_ERROR("max_size must not be smaller than min_size", IGRAPH_EINVAL);
276 }
277
278 igraph_to_cliquer(graph, &g);
279 IGRAPH_FINALLY(graph_free, g);
280
281 cd.handler = cliquehandler_fn;
282 cd.arg = arg;
283 igraph_cliquer_opt.user_data = &cd;
284 igraph_cliquer_opt.user_function = &callback_callback;
285
286 CLIQUER_INTERRUPTABLE(clique_unweighted_find_all(g, min_size, max_size, /* maximal= */ FALSE, &igraph_cliquer_opt));
287
288 graph_free(g);
289 IGRAPH_FINALLY_CLEAN(1);
290
291 return IGRAPH_SUCCESS;
292 }
293
294
295 /* Find weighted cliques in given weight range. */
296
igraph_i_weighted_cliques(const igraph_t * graph,const igraph_vector_t * vertex_weights,igraph_vector_ptr_t * res,igraph_real_t min_weight,igraph_real_t max_weight,igraph_bool_t maximal)297 int igraph_i_weighted_cliques(const igraph_t *graph,
298 const igraph_vector_t *vertex_weights, igraph_vector_ptr_t *res,
299 igraph_real_t min_weight, igraph_real_t max_weight, igraph_bool_t maximal) {
300 graph_t *g;
301 igraph_integer_t vcount = igraph_vcount(graph);
302
303 if (vcount == 0) {
304 igraph_vector_ptr_clear(res);
305 return IGRAPH_SUCCESS;
306 }
307
308 if (min_weight != (int) min_weight) {
309 IGRAPH_WARNING("Only integer vertex weights are supported; the minimum weight will be truncated to its integer part");
310 min_weight = (int) min_weight;
311 }
312
313 if (max_weight != (int) max_weight) {
314 IGRAPH_WARNING("Only integer vertex weights are supported; the maximum weight will be truncated to its integer part");
315 max_weight = (int) max_weight;
316 }
317
318 if (min_weight <= 0) {
319 min_weight = 1;
320 }
321 if (max_weight <= 0) {
322 max_weight = 0;
323 }
324
325 if (max_weight > 0 && max_weight < min_weight) {
326 IGRAPH_ERROR("max_weight must not be smaller than min_weight", IGRAPH_EINVAL);
327 }
328
329 igraph_to_cliquer(graph, &g);
330 IGRAPH_FINALLY(graph_free, g);
331
332 IGRAPH_CHECK(set_weights(vertex_weights, g));
333
334 igraph_vector_ptr_clear(res);
335 igraph_cliquer_opt.user_data = res;
336 igraph_cliquer_opt.user_function = &collect_cliques_callback;
337
338 IGRAPH_FINALLY(free_clique_list, res);
339 CLIQUER_INTERRUPTABLE(clique_find_all(g, min_weight, max_weight, maximal, &igraph_cliquer_opt));
340 IGRAPH_FINALLY_CLEAN(1);
341
342 graph_free(g);
343 IGRAPH_FINALLY_CLEAN(1);
344
345 return IGRAPH_SUCCESS;
346 }
347
348
349 /* Find largest weighted cliques. */
350
igraph_i_largest_weighted_cliques(const igraph_t * graph,const igraph_vector_t * vertex_weights,igraph_vector_ptr_t * res)351 int igraph_i_largest_weighted_cliques(const igraph_t *graph,
352 const igraph_vector_t *vertex_weights, igraph_vector_ptr_t *res) {
353 graph_t *g;
354 igraph_integer_t vcount = igraph_vcount(graph);
355
356 if (vcount == 0) {
357 igraph_vector_ptr_clear(res);
358 return IGRAPH_SUCCESS;
359 }
360
361 igraph_to_cliquer(graph, &g);
362 IGRAPH_FINALLY(graph_free, g);
363
364 IGRAPH_CHECK(set_weights(vertex_weights, g));
365
366 igraph_vector_ptr_clear(res);
367 igraph_cliquer_opt.user_data = res;
368 igraph_cliquer_opt.user_function = &collect_cliques_callback;
369
370 IGRAPH_FINALLY(free_clique_list, res);
371 CLIQUER_INTERRUPTABLE(clique_find_all(g, 0, 0, FALSE, &igraph_cliquer_opt));
372 IGRAPH_FINALLY_CLEAN(1);
373
374 graph_free(g);
375 IGRAPH_FINALLY_CLEAN(1);
376
377 return IGRAPH_SUCCESS;
378 }
379
380
381 /* Find weight of largest weight clique. */
382
igraph_i_weighted_clique_number(const igraph_t * graph,const igraph_vector_t * vertex_weights,igraph_real_t * res)383 int igraph_i_weighted_clique_number(const igraph_t *graph,
384 const igraph_vector_t *vertex_weights, igraph_real_t *res) {
385 graph_t *g;
386 igraph_integer_t vcount = igraph_vcount(graph);
387
388 if (vcount == 0) {
389 *res = 0;
390 return IGRAPH_SUCCESS;
391 }
392
393 igraph_to_cliquer(graph, &g);
394 IGRAPH_FINALLY(graph_free, g);
395
396 IGRAPH_CHECK(set_weights(vertex_weights, g));
397
398 igraph_cliquer_opt.user_function = NULL;
399
400 /* we are not using a callback function, thus this is not interruptable */
401 *res = clique_max_weight(g, &igraph_cliquer_opt);
402
403 graph_free(g);
404 IGRAPH_FINALLY_CLEAN(1);
405
406 return IGRAPH_SUCCESS;
407 }
408