nauty is a program for computing automorphism groups of graphs and digraphs. It can also produce a canonical labelling.
nauty is written in a portable subset of C, and runs on a considerable number of different systems.
A complete manual is included in the package. It is also separately available here.
There is no document which explains in detail how nauty works. However, most of the important ideas were published in my paper Practical Graph Isomorphism, Congressus Numerantium, 30 (1981) 45-87. A scan is available.
There is a small suite of programs called gtools included in the nauty package. For example, geng can generate non-isomorphic graphs very quickly. There are also generators for bipartite graphs, digraphs, and multigraphs.
If you agree to the restrictions listed below, you may fetch version 2.2 (final) of nauty (including gtools) as a gzipped tar file (570558 bytes). If you use Windows you might prefer a zip file (61006 bytes) with DOS line endings. (However, if you use Cygwin with the Unix-line-ends configuration option, the gzipped tar file is preferred.)
Beta 7 of version 2.4 is available for testing. It appears quite stable. There is a gzipped tar file (705105 bytes) and zip file (751559 bytes). See the file README or the manual for a summary of the differences.
nauty uses the GNU autoconf installation system. You are advised to read the file README before compiling anything.
Request: This edition of the source code and installation scripts has been tested on a variety of Unix/Linux systems (including MacOS X, DJGPP and Cygwin), but many systems remain untested. Please send your success and failure stories. Note that old or broken systems may not be supported at all; try an older version of nauty. A few things in the gtools package, especially shortg, are strictly Unix.
You are invited to join the nauty mailing list so that you can receive notices of updates and exchange information with other users.
nauty is subject to the following usage restrictions:
Copyright (1984-2007) Brendan McKay. All rights reserved. Permission is hereby given for use and/or distribution with the exception of sale for profit or application with nontrivial military significance. You must not remove this copyright notice, and you must document any changes that you make to this program. This software is subject to this copyright only, irrespective of any copyright attached to any package of which this is a part.
Absolutely no guarantees or warranties are made concerning the suitability, correctness, or any other aspect of this program. Any use is at your own risk.
The above does not apply to the file planarity.c, which is copyright to the Magma project and distributed with nauty by permission.
Prior to version 2.2, nauty and gtools were distributed separately.
Version 2.0 (beta 9) of nauty.
Version 1.0 (beta 11) of gtools.
Version 1.9 of nauty.
Note that betas 7 and 8 of nauty 2.0 had a bug.
Brendan D. McKay
Computer Science Department
Australian National University
bdm@cs.anu.edu.au