-
Notifications
You must be signed in to change notification settings - Fork 9
/
Copy pathnauty-h.in
1390 lines (1253 loc) · 57.9 KB
/
nauty-h.in
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
/**************************************************************************
* This is the header file for Version 2.7 of nauty(). *
* @configure_input@
**************************************************************************/
#ifndef _NAUTY_H_ /* only process this file once */
#define _NAUTY_H_
/* The parts between the ==== lines are modified by configure when
creating nauty.h out of nauty-h.in. If configure is not being used,
it is necessary to check they are correct.
====================================================================*/
/* Check whether various headers or options are available */
#define HAVE_UNISTD_H @header_unistd_h@ /* <unistd.h> */
#define HAVE_SYSTYPES_H @header_sys_types_h@ /* <sys/types.h> */
#define HAVE_STDDEF_H @header_stddef_h@ /* <stddef.h> */
#define HAVE_STDLIB_H @header_stdlib_h@ /* <stdlib.h> */
#define HAVE_STRING_H @header_string_h@ /* <string.h> */
#define HAVE_LIMITS_H @header_limits_h@ /* <limits.h> */
#define HAVE_STDINT_H @header_stdint_h@ /* <stdint.h> */
#define MALLOC_DEC @malloc_dec@ /* 1 = malloc() is declared in stdlib.h, */
/* 2 = in malloc.h, 0 = in neither place */
#define HAS_MATH_INF @has_math_inf@ /* INFINITY is defined in math.h or */
/* some system header likely to be used */
#define HAS_STDIO_UNLOCK @stdio_nolock@ /* Whether there are getc_unlocked, */
/* putc_unlocked,flockfile and funlockfile */
#define DEFAULT_WORDSIZE @default_wordsize@
/* Note that thread-local storage (TLS) is only useful for running nauty
in multiple threads and will slow it down a little otherwise. */
#define TLS_SUPPORTED @tls_supported@ /* Compiler supports thread-local */
/* If USE_TLS is defined, define TLS_ATTR to be the attribute name
for TLS and define HAVE_TLS=1. Otherwise define TLS_ATTR to be empty
and HAVE_TLS=0. USE_TLS can be defined on the command line or by
configuring with --enable-tls. */
#ifndef USE_TLS
@use_tls@
#endif
#ifdef USE_TLS
#if !TLS_SUPPORTED
#error "TLS is requested but not available"
#else
#define TLS_ATTR @ac_cv_tls@
#define HAVE_TLS 1
#endif
#else
#define TLS_ATTR
#define HAVE_TLS 0
#endif
#define USE_ANSICONTROLS @have_ansicontrols@
/* whether --enable-ansicontrols is used */
#define FLEX_ARRAY_OK @flex_array_ok@
/* whether the compiler supports flexible array members in structures */
#define _FILE_OFFSET_BITS @ac_cv_sys_file_offset_bits@
#if _FILE_OFFSET_BITS == 64
#define _LARGEFILE_SOURCE
#else
#undef _FILE_OFFSET_BITS
#endif
/* Support of gcc extensions __builtin_clz, __builtin_clzl, __builtin_clzll */
#ifndef HAVE_HWLZCNT
#define HAVE_HWLZCNT @have_hwlzcnt@
#endif
#define HAVE_CLZ @have_clz@
#define HAVE_CLZL @have_clzl@
#define HAVE_CLZLL @have_clzll@
/* Support of gcc extensions
__builtin_popcount, __builtin_popcountl, __builtin_popcountll
Note that these may only be fast if the compiler switch -mpopcnt is used.
Also the intrinsics
_mm_popcnt_u32, _mm_popcnt_u64
for the Intel compiler icc. These need no compiler switch.
*/
#ifndef HAVE_HWPOPCNT
#define HAVE_HWPOPCNT @have_hwpopcnt@
#endif
#define HAVE_POPCNT @have_popcnt@
#define HAVE_POPCNTL @have_popcntl@
#define HAVE_POPCNTLL @have_popcntll@
#define HAVE_MMPOP32 @have_mmpop32@
#define HAVE_MMPOP64 @have_mmpop64@
/*==================================================================*/
/* The following line must be uncommented for compiling into Magma. */
/* #define NAUTY_IN_MAGMA */
#ifdef NAUTY_IN_MAGMA
#include "defs.h"
#include "system.h"
#include "bs.h"
#define OLDEXTDEFS
#else
#include <stdio.h>
#define P_(x) x
#endif
#if defined(__unix) || defined(__unix__) || defined(unix)
#define SYS_UNIX
#endif
/*****************************************************************************
* *
* AUTHOR: Brendan D. McKay *
* Research School of Computer Science *
* Australian National University *
* Canberra, ACT 2601, Australia *
* phone: +61 2 6125 3845 *
* email: [email protected] *
* *
* This software is subject to copyright as detailed in the file COPYRIGHT. *
* *
* Reference manual: *
* B. D. McKay and A. Piperno, nauty User's Guide (Version 2.5), *
* http://pallini.di.uniroma1.it *
* http://cs.anu.edu.au/~bdm/nauty/ *
* *
* CHANGE HISTORY *
* 10-Nov-87 : final changes for version 1.2 *
* 5-Dec-87 : renamed to version 1.3 (no changes to this file) *
* 28-Sep-88 : added PC Turbo C support, making version 1.4 *
* 23-Mar-89 : changes for version 1.5 : *
* - reworked M==1 code *
* - defined NAUTYVERSION string *
* - made NAUTYH_READ to allow this file to be read twice *
* - added optional ANSI function prototypes *
* - added validity check for WORDSIZE *
* - added new fields to optionblk structure *
* - updated DEFAULTOPTIONS to add invariants fields *
* - added (set*) cast to definition of GRAPHROW *
* - added definition of ALLOCS and FREES *
* 25-Mar-89 : - added declaration of new function doref() *
* - added UNION macro *
* 29-Mar-89 : - reduced the default MAXN for small machines *
* - removed OUTOFSPACE (no longer used) *
* - added SETDIFF and XOR macros *
* 2-Apr-89 : - extended statsblk structure *
* 4-Apr-89 : - added IS_* macros *
* - added ERRFILE definition *
* - replaced statsblk.outofspace by statsblk.errstatus *
* 5-Apr-89 : - deleted definition of np2vector (no longer used) *
* - introduced EMPTYSET macro *
* 12-Apr-89 : - eliminated MARK, UNMARK and ISMARKED (no longer used) *
* 18-Apr-89 : - added MTOOBIG and CANONGNIL *
* 12-May-89 : - made ISELEM1 and ISELEMENT return 0 or 1 *
* 2-Mar-90 : - added EXTPROC macro and used it *
* 12-Mar-90 : - added SYS_CRAY, with help from N. Sloane and A. Grosky *
* - added dummy groupopts field to optionblk *
* - select some ANSI things if __STDC__ exists *
* 20-Mar-90 : - changed default MAXN for Macintosh versions *
* - created SYS_MACTHINK for Macintosh THINK compiler *
* 27-Mar-90 : - split SYS_MSDOS into SYS_PCMS4 and SYS_PCMS5 *
* 13-Oct-90 : changes for version 1.6: *
* - fix definition of setword for WORDSIZE==64 *
* 14-Oct-90 : - added SYS_APOLLO version to avoid compiler bug *
* 15-Oct-90 : - improve detection of ANSI conformance *
* 17-Oct-90 : - changed temp name in EMPTYSET to avoid A/UX bug *
* 16-Apr-91 : changes for version 1.7: *
* - made version SYS_PCTURBO use free(), not cfree() *
* 2-Sep-91 : - noted that SYS_PCMS5 also works for Quick C *
* - moved MULTIPLY to here from nauty.c *
* 12-Jun-92 : - changed the top part of this comment *
* 27-Aug-92 : - added version SYS_IBMC, thanks to Ivo Duentsch *
* 5-Jun-93 : - renamed to version 1.7+, only change in naututil.h *
* 29-Jul-93 : changes for version 1.8: *
* - fixed error in default 64-bit version of FIRSTBIT *
* (not used in any version before ALPHA) *
* - installed ALPHA version (thanks to Gordon Royle) *
* - defined ALLOCS,FREES for SYS_IBMC *
* 3-Sep-93 : - make calloc void* in ALPHA version *
* 17-Sep-93 : - renamed to version 1.9, *
* changed only dreadnaut.c and nautinv.c *
* 24-Feb-94 : changes for version 1.10: *
* - added version SYS_AMIGAAZT, thanks to Carsten Saager *
* (making 1.9+) *
* 19-Apr-95 : - added prototype wrapper for C++, *
* thanks to Daniel Huson *
* 5-Mar-96 : - added SYS_ALPHA32 version (32-bit setwords on Alpha) *
* 13-Jul-96 : changes for version 2.0: *
* - added dynamic allocation *
* - ERRFILE must be defined *
* - added FLIPELEM1 and FLIPELEMENT macros *
* 13-Aug-96 : - added SWCHUNK? macros *
* - added TAKEBIT macro *
* 28-Nov-96 : - include sys/types.h if not ANSI (tentative!) *
* 24-Jan-97 : - and stdlib.h if ANSI *
* - removed use of cfree() from UNIX variants *
* 25-Jan-97 : - changed options.getcanon from boolean to int *
* Backwards compatibility is ok, as boolean and int *
* are the same. Now getcanon=2 means to get the label *
* and not care about the group. Sometimes faster. *
* 6-Feb-97 : - Put in #undef for FALSE and TRUE to cope with *
* compilers that illegally predefine them. *
* - declared nauty_null and nautil_null *
* 2-Jul-98 : - declared ALLBITS *
* 21-Oct-98 : - allow WORDSIZE==64 using unsigned long long *
* - added BIGNAUTY option for really big graphs *
* 11-Dec-99 : - made bit, leftbit and bytecount static in each file *
* 9-Jan-00 : - declared nauty_check() and nautil_check() *
* 12-Feb-00 : - Used #error for compile-time checks *
* - Added DYNREALLOC *
* 4-Mar-00 : - declared ALLMASK(n) *
* 27-May-00 : - declared CONDYNFREE *
* 28-May-00 : - declared nautil_freedyn() *
* 16-Aug-00 : - added OLDNAUTY and changed canonical labelling *
* 16-Nov-00 : - function prototypes are now default and unavoidable *
* - removed UPROC, now assume all compilers know void *
* - removed nvector, now just int (as it always was) *
* - added extra parameter to targetcell() *
* - removed old versions which were only to skip around *
* bugs that should have been long fixed: *
* SYS_APOLLO and SYS_VAXBSD. *
* - DEFAULTOPIONS now specifies no output *
* - Removed obsolete SYS_MACLSC version *
* 21-Apr-01 : - Added code to satisfy compilation into Magma. This *
* is activated by defining NAUTY_IN_MAGMA above. *
* - The *_null routines no longer exist *
* - Default maxinvarlevel is now 1. (This has no effect *
* unless an invariant is specified.) *
* - Now labelorg has a concrete declaration in nautil.c *
* and EXTDEFS is not needed *
* 5-May-01 : - NILFUNCTION, NILSET, NILGRAPH now obsolete. Use NULL. *
* 11-Sep-01 : - setword is unsigned int in the event that UINT_MAX *
* is defined and indicates it is big enough *
* 17-Oct-01 : - major rewrite for 2.1. SYS_* variables gone! *
* Some modernity assumed, eg size_t *
* 8-Aug-02 : - removed MAKEEMPTY (use EMPTYSET instead) *
* - deleted OLDNAUTY everywhere *
* 27-Aug-02 : - converted to use autoconf. Now the original of this *
* file is nauty-h.in. Run configure to make nauty.h. *
* 20-Dec-02 : - increased INFINITY *
* some reorganization to please Magma *
* - declared nauty_freedyn() *
* 17-Nov-03 : - renamed INFINITY to NAUTY_INFINITY *
* 29-May-04 : - added definition of SETWORD_FORMAT *
* 14-Sep-04 : - extended prototypes even to recursive functions *
* 16-Oct-04 : - added DEFAULTOPTIONS_GRAPH *
* 24-Oct-04 : Starting 2.3 *
* - remove register declarations as modern compilers *
* tend to find them a nuisance *
* - Don't define the obsolete symbol INFINITY if it is *
* defined already *
* 17-Nov-04 : - make 6 counters in statsblk unsigned long *
* 17-Jan-04 : - add init() and cleanup() to dispatchvec *
* 12-Nov-05 : - Changed NAUTY_INFINITY to 2^30+2 in BIGNAUTY case *
* 22-Nov-06 : Starting 2.4 *
* - removed usertcellproc from options *
* changed bestcell to targetcell in dispatch vector *
* declare targetcell and maketargetcell *
* 29-Nov-06 : - add extraoptions to optionblk *
* - add declarations of extra_autom and extra_level *
* 10-Dec-06 : - BIGNAUTY is gone! Now permutation=shortish=int. *
* NAUTY_INFINITY only depends on whether sizeof(int)=2. *
* 27-Jun-08 : - define nauty_counter and LONG_LONG_COUNTERS *
* 30-Jun-08 : - declare version 2.4 *
* 8-Nov-09 : - final release of version 2.4; *
* 10-Nov-10 : Starting 2.5 *
* - declare shortish and permutation obsolete, now int *
* 14-Nov-10 : - SETWORDSNEEDED(n) *
* 23-May-10 : - declare densenauty() *
* 29-Jun-10 : - add PRINT_COUNTER(f,x) *
* - add DEFAULTOPTIONS_DIGRAPH() *
* 27-Mar-11 : - declare writegroupsize() *
* 14-Jan-12 : - add HAVE_TLS and TLS_ATTR *
* 21-Feb-12 : - add ENABLE_ANSI *
* 18-Mar-12 : - add COUNTER_FMT *
* 18-Aug-12 : - add ADDONEARC, ADDONEEDGE, EMPTYGRAPH *
* 29-Aug-12 : - add CLZ macros and FIRSTBITNZ *
* 19-Oct-12 : - add DEFAULT_WORDSIZE *
* 3-Jan-12 : Released 2.5rc1 *
* 18-Jan-12 : Froze 2.5 *
* 18-Jan-12 : - add NAUABORTED and NAUKILLED *
* - add nauty_kill_request *
* - add usercanonproc *
* 1-Oct-15 : - add COUNTER_FMT_RAW *
* 10-Jan-16 : - defined POPCOUNTMAC, optionally use popcnt *
* - remove SYS_CRAY, let's hope it is long obsolete *
* - add Intel popcount intrinsics for icc *
* 12-Jan-16 : - DYNFREE and CONDYNFREE now set the pointer to NULL *
* 16-Jan-16 : - Change NAUTY_INFINITY to 2 billion + 2 *
* 12-Mar-16 : - Add const to alloc_error() *
* : Froze 2.6 *
* 29-Aug-16 : - Add SWHIBIT, REMOVEHIBIT and ATMOSTONEBIT *
* 10-Mar-18 : - Add SETWORD_DEC_FORMAT for decimal output *
* - Fix 64-bit SETWORD_FORMAT to use 0 padding. *
* 28-Feb-19 : - Use intrinsics for WORDSIZE=16 *
* - Macro versions of FIRSTBIT and FIRSTBITNZ are always *
* available as FIRSTBITMAC and FIRSTBITNZMAC *
* 1-Mar-19 : - Add AVOID* tests for non-POSIX header files *
* 31-Aug-19 : - Revise type size determinations to be more robust if *
* configuration wasn't done. *
* - HAVE_HWLZCNT and HAV_HWPOPCNT can be defined at *
* compile time *
* - FIRSTBITNZ, FIRSTBIT and POPCOUNT can be defined at *
* compile time *
* 11-Oct-19 : - Move labelorg and nauty_kill_request into the *
* "C" block for C++ compatibiliy *
* 23-Mar-20 : - Don't define INFINITY even if it is absent from math.h *
* 17-Nov-21 : - Use USE_TLS for thread-local storage *
- Define FLEX_ARRAY_OK *
: Froze 2.7
* @edit_msg@
* *
*****************************************************************************/
/*****************************************************************************
* *
* 16-bit, 32-bit and 64-bit versions can be selected by defining WORDSIZE. *
* The largest graph that can be handled has MAXN vertices. *
* Both WORDSIZE and MAXN can be defined on the command line. *
* WORDSIZE must be 16, 32 or 64; MAXN must be <= NAUTY_INFINITY-2; *
* *
* With a very slight loss of efficiency (depending on platform), nauty *
* can be compiled to dynamically allocate arrays. Predefine MAXN=0 to *
* achieve this effect, which is default behaviour from version 2.0. *
* In that case, graphs of size up to NAUTY_INFINITY-2 can be handled *
* if the memory is available. *
* *
* If only very small graphs need to be processed, use MAXN<=WORDSIZE *
* since this causes substantial code optimizations. *
* *
* Conventions and Assumptions: *
* *
* A 'setword' is the chunk of memory that is occupied by one part of *
* a set. This is assumed to be >= WORDSIZE bits in size. *
* *
* The rightmost (loworder) WORDSIZE bits of setwords are numbered *
* 0..WORDSIZE-1, left to right. It is necessary that the 2^WORDSIZE *
* setwords with the other bits zero are totally ordered under <,=,>. *
* This needs care on a 1's-complement machine. *
* *
* The int variables m and n have consistent meanings throughout. *
* Graphs have n vertices always, and sets have m setwords always. *
* *
* A 'set' consists of m contiguous setwords, whose bits are numbered *
* 0,1,2,... from left (high-order) to right (low-order), using only *
* the rightmost WORDSIZE bits of each setword. It is used to *
* represent a subset of {0,1,...,n-1} in the usual way - bit number x *
* is 1 iff x is in the subset. Bits numbered n or greater, and *
* unnumbered bits, are assumed permanently zero. *
* *
* A 'graph' consists of n contiguous sets. The i-th set represents *
* the vertices adjacent to vertex i, for i = 0,1,...,n-1. *
* *
* A 'permutation' is an array of n ints repesenting a permutation of *
* the set {0,1,...,n-1}. The value of the i-th entry is the number to *
* which i is mapped. *
* *
* If g is a graph and p is a permutation, then g^p is the graph in *
* which vertex i is adjacent to vertex j iff vertex p[i] is adjacent *
* to vertex p[j] in g. *
* *
* A partition nest is represented by a pair (lab,ptn), where lab and ptn *
* are int arrays. The "partition at level x" is the partition whose *
* cells are {lab[i],lab[i+1],...,lab[j]}, where [i,j] is a maximal *
* subinterval of [0,n-1] such that ptn[k] > x for i <= k < j and *
* ptn[j] <= x. The partition at level 0 is given to nauty by the user. *
* This is refined for the root of the tree, which has level 1. *
* *
*****************************************************************************/
#ifndef NAUTY_IN_MAGMA
#if HAVE_SYSTYPES_H && !defined(AVOID_SYS_TYPES_H)
#include <sys/types.h>
#endif
#if HAVE_UNISTD_H && !defined(AVOID_UNISTD_H)
#include <unistd.h>
#endif
#if HAVE_STDDEF_H
#include <stddef.h>
#endif
#if HAVE_STDLIB_H
#include <stdlib.h>
#endif
#if HAVE_LIMITS_H
#include <limits.h>
#endif
#if HAVE_STDINT_H
#include <stdint.h>
#endif
#if HAVE_STRING_H
#include <string.h>
#elif !defined(AVOID_STRINGS_H)
#include <strings.h>
#endif
#endif
/* Now we determine some sizes, relying on limits.h and
stdint.h first in case configuration was not done.
None of these tests are perfect, but sizeof() is not
allowed in preprocessor tests. The program nautest.c
will check these. */
#if defined(INT_MAX)
#if INT_MAX == 65535
#define SIZEOF_INT 2
#else
#define SIZEOF_INT 4
#endif
#else
#define SIZEOF_INT @ac_cv_sizeof_int@
#endif
#if defined(LONG_MAX)
#if LONG_MAX == 2147483647L
#define SIZEOF_LONG 4
#else
#define SIZEOF_LONG 8
#endif
#else
#define SIZEOF_LONG @ac_cv_sizeof_long@
#endif
#if defined(LLONG_MAX)
#define SIZEOF_LONG_LONG 8
#else
#define SIZEOF_LONG @ac_cv_sizeof_long@ /* 0 if nonexistent */
#endif
#if defined(_MSC_VER)
#define SIZEOF_INT128_T 0
#define SIZEOF_INT128 0
#else
#define SIZEOF_INT128_T @ac_cv_sizeof___int128_t@ /* 0 if nonexistent */
#define SIZEOF_INT128 @ac_cv_sizeof___int128@ /* 0 if nonexistent */
#endif
#if defined(_WIN64)
#define SIZEOF_POINTER 8
#elif defined(_WIN32)
#define SIZEOF_POINTER 4
#elif defined(UINTPTR_MAX) && UINTPTRMAX == 4294967295UL
#define SIZEOF_POINTER 4
#else
#define SIZEOF_POINTER @ac_cv_sizeof_voidp@
#endif
/* WORDSIZE is the number of set elements per setword (16, 32 or 64).
WORDSIZE and setword are defined as follows:
DEFAULT_WORDSIZE is usually 0 but is set by the configure script
to NN if --enable-wordsize=NN is used, where NN is 16, 32 or 64.
If WORDSIZE is not defined, but DEFAULT_WORDSIZE > 0, then set
WORDSIZE to the same value as DEFAULT_WORDSIZE.
If WORDSIZE is so far undefined, use 32 unless longs have more
than 32 bits, in which case use 64.
Define setword thus:
WORDSIZE==16 : unsigned short
WORDSIZE==32 : unsigned int unless it is too small,
in which case unsigned long
WORDSIZE==64 : the first of unsigned int, unsigned long,
unsigned long long which is large enough.
*/
#ifdef NAUTY_IN_MAGMA
#undef WORDSIZE
#define WORDSIZE WORDBITS
#endif
#ifndef WORDSIZE
#if DEFAULT_WORDSIZE > 0
#define WORDSIZE DEFAULT_WORDSIZE
#endif
#endif
#ifdef WORDSIZE
#if (WORDSIZE != 16) && (WORDSIZE != 32) && (WORDSIZE != 64)
#error "WORDSIZE must be 16, 32 or 64"
#endif
#else /* WORDSIZE undefined */
#if SIZEOF_LONG>4
#define WORDSIZE 64
#else
#define WORDSIZE 32
#endif
#endif /* WORDSIZE */
#ifdef NAUTY_IN_MAGMA
typedef t_uint setword;
#define SETWORD_INT /* Don't assume this is correct in Magma. */
#else /* NAUTY_IN_MAGMA */
#if WORDSIZE==16
typedef unsigned short setword;
#define SETWORD_SHORT
#endif
#if WORDSIZE==32
#if SIZEOF_INT>=4
typedef unsigned int setword;
#define SETWORD_INT
#else
typedef unsigned long setword;
#define SETWORD_LONG
#endif
#endif
#if WORDSIZE==64
#if SIZEOF_INT>=8
typedef unsigned int setword;
#define SETWORD_INT
#else
#if SIZEOF_LONG>=8
typedef unsigned long setword;
#define SETWORD_LONG
#else
typedef unsigned long long setword;
#define SETWORD_LONGLONG
#endif
#endif
#endif
#endif /* NAUTY_IN_MAGMA else */
#if SIZEOF_LONG_LONG>=8 && SIZEOF_LONG==4
typedef unsigned long long nauty_counter;
#define LONG_LONG_COUNTERS 1
#define COUNTER_FMT "%llu"
#define COUNTER_FMT_RAW "llu"
#else
typedef unsigned long nauty_counter;
#define LONG_LONG_COUNTERS 0
#define COUNTER_FMT "%lu"
#define COUNTER_FMT_RAW "lu"
#endif
#define PRINT_COUNTER(f,x) fprintf(f,COUNTER_FMT,x)
#define NAUTYVERSIONID (27000+HAVE_TLS) /* 10000*version + HAVE_TLS */
#define NAUTYREQUIRED NAUTYVERSIONID /* Minimum compatible version */
#if WORDSIZE==16
#define NAUTYVERSION "2.7 (16 bits)"
#endif
#if WORDSIZE==32
#define NAUTYVERSION "2.7 (32 bits)"
#endif
#if WORDSIZE==64
#define NAUTYVERSION "2.7 (64 bits)"
#endif
#ifndef MAXN /* maximum allowed n value; use 0 for dynamic sizing. */
#define MAXN 0
#define MAXM 0
#else
#define MAXM ((MAXN+WORDSIZE-1)/WORDSIZE) /* max setwords in a set */
#endif /* MAXN */
/* Starting at version 2.2, set operations work for all set sizes unless
ONE_WORD_SETS is defined. In the latter case, if MAXM=1, set ops
work only for single-setword sets. In any case, macro versions
ending with 1 work for single-setword sets and versions ending with
0 work for all set sizes.
*/
#if WORDSIZE==16
#define SETWD(pos) ((pos)>>4) /* number of setword containing bit pos */
#define SETBT(pos) ((pos)&0xF) /* position within setword of bit pos */
#define TIMESWORDSIZE(w) ((w)<<4)
#define SETWORDSNEEDED(n) ((((n)-1)>>4)+1) /* setwords needed for n bits */
#endif
#if WORDSIZE==32
#define SETWD(pos) ((pos)>>5)
#define SETBT(pos) ((pos)&0x1F)
#define TIMESWORDSIZE(w) ((w)<<5)
#define SETWORDSNEEDED(n) ((((n)-1)>>5)+1)
#endif
#if WORDSIZE==64
#define SETWD(pos) ((pos)>>6)
#define SETBT(pos) ((pos)&0x3F)
#define TIMESWORDSIZE(w) ((w)<<6) /* w*WORDSIZE */
#define SETWORDSNEEDED(n) ((((n)-1)>>6)+1)
#endif
#ifdef NAUTY_IN_MAGMA
#define BITT bs_bit
#else
#define BITT bit
#endif
#define ADDELEMENT1(setadd,pos) (*(setadd) |= BITT[pos])
#define DELELEMENT1(setadd,pos) (*(setadd) &= ~BITT[pos])
#define FLIPELEMENT1(setadd,pos) (*(setadd) ^= BITT[pos])
#define ISELEMENT1(setadd,pos) ((*(setadd) & BITT[pos]) != 0)
#define EMPTYSET1(setadd,m) *(setadd) = 0;
#define GRAPHROW1(g,v,m) ((set*)(g)+(v))
#define ADDONEARC1(g,v,w,m) (g)[v] |= BITT[w]
#define ADDONEEDGE1(g,v,w,m) { ADDONEARC1(g,v,w,m); ADDONEARC1(g,w,v,m); }
#define EMPTYGRAPH1(g,m,n) EMPTYSET0(g,n) /* really EMPTYSET0 */
#define ADDELEMENT0(setadd,pos) ((setadd)[SETWD(pos)] |= BITT[SETBT(pos)])
#define DELELEMENT0(setadd,pos) ((setadd)[SETWD(pos)] &= ~BITT[SETBT(pos)])
#define FLIPELEMENT0(setadd,pos) ((setadd)[SETWD(pos)] ^= BITT[SETBT(pos)])
#define ISELEMENT0(setadd,pos) (((setadd)[SETWD(pos)] & BITT[SETBT(pos)]) != 0)
#define EMPTYSET0(setadd,m) \
{setword *es; \
for (es = (setword*)(setadd)+(m); --es >= (setword*)(setadd);) *es=0;}
#define GRAPHROW0(g,v,m) ((set*)(g) + (m)*(size_t)(v))
#define ADDONEARC0(g,v,w,m) ADDELEMENT0(GRAPHROW0(g,v,m),w)
#define ADDONEEDGE0(g,v,w,m) { ADDONEARC0(g,v,w,m); ADDONEARC0(g,w,v,m); }
#define EMPTYGRAPH0(g,m,n) EMPTYSET0(g,(m)*(size_t)(n))
#if (MAXM==1) && defined(ONE_WORD_SETS)
#define ADDELEMENT ADDELEMENT1
#define DELELEMENT DELELEMENT1
#define FLIPELEMENT FLIPELEMENT1
#define ISELEMENT ISELEMENT1
#define EMPTYSET EMPTYSET1
#define GRAPHROW GRAPHROW1
#define ADDONEARC ADDONEARC1
#define ADDONEEDGE ADDONEEDGE1
#define EMPTYGRAPH EMPTYGRAPH1
#else
#define ADDELEMENT ADDELEMENT0
#define DELELEMENT DELELEMENT0
#define FLIPELEMENT FLIPELEMENT0
#define ISELEMENT ISELEMENT0
#define EMPTYSET EMPTYSET0
#define GRAPHROW GRAPHROW0
#define ADDONEARC ADDONEARC0
#define ADDONEEDGE ADDONEEDGE0
#define EMPTYGRAPH EMPTYGRAPH0
#endif
#ifdef NAUTY_IN_MAGMA
#undef EMPTYSET
#define EMPTYSET(setadd,m) {t_int _i; bsp_makeempty(setadd,m,_i);}
#endif
#define NOTSUBSET(word1,word2) ((word1) & ~(word2)) /* test if the 1-bits
in setword word1 do not form a subset of those in word2 */
#define INTERSECT(word1,word2) ((word1) &= (word2)) /* AND word2 into word1 */
#define UNION(word1,word2) ((word1) |= (word2)) /* OR word2 into word1 */
#define SETDIFF(word1,word2) ((word1) &= ~(word2)) /* - word2 into word1 */
#define XOR(word1,word2) ((word1) ^= (word2)) /* XOR word2 into word1 */
#define ZAPBIT(word,x) ((word) &= ~BITT[x]) /* delete bit x in setword */
#define TAKEBIT(iw,w) {(iw) = FIRSTBITNZ(w); (w) ^= BITT[iw];}
#define SWHIBIT(w) ((w)&(-(w))) /* Lower order bit of unsigned type */
#define REMOVEHIBIT(bit,w) {(bit) = SWHIBIT(w); (w) ^= (bit);}
#define ATMOSTONEBIT(w) (((w)&(-(w)))==(w)) /* True if |w| <= 1 */
#ifdef SETWORD_LONGLONG
#define MSK3232 0xFFFFFFFF00000000ULL
#define MSK1648 0xFFFF000000000000ULL
#define MSK0856 0xFF00000000000000ULL
#define MSK1632 0x0000FFFF00000000ULL
#define MSK0840 0xFF0000000000ULL
#define MSK1616 0xFFFF0000ULL
#define MSK0824 0xFF000000ULL
#define MSK0808 0xFF00ULL
#define MSK63C 0x7FFFFFFFFFFFFFFFULL
#define MSK31C 0x7FFFFFFFULL
#define MSK15C 0x7FFFULL
#define MSK64 0xFFFFFFFFFFFFFFFFULL
#define MSK32 0xFFFFFFFFULL
#define MSK16 0xFFFFULL
#define MSK8 0xFFULL
#endif
#ifdef SETWORD_LONG
#define MSK3232 0xFFFFFFFF00000000UL
#define MSK1648 0xFFFF000000000000UL
#define MSK0856 0xFF00000000000000UL
#define MSK1632 0x0000FFFF00000000UL
#define MSK0840 0xFF0000000000UL
#define MSK1616 0xFFFF0000UL
#define MSK0824 0xFF000000UL
#define MSK0808 0xFF00UL
#define MSK63C 0x7FFFFFFFFFFFFFFFUL
#define MSK31C 0x7FFFFFFFUL
#define MSK15C 0x7FFFUL
#define MSK64 0xFFFFFFFFFFFFFFFFUL
#define MSK32 0xFFFFFFFFUL
#define MSK16 0xFFFFUL
#define MSK8 0xFFUL
#endif
#if defined(SETWORD_INT) || defined(SETWORD_SHORT)
#define MSK3232 0xFFFFFFFF00000000U
#define MSK1648 0xFFFF000000000000U
#define MSK0856 0xFF00000000000000U
#define MSK1632 0x0000FFFF00000000U
#define MSK0840 0xFF0000000000U
#define MSK1616 0xFFFF0000U
#define MSK0824 0xFF000000U
#define MSK0808 0xFF00U
#define MSK63C 0x7FFFFFFFFFFFFFFFU
#define MSK31C 0x7FFFFFFFU
#define MSK15C 0x7FFFU
#define MSK64 0xFFFFFFFFFFFFFFFFU
#define MSK32 0xFFFFFFFFU
#define MSK16 0xFFFFU
#define MSK8 0xFFU
#endif
#if defined(SETWORD_LONGLONG)
#define SETWORD_DEC_FORMAT "%llu"
#if WORDSIZE==16
#define SETWORD_FORMAT "%04llx"
#endif
#if WORDSIZE==32
#define SETWORD_FORMAT "%08llx"
#endif
#if WORDSIZE==64
#define SETWORD_FORMAT "%016llx"
#endif
#endif
#if defined(SETWORD_LONG)
#define SETWORD_DEC_FORMAT "%lu"
#if WORDSIZE==16
#define SETWORD_FORMAT "%04lx"
#endif
#if WORDSIZE==32
#define SETWORD_FORMAT "%08lx"
#endif
#if WORDSIZE==64
#define SETWORD_FORMAT "%016lx"
#endif
#endif
#if defined(SETWORD_INT)
#define SETWORD_DEC_FORMAT "%u"
#if WORDSIZE==16
#define SETWORD_FORMAT "%04x"
#endif
#if WORDSIZE==32
#define SETWORD_FORMAT "%08x"
#endif
#if WORDSIZE==64
#define SETWORD_FORMAT "%016x"
#endif
#endif
#if defined(SETWORD_SHORT)
#define SETWORD_DEC_FORMAT "%hu"
#if WORDSIZE==16
#define SETWORD_FORMAT "%04hx"
#endif
#if WORDSIZE==32
#define SETWORD_FORMAT "%08hx"
#endif
#if WORDSIZE==64
#define SETWORD_FORMAT "%016hx"
#endif
#endif
/* POPCOUNT(x) = number of 1-bits in a setword x
POPCOUNTMAC(x) = Macro version of POPCOUNT
FIRSTBIT(x) = number of first 1-bit in non-zero setword (0..WORDSIZE-1)
or WORDSIZE if x == 0
FIRSTBITNZ(x) = as FIRSTBIT(x) but assumes x is not zero
BITMASK(x) = setword whose rightmost WORDSIZE-x-1 (numbered) bits
are 1 and the rest 0 (0 <= x < WORDSIZE)
(I.e., bits 0..x are unselected and the rest selected.)
ALLBITS = all (numbered) bits in a setword */
#if WORDSIZE==64
#define POPCOUNTMAC(x) (bytecount[(x)>>56 & 0xFF] + bytecount[(x)>>48 & 0xFF] \
+ bytecount[(x)>>40 & 0xFF] + bytecount[(x)>>32 & 0xFF] \
+ bytecount[(x)>>24 & 0xFF] + bytecount[(x)>>16 & 0xFF] \
+ bytecount[(x)>>8 & 0xFF] + bytecount[(x) & 0xFF])
#define FIRSTBITMAC(x) ((x) & MSK3232 ? \
(x) & MSK1648 ? \
(x) & MSK0856 ? \
0+leftbit[((x)>>56) & MSK8] : \
8+leftbit[(x)>>48] \
: (x) & MSK0840 ? \
16+leftbit[(x)>>40] : \
24+leftbit[(x)>>32] \
: (x) & MSK1616 ? \
(x) & MSK0824 ? \
32+leftbit[(x)>>24] : \
40+leftbit[(x)>>16] \
: (x) & MSK0808 ? \
48+leftbit[(x)>>8] : \
56+leftbit[x])
#define BITMASK(x) (MSK63C >> (x))
#define ALLBITS MSK64
#define SWCHUNK0(w) ((long)((w)>>48)&0xFFFFL)
#define SWCHUNK1(w) ((long)((w)>>32)&0xFFFFL)
#define SWCHUNK2(w) ((long)((w)>>16)&0xFFFFL)
#define SWCHUNK3(w) ((long)(w)&0xFFFFL)
#endif
#if WORDSIZE==32
#define POPCOUNTMAC(x) (bytecount[(x)>>24 & 0xFF] + bytecount[(x)>>16 & 0xFF] \
+ bytecount[(x)>>8 & 0xFF] + bytecount[(x) & 0xFF])
#define FIRSTBITMAC(x) ((x) & MSK1616 ? ((x) & MSK0824 ? \
leftbit[((x)>>24) & MSK8] : 8+leftbit[(x)>>16]) \
: ((x) & MSK0808 ? 16+leftbit[(x)>>8] : 24+leftbit[x]))
#define BITMASK(x) (MSK31C >> (x))
#define ALLBITS MSK32
#define SWCHUNK0(w) ((long)((w)>>16)&0xFFFFL)
#define SWCHUNK1(w) ((long)(w)&0xFFFFL)
#endif
#if WORDSIZE==16
#define POPCOUNTMAC(x) (bytecount[(x)>>8 & 0xFF] + bytecount[(x) & 0xFF])
#define FIRSTBITMAC(x) ((x) & MSK0808 ? leftbit[((x)>>8) & MSK8] : 8+leftbit[x])
#define BITMASK(x) ((setword)(MSK15C >> (x)))
#define ALLBITS ((setword)MSK16)
#define SWCHUNK0(w) ((long)(w)&0xFFFFL)
#endif
#define FIRSTBITNZMAC FIRSTBITMAC
/* Use clz instructions if available */
#ifndef FIRSTBITNZ /* Can be defined outside */
#ifdef NAUTY_IN_MAGMA
#define FIRSTBITNZ(x) bs_firstbit(x)
#elif defined(_MSC_VER)
#if _MSC_VER >= 1800
#include <intrin.h>
#else
#include <x86intrin.h>
#endif
#if HAVE_HWLZCNT
#if WORDSIZE==64 && defined(_WIN64)
#define FIRSTBITNZ(x) (int)_lzcnt_u64(x)
#elif WORDSIZE==32
#define FIRSTBITNZ(x) (int)_lzcnt_u32(x)
#else
#define FIRSTBITNZ(x) (int)_lzcnt16(x)
#endif
#else /* not HAVE_HWLZCNT */
#if WORDSIZE==64 && defined(_WIN64)
static int msc_bsr_64(setword x) \
{ unsigned long *p; \
_BitScanReverse64(&p,x); return 63 - *p; }
#define FIRSTBITNZ(x) (msc_bsr_64(x))
#elif WORDSIZE==32
#pragma intrinsic(_BitScanReverse)
static int msc_bsr_32(setword x) \
{ unsigned *p; \
_BitScanReverse(&p,x); return 31 - *p; }
#define FIRSTBITNZ(x) (msc_bsr_32(x))
#elif WORDSIZE==16
#pragma intrinsic(_BitScanReverse)
static int msc_bsr_16(setword x) \
{ unsigned long *p; \
_BitScanReverse(&p,(unsigned long)x); return 15 - *p; }
#define FIRSTBITNZ(x) (msc_bsr_16(x))
#endif /* WORDSIZE choice */
#endif /* HAVE_HWLZCNT choice */
#else /* Not MAGMA or WIN */
#if HAVE_HWLZCNT
#if defined(SETWORD_LONGLONG) && HAVE_CLZLL
#define FIRSTBITNZ(x) __builtin_clzll(x)
#elif defined(SETWORD_LONG) && HAVE_CLZL
#define FIRSTBITNZ(x) __builtin_clzl(x)
#elif defined(SETWORD_INT) && HAVE_CLZ
#define FIRSTBITNZ(x) __builtin_clz(x)
#elif defined(SETWORD_SHORT) && HAVE_CLZ
#define FIRSTBITNZ(x) (__builtin_clz((unsigned int)(x)) - 16)
#endif /* size choice */
#endif /* HAVE_HWLZCNT */
#endif /* MAGMA-WIN-OTHER choice */
#endif /* ifndef FIRSTBITNZ */
/* Now fall back on macros for things not defined */
#if defined(FIRSTBITNZ) && !defined(FIRSTBIT)
#define FIRSTBIT(x) ((x) ? FIRSTBITNZ(x) : WORDSIZE)
#else
#ifndef FIRSTBITNZ
#define FIRSTBITNZ FIRSTBITNZMAC
#endif
#ifndef FIRSTBIT
#define FIRSTBIT FIRSTBITMAC
#endif
#endif
/* Use popcount instructions if available */
#ifndef POPCOUNT /* Can be defined outside */
#ifdef NAUTY_IN_MAGMA
#undef BITMASK
#define POPCOUNT(x) bs_popcount(x)
#define BITMASK(x) bs_bitmask(x)
#elif defined(_MSC_VER)
#if _MSC_VER >= 1800
#include <intrin.h>
#else
#include <x86intrin.h>
#endif
#if WORDSIZE==64
#pragma instrinsic(_mm_popcnt_u64)
#define POPCOUNT(x) ((int)_mm_popcnt_u64(x))
#elif WORDSIZE==32
#pragma instrinsic(_mm_popcnt_u32)
#define POPCOUNT(x) _mm_popcnt_u32(x)
#elif WORDSIZE==16
#pragma instrinsic(_mm_popcnt_u32)
#define POPCOUNT(x) _mm_popcnt_u32((unsigned int)(x))
#endif
#elif defined(__INTEL_COMPILER)
#include <nmmintrin.h>
#if WORDSIZE==64 && HAVE_MMPOP64
#define POPCOUNT(x) ((int)_mm_popcnt_u64(x))
#elif WORDSIZE==32 && HAVE_MMPOP32
#define POPCOUNT(x) _mm_popcnt_u32(x)
#elif WORDSIZE==16 && HAVE_MMPOP32
#define POPCOUNT(x) _mm_popcnt_u32((unsigned int)(x))
#endif
/* Note that, unlike icc, gcc will not use the POPCNT instruction
without permission, in which case it defines __POPCNT__ . */
#elif defined(__POPCNT__)
#if defined(SETWORD_LONGLONG) && HAVE_POPCNTLL
#define POPCOUNT(x) __builtin_popcountll(x)
#elif defined(SETWORD_LONG) && HAVE_POPCNTL
#define POPCOUNT(x) __builtin_popcountl(x)
#elif defined(SETWORD_INT) && HAVE_POPCNT
#define POPCOUNT(x) __builtin_popcount(x)
#elif defined(SETWORD_SHORT) && HAVE_POPCNT
#define POPCOUNT(x) __builtin_popcount((unsigned int)(x))
#endif
#endif
/* Fall-back position */
#ifndef POPCOUNT
#define POPCOUNT POPCOUNTMAC
#endif
#endif /* ifndef POPCOUNT */
#define ALLMASK(n) ((setword)((n)?~BITMASK((n)-1):0)) /* First n bits */
/* various constants: */
#undef FALSE
#undef TRUE
#define FALSE 0
#define TRUE 1
#if SIZEOF_INT>=4
#define NAUTY_INFINITY 2000000002 /* Max graph size is 2 billion */
#else
#define NAUTY_INFINITY 0x7FFF
#endif
/* The following four types are obsolete, use int in new code. */
typedef int shortish;
typedef shortish permutation;
typedef int nvector,np2vector;
#if MAXN > NAUTY_INFINITY-2
#error MAXN must be at most NAUTY_INFINITY-2
#endif
/* typedefs for sets, graphs, permutations, etc.: */
typedef int boolean; /* boolean MUST be the same as int */
#define UPROC void /* obsolete */
typedef setword set,graph;
#ifdef NAUTY_IN_MAGMA
typedef graph nauty_graph;
typedef set nauty_set;
#endif
typedef struct
{
double grpsize1; /* size of group is */
int grpsize2; /* grpsize1 * 10^grpsize2 */
#define groupsize1 grpsize1 /* for backwards compatibility */
#define groupsize2 grpsize2