1/************************************************************************** 2* This is the header file for Version 2.7 of nauty(). * 3* @configure_input@ 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 10creating nauty.h out of nauty-h.in. If configure is not being used, 11it is necessary to check they are correct. 12====================================================================*/ 13 14/* Check whether various headers or options are available */ 15#define HAVE_UNISTD_H @header_unistd_h@ /* <unistd.h> */ 16#define HAVE_SYSTYPES_H @header_sys_types_h@ /* <sys/types.h> */ 17#define HAVE_STDDEF_H @header_stddef_h@ /* <stddef.h> */ 18#define HAVE_STDLIB_H @header_stdlib_h@ /* <stdlib.h> */ 19#define HAVE_STRING_H @header_string_h@ /* <string.h> */ 20#define HAVE_LIMITS_H @header_limits_h@ /* <limits.h> */ 21#define HAVE_STDINT_H @header_stdint_h@ /* <stdint.h> */ 22#define MALLOC_DEC @malloc_dec@ /* 1 = malloc() is declared in stdlib.h, */ 23 /* 2 = in malloc.h, 0 = in neither place */ 24#define HAS_MATH_INF @has_math_inf@ /* INFINITY is defined in math.h or */ 25 /* some system header likely to be used */ 26#define HAS_STDIO_UNLOCK @stdio_nolock@ /* Whether there are getc_unlocked, */ 27 /* putc_unlocked,flockfile and funlockfile */ 28 29#define DEFAULT_WORDSIZE @default_wordsize@ 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 @tls_supported@ /* 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@use_tls@ 42#endif 43#ifdef USE_TLS 44#if !TLS_SUPPORTED 45 #error "TLS is requested but not available" 46#else 47#define TLS_ATTR @ac_cv_tls@ 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 @have_ansicontrols@ 56 /* whether --enable-ansicontrols is used */ 57#define FLEX_ARRAY_OK @flex_array_ok@ 58 /* whether the compiler supports flexible array members in structures */ 59 60#define _FILE_OFFSET_BITS @ac_cv_sys_file_offset_bits@ 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 @have_hwlzcnt@ 70#endif 71#define HAVE_CLZ @have_clz@ 72#define HAVE_CLZL @have_clzl@ 73#define HAVE_CLZLL @have_clzll@ 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 @have_hwpopcnt@ 85#endif 86#define HAVE_POPCNT @have_popcnt@ 87#define HAVE_POPCNTL @have_popcntl@ 88#define HAVE_POPCNTLL @have_popcntll@ 89#define HAVE_MMPOP32 @have_mmpop32@ 90#define HAVE_MMPOP64 @have_mmpop64@ 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* @edit_msg@ 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 @ac_cv_sizeof_int@ 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 @ac_cv_sizeof_long@ 421#endif 422 423#if defined(LLONG_MAX) 424#define SIZEOF_LONG_LONG 8 425#else 426#define SIZEOF_LONG @ac_cv_sizeof_long@ /* 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 @ac_cv_sizeof___int128_t@ /* 0 if nonexistent */ 434#define SIZEOF_INT128 @ac_cv_sizeof___int128@ /* 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 @ac_cv_sizeof_voidp@ 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 493typedef 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 499typedef unsigned short setword; 500#define SETWORD_SHORT 501#endif 502 503#if WORDSIZE==32 504#if SIZEOF_INT>=4 505typedef unsigned int setword; 506#define SETWORD_INT 507#else 508typedef unsigned long setword; 509#define SETWORD_LONG 510#endif 511#endif 512 513#if WORDSIZE==64 514#if SIZEOF_INT>=8 515typedef unsigned int setword; 516#define SETWORD_INT 517#else 518#if SIZEOF_LONG>=8 519typedef unsigned long setword; 520#define SETWORD_LONG 521#else 522typedef 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 531typedef unsigned long long nauty_counter; 532#define LONG_LONG_COUNTERS 1 533#define COUNTER_FMT "%llu" 534#define COUNTER_FMT_RAW "llu" 535#else 536typedef 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) 853static 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) 859static 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) 865static 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. */ 975typedef int shortish; 976typedef shortish permutation; 977typedef 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 985typedef int boolean; /* boolean MUST be the same as int */ 986 987#define UPROC void /* obsolete */ 988 989typedef setword set,graph; 990#ifdef NAUTY_IN_MAGMA 991typedef graph nauty_graph; 992typedef set nauty_set; 993#endif 994 995typedef 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 1026struct optionstruct; /* incomplete definition */ 1027 1028typedef 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 1053typedef 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 1119extern 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 1134extern void *malloc(size_t); 1135extern void *realloc(void*,size_t); 1136extern 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 1222extern setword bit[]; 1223extern int bytecount[]; 1224extern int leftbit[]; 1225 1226#else 1227 /* array giving setwords with single 1-bit */ 1228#if WORDSIZE==64 1229#ifdef SETWORD_LONGLONG 1230EXTDEF_CLASS const 1231setword 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 1252EXTDEF_CLASS const 1253setword 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 1274EXTDEF_CLASS const 1275setword 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 1283EXTDEF_CLASS const 1284setword 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: */ 1289EXTDEF_CLASS const 1290int 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: */ 1308EXTDEF_CLASS const 1309int 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 1336extern "C" { 1337#endif 1338 1339extern void alloc_error(const char*); 1340extern void breakout(int*,int*,int,int,int,set*,int); 1341extern boolean cheapautom(int*,int,boolean,int); 1342extern 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); 1346extern void extra_autom(int*,int); 1347extern void extra_level(int,int*,int*,int,int,int,int,int,int); 1348extern boolean isautom(graph*,int*,boolean,int,int); 1349extern dispatchvec dispatch_graph; 1350extern int itos(int,char*); 1351extern void fmperm(int*,set*,set*,int,int); 1352extern void fmptn(int*,int*,int,set*,set*,int,int); 1353extern void longprune(set*,set*,set*,set*,int); 1354extern void nauty(graph*,int*,int*,set*,int*,optionblk*, 1355 statsblk*,set*,int,int,int,graph*); 1356extern 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); 1359extern int nextelement(set*,int,int); 1360extern int orbjoin(int*,int*,int); 1361extern void permset(set*,set*,int,int*); 1362extern void putstring(FILE*,char*); 1363extern void refine(graph*,int*,int*,int,int*,int*,set*,int*,int,int); 1364extern void refine1(graph*,int*,int*,int,int*,int*,set*,int*,int,int); 1365extern void shortprune(set*,set*,int); 1366extern int targetcell(graph*,int*,int*,int,int,boolean,int,int,int); 1367extern int testcanlab(graph*,graph*,int*,int*,int,int); 1368extern void updatecan(graph*,graph*,int*,int,int,int); 1369extern void writeperm(FILE*,int*,boolean,int,int); 1370extern void nauty_freedyn(void); 1371extern void nauty_check(int,int,int,int); 1372extern void naugraph_check(int,int,int,int); 1373extern void nautil_check(int,int,int,int); 1374extern void nautil_freedyn(void); 1375extern void naugraph_freedyn(void); 1376extern void densenauty(graph*,int*,int*,int*, 1377 optionblk*,statsblk*,int,int,graph*); 1378extern void writegroupsize(FILE*,double,int); 1379 1380extern int labelorg; /* Declared in nautil.c */ 1381extern volatile int nauty_kill_request; /* Also declared in nautil.c */ 1382 1383#ifdef __cplusplus 1384} 1385#endif 1386 1387/* @edit_msg@ */ 1388 1389 1390#endif /* _NAUTY_H_ */ 1391