1
2 /*
3 * This file contains the clique searching routines.
4 *
5 * Copyright (C) 2002 Sampo Niskanen, Patric �sterg�rd.
6 * Licensed under the GNU GPL, read the file LICENSE for details.
7 */
8
9 #include <stdio.h>
10 #include <stdlib.h>
11 #include <limits.h>
12 #include <unistd.h>
13 #include <sys/time.h>
14 #include <sys/times.h>
15
16 #include "cliquer/cliquer.h"
17
18
19 /* Default cliquer options */
20 static clique_options clique_default_options_struct = {
21 reorder_by_default, NULL, clique_print_time, NULL, NULL, NULL, NULL, 0
22 };
23 clique_options *clique_default_options=&clique_default_options_struct;
24
25
26 /* Calculate d/q, rounding result upwards/downwards. */
27 #define DIV_UP(d,q) (((d)+(q)-1)/(q))
28 #define DIV_DOWN(d,q) ((int)((d)/(q)))
29
30
31 /* Global variables used: */
32 /* These must be saved and restored in re-entrance. */
33 static int *clique_size; /* c[i] == max. clique size in {0,1,...,i-1} */
34 static set_t current_clique; /* Current clique being searched. */
35 static set_t best_clique; /* Largest/heaviest clique found so far. */
36 static struct tms cputimer; /* Timer for opts->time_function() */
37 static struct timeval realtimer; /* Timer for opts->time_function() */
38 static int clique_list_count=0; /* No. of cliques in opts->clique_list[] */
39 static int weight_multiplier=1; /* Weights multiplied by this when passing
40 * to time_function(). */
41
42 /* List cache (contains memory blocks of size g->n * sizeof(int)) */
43 static int **temp_list=NULL;
44 static int temp_count=0;
45
46
47 /*
48 * Macros for re-entrance. ENTRANCE_SAVE() must be called immediately
49 * after variable definitions, ENTRANCE_RESTORE() restores global
50 * variables to original values. entrance_level should be increased
51 * and decreased accordingly.
52 */
53 static int entrance_level=0; /* How many levels for entrance have occurred? */
54
55 #define ENTRANCE_SAVE() \
56 int *old_clique_size = clique_size; \
57 set_t old_current_clique = current_clique; \
58 set_t old_best_clique = best_clique; \
59 int old_clique_list_count = clique_list_count; \
60 int old_weight_multiplier = weight_multiplier; \
61 int **old_temp_list = temp_list; \
62 int old_temp_count = temp_count; \
63 struct tms old_cputimer; \
64 struct timeval old_realtimer; \
65 memcpy(&old_cputimer,&cputimer,sizeof(struct tms)); \
66 memcpy(&old_realtimer,&realtimer,sizeof(struct timeval));
67
68 #define ENTRANCE_RESTORE() \
69 clique_size = old_clique_size; \
70 current_clique = old_current_clique; \
71 best_clique = old_best_clique; \
72 clique_list_count = old_clique_list_count; \
73 weight_multiplier = old_weight_multiplier; \
74 temp_list = old_temp_list; \
75 temp_count = old_temp_count; \
76 memcpy(&cputimer,&old_cputimer,sizeof(struct tms)); \
77 memcpy(&realtimer,&old_realtimer,sizeof(struct timeval));
78
79
80 /* Number of clock ticks per second (as returned by sysconf(_SC_CLK_TCK)) */
81 static int clocks_per_sec=0;
82
83
84
85
86 /* Recursion and helper functions */
87 static boolean sub_unweighted_single(int *table, int size, int min_size,
88 graph_t *g);
89 static int sub_unweighted_all(int *table, int size, int min_size, int max_size,
90 boolean maximal, graph_t *g,
91 clique_options *opts);
92 static int sub_weighted_all(int *table, int size, int weight,
93 int current_weight, int prune_low, int prune_high,
94 int min_weight, int max_weight, boolean maximal,
95 graph_t *g, clique_options *opts);
96
97
98 static boolean store_clique(set_t clique, graph_t *g, clique_options *opts);
99 static boolean is_maximal(set_t clique, graph_t *g);
100 static boolean false_function(set_t clique,graph_t *g,clique_options *opts);
101
102
103
104
105
106 /***** Unweighted searches *****/
107 /*
108 * Unweighted searches are done separately from weighted searches because
109 * some effective pruning methods can be used when the vertex weights
110 * are all 1. Single and all clique finding routines are separated,
111 * because the single clique finding routine can store the found clique
112 * while it is returning from the recursion, thus requiring no implicit
113 * storing of the current clique. When searching for all cliques the
114 * current clique must be stored.
115 */
116
117
118 /*
119 * unweighted_clique_search_single()
120 *
121 * Searches for a single clique of size min_size. Stores maximum clique
122 * sizes into clique_size[].
123 *
124 * table - the order of the vertices in g to use
125 * min_size - minimum size of clique to search for. If min_size==0,
126 * searches for a maximum clique.
127 * g - the graph
128 * opts - time printing options
129 *
130 * opts->time_function is called after each base-level recursion, if
131 * non-NULL.
132 *
133 * Returns the size of the clique found, or 0 if min_size>0 and a clique
134 * of that size was not found (or if time_function aborted the search).
135 * The largest clique found is stored in current_clique.
136 *
137 * Note: Does NOT use opts->user_function of opts->clique_list.
138 */
unweighted_clique_search_single(int * table,int min_size,graph_t * g,clique_options * opts)139 static int unweighted_clique_search_single(int *table, int min_size,
140 graph_t *g, clique_options *opts) {
141 struct tms tms;
142 struct timeval timeval;
143 int i,j;
144 int v,w;
145 int *newtable;
146 int newsize;
147
148 v=table[0];
149 clique_size[v]=1;
150 set_empty(current_clique);
151 SET_ADD_ELEMENT(current_clique,v);
152 if (min_size==1)
153 return 1;
154
155 if (temp_count) {
156 temp_count--;
157 newtable=temp_list[temp_count];
158 } else {
159 newtable=malloc(g->n * sizeof(int));
160 }
161 for (i=1; i < g->n; i++) {
162 w=v;
163 v=table[i];
164
165 newsize=0;
166 for (j=0; j<i; j++) {
167 if (GRAPH_IS_EDGE(g, v, table[j])) {
168 newtable[newsize]=table[j];
169 newsize++;
170 }
171 }
172
173 if (sub_unweighted_single(newtable,newsize,clique_size[w],g)) {
174 SET_ADD_ELEMENT(current_clique,v);
175 clique_size[v]=clique_size[w]+1;
176 } else {
177 clique_size[v]=clique_size[w];
178 }
179
180 if (opts && opts->time_function) {
181 gettimeofday(&timeval,NULL);
182 times(&tms);
183 if (!opts->time_function(entrance_level,
184 i+1,g->n,clique_size[v] *
185 weight_multiplier,
186 (double)(tms.tms_utime-
187 cputimer.tms_utime)/
188 clocks_per_sec,
189 timeval.tv_sec-
190 realtimer.tv_sec+
191 (double)(timeval.tv_usec-
192 realtimer.tv_usec)/
193 1000000,opts)) {
194 temp_list[temp_count++]=newtable;
195 return 0;
196 }
197 }
198
199 if (min_size) {
200 if (clique_size[v]>=min_size) {
201 temp_list[temp_count++]=newtable;
202 return clique_size[v];
203 }
204 if (clique_size[v]+g->n-i-1 < min_size) {
205 temp_list[temp_count++]=newtable;
206 return 0;
207 }
208 }
209 }
210
211 temp_list[temp_count++]=newtable;
212
213 if (min_size)
214 return 0;
215 return clique_size[v];
216 }
217
218 /*
219 * sub_unweighted_single()
220 *
221 * Recursion function for searching for a single clique of size min_size.
222 *
223 * table - subset of the vertices in graph
224 * size - size of table
225 * min_size - size of clique to look for within the subgraph
226 * (decreased with every recursion)
227 * g - the graph
228 *
229 * Returns TRUE if a clique of size min_size is found, FALSE otherwise.
230 * If a clique of size min_size is found, it is stored in current_clique.
231 *
232 * clique_size[] for all values in table must be defined and correct,
233 * otherwise inaccurate results may occur.
234 */
sub_unweighted_single(int * table,int size,int min_size,graph_t * g)235 static boolean sub_unweighted_single(int *table, int size, int min_size,
236 graph_t *g) {
237 int i;
238 int v;
239 int *newtable;
240 int *p1, *p2;
241
242 /* Zero or one vertices needed anymore. */
243 if (min_size <= 1) {
244 if (size>0 && min_size==1) {
245 set_empty(current_clique);
246 SET_ADD_ELEMENT(current_clique,table[0]);
247 return TRUE;
248 }
249 if (min_size==0) {
250 set_empty(current_clique);
251 return TRUE;
252 }
253 return FALSE;
254 }
255 if (size < min_size)
256 return FALSE;
257
258 /* Dynamic memory allocation with cache */
259 if (temp_count) {
260 temp_count--;
261 newtable=temp_list[temp_count];
262 } else {
263 newtable=malloc(g->n * sizeof(int));
264 }
265
266 for (i = size-1; i >= 0; i--) {
267 v = table[i];
268
269 if (clique_size[v] < min_size)
270 break;
271 /* This is faster when compiling with gcc than placing
272 * this in the for-loop condition. */
273 if (i+1 < min_size)
274 break;
275
276 /* Very ugly code, but works faster than "for (i=...)" */
277 p1 = newtable;
278 for (p2=table; p2 < table+i; p2++) {
279 int w = *p2;
280 if (GRAPH_IS_EDGE(g, v, w)) {
281 *p1 = w;
282 p1++;
283 }
284 }
285
286 /* Avoid unneccessary loops (next size == p1-newtable) */
287 if (p1-newtable < min_size-1)
288 continue;
289 /* Now p1-newtable >= min_size-1 >= 2-1 == 1, so we can use
290 * p1-newtable-1 safely. */
291 if (clique_size[newtable[p1-newtable-1]] < min_size-1)
292 continue;
293
294 if (sub_unweighted_single(newtable,p1-newtable,
295 min_size-1,g)) {
296 /* Clique found. */
297 SET_ADD_ELEMENT(current_clique,v);
298 temp_list[temp_count++]=newtable;
299 return TRUE;
300 }
301 }
302 temp_list[temp_count++]=newtable;
303 return FALSE;
304 }
305
306
307 /*
308 * unweighted_clique_search_all()
309 *
310 * Searches for all cliques with size at least min_size and at most
311 * max_size. Stores the cliques as opts declares.
312 *
313 * table - the order of the vertices in g to search
314 * start - first index where the subgraph table[0], ..., table[start]
315 * might include a requested kind of clique
316 * min_size - minimum size of clique to search for. min_size > 0 !
317 * max_size - maximum size of clique to search for. If no upper limit
318 * is desired, use eg. INT_MAX
319 * maximal - requires cliques to be maximal
320 * g - the graph
321 * opts - time printing and clique storage options
322 *
323 * Cliques found are stored as defined by opts->user_function and
324 * opts->clique_list. opts->time_function is called after each
325 * base-level recursion, if non-NULL.
326 *
327 * clique_size[] must be defined and correct for all values of
328 * table[0], ..., table[start-1].
329 *
330 * Returns the number of cliques stored (not neccessarily number of cliques
331 * in graph, if user/time_function aborts).
332 */
unweighted_clique_search_all(int * table,int start,int min_size,int max_size,boolean maximal,graph_t * g,clique_options * opts)333 static int unweighted_clique_search_all(int *table, int start,
334 int min_size, int max_size,
335 boolean maximal, graph_t *g,
336 clique_options *opts) {
337 struct timeval timeval;
338 struct tms tms;
339 int i,j;
340 int v;
341 int *newtable;
342 int newsize;
343 int count=0;
344
345 if (temp_count) {
346 temp_count--;
347 newtable=temp_list[temp_count];
348 } else {
349 newtable=malloc(g->n * sizeof(int));
350 }
351
352 clique_list_count=0;
353 set_empty(current_clique);
354 for (i=start; i < g->n; i++) {
355 v=table[i];
356 clique_size[v]=min_size; /* Do not prune here. */
357
358 newsize=0;
359 for (j=0; j<i; j++) {
360 if (GRAPH_IS_EDGE(g,v,table[j])) {
361 newtable[newsize]=table[j];
362 newsize++;
363 }
364 }
365
366 SET_ADD_ELEMENT(current_clique,v);
367 j=sub_unweighted_all(newtable,newsize,min_size-1,max_size-1,
368 maximal,g,opts);
369 SET_DEL_ELEMENT(current_clique,v);
370 if (j<0) {
371 /* Abort. */
372 count-=j;
373 break;
374 }
375 count+=j;
376
377 if (opts->time_function) {
378 gettimeofday(&timeval,NULL);
379 times(&tms);
380 if (!opts->time_function(entrance_level,
381 i+1,g->n,min_size *
382 weight_multiplier,
383 (double)(tms.tms_utime-
384 cputimer.tms_utime)/
385 clocks_per_sec,
386 timeval.tv_sec-
387 realtimer.tv_sec+
388 (double)(timeval.tv_usec-
389 realtimer.tv_usec)/
390 1000000,opts)) {
391 /* Abort. */
392 break;
393 }
394 }
395 }
396 temp_list[temp_count++]=newtable;
397 return count;
398 }
399
400 /*
401 * sub_unweighted_all()
402 *
403 * Recursion function for searching for all cliques of given size.
404 *
405 * table - subset of vertices of graph g
406 * size - size of table
407 * min_size - minimum size of cliques to search for (decreased with
408 * every recursion)
409 * max_size - maximum size of cliques to search for (decreased with
410 * every recursion). If no upper limit is desired, use
411 * eg. INT_MAX
412 * maximal - require cliques to be maximal (passed through)
413 * g - the graph
414 * opts - storage options
415 *
416 * All cliques of suitable size found are stored according to opts.
417 *
418 * Returns the number of cliques found. If user_function returns FALSE,
419 * then the number of cliques is returned negative.
420 *
421 * Uses current_clique to store the currently-being-searched clique.
422 * clique_size[] for all values in table must be defined and correct,
423 * otherwise inaccurate results may occur.
424 */
sub_unweighted_all(int * table,int size,int min_size,int max_size,boolean maximal,graph_t * g,clique_options * opts)425 static int sub_unweighted_all(int *table, int size, int min_size, int max_size,
426 boolean maximal, graph_t *g,
427 clique_options *opts) {
428 int i;
429 int v;
430 int n;
431 int *newtable;
432 int *p1, *p2;
433 int count=0; /* Amount of cliques found */
434
435 if (min_size <= 0) {
436 if ((!maximal) || is_maximal(current_clique,g)) {
437 /* We've found one. Store it. */
438 count++;
439 if (!store_clique(current_clique,g,opts)) {
440 return -count;
441 }
442 }
443 if (max_size <= 0) {
444 /* If we add another element, size will be too big. */
445 return count;
446 }
447 }
448
449 if (size < min_size) {
450 return count;
451 }
452
453 /* Dynamic memory allocation with cache */
454 if (temp_count) {
455 temp_count--;
456 newtable=temp_list[temp_count];
457 } else {
458 newtable=malloc(g->n * sizeof(int));
459 }
460
461 for (i=size-1; i>=0; i--) {
462 v = table[i];
463 if (clique_size[v] < min_size) {
464 break;
465 }
466 if (i+1 < min_size) {
467 break;
468 }
469
470 /* Very ugly code, but works faster than "for (i=...)" */
471 p1 = newtable;
472 for (p2=table; p2 < table+i; p2++) {
473 int w = *p2;
474 if (GRAPH_IS_EDGE(g, v, w)) {
475 *p1 = w;
476 p1++;
477 }
478 }
479
480 /* Avoid unneccessary loops (next size == p1-newtable) */
481 if (p1-newtable < min_size-1) {
482 continue;
483 }
484
485 SET_ADD_ELEMENT(current_clique,v);
486 n=sub_unweighted_all(newtable,p1-newtable,
487 min_size-1,max_size-1,maximal,g,opts);
488 SET_DEL_ELEMENT(current_clique,v);
489 if (n < 0) {
490 /* Abort. */
491 count -= n;
492 count = -count;
493 break;
494 }
495 count+=n;
496 }
497 temp_list[temp_count++]=newtable;
498 return count;
499 }
500
501
502
503
504 /***** Weighted clique searches *****/
505 /*
506 * Weighted clique searches can use the same recursive routine, because
507 * in both cases (single/all) they have to search through all potential
508 * permutations searching for heavier cliques.
509 */
510
511
512 /*
513 * weighted_clique_search_single()
514 *
515 * Searches for a single clique of weight at least min_weight, and at
516 * most max_weight. Stores maximum clique sizes into clique_size[]
517 * (or min_weight-1, whichever is smaller).
518 *
519 * table - the order of the vertices in g to use
520 * min_weight - minimum weight of clique to search for. If min_weight==0,
521 * then searches for a maximum weight clique
522 * max_weight - maximum weight of clique to search for. If no upper limit
523 * is desired, use eg. INT_MAX
524 * g - the graph
525 * opts - time printing options
526 *
527 * opts->time_function is called after each base-level recursion, if
528 * non-NULL.
529 *
530 * Returns 0 if a clique of requested weight was not found (also if
531 * time_function requested an abort), otherwise returns >= 1.
532 * If min_weight==0 (search for maximum-weight clique), then the return
533 * value is the weight of the clique found. The found clique is stored
534 * in best_clique.
535 *
536 * Note: Does NOT use opts->user_function of opts->clique_list.
537 */
weighted_clique_search_single(int * table,int min_weight,int max_weight,graph_t * g,clique_options * opts)538 static int weighted_clique_search_single(int *table, int min_weight,
539 int max_weight, graph_t *g,
540 clique_options *opts) {
541 struct timeval timeval;
542 struct tms tms;
543 int i,j;
544 int v;
545 int *newtable;
546 int newsize;
547 int newweight;
548 int search_weight;
549 int min_w;
550 clique_options localopts;
551
552 if (min_weight==0)
553 min_w=INT_MAX;
554 else
555 min_w=min_weight;
556
557
558 if (min_weight==1) {
559 /* min_weight==1 may cause trouble in the routine, and
560 * it's trivial to check as it's own case.
561 * We write nothing to clique_size[]. */
562 for (i=0; i < g->n; i++) {
563 if (g->weights[table[i]] <= max_weight) {
564 set_empty(best_clique);
565 SET_ADD_ELEMENT(best_clique,table[i]);
566 return g->weights[table[i]];
567 }
568 }
569 return 0;
570 }
571
572 localopts.time_function=NULL;
573 localopts.reorder_function=NULL;
574 localopts.reorder_map=NULL;
575 localopts.user_function=false_function;
576 localopts.user_data=NULL;
577 localopts.clique_list=&best_clique;
578 localopts.clique_list_length=1;
579 clique_list_count=0;
580
581 v=table[0];
582 set_empty(best_clique);
583 SET_ADD_ELEMENT(best_clique,v);
584 search_weight=g->weights[v];
585 if (min_weight && (search_weight >= min_weight)) {
586 if (search_weight <= max_weight) {
587 /* Found suitable clique. */
588 return search_weight;
589 }
590 search_weight=min_weight-1;
591 }
592 clique_size[v]=search_weight;
593 set_empty(current_clique);
594
595 if (temp_count) {
596 temp_count--;
597 newtable=temp_list[temp_count];
598 } else {
599 newtable=malloc(g->n * sizeof(int));
600 }
601
602 for (i = 1; i < g->n; i++) {
603 v=table[i];
604
605 newsize=0;
606 newweight=0;
607 for (j=0; j<i; j++) {
608 if (GRAPH_IS_EDGE(g,v,table[j])) {
609 newweight += g->weights[table[j]];
610 newtable[newsize]=table[j];
611 newsize++;
612 }
613 }
614
615
616 SET_ADD_ELEMENT(current_clique,v);
617 search_weight=sub_weighted_all(newtable,newsize,newweight,
618 g->weights[v],search_weight,
619 clique_size[table[i-1]] +
620 g->weights[v],
621 min_w,max_weight,FALSE,
622 g,&localopts);
623 SET_DEL_ELEMENT(current_clique,v);
624 if (search_weight < 0) {
625 break;
626 }
627
628 clique_size[v]=search_weight;
629
630 if (opts->time_function) {
631 gettimeofday(&timeval,NULL);
632 times(&tms);
633 if (!opts->time_function(entrance_level,
634 i+1,g->n,clique_size[v] *
635 weight_multiplier,
636 (double)(tms.tms_utime-
637 cputimer.tms_utime)/
638 clocks_per_sec,
639 timeval.tv_sec-
640 realtimer.tv_sec+
641 (double)(timeval.tv_usec-
642 realtimer.tv_usec)/
643 1000000,opts)) {
644 set_free(current_clique);
645 current_clique=NULL;
646 break;
647 }
648 }
649 }
650 temp_list[temp_count++]=newtable;
651 if (min_weight && (search_weight > 0)) {
652 /* Requested clique has not been found. */
653 return 0;
654 }
655 return clique_size[table[i-1]];
656 }
657
658
659 /*
660 * weighted_clique_search_all()
661 *
662 * Searches for all cliques with weight at least min_weight and at most
663 * max_weight. Stores the cliques as opts declares.
664 *
665 * table - the order of the vertices in g to search
666 * start - first index where the subgraph table[0], ..., table[start]
667 * might include a requested kind of clique
668 * min_weight - minimum weight of clique to search for. min_weight > 0 !
669 * max_weight - maximum weight of clique to search for. If no upper limit
670 * is desired, use eg. INT_MAX
671 * maximal - search only for maximal cliques
672 * g - the graph
673 * opts - time printing and clique storage options
674 *
675 * Cliques found are stored as defined by opts->user_function and
676 * opts->clique_list. opts->time_function is called after each
677 * base-level recursion, if non-NULL.
678 *
679 * clique_size[] must be defined and correct for all values of
680 * table[0], ..., table[start-1].
681 *
682 * Returns the number of cliques stored (not neccessarily number of cliques
683 * in graph, if user/time_function aborts).
684 */
weighted_clique_search_all(int * table,int start,int min_weight,int max_weight,boolean maximal,graph_t * g,clique_options * opts)685 static int weighted_clique_search_all(int *table, int start,
686 int min_weight, int max_weight,
687 boolean maximal, graph_t *g,
688 clique_options *opts) {
689 struct timeval timeval;
690 struct tms tms;
691 int i,j;
692 int v;
693 int *newtable;
694 int newsize;
695 int newweight;
696
697 if (temp_count) {
698 temp_count--;
699 newtable=temp_list[temp_count];
700 } else {
701 newtable=malloc(g->n * sizeof(int));
702 }
703
704 clique_list_count=0;
705 set_empty(current_clique);
706 for (i=start; i < g->n; i++) {
707 v=table[i];
708 clique_size[v]=min_weight; /* Do not prune here. */
709
710 newsize=0;
711 newweight=0;
712 for (j=0; j<i; j++) {
713 if (GRAPH_IS_EDGE(g,v,table[j])) {
714 newtable[newsize]=table[j];
715 newweight+=g->weights[table[j]];
716 newsize++;
717 }
718 }
719
720 SET_ADD_ELEMENT(current_clique,v);
721 j=sub_weighted_all(newtable,newsize,newweight,
722 g->weights[v],min_weight-1,INT_MAX,
723 min_weight,max_weight,maximal,g,opts);
724 SET_DEL_ELEMENT(current_clique,v);
725
726 if (j<0) {
727 /* Abort. */
728 break;
729 }
730
731 if (opts->time_function) {
732 gettimeofday(&timeval,NULL);
733 times(&tms);
734 if (!opts->time_function(entrance_level,
735 i+1,g->n,clique_size[v] *
736 weight_multiplier,
737 (double)(tms.tms_utime-
738 cputimer.tms_utime)/
739 clocks_per_sec,
740 timeval.tv_sec-
741 realtimer.tv_sec+
742 (double)(timeval.tv_usec-
743 realtimer.tv_usec)/
744 1000000,opts)) {
745 set_free(current_clique);
746 current_clique=NULL;
747 break;
748 }
749 }
750 }
751 temp_list[temp_count++]=newtable;
752
753 return clique_list_count;
754 }
755
756 /*
757 * sub_weighted_all()
758 *
759 * Recursion function for searching for all cliques of given weight.
760 *
761 * table - subset of vertices of graph g
762 * size - size of table
763 * weight - total weight of vertices in table
764 * current_weight - weight of clique found so far
765 * prune_low - ignore all cliques with weight less or equal to this value
766 * (often heaviest clique found so far) (passed through)
767 * prune_high - maximum weight possible for clique in this subgraph
768 * (passed through)
769 * min_size - minimum weight of cliques to search for (passed through)
770 * Must be greater than 0.
771 * max_size - maximum weight of cliques to search for (passed through)
772 * If no upper limit is desired, use eg. INT_MAX
773 * maximal - search only for maximal cliques
774 * g - the graph
775 * opts - storage options
776 *
777 * All cliques of suitable weight found are stored according to opts.
778 *
779 * Returns weight of heaviest clique found (prune_low if a heavier clique
780 * hasn't been found); if a clique with weight at least min_size is found
781 * then min_size-1 is returned. If clique storage failed, -1 is returned.
782 *
783 * The largest clique found smaller than max_weight is stored in
784 * best_clique, if non-NULL.
785 *
786 * Uses current_clique to store the currently-being-searched clique.
787 * clique_size[] for all values in table must be defined and correct,
788 * otherwise inaccurate results may occur.
789 *
790 * To search for a single maximum clique, use min_weight==max_weight==INT_MAX,
791 * with best_clique non-NULL. To search for a single given-weight clique,
792 * use opts->clique_list and opts->user_function=false_function. When
793 * searching for all cliques, min_weight should be given the minimum weight
794 * desired.
795 */
sub_weighted_all(int * table,int size,int weight,int current_weight,int prune_low,int prune_high,int min_weight,int max_weight,boolean maximal,graph_t * g,clique_options * opts)796 static int sub_weighted_all(int *table, int size, int weight,
797 int current_weight, int prune_low, int prune_high,
798 int min_weight, int max_weight, boolean maximal,
799 graph_t *g, clique_options *opts) {
800 int i;
801 int v,w;
802 int *newtable;
803 int *p1, *p2;
804 int newweight;
805
806 if (current_weight >= min_weight) {
807 if ((current_weight <= max_weight) &&
808 ((!maximal) || is_maximal(current_clique,g))) {
809 /* We've found one. Store it. */
810 if (!store_clique(current_clique,g,opts)) {
811 return -1;
812 }
813 }
814 if (current_weight >= max_weight) {
815 /* Clique too heavy. */
816 return min_weight-1;
817 }
818 }
819 if (size <= 0) {
820 /* current_weight < min_weight, prune_low < min_weight,
821 * so return value is always < min_weight. */
822 if (current_weight>prune_low) {
823 if (best_clique)
824 set_copy(best_clique,current_clique);
825 if (current_weight < min_weight)
826 return current_weight;
827 else
828 return min_weight-1;
829 } else {
830 return prune_low;
831 }
832 }
833
834 /* Dynamic memory allocation with cache */
835 if (temp_count) {
836 temp_count--;
837 newtable=temp_list[temp_count];
838 } else {
839 newtable=malloc(g->n * sizeof(int));
840 }
841
842 for (i = size-1; i >= 0; i--) {
843 v = table[i];
844 if (current_weight+clique_size[v] <= prune_low) {
845 /* Dealing with subset without heavy enough clique. */
846 break;
847 }
848 if (current_weight+weight <= prune_low) {
849 /* Even if all elements are added, won't do. */
850 break;
851 }
852
853 /* Very ugly code, but works faster than "for (i=...)" */
854 p1 = newtable;
855 newweight = 0;
856 for (p2=table; p2 < table+i; p2++) {
857 w = *p2;
858 if (GRAPH_IS_EDGE(g, v, w)) {
859 *p1 = w;
860 newweight += g->weights[w];
861 p1++;
862 }
863 }
864
865 w=g->weights[v];
866 weight-=w;
867 /* Avoid a few unneccessary loops */
868 if (current_weight+w+newweight <= prune_low) {
869 continue;
870 }
871
872 SET_ADD_ELEMENT(current_clique,v);
873 prune_low=sub_weighted_all(newtable,p1-newtable,
874 newweight,
875 current_weight+w,
876 prune_low,prune_high,
877 min_weight,max_weight,maximal,
878 g,opts);
879 SET_DEL_ELEMENT(current_clique,v);
880 if ((prune_low<0) || (prune_low>=prune_high)) {
881 /* Impossible to find larger clique. */
882 break;
883 }
884 }
885 temp_list[temp_count++]=newtable;
886 return prune_low;
887 }
888
889
890
891
892 /***** Helper functions *****/
893
894
895 /*
896 * store_clique()
897 *
898 * Stores a clique according to given user options.
899 *
900 * clique - the clique to store
901 * opts - storage options
902 *
903 * Returns FALSE if opts->user_function() returned FALSE; otherwise
904 * returns TRUE.
905 */
store_clique(set_t clique,graph_t * g,clique_options * opts)906 static boolean store_clique(set_t clique, graph_t *g, clique_options *opts) {
907
908 clique_list_count++;
909
910 /* clique_list[] */
911 if (opts->clique_list) {
912 /*
913 * This has been a major source of bugs:
914 * Has clique_list_count been set to 0 before calling
915 * the recursions?
916 */
917 if (clique_list_count <= 0) {
918 fprintf(stderr,"CLIQUER INTERNAL ERROR: "
919 "clique_list_count has negative value!\n");
920 fprintf(stderr,"Please report as a bug.\n");
921 abort();
922 }
923 if (clique_list_count <= opts->clique_list_length)
924 opts->clique_list[clique_list_count-1] =
925 set_duplicate(clique);
926 }
927
928 /* user_function() */
929 if (opts->user_function) {
930 if (!opts->user_function(clique,g,opts)) {
931 /* User function requested abort. */
932 return FALSE;
933 }
934 }
935
936 return TRUE;
937 }
938
939 /*
940 * maximalize_clique()
941 *
942 * Adds greedily all possible vertices in g to set s to make it a maximal
943 * clique.
944 *
945 * s - clique of vertices to make maximal
946 * g - graph
947 *
948 * Note: Not very optimized (uses a simple O(n^2) routine), but is called
949 * at maximum once per clique_xxx() call, so it shouldn't matter.
950 */
maximalize_clique(set_t s,graph_t * g)951 static void maximalize_clique(set_t s,graph_t *g) {
952 int i,j;
953 boolean add;
954
955 for (i=0; i < g->n; i++) {
956 add=TRUE;
957 for (j=0; j < g->n; j++) {
958 if (SET_CONTAINS_FAST(s,j) && !GRAPH_IS_EDGE(g,i,j)) {
959 add=FALSE;
960 break;
961 }
962 }
963 if (add) {
964 SET_ADD_ELEMENT(s,i);
965 }
966 }
967 return;
968 }
969
970
971 /*
972 * is_maximal()
973 *
974 * Check whether a clique is maximal or not.
975 *
976 * clique - set of vertices in clique
977 * g - graph
978 *
979 * Returns TRUE is clique is a maximal clique of g, otherwise FALSE.
980 */
is_maximal(set_t clique,graph_t * g)981 static boolean is_maximal(set_t clique, graph_t *g) {
982 int i,j;
983 int *table;
984 int len;
985 boolean addable;
986
987 if (temp_count) {
988 temp_count--;
989 table=temp_list[temp_count];
990 } else {
991 table=malloc(g->n * sizeof(int));
992 }
993
994 len=0;
995 for (i=0; i < g->n; i++)
996 if (SET_CONTAINS_FAST(clique,i))
997 table[len++]=i;
998
999 for (i=0; i < g->n; i++) {
1000 addable=TRUE;
1001 for (j=0; j<len; j++) {
1002 if (!GRAPH_IS_EDGE(g,i,table[j])) {
1003 addable=FALSE;
1004 break;
1005 }
1006 }
1007 if (addable) {
1008 temp_list[temp_count++]=table;
1009 return FALSE;
1010 }
1011 }
1012 temp_list[temp_count++]=table;
1013 return TRUE;
1014 }
1015
1016
1017 /*
1018 * false_function()
1019 *
1020 * Returns FALSE. Can be used as user_function.
1021 */
false_function(set_t clique,graph_t * g,clique_options * opts)1022 static boolean false_function(set_t clique,graph_t *g,clique_options *opts) {
1023 return FALSE;
1024 }
1025
1026
1027
1028
1029 /***** API-functions *****/
1030
1031 /*
1032 * clique_unweighted_max_weight()
1033 *
1034 * Returns the size of the maximum (sized) clique in g (or 0 if search
1035 * was aborted).
1036 *
1037 * g - the graph
1038 * opts - time printing options
1039 *
1040 * Note: As we don't have an algorithm faster than actually finding
1041 * a maximum clique, we use clique_unweighted_find_single().
1042 * This incurs only very small overhead.
1043 */
clique_unweighted_max_weight(graph_t * g,clique_options * opts)1044 int clique_unweighted_max_weight(graph_t *g, clique_options *opts) {
1045 set_t s;
1046 int size;
1047
1048 ASSERT((sizeof(setelement)*8)==ELEMENTSIZE);
1049 ASSERT(g!=NULL);
1050
1051 s=clique_unweighted_find_single(g,0,0,FALSE,opts);
1052 if (s==NULL) {
1053 /* Search was aborted. */
1054 return 0;
1055 }
1056 size=set_size(s);
1057 set_free(s);
1058 return size;
1059 }
1060
1061
1062 /*
1063 * clique_unweighted_find_single()
1064 *
1065 * Returns a clique with size at least min_size and at most max_size.
1066 *
1067 * g - the graph
1068 * min_size - minimum size of clique to search for. If min_size==0,
1069 * searches for maximum clique.
1070 * max_size - maximum size of clique to search for. If max_size==0, no
1071 * upper limit is used. If min_size==0, this must also be 0.
1072 * maximal - require returned clique to be maximal
1073 * opts - time printing options
1074 *
1075 * Returns the set of vertices forming the clique, or NULL if a clique
1076 * of requested size/maximality does not exist in the graph (or if
1077 * opts->time_function() requests abort).
1078 *
1079 * The returned clique is newly allocated and can be freed by set_free().
1080 *
1081 * Note: Does NOT use opts->user_function() or opts->clique_list[].
1082 */
clique_unweighted_find_single(graph_t * g,int min_size,int max_size,boolean maximal,clique_options * opts)1083 set_t clique_unweighted_find_single(graph_t *g,int min_size,int max_size,
1084 boolean maximal, clique_options *opts) {
1085 int i;
1086 int *table;
1087 set_t s;
1088
1089 ENTRANCE_SAVE();
1090 entrance_level++;
1091
1092 if (opts==NULL)
1093 opts=clique_default_options;
1094
1095 ASSERT((sizeof(setelement)*8)==ELEMENTSIZE);
1096 ASSERT(g!=NULL);
1097 ASSERT(min_size>=0);
1098 ASSERT(max_size>=0);
1099 ASSERT((max_size==0) || (min_size <= max_size));
1100 ASSERT(!((min_size==0) && (max_size>0)));
1101 ASSERT((opts->reorder_function==NULL) || (opts->reorder_map==NULL));
1102
1103 if ((max_size>0) && (min_size>max_size)) {
1104 /* state was not changed */
1105 entrance_level--;
1106 return NULL;
1107 }
1108
1109 if (clocks_per_sec==0)
1110 clocks_per_sec=sysconf(_SC_CLK_TCK);
1111 ASSERT(clocks_per_sec>0);
1112
1113 /* Dynamic allocation */
1114 current_clique=set_new(g->n);
1115 clique_size=malloc(g->n * sizeof(int));
1116 /* table allocated later */
1117 temp_list=malloc((g->n+2)*sizeof(int *));
1118 temp_count=0;
1119
1120 /* "start clock" */
1121 gettimeofday(&realtimer,NULL);
1122 times(&cputimer);
1123
1124 /* reorder */
1125 if (opts->reorder_function) {
1126 table=opts->reorder_function(g,FALSE);
1127 } else if (opts->reorder_map) {
1128 table=reorder_duplicate(opts->reorder_map,g->n);
1129 } else {
1130 table=reorder_ident(g->n);
1131 }
1132 ASSERT(reorder_is_bijection(table,g->n));
1133
1134
1135 if (unweighted_clique_search_single(table,min_size,g,opts)==0) {
1136 set_free(current_clique);
1137 current_clique=NULL;
1138 goto cleanreturn;
1139 }
1140 if (maximal && (min_size>0)) {
1141 maximalize_clique(current_clique,g);
1142
1143 if ((max_size > 0) && (set_size(current_clique) > max_size)) {
1144 clique_options localopts;
1145
1146 s = set_new(g->n);
1147 localopts.time_function = opts->time_function;
1148 localopts.output = opts->output;
1149 localopts.user_function = false_function;
1150 localopts.clique_list = &s;
1151 localopts.clique_list_length = 1;
1152
1153 for (i=0; i < g->n-1; i++)
1154 if (clique_size[table[i]]>=min_size)
1155 break;
1156 if (unweighted_clique_search_all(table,i,min_size,
1157 max_size,maximal,
1158 g,&localopts)) {
1159 set_free(current_clique);
1160 current_clique=s;
1161 } else {
1162 set_free(current_clique);
1163 current_clique=NULL;
1164 }
1165 }
1166 }
1167
1168 cleanreturn:
1169 s=current_clique;
1170
1171 /* Free resources */
1172 for (i=0; i < temp_count; i++)
1173 free(temp_list[i]);
1174 free(temp_list);
1175 free(table);
1176 free(clique_size);
1177
1178 ENTRANCE_RESTORE();
1179 entrance_level--;
1180
1181 return s;
1182 }
1183
1184
1185 /*
1186 * clique_unweighted_find_all()
1187 *
1188 * Find all cliques with size at least min_size and at most max_size.
1189 *
1190 * g - the graph
1191 * min_size - minimum size of cliques to search for. If min_size==0,
1192 * searches for maximum cliques.
1193 * max_size - maximum size of cliques to search for. If max_size==0, no
1194 * upper limit is used. If min_size==0, this must also be 0.
1195 * maximal - require cliques to be maximal cliques
1196 * opts - time printing and clique storage options
1197 *
1198 * Returns the number of cliques found. This can be less than the number
1199 * of cliques in the graph iff opts->time_function() or opts->user_function()
1200 * returns FALSE (request abort).
1201 *
1202 * The cliques found are stored in opts->clique_list[] and
1203 * opts->user_function() is called with them (if non-NULL). The cliques
1204 * stored in opts->clique_list[] are newly allocated, and can be freed
1205 * by set_free().
1206 */
clique_unweighted_find_all(graph_t * g,int min_size,int max_size,boolean maximal,clique_options * opts)1207 int clique_unweighted_find_all(graph_t *g, int min_size, int max_size,
1208 boolean maximal, clique_options *opts) {
1209 int i;
1210 int *table;
1211 int count;
1212
1213 ENTRANCE_SAVE();
1214 entrance_level++;
1215
1216 if (opts==NULL)
1217 opts=clique_default_options;
1218
1219 ASSERT((sizeof(setelement)*8)==ELEMENTSIZE);
1220 ASSERT(g!=NULL);
1221 ASSERT(min_size>=0);
1222 ASSERT(max_size>=0);
1223 ASSERT((max_size==0) || (min_size <= max_size));
1224 ASSERT(!((min_size==0) && (max_size>0)));
1225 ASSERT((opts->reorder_function==NULL) || (opts->reorder_map==NULL));
1226
1227 if ((max_size>0) && (min_size>max_size)) {
1228 /* state was not changed */
1229 entrance_level--;
1230 return 0;
1231 }
1232
1233 if (clocks_per_sec==0)
1234 clocks_per_sec=sysconf(_SC_CLK_TCK);
1235 ASSERT(clocks_per_sec>0);
1236
1237 /* Dynamic allocation */
1238 current_clique=set_new(g->n);
1239 clique_size=malloc(g->n * sizeof(int));
1240 /* table allocated later */
1241 temp_list=malloc((g->n+2)*sizeof(int *));
1242 temp_count=0;
1243
1244 clique_list_count=0;
1245 memset(clique_size,0,g->n * sizeof(int));
1246
1247 /* "start clock" */
1248 gettimeofday(&realtimer,NULL);
1249 times(&cputimer);
1250
1251 /* reorder */
1252 if (opts->reorder_function) {
1253 table=opts->reorder_function(g,FALSE);
1254 } else if (opts->reorder_map) {
1255 table=reorder_duplicate(opts->reorder_map,g->n);
1256 } else {
1257 table=reorder_ident(g->n);
1258 }
1259 ASSERT(reorder_is_bijection(table,g->n));
1260
1261
1262 /* Search as normal until there is a chance to find a suitable
1263 * clique. */
1264 if (unweighted_clique_search_single(table,min_size,g,opts)==0) {
1265 count=0;
1266 goto cleanreturn;
1267 }
1268
1269 if (min_size==0 && max_size==0) {
1270 min_size=max_size=clique_size[table[g->n-1]];
1271 maximal=FALSE; /* No need to test, since we're searching
1272 * for maximum cliques. */
1273 }
1274 if (max_size==0) {
1275 max_size=INT_MAX;
1276 }
1277
1278 for (i=0; i < g->n-1; i++)
1279 if (clique_size[table[i]] >= min_size)
1280 break;
1281 count=unweighted_clique_search_all(table,i,min_size,max_size,
1282 maximal,g,opts);
1283
1284 cleanreturn:
1285 /* Free resources */
1286 for (i=0; i<temp_count; i++)
1287 free(temp_list[i]);
1288 free(temp_list);
1289 free(table);
1290 free(clique_size);
1291 set_free(current_clique);
1292
1293 ENTRANCE_RESTORE();
1294 entrance_level--;
1295
1296 return count;
1297 }
1298
1299
1300
1301
1302 /*
1303 * clique_max_weight()
1304 *
1305 * Returns the weight of the maximum weight clique in the graph (or 0 if
1306 * the search was aborted).
1307 *
1308 * g - the graph
1309 * opts - time printing options
1310 *
1311 * Note: As we don't have an algorithm faster than actually finding
1312 * a maximum weight clique, we use clique_find_single().
1313 * This incurs only very small overhead.
1314 */
clique_max_weight(graph_t * g,clique_options * opts)1315 int clique_max_weight(graph_t *g,clique_options *opts) {
1316 set_t s;
1317 int weight;
1318
1319 ASSERT((sizeof(setelement)*8)==ELEMENTSIZE);
1320 ASSERT(g!=NULL);
1321
1322 s=clique_find_single(g,0,0,FALSE,opts);
1323 if (s==NULL) {
1324 /* Search was aborted. */
1325 return 0;
1326 }
1327 weight=graph_subgraph_weight(g,s);
1328 set_free(s);
1329 return weight;
1330 }
1331
1332
1333 /*
1334 * clique_find_single()
1335 *
1336 * Returns a clique with weight at least min_weight and at most max_weight.
1337 *
1338 * g - the graph
1339 * min_weight - minimum weight of clique to search for. If min_weight==0,
1340 * searches for a maximum weight clique.
1341 * max_weight - maximum weight of clique to search for. If max_weight==0,
1342 * no upper limit is used. If min_weight==0, max_weight must
1343 * also be 0.
1344 * maximal - require returned clique to be maximal
1345 * opts - time printing options
1346 *
1347 * Returns the set of vertices forming the clique, or NULL if a clique
1348 * of requested weight/maximality does not exist in the graph (or if
1349 * opts->time_function() requests abort).
1350 *
1351 * The returned clique is newly allocated and can be freed by set_free().
1352 *
1353 * Note: Does NOT use opts->user_function() or opts->clique_list[].
1354 * Note: Automatically uses clique_unweighted_find_single if all vertex
1355 * weights are the same.
1356 */
clique_find_single(graph_t * g,int min_weight,int max_weight,boolean maximal,clique_options * opts)1357 set_t clique_find_single(graph_t *g,int min_weight,int max_weight,
1358 boolean maximal, clique_options *opts) {
1359 int i;
1360 int *table;
1361 set_t s;
1362
1363 ENTRANCE_SAVE();
1364 entrance_level++;
1365
1366 if (opts==NULL)
1367 opts=clique_default_options;
1368
1369 ASSERT((sizeof(setelement)*8)==ELEMENTSIZE);
1370 ASSERT(g!=NULL);
1371 ASSERT(min_weight>=0);
1372 ASSERT(max_weight>=0);
1373 ASSERT((max_weight==0) || (min_weight <= max_weight));
1374 ASSERT(!((min_weight==0) && (max_weight>0)));
1375 ASSERT((opts->reorder_function==NULL) || (opts->reorder_map==NULL));
1376
1377 if ((max_weight>0) && (min_weight>max_weight)) {
1378 /* state was not changed */
1379 entrance_level--;
1380 return NULL;
1381 }
1382
1383 if (clocks_per_sec==0)
1384 clocks_per_sec=sysconf(_SC_CLK_TCK);
1385 ASSERT(clocks_per_sec>0);
1386
1387 /* Check whether we can use unweighted routines. */
1388 if (!graph_weighted(g)) {
1389 min_weight=DIV_UP(min_weight,g->weights[0]);
1390 if (max_weight) {
1391 max_weight=DIV_DOWN(max_weight,g->weights[0]);
1392 if (max_weight < min_weight) {
1393 /* state was not changed */
1394 entrance_level--;
1395 return NULL;
1396 }
1397 }
1398
1399 weight_multiplier = g->weights[0];
1400 entrance_level--;
1401 s=clique_unweighted_find_single(g,min_weight,max_weight,
1402 maximal,opts);
1403 ENTRANCE_RESTORE();
1404 return s;
1405 }
1406
1407 /* Dynamic allocation */
1408 current_clique=set_new(g->n);
1409 best_clique=set_new(g->n);
1410 clique_size=malloc(g->n * sizeof(int));
1411 memset(clique_size, 0, g->n * sizeof(int));
1412 /* table allocated later */
1413 temp_list=malloc((g->n+2)*sizeof(int *));
1414 temp_count=0;
1415
1416 clique_list_count=0;
1417
1418 /* "start clock" */
1419 gettimeofday(&realtimer,NULL);
1420 times(&cputimer);
1421
1422 /* reorder */
1423 if (opts->reorder_function) {
1424 table=opts->reorder_function(g,TRUE);
1425 } else if (opts->reorder_map) {
1426 table=reorder_duplicate(opts->reorder_map,g->n);
1427 } else {
1428 table=reorder_ident(g->n);
1429 }
1430 ASSERT(reorder_is_bijection(table,g->n));
1431
1432 if (max_weight==0)
1433 max_weight=INT_MAX;
1434
1435 if (weighted_clique_search_single(table,min_weight,max_weight,
1436 g,opts)==0) {
1437 /* Requested clique has not been found. */
1438 set_free(best_clique);
1439 best_clique=NULL;
1440 goto cleanreturn;
1441 }
1442 if (maximal && (min_weight>0)) {
1443 maximalize_clique(best_clique,g);
1444 if (graph_subgraph_weight(g,best_clique) > max_weight) {
1445 clique_options localopts;
1446
1447 localopts.time_function = opts->time_function;
1448 localopts.output = opts->output;
1449 localopts.user_function = false_function;
1450 localopts.clique_list = &best_clique;
1451 localopts.clique_list_length = 1;
1452
1453 for (i=0; i < g->n-1; i++)
1454 if ((clique_size[table[i]] >= min_weight) ||
1455 (clique_size[table[i]] == 0))
1456 break;
1457 if (!weighted_clique_search_all(table,i,min_weight,
1458 max_weight,maximal,
1459 g,&localopts)) {
1460 set_free(best_clique);
1461 best_clique=NULL;
1462 }
1463 }
1464 }
1465
1466 cleanreturn:
1467 s=best_clique;
1468
1469 /* Free resources */
1470 for (i=0; i < temp_count; i++)
1471 free(temp_list[i]);
1472 free(temp_list);
1473 temp_list=NULL;
1474 temp_count=0;
1475 free(table);
1476 set_free(current_clique);
1477 current_clique=NULL;
1478 free(clique_size);
1479 clique_size=NULL;
1480
1481 ENTRANCE_RESTORE();
1482 entrance_level--;
1483
1484 return s;
1485 }
1486
1487
1488
1489
1490
1491 /*
1492 * clique_find_all()
1493 *
1494 * Find all cliques with weight at least min_weight and at most max_weight.
1495 *
1496 * g - the graph
1497 * min_weight - minimum weight of cliques to search for. If min_weight==0,
1498 * searches for maximum weight cliques.
1499 * max_weight - maximum weight of cliques to search for. If max_weight==0,
1500 * no upper limit is used. If min_weight==0, max_weight must
1501 * also be 0.
1502 * maximal - require cliques to be maximal cliques
1503 * opts - time printing and clique storage options
1504 *
1505 * Returns the number of cliques found. This can be less than the number
1506 * of cliques in the graph iff opts->time_function() or opts->user_function()
1507 * returns FALSE (request abort).
1508 *
1509 * The cliques found are stored in opts->clique_list[] and
1510 * opts->user_function() is called with them (if non-NULL). The cliques
1511 * stored in opts->clique_list[] are newly allocated, and can be freed
1512 * by set_free().
1513 *
1514 * Note: Automatically uses clique_unweighted_find_all if all vertex
1515 * weights are the same.
1516 */
clique_find_all(graph_t * g,int min_weight,int max_weight,boolean maximal,clique_options * opts)1517 int clique_find_all(graph_t *g, int min_weight, int max_weight,
1518 boolean maximal, clique_options *opts) {
1519 int i,n;
1520 int *table;
1521
1522 ENTRANCE_SAVE();
1523 entrance_level++;
1524
1525 if (opts==NULL)
1526 opts=clique_default_options;
1527
1528 ASSERT((sizeof(setelement)*8)==ELEMENTSIZE);
1529 ASSERT(g!=NULL);
1530 ASSERT(min_weight>=0);
1531 ASSERT(max_weight>=0);
1532 ASSERT((max_weight==0) || (min_weight <= max_weight));
1533 ASSERT(!((min_weight==0) && (max_weight>0)));
1534 ASSERT((opts->reorder_function==NULL) || (opts->reorder_map==NULL));
1535
1536 if ((max_weight>0) && (min_weight>max_weight)) {
1537 /* state was not changed */
1538 entrance_level--;
1539 return 0;
1540 }
1541
1542 if (clocks_per_sec==0)
1543 clocks_per_sec=sysconf(_SC_CLK_TCK);
1544 ASSERT(clocks_per_sec>0);
1545
1546 if (!graph_weighted(g)) {
1547 min_weight=DIV_UP(min_weight,g->weights[0]);
1548 if (max_weight) {
1549 max_weight=DIV_DOWN(max_weight,g->weights[0]);
1550 if (max_weight < min_weight) {
1551 /* state was not changed */
1552 entrance_level--;
1553 return 0;
1554 }
1555 }
1556
1557 weight_multiplier = g->weights[0];
1558 entrance_level--;
1559 i=clique_unweighted_find_all(g,min_weight,max_weight,maximal,
1560 opts);
1561 ENTRANCE_RESTORE();
1562 return i;
1563 }
1564
1565 /* Dynamic allocation */
1566 current_clique=set_new(g->n);
1567 best_clique=set_new(g->n);
1568 clique_size=malloc(g->n * sizeof(int));
1569 memset(clique_size, 0, g->n * sizeof(int));
1570 /* table allocated later */
1571 temp_list=malloc((g->n+2)*sizeof(int *));
1572 temp_count=0;
1573
1574 /* "start clock" */
1575 gettimeofday(&realtimer,NULL);
1576 times(&cputimer);
1577
1578 /* reorder */
1579 if (opts->reorder_function) {
1580 table=opts->reorder_function(g,TRUE);
1581 } else if (opts->reorder_map) {
1582 table=reorder_duplicate(opts->reorder_map,g->n);
1583 } else {
1584 table=reorder_ident(g->n);
1585 }
1586 ASSERT(reorder_is_bijection(table,g->n));
1587
1588 /* First phase */
1589 n=weighted_clique_search_single(table,min_weight,INT_MAX,g,opts);
1590 if (n==0) {
1591 /* Requested clique has not been found. */
1592 goto cleanreturn;
1593 }
1594
1595 if (min_weight==0) {
1596 min_weight=n;
1597 max_weight=n;
1598 maximal=FALSE; /* They're maximum cliques already. */
1599 }
1600 if (max_weight==0)
1601 max_weight=INT_MAX;
1602
1603 for (i=0; i < g->n; i++)
1604 if ((clique_size[table[i]] >= min_weight) ||
1605 (clique_size[table[i]] == 0))
1606 break;
1607
1608 /* Second phase */
1609 n=weighted_clique_search_all(table,i,min_weight,max_weight,maximal,
1610 g,opts);
1611
1612 cleanreturn:
1613 /* Free resources */
1614 for (i=0; i < temp_count; i++)
1615 free(temp_list[i]);
1616 free(temp_list);
1617 free(table);
1618 set_free(current_clique);
1619 set_free(best_clique);
1620 free(clique_size);
1621
1622 ENTRANCE_RESTORE();
1623 entrance_level--;
1624
1625 return n;
1626 }
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644 /*
1645 * clique_print_time()
1646 *
1647 * Reports current running information every 0.1 seconds or when values
1648 * change.
1649 *
1650 * level - re-entrance level
1651 * i - current recursion level
1652 * n - maximum recursion level
1653 * max - weight of heaviest clique found
1654 * cputime - CPU time used in algorithm so far
1655 * realtime - real time used in algorithm so far
1656 * opts - prints information to (FILE *)opts->output (or stdout if NULL)
1657 *
1658 * Returns always TRUE (ie. never requests abort).
1659 */
clique_print_time(int level,int i,int n,int max,double cputime,double realtime,clique_options * opts)1660 boolean clique_print_time(int level, int i, int n, int max,
1661 double cputime, double realtime,
1662 clique_options *opts) {
1663 static float prev_time=100;
1664 static int prev_i=100;
1665 static int prev_max=100;
1666 static int prev_level=0;
1667 FILE *fp=opts->output;
1668 int j;
1669
1670 if (fp==NULL)
1671 fp=stdout;
1672
1673 if (ABS(prev_time-realtime)>0.1 || i==n || i<prev_i || max!=prev_max ||
1674 level!=prev_level) {
1675 for (j=1; j<level; j++)
1676 fprintf(fp," ");
1677 if (realtime-prev_time < 0.01 || i<=prev_i)
1678 fprintf(fp,"%3d/%d (max %2d) %2.2f s "
1679 "(0.00 s/round)\n",i,n,max,
1680 realtime);
1681 else
1682 fprintf(fp,"%3d/%d (max %2d) %2.2f s "
1683 "(%2.2f s/round)\n",
1684 i,n,max,realtime,
1685 (realtime-prev_time)/(i-prev_i));
1686 prev_time=realtime;
1687 prev_i=i;
1688 prev_max=max;
1689 prev_level=level;
1690 }
1691 return TRUE;
1692 }
1693
1694 /*
1695 * clique_print_time_always()
1696 *
1697 * Reports current running information.
1698 *
1699 * level - re-entrance level
1700 * i - current recursion level
1701 * n - maximum recursion level
1702 * max - largest clique found
1703 * cputime - CPU time used in algorithm so far
1704 * realtime - real time used in algorithm so far
1705 * opts - prints information to (FILE *)opts->output (or stdout if NULL)
1706 *
1707 * Returns always TRUE (ie. never requests abort).
1708 */
clique_print_time_always(int level,int i,int n,int max,double cputime,double realtime,clique_options * opts)1709 boolean clique_print_time_always(int level, int i, int n, int max,
1710 double cputime, double realtime,
1711 clique_options *opts) {
1712 static float prev_time=100;
1713 static int prev_i=100;
1714 FILE *fp=opts->output;
1715 int j;
1716
1717 if (fp==NULL)
1718 fp=stdout;
1719
1720 for (j=1; j<level; j++)
1721 fprintf(fp," ");
1722
1723 if (realtime-prev_time < 0.01 || i<=prev_i)
1724 fprintf(fp,"%3d/%d (max %2d) %2.2f s (0.00 s/round)\n",
1725 i,n,max,realtime);
1726 else
1727 fprintf(fp,"%3d/%d (max %2d) %2.2f s (%2.2f s/round)\n",
1728 i,n,max,realtime,(realtime-prev_time)/(i-prev_i));
1729 prev_time=realtime;
1730 prev_i=i;
1731
1732 return TRUE;
1733 }
1734