summaryrefslogtreecommitdiff
path: root/nauty/nautycliquer.h
diff options
context:
space:
mode:
Diffstat (limited to 'nauty/nautycliquer.h')
-rw-r--r--nauty/nautycliquer.h647
1 files changed, 647 insertions, 0 deletions
diff --git a/nauty/nautycliquer.h b/nauty/nautycliquer.h
new file mode 100644
index 0000000..ff232e5
--- /dev/null
+++ b/nauty/nautycliquer.h
@@ -0,0 +1,647 @@
+/* This file has all the included material used by cliquer-1.21
+ and prototypes for the interface procedures in nautycliquer.c */
+
+#ifndef NAUTYCLIQUER_H
+#define NAUTYCLIQUER_H
+
+#include "nauty.h"
+#include "gtools.h"
+#include <limits.h>
+
+/**********************************************************************
+#include "cliquerconf.h"
+*/
+
+/*
+ * setelement is the basic memory type used in sets. It is often fastest
+ * to be as large as can fit into the CPU registers.
+ *
+ * ELEMENTSIZE is the size of one setelement, measured in bits. It must
+ * be either 16, 32 or 64 (otherwise additional changes must be made to
+ * the source).
+ *
+ * The default is to use "unsigned long int" and attempt to guess the
+ * size using <limits.h>, which should work pretty well. Check functioning
+ * with "make test".
+ */
+
+/* typedef unsigned long int setelement; */
+/* #define ELEMENTSIZE 64 */
+
+/*
+ * INLINE is a command prepended to function declarations to instruct the
+ * compiler to inline the function. If inlining is not desired, define blank.
+ *
+ * The default is to use "inline", which is recognized by most compilers.
+ */
+
+/* #define INLINE */
+/* #define INLINE __inline__ */
+
+
+/*
+ * Set handling functions are defined as static functions in set.h for
+ * performance reasons. This may cause unnecessary warnings from the
+ * compiler. Some compilers (such as GCC) have the possibility to turn
+ * off the warnings on a per-function basis using a flag prepended to
+ * the function declaration.
+ *
+ * The default is to use the correct attribute when compiling with GCC,
+ * or no flag otherwise.
+ */
+
+/* #define UNUSED_FUNCTION __attribute__((unused)) */
+/* #define UNUSED_FUNCTION */
+
+/*
+ * Uncommenting the following will disable all assertions (checks that
+ * function arguments and other variables are correct). This is highly
+ * discouraged, as it allows bugs to go unnoticed easier. The assertions
+ * are set so that they do not slow down programs notably.
+ */
+
+/* #define ASSERT(x) */
+
+/**********************************************************************
+#include "misc.h"
+*/
+
+/*
+ * We #define boolean instead of using a typedef because nauty.h uses it
+ * also. AFAIK, there is no way to check for an existing typedef, and
+ * re-typedefing is illegal (even when using exactly the same datatype!).
+#ifndef boolean
+#define boolean int
+#endif
+
+BDM: In nauty's version we will use nauty's boolean (which is int anyway).
+ */
+
+/*
+ * Default value for UNUSED_FUNCTION: use "__attribute__((unused))" for
+ * GCC versions that support it, otherwise leave blank.
+ */
+#ifndef UNUSED_FUNCTION
+# if __GNUC__ > 2 || (__GNUC__ == 2 && __GNUC_MINOR__ > 4)
+# define UNUSED_FUNCTION __attribute__((unused))
+# else
+# define UNUSED_FUNCTION
+# endif
+#endif /* !UNUSED_FUNCTION */
+
+/*
+ * Default inlining directive: "inline"
+ */
+#ifndef INLINE
+#define INLINE inline
+#endif
+
+#ifndef ASSERT
+#define ASSERT(expr) \
+ if (!(expr)) { \
+ fprintf(stderr,"cliquer file %s: line %d: assertion failed: " \
+ "(%s)\n",__FILE__,__LINE__,#expr); \
+ abort(); \
+ }
+#endif /* !ASSERT */
+
+
+#ifndef FALSE
+#define FALSE (0)
+#endif
+#ifndef TRUE
+#define TRUE (!FALSE)
+#endif
+
+
+#ifndef MIN
+#define MIN(a,b) (((a)<(b))?(a):(b))
+#endif
+#ifndef MAX
+#define MAX(a,b) (((a)>(b))?(a):(b))
+#endif
+#ifndef ABS
+#define ABS(v) (((v)<0)?(-(v)):(v))
+#endif
+
+/**********************************************************************
+#include "set.h"
+*/
+
+/*
+ * This file contains the set handling routines.
+ *
+ * Copyright (C) 2002 Sampo Niskanen, Patric Östergård.
+ * Licensed under the GNU GPL, read the file LICENSE for details.
+ */
+
+/*
+ * Sets are arrays of setelement's (typically unsigned long int's) with
+ * representative bits for each value they can contain. The values
+ * are numbered 0,...,n-1.
+ */
+
+
+/*** Variable types and constants. ***/
+
+
+/*
+ * If setelement hasn't been declared:
+ * - use "unsigned long int" as setelement
+ * - try to deduce size from ULONG_MAX
+ */
+
+#ifndef ELEMENTSIZE
+typedef unsigned long int setelement;
+# if (ULONG_MAX == 65535)
+# define ELEMENTSIZE 16
+# elif (ULONG_MAX == 4294967295)
+# define ELEMENTSIZE 32
+# else
+# define ELEMENTSIZE 64
+# endif
+#endif /* !ELEMENTSIZE */
+
+typedef setelement * set_t;
+
+
+/*** Counting amount of 1 bits in a setelement ***/
+
+/* Array for amount of 1 bits in a byte. */
+static int set_bit_count[256] = {
+ 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,
+ 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
+ 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
+ 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
+ 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
+ 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
+ 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
+ 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
+ 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
+ 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
+ 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
+ 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
+ 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
+ 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
+ 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
+ 4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8 };
+
+/* The following macros assume that all higher bits are 0.
+ * They may in some cases be useful also on with other ELEMENTSIZE's,
+ * so we define them all. */
+#define SET_ELEMENT_BIT_COUNT_8(a) (set_bit_count[(a)])
+#define SET_ELEMENT_BIT_COUNT_16(a) (set_bit_count[(a)>>8] + \
+ set_bit_count[(a)&0xFF])
+#define SET_ELEMENT_BIT_COUNT_32(a) (set_bit_count[(a)>>24] + \
+ set_bit_count[((a)>>16)&0xFF] + \
+ set_bit_count[((a)>>8)&0xFF] + \
+ set_bit_count[(a)&0xFF])
+#define SET_ELEMENT_BIT_COUNT_64(a) (set_bit_count[(a)>>56] + \
+ set_bit_count[((a)>>48)&0xFF] + \
+ set_bit_count[((a)>>40)&0xFF] + \
+ set_bit_count[((a)>>32)&0xFF] + \
+ set_bit_count[((a)>>24)&0xFF] + \
+ set_bit_count[((a)>>16)&0xFF] + \
+ set_bit_count[((a)>>8)&0xFF] + \
+ set_bit_count[(a)&0xFF])
+#if (ELEMENTSIZE==64)
+# define SET_ELEMENT_BIT_COUNT(a) SET_ELEMENT_BIT_COUNT_64(a)
+# define FULL_ELEMENT ((setelement)0xFFFFFFFFFFFFFFFF)
+#elif (ELEMENTSIZE==32)
+# define SET_ELEMENT_BIT_COUNT(a) SET_ELEMENT_BIT_COUNT_32(a)
+# define FULL_ELEMENT ((setelement)0xFFFFFFFF)
+#elif (ELEMENTSIZE==16)
+# define SET_ELEMENT_BIT_COUNT(a) SET_ELEMENT_BIT_COUNT_16(a)
+# define FULL_ELEMENT ((setelement)0xFFFF)
+#else
+# error "SET_ELEMENT_BIT_COUNT(a) not defined for current ELEMENTSIZE"
+#endif
+
+/*** Macros and functions ***/
+
+/*
+ * Gives a value with bit x (counting from lsb up) set.
+ *
+ * Making this as a table might speed up things on some machines
+ * (though on most modern machines it's faster to shift instead of
+ * using memory). Making it a macro makes it easy to change.
+ */
+#define SET_BIT_MASK(x) ((setelement)1<<(x))
+
+/* Set element handling macros */
+
+#define SET_ELEMENT_INTERSECT(a,b) ((a)&(b))
+#define SET_ELEMENT_UNION(a,b) ((a)|(b))
+#define SET_ELEMENT_DIFFERENCE(a,b) ((a)&(~(b)))
+#define SET_ELEMENT_CONTAINS(e,v) ((e)&SET_BIT_MASK(v))
+
+/* Set handling macros */
+
+#define SET_ADD_ELEMENT(s,a) \
+ ((s)[(a)/ELEMENTSIZE] |= SET_BIT_MASK((a)%ELEMENTSIZE))
+#define SET_DEL_ELEMENT(s,a) \
+ ((s)[(a)/ELEMENTSIZE] &= ~SET_BIT_MASK((a)%ELEMENTSIZE))
+#define SET_CONTAINS_FAST(s,a) (SET_ELEMENT_CONTAINS((s)[(a)/ELEMENTSIZE], \
+ (a)%ELEMENTSIZE))
+#define SET_CONTAINS(s,a) (((a)<SET_MAX_SIZE(s))?SET_CONTAINS_FAST(s,a):FALSE)
+
+/* Sets can hold values between 0,...,SET_MAX_SIZE(s)-1 */
+#define SET_MAX_SIZE(s) ((s)[-1])
+/* Sets consist of an array of SET_ARRAY_LENGTH(s) setelements */
+#define SET_ARRAY_LENGTH(s) (((s)[-1]+ELEMENTSIZE-1)/ELEMENTSIZE)
+
+/*
+ * set_new()
+ *
+ * Create a new set that can hold values in the range 0,...,size-1.
+ */
+UNUSED_FUNCTION
+static set_t set_new(int size) {
+ int n;
+ set_t s;
+
+ ASSERT(size>0);
+
+ n=(size/ELEMENTSIZE+1)+1;
+ s=calloc(n,sizeof(setelement));
+ s[0]=size;
+
+ return &(s[1]);
+}
+
+/*
+ * set_free()
+ *
+ * Free the memory associated with set s.
+ */
+UNUSED_FUNCTION INLINE
+static void set_free(set_t s) {
+ ASSERT(s!=NULL);
+ free(&(s[-1]));
+}
+
+/*
+ * set_resize()
+ *
+ * Resizes set s to given size. If the size is less than SET_MAX_SIZE(s),
+ * the last elements are dropped.
+ *
+ * Returns a pointer to the new set.
+ */
+UNUSED_FUNCTION INLINE
+static set_t set_resize(set_t s, int size) {
+ int n;
+
+ ASSERT(size>0);
+
+ n=(size/ELEMENTSIZE+1);
+ s=((setelement *)realloc(s-1,(n+1)*sizeof(setelement)))+1;
+
+ if (n>SET_ARRAY_LENGTH(s))
+ memset(s+SET_ARRAY_LENGTH(s),0,
+ (n-SET_ARRAY_LENGTH(s))*sizeof(setelement));
+ if (size < SET_MAX_SIZE(s))
+ s[(size-1)/ELEMENTSIZE] &= (FULL_ELEMENT >>
+ (ELEMENTSIZE-size%ELEMENTSIZE));
+ s[-1]=size;
+
+ return s;
+}
+
+/*
+ * set_size()
+ *
+ * Returns the number of elements in set s.
+ */
+UNUSED_FUNCTION INLINE
+static int set_size(set_t s) {
+ int count=0;
+ setelement *c;
+
+ for (c=s; c < s+SET_ARRAY_LENGTH(s); c++)
+ count+=SET_ELEMENT_BIT_COUNT(*c);
+ return count;
+}
+
+/*
+ * set_duplicate()
+ *
+ * Returns a newly allocated duplicate of set s.
+ */
+UNUSED_FUNCTION INLINE
+static set_t set_duplicate(set_t s) {
+ set_t new;
+
+ new=set_new(SET_MAX_SIZE(s));
+ memcpy(new,s,SET_ARRAY_LENGTH(s)*sizeof(setelement));
+ return new;
+}
+
+/*
+ * set_copy()
+ *
+ * Copies set src to dest. If dest is NULL, is equal to set_duplicate.
+ * If dest smaller than src, it is freed and a new set of the same size as
+ * src is returned.
+ */
+UNUSED_FUNCTION INLINE
+static set_t set_copy(set_t dest,set_t src) {
+ if (dest==NULL)
+ return set_duplicate(src);
+ if (SET_MAX_SIZE(dest)<SET_MAX_SIZE(src)) {
+ set_free(dest);
+ return set_duplicate(src);
+ }
+ memcpy(dest,src,SET_ARRAY_LENGTH(src)*sizeof(setelement));
+ memset(dest+SET_ARRAY_LENGTH(src),0,((SET_ARRAY_LENGTH(dest) -
+ SET_ARRAY_LENGTH(src)) *
+ sizeof(setelement)));
+ return dest;
+}
+
+/*
+ * set_empty()
+ *
+ * Removes all elements from the set s.
+ */
+UNUSED_FUNCTION INLINE
+static void set_empty(set_t s) {
+ memset(s,0,SET_ARRAY_LENGTH(s)*sizeof(setelement));
+ return;
+}
+
+/*
+ * set_intersection()
+ *
+ * Store the intersection of sets a and b into res. If res is NULL,
+ * a new set is created and the result is written to it. If res is
+ * smaller than the larger one of a and b, it is freed and a new set
+ * is created and the result is returned.
+ *
+ * Returns either res or a new set that has been allocated in its stead.
+ *
+ * Note: res may not be a or b.
+ */
+UNUSED_FUNCTION INLINE
+static set_t set_intersection(set_t res,set_t a,set_t b) {
+ int i,max;
+
+ if (res==NULL) {
+ res = set_new(MAX(SET_MAX_SIZE(a),SET_MAX_SIZE(b)));
+ } else if (SET_MAX_SIZE(res) < MAX(SET_MAX_SIZE(a),SET_MAX_SIZE(b))) {
+ set_free(res);
+ res = set_new(MAX(SET_MAX_SIZE(a),SET_MAX_SIZE(b)));
+ } else {
+ set_empty(res);
+ }
+
+ max=MIN(SET_ARRAY_LENGTH(a),SET_ARRAY_LENGTH(b));
+ for (i=0; i<max; i++) {
+ res[i]=SET_ELEMENT_INTERSECT(a[i],b[i]);
+ }
+
+ return res;
+}
+
+/*
+ * set_union()
+ *
+ * Store the union of sets a and b into res. If res is NULL, a new set
+ * is created and the result is written to it. If res is smaller than
+ * the larger one of a and b, it is freed and a new set is created and
+ * the result is returned.
+ *
+ * Returns either res or a new set that has been allocated in its stead.
+ *
+ * Note: res may not be a or b.
+ */
+UNUSED_FUNCTION INLINE
+static set_t set_union(set_t res,set_t a,set_t b) {
+ int i,max;
+
+ if (res==NULL) {
+ res = set_new(MAX(SET_MAX_SIZE(a),SET_MAX_SIZE(b)));
+ } else if (SET_MAX_SIZE(res) < MAX(SET_MAX_SIZE(a),SET_MAX_SIZE(b))) {
+ set_free(res);
+ res = set_new(MAX(SET_MAX_SIZE(a),SET_MAX_SIZE(b)));
+ } else {
+ set_empty(res);
+ }
+
+ max=MAX(SET_ARRAY_LENGTH(a),SET_ARRAY_LENGTH(b));
+ for (i=0; i<max; i++) {
+ res[i]=SET_ELEMENT_UNION(a[i],b[i]);
+ }
+
+ return res;
+}
+
+
+/*
+ * set_return_next()
+ *
+ * Returns the smallest value in set s which is greater than n, or -1 if
+ * such a value does not exist.
+ *
+ * Can be used to iterate through all values of s:
+ *
+ * int i=-1;
+ * while ((i=set_return_next(s,i))>=0) {
+ * // i is in set s
+ * }
+ */
+UNUSED_FUNCTION INLINE
+static int set_return_next(set_t s, int n) {
+ if (n<0)
+ n=0;
+ else
+ n++;
+ if (n >= SET_MAX_SIZE(s))
+ return -1;
+
+ while (n%ELEMENTSIZE) {
+ if (SET_CONTAINS(s,n))
+ return n;
+ n++;
+ if (n >= SET_MAX_SIZE(s))
+ return -1;
+ }
+
+ while (s[n/ELEMENTSIZE]==0) {
+ n+=ELEMENTSIZE;
+ if (n >= SET_MAX_SIZE(s))
+ return -1;
+ }
+ while (!SET_CONTAINS(s,n)) {
+ n++;
+ if (n >= SET_MAX_SIZE(s))
+ return -1;
+ }
+ return n;
+}
+
+
+/*
+ * set_print()
+ *
+ * Prints the size and contents of set s to stdout.
+ * Mainly useful for debugging purposes and trivial output.
+ */
+UNUSED_FUNCTION
+static void set_print(set_t s) {
+ int i;
+ printf("size=%d(max %d)",set_size(s),(int)SET_MAX_SIZE(s));
+ for (i=0; i<SET_MAX_SIZE(s); i++)
+ if (SET_CONTAINS(s,i))
+ printf(" %d",i);
+ printf("\n");
+ return;
+}
+
+/********************************************************************
+#include "graph.h"
+*/
+
+typedef struct _graph_t graph_t;
+struct _graph_t {
+ int n; /* Vertices numbered 0...n-1 */
+ set_t *edges; /* A list of n sets (the edges). */
+ int *weights; /* A list of n vertex weights. */
+};
+
+
+#define GRAPH_IS_EDGE_FAST(g,i,j) (SET_CONTAINS_FAST((g)->edges[(i)],(j)))
+#define GRAPH_IS_EDGE(g,i,j) (((i)<((g)->n))?SET_CONTAINS((g)->edges[(i)], \
+ (j)):FALSE)
+#define GRAPH_ADD_EDGE(g,i,j) do { \
+ SET_ADD_ELEMENT((g)->edges[(i)],(j)); \
+ SET_ADD_ELEMENT((g)->edges[(j)],(i)); \
+} while (FALSE)
+#define GRAPH_DEL_EDGE(g,i,j) do { \
+ SET_DEL_ELEMENT((g)->edges[(i)],(j)); \
+ SET_DEL_ELEMENT((g)->edges[(j)],(i)); \
+} while (FALSE)
+
+
+extern graph_t *graph_new(int n);
+extern void graph_free(graph_t *g);
+extern void graph_resize(graph_t *g, int size);
+extern void graph_crop(graph_t *g);
+
+extern boolean graph_weighted(graph_t *g);
+extern int graph_edge_count(graph_t *g);
+
+extern graph_t *graph_read_dimacs(FILE *fp);
+extern graph_t *graph_read_dimacs_file(char *file);
+extern boolean graph_write_dimacs_ascii(graph_t *g, char *comment,FILE *fp);
+extern boolean graph_write_dimacs_ascii_file(graph_t *g,char *comment,
+ char *file);
+extern boolean graph_write_dimacs_binary(graph_t *g, char *comment,FILE *fp);
+extern boolean graph_write_dimacs_binary_file(graph_t *g, char *comment,
+ char *file);
+
+extern void graph_print(graph_t *g);
+extern boolean graph_test(graph_t *g, FILE *output);
+extern int graph_test_regular(graph_t *g);
+
+UNUSED_FUNCTION INLINE
+static int graph_subgraph_weight(graph_t *g,set_t s) {
+ int i,j;
+ int count=0;
+ setelement e;
+
+ for (i=0; i<SET_ARRAY_LENGTH(s); i++) {
+ if (s[i]) {
+ e=s[i];
+ for (j=0; j<ELEMENTSIZE; j++) {
+ if (e&1)
+ count+=g->weights[i*ELEMENTSIZE+j];
+ e = e>>1;
+ }
+ }
+ }
+ return count;
+}
+
+UNUSED_FUNCTION INLINE
+static int graph_vertex_degree(graph_t *g, int v) {
+ return set_size(g->edges[v]);
+}
+
+/********************************************************************
+#include "reorder.h"
+*/
+
+extern void reorder_set(set_t s,int *order);
+extern void reorder_graph(graph_t *g, int *order);
+extern int *reorder_duplicate(int *order,int n);
+extern void reorder_invert(int *order,int n);
+extern void reorder_reverse(int *order,int n);
+extern int *reorder_ident(int n);
+extern boolean reorder_is_bijection(int *order,int n);
+
+
+#define reorder_by_default reorder_by_greedy_coloring
+extern int *reorder_by_greedy_coloring(graph_t *g, boolean weighted);
+extern int *reorder_by_weighted_greedy_coloring(graph_t *g, boolean weighted);
+extern int *reorder_by_unweighted_greedy_coloring(graph_t *g,boolean weighted);
+extern int *reorder_by_degree(graph_t *g, boolean weighted);
+extern int *reorder_by_random(graph_t *g, boolean weighted);
+extern int *reorder_by_ident(graph_t *g, boolean weighted);
+extern int *reorder_by_reverse(graph_t *g, boolean weighted);
+
+
+typedef struct _clique_options clique_options;
+struct _clique_options {
+ int *(*reorder_function)(graph_t *, boolean);
+ int *reorder_map;
+
+ /* arguments: level, n, max, user_time, system_time, opts */
+ boolean (*time_function)(int,int,int,int,double,double,
+ clique_options *);
+ FILE *output;
+
+ boolean (*user_function)(set_t,graph_t *,clique_options *);
+ void *user_data;
+ set_t *clique_list;
+ int clique_list_length;
+};
+
+extern clique_options *clique_default_options;
+
+/* Weighted clique functions */
+extern int clique_max_weight(graph_t *g,clique_options *opts);
+extern set_t clique_find_single(graph_t *g,int min_weight,int max_weight,
+ boolean maximal, clique_options *opts);
+extern int clique_find_all(graph_t *g, int req_weight, boolean exact,
+ boolean maximal, clique_options *opts);
+
+/* Unweighted clique functions */
+#define clique_unweighted_max_size clique_unweighted_max_weight
+extern int clique_unweighted_max_weight(graph_t *g, clique_options *opts);
+extern set_t clique_unweighted_find_single(graph_t *g,int min_size,
+ int max_size,boolean maximal,
+ clique_options *opts);
+extern int clique_unweighted_find_all(graph_t *g, int min_size, int max_size,
+ boolean maximal, clique_options *opts);
+
+/* Time printing functions */
+extern boolean clique_print_time(int level, int i, int n, int max,
+ double cputime, double realtime,
+ clique_options *opts);
+extern boolean clique_print_time_always(int level, int i, int n, int max,
+ double cputime, double realtime,
+ clique_options *opts);
+
+
+/* Alternate spelling (let's be a little forgiving): */
+#define cliquer_options clique_options
+#define cliquer_default_options clique_default_options
+
+/* Procedures defined in nautycliquer.c */
+extern int find_clique(graph *g, int m, int n,
+ int min, int max, boolean maximal);
+extern int find_indset(graph *g, int m, int n,
+ int min, int max, boolean maximal);
+
+#endif /* !NAUTYCLIQUER_H */
generated by cgit v1.2.3 (git 2.25.1) at 2025-12-17 11:08:00 +0000