nauty and Traces

Brendan McKay and Adolfo Piperno

Please visit the new nauty Traces page at http://pallini.di.uniroma1.it for much more than is here.

Summary

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, digraphs, and multigraphs, and programs for manipulating files of graphs in a compact format.

Documentation

A complete manual is included in the package. It is also separately available here.

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.

How to cite nauty or Traces

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. http://dx.doi.org/10.1016/j.jsc.2013.09.003. Preprint version at arxiv.org.

How to get it

If you agree to the restrictions listed below, you may fetch version 2.5r9 of nauty, and version 2.0 of Traces, as a gzipped tar file (1002946 bytes).

See the file changes24-25.txt for a summary of recent changes.

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 nauty25r9.tar.gz
   cd nauty25r9
   ./configure
   make

After this procedure, the directory nauty25r9 contains all the nauty executables. Move them somewhere else as you wish. Some options are available at the configuration stage; see the guide.

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.

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.

Restrictions

nauty is copyright (1984-2013) Brendan McKay. 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, nor to the file watercluster2.c, which is copyright to Gunnar Brinkmann.

Old Versions

Prior to version 2.2, nauty and gtools were distributed separately. Traces was not distributed with nauty until version 2.5.

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.

Authors

Brendan D. McKay
Research School of Computer Science
Australian National University
Canberra, ACT, Australia
bdm at cs dot anu dot edu dot au

Adolfo Piperno
Dipartimento di Informatica
Sapienza Universitá di Roma
Roma, Italy
piperno at di dot uniroma1 dot it