go to
Brendan McKay's nauty page →nauty and Traces are programs for computing automorphism groups of graphs and digraphs [*]. They can also produce a canonical label. They 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 package. For example, geng can generate non-isomorphic graphs very quickly. There are also generators for bipartite graphs, digraphs, and multigraphs.
[*] At present, Traces does not accept digraphs.
Documentation
A complete manual is included in the package. It is also separately available here.
Most of the important ideas in nauty were published in the paper McKay, B., Practical Graph Isomorphism, Congressus Numerantium, 30 (1981) 45-87. A scan (2.6 MB) is available.
A preliminary version of Traces is described in Piperno, A., Search Space Contraction in Canonical Labeling of Graphs, available at arxiv.org.
The current algorithms behind nauty and Traces are described in the paper B. D. McKay and A. Piperno, Practical Graph Isomorphism, II, available at arxiv.org.
How to get it
If you agree to the restrictions listed below, you may fetch version 2.5 (r4) of nauty as a gzipped tar file (1 MB). Traces is fully integrated in the package.
See the file changes24-25.txt for a summary of recent changes.
The package uses the GNU autoconf installation system. You are advised to read the file README before compiling anything.
Installation procedure
tar xvzf nauty25r4.tar.gzcd nauty25r4
./configure
make
After this procedure, the directory nauty25r4 contains all the executables. Move them somewhere else as you wish.
Dreadnaut users
Type An to enter nauty dense mode, As for nauty sparse mode, At for Traces mode. Type an additional + to convert the current graph. With a few exceptions, all dreadnaut commands are available in every mode. See the manual for a full description of the new features.
News and comments
Nauty & Traces released
Version 2.5 of nauty and traces, released on Jan 2, 2013, has been replaced by version 2.5r4.
Request
This edition of the source code and installation scripts has been tested on a variety of Unix/Linux systems (including MacOS X), 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 utilities such as shortg require a Unix-like environment.
Nauty mailing list
You are invited to join the nauty mailing list so that you can receive notices of updates and exchange information with other users.
Graph Pictures
Restrictions
nauty and traces is subject to the following usage restrictions:
nauty is copyright (1984-2013) Brendan McKay. All rights reserved. Traces is copyright (2008-2013) Adolfo Piperno. 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, nor to the file watercluster2.c, which is copyright to Gunnar Brinkmann.