| 1 |
README file for nauty 2.4 |
| 2 |
This file is only of historical interest as this version is very old. |
| 3 |
|
| 4 |
Brendan McKay, [email protected] |
| 5 |
|
| 6 |
------------------------------------------------------------ |
| 7 |
|
| 8 |
The most recent distribution of nauty can be found at |
| 9 |
http://cs.anu.edu.au/~bdm/nauty . |
| 10 |
|
| 11 |
The manual nug.pdf is available at that site and is also included |
| 12 |
in the distribution package. |
| 13 |
|
| 14 |
Note that nauty is copyright but free to use for most purposes. |
| 15 |
The details are in the file nauty.h. |
| 16 |
|
| 17 |
The code in the file planarity.c (used by the planarg program) |
| 18 |
is copyright to the Magma project. |
| 19 |
|
| 20 |
------------------------------------------------------------ |
| 21 |
|
| 22 |
INSTALLATION. |
| 23 |
|
| 24 |
The first step is to unpack the archive. On Unix-ish systems |
| 25 |
you can use one of these commands: |
| 26 |
|
| 27 |
tar xzf nauty24.tar.gz |
| 28 |
or |
| 29 |
gunzip -c nauty24.tar.gz | tar xf - |
| 30 |
|
| 31 |
This will write all the files into the subdirectory nauty24. |
| 32 |
Go to that directory. |
| 33 |
|
| 34 |
If you have a working shell, and make, you can run |
| 35 |
./configure |
| 36 |
followed by |
| 37 |
make all |
| 38 |
to compile nauty for your system. |
| 39 |
|
| 40 |
If that succeeds without problem, you will have have the |
| 41 |
program dreadnaut ready to run. |
| 42 |
|
| 43 |
If you have problems during compilation, it may be that the |
| 44 |
configuration scripts are inadequate for your system. Usually it |
| 45 |
is because of some missing system header, incompatible typedef, |
| 46 |
or similar. Please send the details to the author. |
| 47 |
|
| 48 |
If you don't have a shell or make, manually edit the files nauty.h, |
| 49 |
naututil.h and gtools.h as distributed. The parts between the lines |
| 50 |
======= near the start are the main things to look at. After this |
| 51 |
manual editing, you can use makefile as a guide to compilation. |
| 52 |
|
| 53 |
Programs which use an older version of nauty need to be |
| 54 |
recompiled (** not just relinked **). Make sure they use the |
| 55 |
DEFAULTOPTIONS_GRAPH or DEFAULTOPTIONS_SPARSEGRAPH macro to define |
| 56 |
the fields of the options parameter. |
| 57 |
|
| 58 |
See below for compiling on a PC under DJGPP. |
| 59 |
|
| 60 |
If you are using Windows in an environment that needs Windows line |
| 61 |
endings (which is a configuration option in Cygwin, for example), |
| 62 |
then you might prefer to use nauty24.zip rather than |
| 63 |
nauty24.tar.gz. |
| 64 |
|
| 65 |
------------------------------------------------------------ |
| 66 |
|
| 67 |
TESTING. |
| 68 |
|
| 69 |
After compiling nauty successfully, it is recommended that you run |
| 70 |
the included test programs. The simplest way is |
| 71 |
make checks |
| 72 |
|
| 73 |
------------------------------------------------------------ |
| 74 |
|
| 75 |
MAILING LIST. |
| 76 |
|
| 77 |
There is a mailing list for announcements and discussion about |
| 78 |
nauty and related topics. You can subscribe at |
| 79 |
http://dcsmail.anu.edu.au/cgi-bin/mailman/listinfo/nauty-list |
| 80 |
|
| 81 |
------------------------------------------------------------ |
| 82 |
|
| 83 |
OTHER FILES IN THE PACKAGE. |
| 84 |
|
| 85 |
A few additional goodies are included. |
| 86 |
|
| 87 |
sumlines.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 |
|
| 94 |
naugroup.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 |
|
| 101 |
DJGPP. |
| 102 |
|
| 103 |
The Unix-like environment DJGPP can be used to run nauty and gtools on |
| 104 |
DOS/Win computers. DJGPP is available at http://www.delorie.com/djgpp . |
| 105 |
The program shortg does not work since DJGPP does not provide a working |
| 106 |
pipe() system call. Using the bash shell is recommended. In DOS, |
| 107 |
Windows NT and early Windows editions, you will need to convert all |
| 108 |
long file names to the 8+3 limits. Thanks to Guenter Sterntenbrink |
| 109 |
for helping with this. |
| 110 |
|
| 111 |
If configure gives an error message similar to this: |
| 112 |
can not guess host type: you must specify one |
| 113 |
then try |
| 114 |
./configure --host=i686 |
| 115 |
or use i586 for Pentium 2. If all of those fail, try |
| 116 |
./configure --host=unknown |
| 117 |
|
| 118 |
------------------------------------------------------------ |
| 119 |
|
| 120 |
Making 32-bit executables on 64-bit Linux systems. |
| 121 |
|
| 122 |
(In bash or sh:) |
| 123 |
CFLAGS=-m32 CXXFLAGS=-m32 LDFLAGS=-m32 ./configure |
| 124 |
make clean; make |
| 125 |
|
| 126 |
This requires the libraries ia32-libs and libc6-dev-i386. |
| 127 |
|
| 128 |
------------------------------------------------------------ |
| 129 |
|
| 130 |
RECENT CHANGES. |
| 131 |
|
| 132 |
Here we list substantive changes made since the first 2.2 release. |
| 133 |
|
| 134 |
Nov 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 |
|
| 141 |
Nov 18, 2000: Adjusted the makefile and countg/testg to work in |
| 142 |
the DOS/Win environment DJGPPP (see the previous section). |
| 143 |
|
| 144 |
May 1, 2003: Fixed PRUNE feature of genbg. |
| 145 |
|
| 146 |
May 3, 2003: Added utility directg for making all orientations of graphs. |
| 147 |
|
| 148 |
Oct 4, 2003: Added options -a, -Z, -d, -z to genbg. Also, the -l |
| 149 |
(canonical label) option now preserves the colouring. |
| 150 |
|
| 151 |
Nov 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 |
|
| 155 |
Nov 19, 2003: Added program biplabg to relabel bipartite graphs with the |
| 156 |
colour classes contiguous. |
| 157 |
|
| 158 |
Feb 13, 2004: Revised C options for solaris on pentium |
| 159 |
|
| 160 |
Mar 1, 2004: dretog knows !...\n type of comment |
| 161 |
|
| 162 |
May 7, 2004: geng can be called from another program (see instructions |
| 163 |
in geng.c.) |
| 164 |
|
| 165 |
May 29, 2004: added definition of SETWORD_FORMAT used to write a setword |
| 166 |
with printf( ) - see nauty.h |
| 167 |
|
| 168 |
Sep 11, 2004: Added utility multig for making multigraphs based on |
| 169 |
provided simple graphs; similar to directg |
| 170 |
|
| 171 |
Oct 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 |
|
| 179 |
May 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 |
|
| 201 |
Nov 10, 2004: Use faster routine getc_unlocked() for reading graphs if |
| 202 |
available. It can make a surprising difference. |
| 203 |
|
| 204 |
Nov 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 |
|
| 215 |
Nov 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 |
|
| 219 |
Jan 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 |
|
| 225 |
May 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 |
|
| 229 |
Nov 12, 2005: Changed NAUTY_INFINITY to 2^30+2 in BIGNAUTY case |
| 230 |
|
| 231 |
2006 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 |
|
| 248 |
Nov 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 |
|
| 254 |
Nov 29, 2006: Added extraoptions field (currently unused) to optionblk |
| 255 |
|
| 256 |
Dec 9, 2006: Added an invariant adjacencies_sg(), recommended for digraphs |
| 257 |
when using sparse representation. |
| 258 |
|
| 259 |
Dec 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 |
|
| 268 |
June 26, 2007: Fixed an error in listg -s reported by Evan Heidtmann. |
| 269 |
|
| 270 |
July 12, 2007: Added -f option to directg. |
| 271 |
|
| 272 |
Aug 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 |
|
| 277 |
Aug-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 |
|
| 283 |
Oct 14, 2007: Added -T switch to shortg to specify scratch directory. |
| 284 |
|
| 285 |
Mar 3, 2008: Fixed makefile for compilation in a 64-bit environment. |
| 286 |
|
| 287 |
Oct 11, 2008: Added -l and -m to genrang |
| 288 |
|
| 289 |
Nov 29, 2008: Slightly improved -c for geng and genbg |
| 290 |
Added tournament generator gentourng. |
| 291 |
|
| 292 |
Mar 3, 2009: Added -V to directg. |