1 2README file for nauty 2.4 3 4Brendan McKay, bdm@cs.anu.edu.au 5 6------------------------------------------------------------ 7 8The most recent distribution of nauty can be found at 9http://cs.anu.edu.au/~bdm/nauty . 10 11The manual nug.pdf is available at that site and is also included 12in the distribution package. 13 14Note that nauty is copyright but free to use for most purposes. 15The details are in the file nauty.h. 16 17The code in the file planarity.c (used by the planarg program) 18is copyright to the Magma project. 19 20------------------------------------------------------------ 21 22INSTALLATION. 23 24The first step is to unpack the archive. On Unix-ish systems 25you can use one of these commands: 26 27 tar xzf nauty24.tar.gz 28or 29 gunzip -c nauty24.tar.gz | tar xf - 30 31This will write all the files into the subdirectory nauty24. 32Go to that directory. 33 34If you have a working shell, and make, you can run 35 ./configure 36followed by 37 make all 38to compile nauty for your system. 39 40If that succeeds without problem, you will have have the 41program dreadnaut ready to run. 42 43If you have problems during compilation, it may be that the 44configuration scripts are inadequate for your system. Usually it 45is because of some missing system header, incompatible typedef, 46or similar. Please send the details to the author. 47 48If you don't have a shell or make, manually edit the files nauty.h, 49naututil.h and gtools.h as distributed. The parts between the lines 50======= near the start are the main things to look at. After this 51manual editing, you can use makefile as a guide to compilation. 52 53Programs which use an older version of nauty need to be 54recompiled (** not just relinked **). Make sure they use the 55DEFAULTOPTIONS_GRAPH or DEFAULTOPTIONS_SPARSEGRAPH macro to define 56the fields of the options parameter. 57 58See below for compiling on a PC under DJGPP. 59 60If you are using Windows in an environment that needs Windows line 61endings (which is a configuration option in Cygwin, for example), 62then you might prefer to use nauty24.zip rather than 63nauty24.tar.gz. 64 65------------------------------------------------------------ 66 67TESTING. 68 69After compiling nauty successfully, it is recommended that you run 70the included test programs. The simplest way is 71 make checks 72 73------------------------------------------------------------ 74 75MAILING LIST. 76 77There is a mailing list for announcements and discussion about 78nauty and related topics. You can subscribe at 79http://dcsmail.anu.edu.au/cgi-bin/mailman/listinfo/nauty-list 80 81------------------------------------------------------------ 82 83OTHER FILES IN THE PACKAGE. 84 85A few additional goodies are included. 86 87sumlines.c - This is a program designed to digest the outputs from 88 multiple runs of a program (such as a computation split into multiple 89 parts). Lines matching given patterns can be counted and checked, 90 and numbers appearing in them can be accumulated. Instructions appear 91 in the source file. See the option GMP near the head of the program 92 before trying to compile. 93 94naugroup.h, naugroup.c - These define procedures for exhaustively 95 listing a group found by nauty. This is done in a space-efficient way. 96 A sample program appears in nautyex3.c, but so far there is no 97 complete documentation. 98 99------------------------------------------------------------ 100 101DJGPP. 102 103The Unix-like environment DJGPP can be used to run nauty and gtools on 104DOS/Win computers. DJGPP is available at http://www.delorie.com/djgpp . 105The program shortg does not work since DJGPP does not provide a working 106pipe() system call. Using the bash shell is recommended. In DOS, 107Windows NT and early Windows editions, you will need to convert all 108long file names to the 8+3 limits. Thanks to Guenter Sterntenbrink 109for helping with this. 110 111If configure gives an error message similar to this: 112 can not guess host type: you must specify one 113then try 114 ./configure --host=i686 115or use i586 for Pentium 2. If all of those fail, try 116 ./configure --host=unknown 117 118------------------------------------------------------------ 119 120Making 32-bit executables on 64-bit Linux systems. 121 122(In bash or sh:) 123CFLAGS=-m32 CXXFLAGS=-m32 LDFLAGS=-m32 ./configure 124make clean; make 125 126This requires the libraries ia32-libs and libc6-dev-i386. 127 128------------------------------------------------------------ 129 130RECENT CHANGES. 131 132Here we list substantive changes made since the first 2.2 release. 133 134Nov 16, 2002: Replaced rng.c after communication with Don Knuth. 135 The previous version had a bug (mine!) when there was no explicit 136 initialization done by the user. It appears the error had no 137 impact on nauty (which only uses rng.c for the "s" command in 138 dreadnaut, and for genrang, but both always initialize). 139 No change to the nauty version number but beta=2. 140 141Nov 18, 2000: Adjusted the makefile and countg/testg to work in 142 the DOS/Win environment DJGPPP (see the previous section). 143 144May 1, 2003: Fixed PRUNE feature of genbg. 145 146May 3, 2003: Added utility directg for making all orientations of graphs. 147 148Oct 4, 2003: Added options -a, -Z, -d, -z to genbg. Also, the -l 149 (canonical label) option now preserves the colouring. 150 151Nov 17, 2003: Renamed INFINITY to NAUTY_INFINITY since many C header 152 libraries define INFINITY. If INFINITY is not defined by 153 the system, you can still use it. 154 155Nov 19, 2003: Added program biplabg to relabel bipartite graphs with the 156 colour classes contiguous. 157 158Feb 13, 2004: Revised C options for solaris on pentium 159 160Mar 1, 2004: dretog knows !...\n type of comment 161 162May 7, 2004: geng can be called from another program (see instructions 163 in geng.c.) 164 165May 29, 2004: added definition of SETWORD_FORMAT used to write a setword 166 with printf( ) - see nauty.h 167 168Sep 11, 2004: Added utility multig for making multigraphs based on 169 provided simple graphs; similar to directg 170 171Oct 16, 2004: To avoid problems caused by system-dependent handling of 172 external declarations, nauty() no longer accepts NULL as 173 the value of options.dispatch. To get the previous 174 behaviour, use the value &graph_dispatch. This will be 175 handled automatically if programs calling nauty use 176 DEFAULTOPTIONS to declare options and are recompiled. 177 Even better is to use DEFAULTOPTIONS_GRAPH. 178 179May 5, 2005: A bug in the writing of sparse6 was found and fixed. 180 This is procedure ntos6() in gtools.c, which is invoked 181 by writes6(). The bug could only happen if all the 182 following are true: 183 1. n = 2, 4, 8 or 16 (for n=2, only if the graph has loops) 184 2. Vertex n-2 has non-zero degree, but vertex n-1 has 185 zero degree. 186 These conditions never happen for graphs generated by 187 geng or genbg, nor for regular graphs or connected graphs, 188 nor for graphs canonically labelled by nauty (except maybe 189 with some unusual vertex colouring or invariant). 190 If the conditions do happen, the buggy routine may 191 (with some probability) add a spurious loop to vertex n-1. 192 193 In the package is a utility checks6: 194 195 Usage: checks6 [-w] [infile [outfile]] 196 Check a file of graphs, optionally write corrected version 197 -w Write corrected graphs (default is not to write) 198 199------now we start version 2.3 (not released) and 2.4------ 200 201Nov 10, 2004: Use faster routine getc_unlocked() for reading graphs if 202 available. It can make a surprising difference. 203 204Nov 17, 2004: If putenv() or setenv() are available, we set LC_COLLATE to 205 "C" before executing "sort" in shortg. This should alleviate 206 collation issues with sort. However, note that many 207 utilities use the locale these days so you are advised to 208 have LC_COLLATE defined to be "C" always when you are dealing 209 with files of graphs. 210 211 Six counters in statsblk became "unsigned long" instead of 212 "long". nauty doesn't actually use these, but we might as 213 well give them twice as long before they overflow. 214 215Nov 24, 2004: Made geng faster for generating trees. The output labelling 216 may be different from before. A very much faster tree 217 generator is in the works. 218 219Jan 17, 2005: Added two items to dispatch vectors: 220 init : used for initialising something at the start 221 cleanup : used for doing something at the end, such as 222 freeing space allocated by init() 223 See the manual for calling sequences. 224 225May 20, 2005: Update graph6 and sparse6 formats to allow much large sizes. 226 The limit is now 68719476735 vertices (best of luck getting 227 close to that!). 228 229Nov 12, 2005: Changed NAUTY_INFINITY to 2^30+2 in BIGNAUTY case 230 2312006 various: Procedures for sparse graphs implemented. 232 233 New program planarg to test for planarity and find 234 planar embeddings: planarg -help for details. 235 The planarity code was written by Paulette Lieby for the 236 Magma project and used with permission. 237 238 labelg got -S to use sparse graphs. 239 genbg -N changed to genbg -n (only Gordon uses this). 240 genrang gained -R switch for regular graphs in text format. 241 gtools.c has code for reading and writing planarcode. 242 listg got a compile time option to select "Matrix" or 243 "array" for Maple output. 244 pickg/countg got -T for counting triangles 245 246 Better configuration for MacOSX. 247 248Nov 22, 2006: Removed usertcellproc from options. Greater functionality 249 is now available using the new targetcell field in the 250 dispatch vector. The u8 command has gone from dreadnaut. 251 252 Changed bestcell to targetcell in dispatch vector. 253 254Nov 29, 2006: Added extraoptions field (currently unused) to optionblk 255 256Dec 9, 2006: Added an invariant adjacencies_sg(), recommended for digraphs 257 when using sparse representation. 258 259Dec 10, 2006: Remove BIGNAUTY, whose usefulness has passed. Now the types 260 shortish and permutation are synonymous with int always. 261 The limit on the number of vertices is 2^30 unless int 262 has only 16 bits (still any of them around?) in which 263 case it is 2^15-3. Programs previously linked with 264 files like nautyB.o can now be linked with nauty.o. 265 Alternatively, "make bigs" will create files like 266 nautyB.o by copying. 267 268June 26, 2007: Fixed an error in listg -s reported by Evan Heidtmann. 269 270July 12, 2007: Added -f option to directg. 271 272Aug 14, 2007: Added -i,-I,-K options to shortg, parallel to labelg. 273 Since -k is used in labelg in place of -I, changed labelg 274 to use -I also, with -k remaining as an undocumented 275 compatibility feature. 276 277Aug-Sep 2007: Minor things: 278 * naututil-h.in now defines CPUTIME=0.0 as a last resort 279 * gtools.c now implements EDGECODE (not used anywhere yet) 280 * fixed definition of SG_FREE in nausparse.h (not used) 281 * geng favours space over time for n > 28 282 283Oct 14, 2007: Added -T switch to shortg to specify scratch directory. 284 285Mar 3, 2008: Fixed makefile for compilation in a 64-bit environment. 286 287Oct 11, 2008: Added -l and -m to genrang 288 289Nov 29, 2008: Slightly improved -c for geng and genbg 290 Added tournament generator gentourng. 291 292Mar 3, 2009: Added -V to directg. 293