1 /**************************************************************************
2 * This is the header file for Version 2.7 of nauty(). *
3 * nauty.h. Generated from nauty-h.in by configure.
4 **************************************************************************/
5
6 #ifndef _NAUTY_H_ /* only process this file once */
7 #define _NAUTY_H_
8
9 /* The parts between the ==== lines are modified by configure when
10 creating nauty.h out of nauty-h.in. If configure is not being used,
11 it is necessary to check they are correct.
12 ====================================================================*/
13
14 /* Check whether various headers or options are available */
15 #define HAVE_UNISTD_H 1 /* <unistd.h> */
16 #define HAVE_SYSTYPES_H 1 /* <sys/types.h> */
17 #define HAVE_STDDEF_H 1 /* <stddef.h> */
18 #define HAVE_STDLIB_H 1 /* <stdlib.h> */
19 #define HAVE_STRING_H 1 /* <string.h> */
20 #define HAVE_LIMITS_H 1 /* <limits.h> */
21 #define HAVE_STDINT_H 1 /* <stdint.h> */
22 #define MALLOC_DEC 1 /* 1 = malloc() is declared in stdlib.h, */
23 /* 2 = in malloc.h, 0 = in neither place */
24 #define HAS_MATH_INF 1 /* INFINITY is defined in math.h or */
25 /* some system header likely to be used */
26 #define HAS_STDIO_UNLOCK 1 /* Whether there are getc_unlocked, */
27 /* putc_unlocked,flockfile and funlockfile */
28
29 #define DEFAULT_WORDSIZE 32
30
31
32 /* Note that thread-local storage (TLS) is only useful for running nauty
33 in multiple threads and will slow it down a little otherwise. */
34 #define TLS_SUPPORTED 1 /* Compiler supports thread-local */
35
36 /* If USE_TLS is defined, define TLS_ATTR to be the attribute name
37 for TLS and define HAVE_TLS=1. Otherwise define TLS_ATTR to be empty
38 and HAVE_TLS=0. USE_TLS can be defined on the command line or by
39 configuring with --enable-tls. */
40 #ifndef USE_TLS
41
42 #endif
43 #ifdef USE_TLS
44 #if !TLS_SUPPORTED
45 #error "TLS is requested but not available"
46 #else
47 #define TLS_ATTR _Thread_local
48 #define HAVE_TLS 1
49 #endif
50 #else
51 #define TLS_ATTR
52 #define HAVE_TLS 0
53 #endif
54
55 #define USE_ANSICONTROLS 0
56 /* whether --enable-ansicontrols is used */
57 #define FLEX_ARRAY_OK 0
58 /* whether the compiler supports flexible array members in structures */
59
60 #define _FILE_OFFSET_BITS 0
61 #if _FILE_OFFSET_BITS == 64
62 #define _LARGEFILE_SOURCE
63 #else
64 #undef _FILE_OFFSET_BITS
65 #endif
66
67 /* Support of gcc extensions __builtin_clz, __builtin_clzl, __builtin_clzll */
68 #ifndef HAVE_HWLZCNT
69 #define HAVE_HWLZCNT 0
70 #endif
71 #define HAVE_CLZ 0
72 #define HAVE_CLZL 0
73 #define HAVE_CLZLL 0
74
75 /* Support of gcc extensions
76 __builtin_popcount, __builtin_popcountl, __builtin_popcountll
77 Note that these may only be fast if the compiler switch -mpopcnt is used.
78
79 Also the intrinsics
80 _mm_popcnt_u32, _mm_popcnt_u64
81 for the Intel compiler icc. These need no compiler switch.
82 */
83 #ifndef HAVE_HWPOPCNT
84 #define HAVE_HWPOPCNT 0
85 #endif
86 #define HAVE_POPCNT 0
87 #define HAVE_POPCNTL 0
88 #define HAVE_POPCNTLL 0
89 #define HAVE_MMPOP32 0
90 #define HAVE_MMPOP64 0
91
92 /*==================================================================*/
93
94 /* The following line must be uncommented for compiling into Magma. */
95 /* #define NAUTY_IN_MAGMA */
96
97 #ifdef NAUTY_IN_MAGMA
98 #include "defs.h"
99 #include "system.h"
100 #include "bs.h"
101 #define OLDEXTDEFS
102 #else
103 #include <stdio.h>
104 #define P_(x) x
105 #endif
106
107 #if defined(__unix) || defined(__unix__) || defined(unix)
108 #define SYS_UNIX
109 #endif
110
111 /*****************************************************************************
112 * *
113 * AUTHOR: Brendan D. McKay *
114 * Research School of Computer Science *
115 * Australian National University *
116 * Canberra, ACT 2601, Australia *
117 * phone: +61 2 6125 3845 *
118 * email: Brendan.McKay@anu.edu.au *
119 * *
120 * This software is subject to copyright as detailed in the file COPYRIGHT. *
121 * *
122 * Reference manual: *
123 * B. D. McKay and A. Piperno, nauty User's Guide (Version 2.5), *
124 * http://pallini.di.uniroma1.it *
125 * http://cs.anu.edu.au/~bdm/nauty/ *
126 * *
127 * CHANGE HISTORY *
128 * 10-Nov-87 : final changes for version 1.2 *
129 * 5-Dec-87 : renamed to version 1.3 (no changes to this file) *
130 * 28-Sep-88 : added PC Turbo C support, making version 1.4 *
131 * 23-Mar-89 : changes for version 1.5 : *
132 * - reworked M==1 code *
133 * - defined NAUTYVERSION string *
134 * - made NAUTYH_READ to allow this file to be read twice *
135 * - added optional ANSI function prototypes *
136 * - added validity check for WORDSIZE *
137 * - added new fields to optionblk structure *
138 * - updated DEFAULTOPTIONS to add invariants fields *
139 * - added (set*) cast to definition of GRAPHROW *
140 * - added definition of ALLOCS and FREES *
141 * 25-Mar-89 : - added declaration of new function doref() *
142 * - added UNION macro *
143 * 29-Mar-89 : - reduced the default MAXN for small machines *
144 * - removed OUTOFSPACE (no longer used) *
145 * - added SETDIFF and XOR macros *
146 * 2-Apr-89 : - extended statsblk structure *
147 * 4-Apr-89 : - added IS_* macros *
148 * - added ERRFILE definition *
149 * - replaced statsblk.outofspace by statsblk.errstatus *
150 * 5-Apr-89 : - deleted definition of np2vector (no longer used) *
151 * - introduced EMPTYSET macro *
152 * 12-Apr-89 : - eliminated MARK, UNMARK and ISMARKED (no longer used) *
153 * 18-Apr-89 : - added MTOOBIG and CANONGNIL *
154 * 12-May-89 : - made ISELEM1 and ISELEMENT return 0 or 1 *
155 * 2-Mar-90 : - added EXTPROC macro and used it *
156 * 12-Mar-90 : - added SYS_CRAY, with help from N. Sloane and A. Grosky *
157 * - added dummy groupopts field to optionblk *
158 * - select some ANSI things if __STDC__ exists *
159 * 20-Mar-90 : - changed default MAXN for Macintosh versions *
160 * - created SYS_MACTHINK for Macintosh THINK compiler *
161 * 27-Mar-90 : - split SYS_MSDOS into SYS_PCMS4 and SYS_PCMS5 *
162 * 13-Oct-90 : changes for version 1.6: *
163 * - fix definition of setword for WORDSIZE==64 *
164 * 14-Oct-90 : - added SYS_APOLLO version to avoid compiler bug *
165 * 15-Oct-90 : - improve detection of ANSI conformance *
166 * 17-Oct-90 : - changed temp name in EMPTYSET to avoid A/UX bug *
167 * 16-Apr-91 : changes for version 1.7: *
168 * - made version SYS_PCTURBO use free(), not cfree() *
169 * 2-Sep-91 : - noted that SYS_PCMS5 also works for Quick C *
170 * - moved MULTIPLY to here from nauty.c *
171 * 12-Jun-92 : - changed the top part of this comment *
172 * 27-Aug-92 : - added version SYS_IBMC, thanks to Ivo Duentsch *
173 * 5-Jun-93 : - renamed to version 1.7+, only change in naututil.h *
174 * 29-Jul-93 : changes for version 1.8: *
175 * - fixed error in default 64-bit version of FIRSTBIT *
176 * (not used in any version before ALPHA) *
177 * - installed ALPHA version (thanks to Gordon Royle) *
178 * - defined ALLOCS,FREES for SYS_IBMC *
179 * 3-Sep-93 : - make calloc void* in ALPHA version *
180 * 17-Sep-93 : - renamed to version 1.9, *
181 * changed only dreadnaut.c and nautinv.c *
182 * 24-Feb-94 : changes for version 1.10: *
183 * - added version SYS_AMIGAAZT, thanks to Carsten Saager *
184 * (making 1.9+) *
185 * 19-Apr-95 : - added prototype wrapper for C++, *
186 * thanks to Daniel Huson *
187 * 5-Mar-96 : - added SYS_ALPHA32 version (32-bit setwords on Alpha) *
188 * 13-Jul-96 : changes for version 2.0: *
189 * - added dynamic allocation *
190 * - ERRFILE must be defined *
191 * - added FLIPELEM1 and FLIPELEMENT macros *
192 * 13-Aug-96 : - added SWCHUNK? macros *
193 * - added TAKEBIT macro *
194 * 28-Nov-96 : - include sys/types.h if not ANSI (tentative!) *
195 * 24-Jan-97 : - and stdlib.h if ANSI *
196 * - removed use of cfree() from UNIX variants *
197 * 25-Jan-97 : - changed options.getcanon from boolean to int *
198 * Backwards compatibility is ok, as boolean and int *
199 * are the same. Now getcanon=2 means to get the label *
200 * and not care about the group. Sometimes faster. *
201 * 6-Feb-97 : - Put in #undef for FALSE and TRUE to cope with *
202 * compilers that illegally predefine them. *
203 * - declared nauty_null and nautil_null *
204 * 2-Jul-98 : - declared ALLBITS *
205 * 21-Oct-98 : - allow WORDSIZE==64 using unsigned long long *
206 * - added BIGNAUTY option for really big graphs *
207 * 11-Dec-99 : - made bit, leftbit and bytecount static in each file *
208 * 9-Jan-00 : - declared nauty_check() and nautil_check() *
209 * 12-Feb-00 : - Used #error for compile-time checks *
210 * - Added DYNREALLOC *
211 * 4-Mar-00 : - declared ALLMASK(n) *
212 * 27-May-00 : - declared CONDYNFREE *
213 * 28-May-00 : - declared nautil_freedyn() *
214 * 16-Aug-00 : - added OLDNAUTY and changed canonical labelling *
215 * 16-Nov-00 : - function prototypes are now default and unavoidable *
216 * - removed UPROC, now assume all compilers know void *
217 * - removed nvector, now just int (as it always was) *
218 * - added extra parameter to targetcell() *
219 * - removed old versions which were only to skip around *
220 * bugs that should have been long fixed: *
221 * SYS_APOLLO and SYS_VAXBSD. *
222 * - DEFAULTOPIONS now specifies no output *
223 * - Removed obsolete SYS_MACLSC version *
224 * 21-Apr-01 : - Added code to satisfy compilation into Magma. This *
225 * is activated by defining NAUTY_IN_MAGMA above. *
226 * - The *_null routines no longer exist *
227 * - Default maxinvarlevel is now 1. (This has no effect *
228 * unless an invariant is specified.) *
229 * - Now labelorg has a concrete declaration in nautil.c *
230 * and EXTDEFS is not needed *
231 * 5-May-01 : - NILFUNCTION, NILSET, NILGRAPH now obsolete. Use NULL. *
232 * 11-Sep-01 : - setword is unsigned int in the event that UINT_MAX *
233 * is defined and indicates it is big enough *
234 * 17-Oct-01 : - major rewrite for 2.1. SYS_* variables gone! *
235 * Some modernity assumed, eg size_t *
236 * 8-Aug-02 : - removed MAKEEMPTY (use EMPTYSET instead) *
237 * - deleted OLDNAUTY everywhere *
238 * 27-Aug-02 : - converted to use autoconf. Now the original of this *
239 * file is nauty-h.in. Run configure to make nauty.h. *
240 * 20-Dec-02 : - increased INFINITY *
241 * some reorganization to please Magma *
242 * - declared nauty_freedyn() *
243 * 17-Nov-03 : - renamed INFINITY to NAUTY_INFINITY *
244 * 29-May-04 : - added definition of SETWORD_FORMAT *
245 * 14-Sep-04 : - extended prototypes even to recursive functions *
246 * 16-Oct-04 : - added DEFAULTOPTIONS_GRAPH *
247 * 24-Oct-04 : Starting 2.3 *
248 * - remove register declarations as modern compilers *
249 * tend to find them a nuisance *
250 * - Don't define the obsolete symbol INFINITY if it is *
251 * defined already *
252 * 17-Nov-04 : - make 6 counters in statsblk unsigned long *
253 * 17-Jan-04 : - add init() and cleanup() to dispatchvec *
254 * 12-Nov-05 : - Changed NAUTY_INFINITY to 2^30+2 in BIGNAUTY case *
255 * 22-Nov-06 : Starting 2.4 *
256 * - removed usertcellproc from options *
257 * changed bestcell to targetcell in dispatch vector *
258 * declare targetcell and maketargetcell *
259 * 29-Nov-06 : - add extraoptions to optionblk *
260 * - add declarations of extra_autom and extra_level *
261 * 10-Dec-06 : - BIGNAUTY is gone! Now permutation=shortish=int. *
262 * NAUTY_INFINITY only depends on whether sizeof(int)=2. *
263 * 27-Jun-08 : - define nauty_counter and LONG_LONG_COUNTERS *
264 * 30-Jun-08 : - declare version 2.4 *
265 * 8-Nov-09 : - final release of version 2.4; *
266 * 10-Nov-10 : Starting 2.5 *
267 * - declare shortish and permutation obsolete, now int *
268 * 14-Nov-10 : - SETWORDSNEEDED(n) *
269 * 23-May-10 : - declare densenauty() *
270 * 29-Jun-10 : - add PRINT_COUNTER(f,x) *
271 * - add DEFAULTOPTIONS_DIGRAPH() *
272 * 27-Mar-11 : - declare writegroupsize() *
273 * 14-Jan-12 : - add HAVE_TLS and TLS_ATTR *
274 * 21-Feb-12 : - add ENABLE_ANSI *
275 * 18-Mar-12 : - add COUNTER_FMT *
276 * 18-Aug-12 : - add ADDONEARC, ADDONEEDGE, EMPTYGRAPH *
277 * 29-Aug-12 : - add CLZ macros and FIRSTBITNZ *
278 * 19-Oct-12 : - add DEFAULT_WORDSIZE *
279 * 3-Jan-12 : Released 2.5rc1 *
280 * 18-Jan-12 : Froze 2.5 *
281 * 18-Jan-12 : - add NAUABORTED and NAUKILLED *
282 * - add nauty_kill_request *
283 * - add usercanonproc *
284 * 1-Oct-15 : - add COUNTER_FMT_RAW *
285 * 10-Jan-16 : - defined POPCOUNTMAC, optionally use popcnt *
286 * - remove SYS_CRAY, let's hope it is long obsolete *
287 * - add Intel popcount intrinsics for icc *
288 * 12-Jan-16 : - DYNFREE and CONDYNFREE now set the pointer to NULL *
289 * 16-Jan-16 : - Change NAUTY_INFINITY to 2 billion + 2 *
290 * 12-Mar-16 : - Add const to alloc_error() *
291 * : Froze 2.6 *
292 * 29-Aug-16 : - Add SWHIBIT, REMOVEHIBIT and ATMOSTONEBIT *
293 * 10-Mar-18 : - Add SETWORD_DEC_FORMAT for decimal output *
294 * - Fix 64-bit SETWORD_FORMAT to use 0 padding. *
295 * 28-Feb-19 : - Use intrinsics for WORDSIZE=16 *
296 * - Macro versions of FIRSTBIT and FIRSTBITNZ are always *
297 * available as FIRSTBITMAC and FIRSTBITNZMAC *
298 * 1-Mar-19 : - Add AVOID* tests for non-POSIX header files *
299 * 31-Aug-19 : - Revise type size determinations to be more robust if *
300 * configuration wasn't done. *
301 * - HAVE_HWLZCNT and HAV_HWPOPCNT can be defined at *
302 * compile time *
303 * - FIRSTBITNZ, FIRSTBIT and POPCOUNT can be defined at *
304 * compile time *
305 * 11-Oct-19 : - Move labelorg and nauty_kill_request into the *
306 * "C" block for C++ compatibiliy *
307 * 23-Mar-20 : - Don't define INFINITY even if it is absent from math.h *
308 * 17-Nov-21 : - Use USE_TLS for thread-local storage *
309 - Define FLEX_ARRAY_OK *
310 : Froze 2.7
311 * ++++++ This file is automatically generated, don't edit it by hand! ++++++
312 * *
313 *****************************************************************************/
314
315 /*****************************************************************************
316 * *
317 * 16-bit, 32-bit and 64-bit versions can be selected by defining WORDSIZE. *
318 * The largest graph that can be handled has MAXN vertices. *
319 * Both WORDSIZE and MAXN can be defined on the command line. *
320 * WORDSIZE must be 16, 32 or 64; MAXN must be <= NAUTY_INFINITY-2; *
321 * *
322 * With a very slight loss of efficiency (depending on platform), nauty *
323 * can be compiled to dynamically allocate arrays. Predefine MAXN=0 to *
324 * achieve this effect, which is default behaviour from version 2.0. *
325 * In that case, graphs of size up to NAUTY_INFINITY-2 can be handled *
326 * if the memory is available. *
327 * *
328 * If only very small graphs need to be processed, use MAXN<=WORDSIZE *
329 * since this causes substantial code optimizations. *
330 * *
331 * Conventions and Assumptions: *
332 * *
333 * A 'setword' is the chunk of memory that is occupied by one part of *
334 * a set. This is assumed to be >= WORDSIZE bits in size. *
335 * *
336 * The rightmost (loworder) WORDSIZE bits of setwords are numbered *
337 * 0..WORDSIZE-1, left to right. It is necessary that the 2^WORDSIZE *
338 * setwords with the other bits zero are totally ordered under <,=,>. *
339 * This needs care on a 1's-complement machine. *
340 * *
341 * The int variables m and n have consistent meanings throughout. *
342 * Graphs have n vertices always, and sets have m setwords always. *
343 * *
344 * A 'set' consists of m contiguous setwords, whose bits are numbered *
345 * 0,1,2,... from left (high-order) to right (low-order), using only *
346 * the rightmost WORDSIZE bits of each setword. It is used to *
347 * represent a subset of {0,1,...,n-1} in the usual way - bit number x *
348 * is 1 iff x is in the subset. Bits numbered n or greater, and *
349 * unnumbered bits, are assumed permanently zero. *
350 * *
351 * A 'graph' consists of n contiguous sets. The i-th set represents *
352 * the vertices adjacent to vertex i, for i = 0,1,...,n-1. *
353 * *
354 * A 'permutation' is an array of n ints repesenting a permutation of *
355 * the set {0,1,...,n-1}. The value of the i-th entry is the number to *
356 * which i is mapped. *
357 * *
358 * If g is a graph and p is a permutation, then g^p is the graph in *
359 * which vertex i is adjacent to vertex j iff vertex p[i] is adjacent *
360 * to vertex p[j] in g. *
361 * *
362 * A partition nest is represented by a pair (lab,ptn), where lab and ptn *
363 * are int arrays. The "partition at level x" is the partition whose *
364 * cells are {lab[i],lab[i+1],...,lab[j]}, where [i,j] is a maximal *
365 * subinterval of [0,n-1] such that ptn[k] > x for i <= k < j and *
366 * ptn[j] <= x. The partition at level 0 is given to nauty by the user. *
367 * This is refined for the root of the tree, which has level 1. *
368 * *
369 *****************************************************************************/
370
371 #ifndef NAUTY_IN_MAGMA
372 #if HAVE_SYSTYPES_H && !defined(AVOID_SYS_TYPES_H)
373 #include <sys/types.h>
374 #endif
375 #if HAVE_UNISTD_H && !defined(AVOID_UNISTD_H)
376 #include <unistd.h>
377 #endif
378 #if HAVE_STDDEF_H
379 #include <stddef.h>
380 #endif
381 #if HAVE_STDLIB_H
382 #include <stdlib.h>
383 #endif
384 #if HAVE_LIMITS_H
385 #include <limits.h>
386 #endif
387 #if HAVE_STDINT_H
388 #include <stdint.h>
389 #endif
390 #if HAVE_STRING_H
391 #include <string.h>
392 #elif !defined(AVOID_STRINGS_H)
393 #include <strings.h>
394 #endif
395 #endif
396
397 /* Now we determine some sizes, relying on limits.h and
398 stdint.h first in case configuration was not done.
399 None of these tests are perfect, but sizeof() is not
400 allowed in preprocessor tests. The program nautest.c
401 will check these. */
402
403 #if defined(INT_MAX)
404 #if INT_MAX == 65535
405 #define SIZEOF_INT 2
406 #else
407 #define SIZEOF_INT 4
408 #endif
409 #else
410 #define SIZEOF_INT 4
411 #endif
412
413 #if defined(LONG_MAX)
414 #if LONG_MAX == 2147483647L
415 #define SIZEOF_LONG 4
416 #else
417 #define SIZEOF_LONG 8
418 #endif
419 #else
420 #define SIZEOF_LONG 8
421 #endif
422
423 #if defined(LLONG_MAX)
424 #define SIZEOF_LONG_LONG 8
425 #else
426 #define SIZEOF_LONG 8 /* 0 if nonexistent */
427 #endif
428
429 #if defined(_MSC_VER)
430 #define SIZEOF_INT128_T 0
431 #define SIZEOF_INT128 0
432 #else
433 #define SIZEOF_INT128_T 16 /* 0 if nonexistent */
434 #define SIZEOF_INT128 16 /* 0 if nonexistent */
435 #endif
436
437 #if defined(_WIN64)
438 #define SIZEOF_POINTER 8
439 #elif defined(_WIN32)
440 #define SIZEOF_POINTER 4
441 #elif defined(UINTPTR_MAX) && UINTPTRMAX == 4294967295UL
442 #define SIZEOF_POINTER 4
443 #else
444 #define SIZEOF_POINTER 8
445 #endif
446
447 /* WORDSIZE is the number of set elements per setword (16, 32 or 64).
448 WORDSIZE and setword are defined as follows:
449
450 DEFAULT_WORDSIZE is usually 0 but is set by the configure script
451 to NN if --enable-wordsize=NN is used, where NN is 16, 32 or 64.
452
453 If WORDSIZE is not defined, but DEFAULT_WORDSIZE > 0, then set
454 WORDSIZE to the same value as DEFAULT_WORDSIZE.
455 If WORDSIZE is so far undefined, use 32 unless longs have more
456 than 32 bits, in which case use 64.
457 Define setword thus:
458 WORDSIZE==16 : unsigned short
459 WORDSIZE==32 : unsigned int unless it is too small,
460 in which case unsigned long
461 WORDSIZE==64 : the first of unsigned int, unsigned long,
462 unsigned long long which is large enough.
463 */
464
465 #ifdef NAUTY_IN_MAGMA
466 #undef WORDSIZE
467 #define WORDSIZE WORDBITS
468 #endif
469
470 #ifndef WORDSIZE
471 #if DEFAULT_WORDSIZE > 0
472 #define WORDSIZE DEFAULT_WORDSIZE
473 #endif
474 #endif
475
476 #ifdef WORDSIZE
477
478 #if (WORDSIZE != 16) && (WORDSIZE != 32) && (WORDSIZE != 64)
479 #error "WORDSIZE must be 16, 32 or 64"
480 #endif
481
482 #else /* WORDSIZE undefined */
483
484 #if SIZEOF_LONG>4
485 #define WORDSIZE 64
486 #else
487 #define WORDSIZE 32
488 #endif
489
490 #endif /* WORDSIZE */
491
492 #ifdef NAUTY_IN_MAGMA
493 typedef t_uint setword;
494 #define SETWORD_INT /* Don't assume this is correct in Magma. */
495
496 #else /* NAUTY_IN_MAGMA */
497
498 #if WORDSIZE==16
499 typedef unsigned short setword;
500 #define SETWORD_SHORT
501 #endif
502
503 #if WORDSIZE==32
504 #if SIZEOF_INT>=4
505 typedef unsigned int setword;
506 #define SETWORD_INT
507 #else
508 typedef unsigned long setword;
509 #define SETWORD_LONG
510 #endif
511 #endif
512
513 #if WORDSIZE==64
514 #if SIZEOF_INT>=8
515 typedef unsigned int setword;
516 #define SETWORD_INT
517 #else
518 #if SIZEOF_LONG>=8
519 typedef unsigned long setword;
520 #define SETWORD_LONG
521 #else
522 typedef unsigned long long setword;
523 #define SETWORD_LONGLONG
524 #endif
525 #endif
526 #endif
527
528 #endif /* NAUTY_IN_MAGMA else */
529
530 #if SIZEOF_LONG_LONG>=8 && SIZEOF_LONG==4
531 typedef unsigned long long nauty_counter;
532 #define LONG_LONG_COUNTERS 1
533 #define COUNTER_FMT "%llu"
534 #define COUNTER_FMT_RAW "llu"
535 #else
536 typedef unsigned long nauty_counter;
537 #define LONG_LONG_COUNTERS 0
538 #define COUNTER_FMT "%lu"
539 #define COUNTER_FMT_RAW "lu"
540 #endif
541 #define PRINT_COUNTER(f,x) fprintf(f,COUNTER_FMT,x)
542
543 #define NAUTYVERSIONID (27000+HAVE_TLS) /* 10000*version + HAVE_TLS */
544 #define NAUTYREQUIRED NAUTYVERSIONID /* Minimum compatible version */
545
546 #if WORDSIZE==16
547 #define NAUTYVERSION "2.7 (16 bits)"
548 #endif
549 #if WORDSIZE==32
550 #define NAUTYVERSION "2.7 (32 bits)"
551 #endif
552 #if WORDSIZE==64
553 #define NAUTYVERSION "2.7 (64 bits)"
554 #endif
555
556 #ifndef MAXN /* maximum allowed n value; use 0 for dynamic sizing. */
557 #define MAXN 0
558 #define MAXM 0
559 #else
560 #define MAXM ((MAXN+WORDSIZE-1)/WORDSIZE) /* max setwords in a set */
561 #endif /* MAXN */
562
563 /* Starting at version 2.2, set operations work for all set sizes unless
564 ONE_WORD_SETS is defined. In the latter case, if MAXM=1, set ops
565 work only for single-setword sets. In any case, macro versions
566 ending with 1 work for single-setword sets and versions ending with
567 0 work for all set sizes.
568 */
569
570 #if WORDSIZE==16
571 #define SETWD(pos) ((pos)>>4) /* number of setword containing bit pos */
572 #define SETBT(pos) ((pos)&0xF) /* position within setword of bit pos */
573 #define TIMESWORDSIZE(w) ((w)<<4)
574 #define SETWORDSNEEDED(n) ((((n)-1)>>4)+1) /* setwords needed for n bits */
575 #endif
576
577 #if WORDSIZE==32
578 #define SETWD(pos) ((pos)>>5)
579 #define SETBT(pos) ((pos)&0x1F)
580 #define TIMESWORDSIZE(w) ((w)<<5)
581 #define SETWORDSNEEDED(n) ((((n)-1)>>5)+1)
582 #endif
583
584 #if WORDSIZE==64
585 #define SETWD(pos) ((pos)>>6)
586 #define SETBT(pos) ((pos)&0x3F)
587 #define TIMESWORDSIZE(w) ((w)<<6) /* w*WORDSIZE */
588 #define SETWORDSNEEDED(n) ((((n)-1)>>6)+1)
589 #endif
590
591 #ifdef NAUTY_IN_MAGMA
592 #define BITT bs_bit
593 #else
594 #define BITT bit
595 #endif
596
597 #define ADDELEMENT1(setadd,pos) (*(setadd) |= BITT[pos])
598 #define DELELEMENT1(setadd,pos) (*(setadd) &= ~BITT[pos])
599 #define FLIPELEMENT1(setadd,pos) (*(setadd) ^= BITT[pos])
600 #define ISELEMENT1(setadd,pos) ((*(setadd) & BITT[pos]) != 0)
601 #define EMPTYSET1(setadd,m) *(setadd) = 0;
602 #define GRAPHROW1(g,v,m) ((set*)(g)+(v))
603 #define ADDONEARC1(g,v,w,m) (g)[v] |= BITT[w]
604 #define ADDONEEDGE1(g,v,w,m) { ADDONEARC1(g,v,w,m); ADDONEARC1(g,w,v,m); }
605 #define EMPTYGRAPH1(g,m,n) EMPTYSET0(g,n) /* really EMPTYSET0 */
606
607 #define ADDELEMENT0(setadd,pos) ((setadd)[SETWD(pos)] |= BITT[SETBT(pos)])
608 #define DELELEMENT0(setadd,pos) ((setadd)[SETWD(pos)] &= ~BITT[SETBT(pos)])
609 #define FLIPELEMENT0(setadd,pos) ((setadd)[SETWD(pos)] ^= BITT[SETBT(pos)])
610 #define ISELEMENT0(setadd,pos) (((setadd)[SETWD(pos)] & BITT[SETBT(pos)]) != 0)
611 #define EMPTYSET0(setadd,m) \
612 {setword *es; \
613 for (es = (setword*)(setadd)+(m); --es >= (setword*)(setadd);) *es=0;}
614 #define GRAPHROW0(g,v,m) ((set*)(g) + (m)*(size_t)(v))
615 #define ADDONEARC0(g,v,w,m) ADDELEMENT0(GRAPHROW0(g,v,m),w)
616 #define ADDONEEDGE0(g,v,w,m) { ADDONEARC0(g,v,w,m); ADDONEARC0(g,w,v,m); }
617 #define EMPTYGRAPH0(g,m,n) EMPTYSET0(g,(m)*(size_t)(n))
618
619 #if (MAXM==1) && defined(ONE_WORD_SETS)
620 #define ADDELEMENT ADDELEMENT1
621 #define DELELEMENT DELELEMENT1
622 #define FLIPELEMENT FLIPELEMENT1
623 #define ISELEMENT ISELEMENT1
624 #define EMPTYSET EMPTYSET1
625 #define GRAPHROW GRAPHROW1
626 #define ADDONEARC ADDONEARC1
627 #define ADDONEEDGE ADDONEEDGE1
628 #define EMPTYGRAPH EMPTYGRAPH1
629 #else
630 #define ADDELEMENT ADDELEMENT0
631 #define DELELEMENT DELELEMENT0
632 #define FLIPELEMENT FLIPELEMENT0
633 #define ISELEMENT ISELEMENT0
634 #define EMPTYSET EMPTYSET0
635 #define GRAPHROW GRAPHROW0
636 #define ADDONEARC ADDONEARC0
637 #define ADDONEEDGE ADDONEEDGE0
638 #define EMPTYGRAPH EMPTYGRAPH0
639 #endif
640
641
642 #ifdef NAUTY_IN_MAGMA
643 #undef EMPTYSET
644 #define EMPTYSET(setadd,m) {t_int _i; bsp_makeempty(setadd,m,_i);}
645 #endif
646
647 #define NOTSUBSET(word1,word2) ((word1) & ~(word2)) /* test if the 1-bits
648 in setword word1 do not form a subset of those in word2 */
649 #define INTERSECT(word1,word2) ((word1) &= (word2)) /* AND word2 into word1 */
650 #define UNION(word1,word2) ((word1) |= (word2)) /* OR word2 into word1 */
651 #define SETDIFF(word1,word2) ((word1) &= ~(word2)) /* - word2 into word1 */
652 #define XOR(word1,word2) ((word1) ^= (word2)) /* XOR word2 into word1 */
653 #define ZAPBIT(word,x) ((word) &= ~BITT[x]) /* delete bit x in setword */
654 #define TAKEBIT(iw,w) {(iw) = FIRSTBITNZ(w); (w) ^= BITT[iw];}
655
656 #define SWHIBIT(w) ((w)&(-(w))) /* Lower order bit of unsigned type */
657 #define REMOVEHIBIT(bit,w) {(bit) = SWHIBIT(w); (w) ^= (bit);}
658 #define ATMOSTONEBIT(w) (((w)&(-(w)))==(w)) /* True if |w| <= 1 */
659
660 #ifdef SETWORD_LONGLONG
661 #define MSK3232 0xFFFFFFFF00000000ULL
662 #define MSK1648 0xFFFF000000000000ULL
663 #define MSK0856 0xFF00000000000000ULL
664 #define MSK1632 0x0000FFFF00000000ULL
665 #define MSK0840 0xFF0000000000ULL
666 #define MSK1616 0xFFFF0000ULL
667 #define MSK0824 0xFF000000ULL
668 #define MSK0808 0xFF00ULL
669 #define MSK63C 0x7FFFFFFFFFFFFFFFULL
670 #define MSK31C 0x7FFFFFFFULL
671 #define MSK15C 0x7FFFULL
672 #define MSK64 0xFFFFFFFFFFFFFFFFULL
673 #define MSK32 0xFFFFFFFFULL
674 #define MSK16 0xFFFFULL
675 #define MSK8 0xFFULL
676 #endif
677
678 #ifdef SETWORD_LONG
679 #define MSK3232 0xFFFFFFFF00000000UL
680 #define MSK1648 0xFFFF000000000000UL
681 #define MSK0856 0xFF00000000000000UL
682 #define MSK1632 0x0000FFFF00000000UL
683 #define MSK0840 0xFF0000000000UL
684 #define MSK1616 0xFFFF0000UL
685 #define MSK0824 0xFF000000UL
686 #define MSK0808 0xFF00UL
687 #define MSK63C 0x7FFFFFFFFFFFFFFFUL
688 #define MSK31C 0x7FFFFFFFUL
689 #define MSK15C 0x7FFFUL
690 #define MSK64 0xFFFFFFFFFFFFFFFFUL
691 #define MSK32 0xFFFFFFFFUL
692 #define MSK16 0xFFFFUL
693 #define MSK8 0xFFUL
694 #endif
695
696 #if defined(SETWORD_INT) || defined(SETWORD_SHORT)
697 #define MSK3232 0xFFFFFFFF00000000U
698 #define MSK1648 0xFFFF000000000000U
699 #define MSK0856 0xFF00000000000000U
700 #define MSK1632 0x0000FFFF00000000U
701 #define MSK0840 0xFF0000000000U
702 #define MSK1616 0xFFFF0000U
703 #define MSK0824 0xFF000000U
704 #define MSK0808 0xFF00U
705 #define MSK63C 0x7FFFFFFFFFFFFFFFU
706 #define MSK31C 0x7FFFFFFFU
707 #define MSK15C 0x7FFFU
708 #define MSK64 0xFFFFFFFFFFFFFFFFU
709 #define MSK32 0xFFFFFFFFU
710 #define MSK16 0xFFFFU
711 #define MSK8 0xFFU
712 #endif
713
714 #if defined(SETWORD_LONGLONG)
715 #define SETWORD_DEC_FORMAT "%llu"
716 #if WORDSIZE==16
717 #define SETWORD_FORMAT "%04llx"
718 #endif
719 #if WORDSIZE==32
720 #define SETWORD_FORMAT "%08llx"
721 #endif
722 #if WORDSIZE==64
723 #define SETWORD_FORMAT "%016llx"
724 #endif
725 #endif
726
727 #if defined(SETWORD_LONG)
728 #define SETWORD_DEC_FORMAT "%lu"
729 #if WORDSIZE==16
730 #define SETWORD_FORMAT "%04lx"
731 #endif
732 #if WORDSIZE==32
733 #define SETWORD_FORMAT "%08lx"
734 #endif
735 #if WORDSIZE==64
736 #define SETWORD_FORMAT "%016lx"
737 #endif
738 #endif
739
740 #if defined(SETWORD_INT)
741 #define SETWORD_DEC_FORMAT "%u"
742 #if WORDSIZE==16
743 #define SETWORD_FORMAT "%04x"
744 #endif
745 #if WORDSIZE==32
746 #define SETWORD_FORMAT "%08x"
747 #endif
748 #if WORDSIZE==64
749 #define SETWORD_FORMAT "%016x"
750 #endif
751 #endif
752
753 #if defined(SETWORD_SHORT)
754 #define SETWORD_DEC_FORMAT "%hu"
755 #if WORDSIZE==16
756 #define SETWORD_FORMAT "%04hx"
757 #endif
758 #if WORDSIZE==32
759 #define SETWORD_FORMAT "%08hx"
760 #endif
761 #if WORDSIZE==64
762 #define SETWORD_FORMAT "%016hx"
763 #endif
764 #endif
765
766 /* POPCOUNT(x) = number of 1-bits in a setword x
767 POPCOUNTMAC(x) = Macro version of POPCOUNT
768 FIRSTBIT(x) = number of first 1-bit in non-zero setword (0..WORDSIZE-1)
769 or WORDSIZE if x == 0
770 FIRSTBITNZ(x) = as FIRSTBIT(x) but assumes x is not zero
771 BITMASK(x) = setword whose rightmost WORDSIZE-x-1 (numbered) bits
772 are 1 and the rest 0 (0 <= x < WORDSIZE)
773 (I.e., bits 0..x are unselected and the rest selected.)
774 ALLBITS = all (numbered) bits in a setword */
775
776 #if WORDSIZE==64
777 #define POPCOUNTMAC(x) (bytecount[(x)>>56 & 0xFF] + bytecount[(x)>>48 & 0xFF] \
778 + bytecount[(x)>>40 & 0xFF] + bytecount[(x)>>32 & 0xFF] \
779 + bytecount[(x)>>24 & 0xFF] + bytecount[(x)>>16 & 0xFF] \
780 + bytecount[(x)>>8 & 0xFF] + bytecount[(x) & 0xFF])
781 #define FIRSTBITMAC(x) ((x) & MSK3232 ? \
782 (x) & MSK1648 ? \
783 (x) & MSK0856 ? \
784 0+leftbit[((x)>>56) & MSK8] : \
785 8+leftbit[(x)>>48] \
786 : (x) & MSK0840 ? \
787 16+leftbit[(x)>>40] : \
788 24+leftbit[(x)>>32] \
789 : (x) & MSK1616 ? \
790 (x) & MSK0824 ? \
791 32+leftbit[(x)>>24] : \
792 40+leftbit[(x)>>16] \
793 : (x) & MSK0808 ? \
794 48+leftbit[(x)>>8] : \
795 56+leftbit[x])
796 #define BITMASK(x) (MSK63C >> (x))
797 #define ALLBITS MSK64
798 #define SWCHUNK0(w) ((long)((w)>>48)&0xFFFFL)
799 #define SWCHUNK1(w) ((long)((w)>>32)&0xFFFFL)
800 #define SWCHUNK2(w) ((long)((w)>>16)&0xFFFFL)
801 #define SWCHUNK3(w) ((long)(w)&0xFFFFL)
802 #endif
803
804 #if WORDSIZE==32
805 #define POPCOUNTMAC(x) (bytecount[(x)>>24 & 0xFF] + bytecount[(x)>>16 & 0xFF] \
806 + bytecount[(x)>>8 & 0xFF] + bytecount[(x) & 0xFF])
807 #define FIRSTBITMAC(x) ((x) & MSK1616 ? ((x) & MSK0824 ? \
808 leftbit[((x)>>24) & MSK8] : 8+leftbit[(x)>>16]) \
809 : ((x) & MSK0808 ? 16+leftbit[(x)>>8] : 24+leftbit[x]))
810 #define BITMASK(x) (MSK31C >> (x))
811 #define ALLBITS MSK32
812 #define SWCHUNK0(w) ((long)((w)>>16)&0xFFFFL)
813 #define SWCHUNK1(w) ((long)(w)&0xFFFFL)
814 #endif
815
816 #if WORDSIZE==16
817 #define POPCOUNTMAC(x) (bytecount[(x)>>8 & 0xFF] + bytecount[(x) & 0xFF])
818 #define FIRSTBITMAC(x) ((x) & MSK0808 ? leftbit[((x)>>8) & MSK8] : 8+leftbit[x])
819 #define BITMASK(x) ((setword)(MSK15C >> (x)))
820 #define ALLBITS ((setword)MSK16)
821 #define SWCHUNK0(w) ((long)(w)&0xFFFFL)
822 #endif
823
824 #define FIRSTBITNZMAC FIRSTBITMAC
825
826 /* Use clz instructions if available */
827
828 #ifndef FIRSTBITNZ /* Can be defined outside */
829
830 #ifdef NAUTY_IN_MAGMA
831 #define FIRSTBITNZ(x) bs_firstbit(x)
832
833 #elif defined(_MSC_VER)
834 #if _MSC_VER >= 1800
835 #include <intrin.h>
836 #else
837 #include <x86intrin.h>
838 #endif
839
840 #if HAVE_HWLZCNT
841
842 #if WORDSIZE==64 && defined(_WIN64)
843 #define FIRSTBITNZ(x) (int)_lzcnt_u64(x)
844 #elif WORDSIZE==32
845 #define FIRSTBITNZ(x) (int)_lzcnt_u32(x)
846 #else
847 #define FIRSTBITNZ(x) (int)_lzcnt16(x)
848 #endif
849
850 #else /* not HAVE_HWLZCNT */
851
852 #if WORDSIZE==64 && defined(_WIN64)
msc_bsr_64(setword x)853 static int msc_bsr_64(setword x) \
854 { unsigned long *p; \
855 _BitScanReverse64(&p,x); return 63 - *p; }
856 #define FIRSTBITNZ(x) (msc_bsr_64(x))
857 #elif WORDSIZE==32
858 #pragma intrinsic(_BitScanReverse)
msc_bsr_32(setword x)859 static int msc_bsr_32(setword x) \
860 { unsigned *p; \
861 _BitScanReverse(&p,x); return 31 - *p; }
862 #define FIRSTBITNZ(x) (msc_bsr_32(x))
863 #elif WORDSIZE==16
864 #pragma intrinsic(_BitScanReverse)
msc_bsr_16(setword x)865 static int msc_bsr_16(setword x) \
866 { unsigned long *p; \
867 _BitScanReverse(&p,(unsigned long)x); return 15 - *p; }
868 #define FIRSTBITNZ(x) (msc_bsr_16(x))
869 #endif /* WORDSIZE choice */
870
871 #endif /* HAVE_HWLZCNT choice */
872
873 #else /* Not MAGMA or WIN */
874
875 #if HAVE_HWLZCNT
876 #if defined(SETWORD_LONGLONG) && HAVE_CLZLL
877 #define FIRSTBITNZ(x) __builtin_clzll(x)
878 #elif defined(SETWORD_LONG) && HAVE_CLZL
879 #define FIRSTBITNZ(x) __builtin_clzl(x)
880 #elif defined(SETWORD_INT) && HAVE_CLZ
881 #define FIRSTBITNZ(x) __builtin_clz(x)
882 #elif defined(SETWORD_SHORT) && HAVE_CLZ
883 #define FIRSTBITNZ(x) (__builtin_clz((unsigned int)(x)) - 16)
884 #endif /* size choice */
885 #endif /* HAVE_HWLZCNT */
886
887 #endif /* MAGMA-WIN-OTHER choice */
888
889 #endif /* ifndef FIRSTBITNZ */
890
891 /* Now fall back on macros for things not defined */
892 #if defined(FIRSTBITNZ) && !defined(FIRSTBIT)
893 #define FIRSTBIT(x) ((x) ? FIRSTBITNZ(x) : WORDSIZE)
894 #else
895 #ifndef FIRSTBITNZ
896 #define FIRSTBITNZ FIRSTBITNZMAC
897 #endif
898 #ifndef FIRSTBIT
899 #define FIRSTBIT FIRSTBITMAC
900 #endif
901 #endif
902
903 /* Use popcount instructions if available */
904
905 #ifndef POPCOUNT /* Can be defined outside */
906
907 #ifdef NAUTY_IN_MAGMA
908 #undef BITMASK
909 #define POPCOUNT(x) bs_popcount(x)
910 #define BITMASK(x) bs_bitmask(x)
911
912 #elif defined(_MSC_VER)
913 #if _MSC_VER >= 1800
914 #include <intrin.h>
915 #else
916 #include <x86intrin.h>
917 #endif
918 #if WORDSIZE==64
919 #pragma instrinsic(_mm_popcnt_u64)
920 #define POPCOUNT(x) ((int)_mm_popcnt_u64(x))
921 #elif WORDSIZE==32
922 #pragma instrinsic(_mm_popcnt_u32)
923 #define POPCOUNT(x) _mm_popcnt_u32(x)
924 #elif WORDSIZE==16
925 #pragma instrinsic(_mm_popcnt_u32)
926 #define POPCOUNT(x) _mm_popcnt_u32((unsigned int)(x))
927 #endif
928
929 #elif defined(__INTEL_COMPILER)
930 #include <nmmintrin.h>
931 #if WORDSIZE==64 && HAVE_MMPOP64
932 #define POPCOUNT(x) ((int)_mm_popcnt_u64(x))
933 #elif WORDSIZE==32 && HAVE_MMPOP32
934 #define POPCOUNT(x) _mm_popcnt_u32(x)
935 #elif WORDSIZE==16 && HAVE_MMPOP32
936 #define POPCOUNT(x) _mm_popcnt_u32((unsigned int)(x))
937 #endif
938
939 /* Note that, unlike icc, gcc will not use the POPCNT instruction
940 without permission, in which case it defines __POPCNT__ . */
941 #elif defined(__POPCNT__)
942 #if defined(SETWORD_LONGLONG) && HAVE_POPCNTLL
943 #define POPCOUNT(x) __builtin_popcountll(x)
944 #elif defined(SETWORD_LONG) && HAVE_POPCNTL
945 #define POPCOUNT(x) __builtin_popcountl(x)
946 #elif defined(SETWORD_INT) && HAVE_POPCNT
947 #define POPCOUNT(x) __builtin_popcount(x)
948 #elif defined(SETWORD_SHORT) && HAVE_POPCNT
949 #define POPCOUNT(x) __builtin_popcount((unsigned int)(x))
950 #endif
951 #endif
952
953 /* Fall-back position */
954 #ifndef POPCOUNT
955 #define POPCOUNT POPCOUNTMAC
956 #endif
957
958 #endif /* ifndef POPCOUNT */
959
960 #define ALLMASK(n) ((setword)((n)?~BITMASK((n)-1):0)) /* First n bits */
961
962 /* various constants: */
963 #undef FALSE
964 #undef TRUE
965 #define FALSE 0
966 #define TRUE 1
967
968 #if SIZEOF_INT>=4
969 #define NAUTY_INFINITY 2000000002 /* Max graph size is 2 billion */
970 #else
971 #define NAUTY_INFINITY 0x7FFF
972 #endif
973
974 /* The following four types are obsolete, use int in new code. */
975 typedef int shortish;
976 typedef shortish permutation;
977 typedef int nvector,np2vector;
978
979 #if MAXN > NAUTY_INFINITY-2
980 #error MAXN must be at most NAUTY_INFINITY-2
981 #endif
982
983 /* typedefs for sets, graphs, permutations, etc.: */
984
985 typedef int boolean; /* boolean MUST be the same as int */
986
987 #define UPROC void /* obsolete */
988
989 typedef setword set,graph;
990 #ifdef NAUTY_IN_MAGMA
991 typedef graph nauty_graph;
992 typedef set nauty_set;
993 #endif
994
995 typedef struct
996 {
997 double grpsize1; /* size of group is */
998 int grpsize2; /* grpsize1 * 10^grpsize2 */
999 #define groupsize1 grpsize1 /* for backwards compatibility */
1000 #define groupsize2 grpsize2
1001 int numorbits; /* number of orbits in group */
1002 int numgenerators; /* number of generators found */
1003 int errstatus; /* if non-zero : an error code */
1004 #define outofspace errstatus; /* for backwards compatibility */
1005 unsigned long numnodes; /* total number of nodes */
1006 unsigned long numbadleaves; /* number of leaves of no use */
1007 int maxlevel; /* maximum depth of search */
1008 unsigned long tctotal; /* total size of all target cells */
1009 unsigned long canupdates; /* number of updates of best label */
1010 unsigned long invapplics; /* number of applications of invarproc */
1011 unsigned long invsuccesses; /* number of successful uses of invarproc() */
1012 int invarsuclevel; /* least level where invarproc worked */
1013 } statsblk;
1014
1015 /* codes for errstatus field (see nauty.c for more accurate descriptions): */
1016 /* 0 is normal - no error */
1017 #define NTOOBIG 1 /* n > MAXN or n > WORDSIZE*m */
1018 #define MTOOBIG 2 /* m > MAXM */
1019 #define CANONGNIL 3 /* canong = NULL, but getcanon = TRUE */
1020 #define NAUABORTED 4 /* nauty is terminated early under program control */
1021 #define NAUKILLED 5 /* nauty is terminated early by caught signal */
1022
1023 /* manipulation of real approximation to group size */
1024 #define MULTIPLY(s1,s2,i) if ((s1 *= i) >= 1e10) {s1 /= 1e10; s2 += 10;}
1025
1026 struct optionstruct; /* incomplete definition */
1027
1028 typedef struct
1029 {
1030 boolean (*isautom) /* test for automorphism */
1031 (graph*,int*,boolean,int,int);
1032 int (*testcanlab) /* test for better labelling */
1033 (graph*,graph*,int*,int*,int,int);
1034 void (*updatecan) /* update canonical object */
1035 (graph*,graph*,int*,int,int,int);
1036 void (*refine) /* refine partition */
1037 (graph*,int*,int*,int,int*,int*,set*,int*,int,int);
1038 void (*refine1) /* refine partition, MAXM==1 */
1039 (graph*,int*,int*,int,int*,int*,set*,int*,int,int);
1040 boolean (*cheapautom) /* test for easy automorphism */
1041 (int*,int,boolean,int);
1042 int (*targetcell) /* decide which cell to split */
1043 (graph*,int*,int*,int,int,boolean,int,int,int);
1044 void (*freedyn)(void); /* free dynamic memory */
1045 void (*check) /* check compilation parameters */
1046 (int,int,int,int);
1047 void (*init)(graph*,graph**,graph*,graph**,int*,int*,set*,
1048 struct optionstruct*,int*,int,int);
1049 void (*cleanup)(graph*,graph**,graph*,graph**,int*,int*,
1050 struct optionstruct*,statsblk*,int,int);
1051 } dispatchvec;
1052
1053 typedef struct optionstruct
1054 {
1055 int getcanon; /* make canong and canonlab? */
1056 #define LABELONLY 2 /* new value UNIMPLEMENTED */
1057 boolean digraph; /* multiple edges or loops? */
1058 boolean writeautoms; /* write automorphisms? */
1059 boolean writemarkers; /* write stats on pts fixed, etc.? */
1060 boolean defaultptn; /* set lab,ptn,active for single cell? */
1061 boolean cartesian; /* use cartesian rep for writing automs? */
1062 int linelength; /* max chars/line (excl. '\n') for output */
1063 FILE *outfile; /* file for output, if any */
1064 void (*userrefproc) /* replacement for usual refine procedure */
1065 (graph*,int*,int*,int,int*,int*,set*,int*,int,int);
1066 void (*userautomproc) /* procedure called for each automorphism */
1067 (int,int*,int*,int,int,int);
1068 void (*userlevelproc) /* procedure called for each level */
1069 (int*,int*,int,int*,statsblk*,int,int,int,int,int,int);
1070 void (*usernodeproc) /* procedure called for each node */
1071 (graph*,int*,int*,int,int,int,int,int,int);
1072 int (*usercanonproc) /* procedure called for better labellings */
1073 (graph*,int*,graph*,unsigned long,int,int,int);
1074 void (*invarproc) /* procedure to compute vertex-invariant */
1075 (graph*,int*,int*,int,int,int,int*,int,boolean,int,int);
1076 int tc_level; /* max level for smart target cell choosing */
1077 int mininvarlevel; /* min level for invariant computation */
1078 int maxinvarlevel; /* max level for invariant computation */
1079 int invararg; /* value passed to (*invarproc)() */
1080 dispatchvec *dispatch; /* vector of object-specific routines */
1081 boolean schreier; /* use random schreier method */
1082 void *extra_options; /* arbitrary extra options */
1083 #ifdef NAUTY_IN_MAGMA
1084 boolean print_stats; /* CAYLEY specfic - GYM Sep 1990 */
1085 char *invarprocname; /* Magma - no longer global sjc 1994 */
1086 int lab_h; /* Magma - no longer global sjc 1994 */
1087 int ptn_h; /* Magma - no longer global sjc 1994 */
1088 int orbitset_h; /* Magma - no longer global sjc 1994 */
1089 #endif
1090 } optionblk;
1091
1092 #ifndef CONSOLWIDTH
1093 #define CONSOLWIDTH 78
1094 #endif
1095
1096 /* The following are obsolete. Just use NULL. */
1097 #define NILFUNCTION ((void(*)())NULL) /* nil pointer to user-function */
1098 #define NILSET ((set*)NULL) /* nil pointer to set */
1099 #define NILGRAPH ((graph*)NULL) /* nil pointer to graph */
1100
1101 #define DEFAULTOPTIONS_GRAPH(options) optionblk options = \
1102 {0,FALSE,FALSE,FALSE,TRUE,FALSE,CONSOLWIDTH, \
1103 NULL,NULL,NULL,NULL,NULL,NULL,NULL,100,0,1,0,&dispatch_graph,FALSE,NULL}
1104 #define DEFAULTOPTIONS_DIGRAPH(options) optionblk options = \
1105 {0,TRUE,FALSE,FALSE,TRUE,FALSE,CONSOLWIDTH, \
1106 NULL,NULL,NULL,NULL,NULL,NULL,adjacencies,100,0,999,0,&dispatch_graph,FALSE,NULL}
1107
1108 #ifndef DEFAULTOPTIONS
1109 #define DEFAULTOPTIONS DEFAULTOPTIONS_GRAPH
1110 #endif
1111 #ifndef DEFAULTOPTIONS_DENSEGRAPH
1112 #define DEFAULTOPTIONS_DENSEGRAPH DEFAULTOPTIONS_GRAPH
1113 #endif
1114
1115 #ifdef NAUTY_IN_MAGMA
1116 #define PUTC(c,f) io_putchar(c)
1117 #else
1118 #ifdef IS_JAVA
1119 extern void javastream(FILE* f,char c);
1120 #define PUTC(c,f) javastream(f,c)
1121 #else
1122 #define PUTC(c,f) putc(c,f)
1123 #endif
1124 #endif
1125
1126 /* We hope that malloc, free, realloc are declared either in <stdlib.h>
1127 or <malloc.h>. Otherwise we will define them. We also assume that
1128 size_t has been defined by the time we get to define malloc(). */
1129 #ifndef NAUTY_IN_MAGMA
1130 #if MALLOC_DEC==2
1131 #include <malloc.h>
1132 #endif
1133 #if MALLOC_DEC==0
1134 extern void *malloc(size_t);
1135 extern void *realloc(void*,size_t);
1136 extern void free(void*);
1137 #endif
1138 #endif
1139
1140 /* ALLOCS(x,y) should return a pointer (any pointer type) to x*y units of new
1141 storage, not necessarily initialised. A "unit" of storage is defined by
1142 the sizeof operator. x and y are integer values of type int or larger,
1143 but x*y may well be too large for an int. The macro should cast to the
1144 correct type for the call. On failure, ALLOCS(x,y) should return a NULL
1145 pointer. FREES(p) should free storage previously allocated by ALLOCS,
1146 where p is the value that ALLOCS returned. */
1147
1148 #ifdef NAUTY_IN_MAGMA
1149 #define ALLOCS(x,y) mem_malloc((size_t)(x)*(size_t)(y))
1150 #define REALLOCS(p,x) mem_realloc(p,(size_t)(x))
1151 #define FREES(p) mem_free(p)
1152 #else
1153 #define ALLOCS(x,y) malloc((size_t)(x)*(size_t)(y))
1154 #define REALLOCS(p,x) realloc(p,(size_t)(x))
1155 #define FREES(p) free(p)
1156 #endif
1157
1158 /* The following macros are used by nauty if MAXN=0. They dynamically
1159 allocate arrays of size dependent on m or n. For each array there
1160 should be two static variables:
1161 type *name;
1162 size_t name_sz;
1163 "name" will hold a pointer to an allocated array. "name_sz" will hold
1164 the size of the allocated array in units of sizeof(type). DYNALLSTAT
1165 declares both variables and initialises name_sz=0. DYNALLOC1 and
1166 DYNALLOC2 test if there is enough space allocated, and if not free
1167 the existing space and allocate a bigger space. The allocated space
1168 is not initialised.
1169
1170 In the case of DYNALLOC1, the space is allocated using
1171 ALLOCS(sz,sizeof(type)).
1172 In the case of DYNALLOC2, the space is allocated using
1173 ALLOCS(sz1,sz2*sizeof(type)).
1174
1175 DYNREALLOC is like DYNALLOC1 except that the old contents are copied
1176 into the new space. Availability of realloc() is assumed.
1177
1178 DYNFREE frees any allocated array and sets name_sz back to 0.
1179 CONDYNFREE does the same, but only if name_sz exceeds some limit.
1180 */
1181
1182 #define DYNALLSTAT(type,name,name_sz) \
1183 static TLS_ATTR type *name; static TLS_ATTR size_t name_sz=0
1184 #define DYNALLOC1(type,name,name_sz,sz,msg) \
1185 if ((size_t)(sz) > name_sz) \
1186 { if (name_sz) FREES(name); name_sz = (sz); \
1187 if ((name=(type*)ALLOCS(sz,sizeof(type))) == NULL) {alloc_error(msg);}}
1188 #define DYNALLOC2(type,name,name_sz,sz1,sz2,msg) \
1189 if ((size_t)(sz1)*(size_t)(sz2) > name_sz) \
1190 { if (name_sz) FREES(name); name_sz = (size_t)(sz1)*(size_t)(sz2); \
1191 if ((name=(type*)ALLOCS((sz1),(sz2)*sizeof(type))) == NULL) \
1192 {alloc_error(msg);}}
1193 #define DYNREALLOC(type,name,name_sz,sz,msg) \
1194 {if ((size_t)(sz) > name_sz) \
1195 { if ((name = (type*)REALLOCS(name,(sz)*sizeof(type))) == NULL) \
1196 {alloc_error(msg);} else name_sz = (sz);}}
1197 #define DYNFREE(name,name_sz) \
1198 { if (name) FREES(name); name = NULL; name_sz = 0;}
1199 #define CONDYNFREE(name,name_sz,minsz) \
1200 if (name_sz > (size_t)(minsz)) {DYNFREE(name,name_sz);}
1201
1202 /* File to write error messages to (used as first argument to fprintf()). */
1203 #define ERRFILE stderr
1204
1205 /* Don't use OLDEXTDEFS, it is only still here for Magma. */
1206 #ifdef OLDEXTDEFS
1207 #define EXTDEF_CLASS
1208 #ifdef EXTDEFS
1209 #define EXTDEF_TYPE 1
1210 #else
1211 #define EXTDEF_TYPE 2
1212 #endif
1213 #else
1214 #define EXTDEF_CLASS static
1215 #define EXTDEF_TYPE 2
1216 #endif
1217
1218 #ifndef NAUTY_IN_MAGMA
1219 /* Things equivalent to bit, bytecount, leftbit are defined
1220 in bs.h for Magma. */
1221 #if EXTDEF_TYPE==1
1222 extern setword bit[];
1223 extern int bytecount[];
1224 extern int leftbit[];
1225
1226 #else
1227 /* array giving setwords with single 1-bit */
1228 #if WORDSIZE==64
1229 #ifdef SETWORD_LONGLONG
1230 EXTDEF_CLASS const
1231 setword bit[] = {01000000000000000000000LL,0400000000000000000000LL,
1232 0200000000000000000000LL,0100000000000000000000LL,
1233 040000000000000000000LL,020000000000000000000LL,
1234 010000000000000000000LL,04000000000000000000LL,
1235 02000000000000000000LL,01000000000000000000LL,
1236 0400000000000000000LL,0200000000000000000LL,
1237 0100000000000000000LL,040000000000000000LL,
1238 020000000000000000LL,010000000000000000LL,
1239 04000000000000000LL,02000000000000000LL,
1240 01000000000000000LL,0400000000000000LL,0200000000000000LL,
1241 0100000000000000LL,040000000000000LL,020000000000000LL,
1242 010000000000000LL,04000000000000LL,02000000000000LL,
1243 01000000000000LL,0400000000000LL,0200000000000LL,
1244 0100000000000LL,040000000000LL,020000000000LL,010000000000LL,
1245 04000000000LL,02000000000LL,01000000000LL,0400000000LL,
1246 0200000000LL,0100000000LL,040000000LL,020000000LL,
1247 010000000LL,04000000LL,02000000LL,01000000LL,0400000LL,
1248 0200000LL,0100000LL,040000LL,020000LL,010000LL,04000LL,
1249 02000LL,01000LL,0400LL,0200LL,0100LL,040LL,020LL,010LL,
1250 04LL,02LL,01LL};
1251 #else
1252 EXTDEF_CLASS const
1253 setword bit[] = {01000000000000000000000,0400000000000000000000,
1254 0200000000000000000000,0100000000000000000000,
1255 040000000000000000000,020000000000000000000,
1256 010000000000000000000,04000000000000000000,
1257 02000000000000000000,01000000000000000000,
1258 0400000000000000000,0200000000000000000,
1259 0100000000000000000,040000000000000000,020000000000000000,
1260 010000000000000000,04000000000000000,02000000000000000,
1261 01000000000000000,0400000000000000,0200000000000000,
1262 0100000000000000,040000000000000,020000000000000,
1263 010000000000000,04000000000000,02000000000000,
1264 01000000000000,0400000000000,0200000000000,0100000000000,
1265 040000000000,020000000000,010000000000,04000000000,
1266 02000000000,01000000000,0400000000,0200000000,0100000000,
1267 040000000,020000000,010000000,04000000,02000000,01000000,
1268 0400000,0200000,0100000,040000,020000,010000,04000,
1269 02000,01000,0400,0200,0100,040,020,010,04,02,01};
1270 #endif
1271 #endif
1272
1273 #if WORDSIZE==32
1274 EXTDEF_CLASS const
1275 setword bit[] = {020000000000,010000000000,04000000000,02000000000,
1276 01000000000,0400000000,0200000000,0100000000,040000000,
1277 020000000,010000000,04000000,02000000,01000000,0400000,
1278 0200000,0100000,040000,020000,010000,04000,02000,01000,
1279 0400,0200,0100,040,020,010,04,02,01};
1280 #endif
1281
1282 #if WORDSIZE==16
1283 EXTDEF_CLASS const
1284 setword bit[] = {0100000,040000,020000,010000,04000,02000,01000,0400,0200,
1285 0100,040,020,010,04,02,01};
1286 #endif
1287
1288 /* array giving number of 1-bits in bytes valued 0..255: */
1289 EXTDEF_CLASS const
1290 int bytecount[] = {0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,
1291 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
1292 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
1293 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
1294 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
1295 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
1296 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
1297 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
1298 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
1299 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
1300 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
1301 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
1302 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
1303 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
1304 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
1305 4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8};
1306
1307 /* array giving position (1..7) of high-order 1-bit in byte: */
1308 EXTDEF_CLASS const
1309 int leftbit[] = {8,7,6,6,5,5,5,5,4,4,4,4,4,4,4,4,
1310 3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,
1311 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
1312 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
1313 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1314 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1315 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1316 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1317 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
1318 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
1319 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
1320 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
1321 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
1322 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
1323 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
1324 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
1325 #endif /* EXTDEFS */
1326
1327 #endif /* not NAUTY_IN_MAGMA */
1328
1329 #define ANSIPROT 1
1330 #define EXTPROC(func,args) extern func args; /* obsolete */
1331
1332 /* The following is for C++ programs that read nauty.h. Compile nauty
1333 itself using C, not C++. */
1334
1335 #ifdef __cplusplus
1336 extern "C" {
1337 #endif
1338
1339 extern void alloc_error(const char*);
1340 extern void breakout(int*,int*,int,int,int,set*,int);
1341 extern boolean cheapautom(int*,int,boolean,int);
1342 extern void doref(graph*,int*,int*,int,int*,int*,int*,set*,int*,
1343 void(*)(graph*,int*,int*,int,int*,int*,set*,int*,int,int),
1344 void(*)(graph*,int*,int*,int,int,int,int*,int,boolean,int,int),
1345 int,int,int,boolean,int,int);
1346 extern void extra_autom(int*,int);
1347 extern void extra_level(int,int*,int*,int,int,int,int,int,int);
1348 extern boolean isautom(graph*,int*,boolean,int,int);
1349 extern dispatchvec dispatch_graph;
1350 extern int itos(int,char*);
1351 extern void fmperm(int*,set*,set*,int,int);
1352 extern void fmptn(int*,int*,int,set*,set*,int,int);
1353 extern void longprune(set*,set*,set*,set*,int);
1354 extern void nauty(graph*,int*,int*,set*,int*,optionblk*,
1355 statsblk*,set*,int,int,int,graph*);
1356 extern void maketargetcell(graph*,int*,int*,int,
1357 set*,int*,int*,int,boolean,int,
1358 int (*)(graph*,int*,int*,int,int,boolean,int,int,int),int,int);
1359 extern int nextelement(set*,int,int);
1360 extern int orbjoin(int*,int*,int);
1361 extern void permset(set*,set*,int,int*);
1362 extern void putstring(FILE*,char*);
1363 extern void refine(graph*,int*,int*,int,int*,int*,set*,int*,int,int);
1364 extern void refine1(graph*,int*,int*,int,int*,int*,set*,int*,int,int);
1365 extern void shortprune(set*,set*,int);
1366 extern int targetcell(graph*,int*,int*,int,int,boolean,int,int,int);
1367 extern int testcanlab(graph*,graph*,int*,int*,int,int);
1368 extern void updatecan(graph*,graph*,int*,int,int,int);
1369 extern void writeperm(FILE*,int*,boolean,int,int);
1370 extern void nauty_freedyn(void);
1371 extern void nauty_check(int,int,int,int);
1372 extern void naugraph_check(int,int,int,int);
1373 extern void nautil_check(int,int,int,int);
1374 extern void nautil_freedyn(void);
1375 extern void naugraph_freedyn(void);
1376 extern void densenauty(graph*,int*,int*,int*,
1377 optionblk*,statsblk*,int,int,graph*);
1378 extern void writegroupsize(FILE*,double,int);
1379
1380 extern int labelorg; /* Declared in nautil.c */
1381 extern volatile int nauty_kill_request; /* Also declared in nautil.c */
1382
1383 #ifdef __cplusplus
1384 }
1385 #endif
1386
1387 /* ++++++ This file is automatically generated, don't edit it by hand! ++++++ */
1388
1389
1390 #endif /* _NAUTY_H_ */
1391