Please visit the other nauty Traces page at https://pallini.di.uniroma1.it for more than is here.
nauty and Traces are programs for computing automorphism groups of graphs and digraphs. They can also produce a canonical labelling.
nauty and Traces are written in a portable subset of C, and run on a considerable number of different systems.
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, trees, digraphs, multigraphs, and other classes, and many programs for manipulating files of graphs in a compact format.
A complete manual is included in the package. It is also
separately available here.
See the file changes24-27.txt for a summary of recent changes.
The original design of nauty is in B. D. McKay,
Practical Graph Isomorphism, Congressus Numerantium, 30 (1981) 45-87.
A scan is available.
The original design of Traces is in A. Piperno, Search Space Contraction in Canonical Labeling of Graphs, available at arxiv.org.
The current algorithms behind nauty and Traces are described in the paper of McKay and Piperno cited below.
If you use nauty or Traces in your research, please
cite this paper:
B. D. McKay and A. Piperno, Practical Graph Isomorphism, II, J. Symbolic Computation (2013) 60 94-112. https://doi.org/10.1016/j.jsc.2013.09.003. Preprint version at arxiv.org.
If you agree to the restrictions listed below, you may fetch version 2.7 of nauty, and version 2.1 of Traces, as a gzipped tar file (1.6MB).
nauty uses the GNU autoconf installation system. You are advised to read the file README before compiling anything.
Installation procedure for Linux, MacOSX, Cygwin, etc.
tar xvzf nauty27r1.tar.gz
After this procedure, the directory nauty27r1 contains all the nauty executables. Move them somewhere else as you wish. Some options are available at the configuration stage; see the manual.
A list of the significant changes since version 2.4 are here: changes24-27.txt.
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, need a Unix-like environment (such as pipes), though newer versions of Cygwin are fine.
A bug was discovered in nauty by James Trimble and Chris Jefferson in October 2019. Versions 26r12, 27rc5 27r1 have been fixed. See the changes file for a description.
You are invited to join the nauty mailing list so that you can receive notices of updates and exchange information with other users. Once you join the list, you can post to it by sending mail to email@example.com .
Traces and dretodot are copyright to Adolfo Piperno.
Files planarity.[ch] are copyright to the Magma project.
File watercluster2.c is copyright to Gunnar Brinkmann.
Files nautycliquer.h and nautycliquer.c are copyright to Sampo Niskanen and Patric Östergård. Everything else in the package is copyright to Brendan McKay.
The minimal restrictions on usage are in the file COPYRIGHT in the package and here.
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.
Prior to version 2.2, nauty and gtools were distributed separately. Traces was not distributed with nauty until version 2.5.
Version 2.6r12 of nauty and Version 2.1 of Traces.
Version 2.5r9 of nauty and Version 2.0 of Traces.
Version 2.4r2 of nauty.
Version 2.2 of nauty.
Version 2.0 (beta 9) of nauty.
Version 1.0 (beta 11) of gtools.
Version 1.9 of nauty.
Brendan D. McKay
Research School of Computer Science
Australian National University
Canberra, ACT, Australia
brendan dot mckay at anu dot edu dot au
Dipartimento di Informatica
Sapienza Universitá di Roma
piperno at di dot uniroma1 dot it