Brendan McKay
Department of Computer Science
Australian National University
Canberra ACT 0200, Australia
bdm at cs dot anu dot edu dot au
Personal page →
Adolfo Piperno
Dipartimento di Informatica
Sapienza Università di Roma
Via Salaria 113, 00198 Rome, Italy
(λxy.pipernoxdiyuniroma1yit) @ . Wikipedia: The Lambda-Calculus →
(λxy.M)PQ = M[P/x][Q/y] "substitute P for x and Q for y in M"
Personal page →
automorphism group computation
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, and programs for manipulating files of graphs in a compact format.
[*] At present, Traces does not accept digraphs.
A complete manual is included in the package. It is also separately available here.
The original design of nauty is in McKay, B.D., Practical Graph Isomorphism, Congressus Numerantium, 30 (1981) 45-87. A scan (2.6 MB) is available.
The original design of Traces is in 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 of McKay and Piperno cited below.
If you use nauty or Traces in your research,
please cite this paper:
McKay, B.D. and Piperno, A.,
Practical Graph Isomorphism, II,
Journal of Symbolic Computation, 60 (2014),
pp. 94-112, https://doi.org/10.1016/j.jsc.2013.09.003
(a BibTex entry is here).
If you agree to the restrictions listed below, you may fetch version 2_8_9 of nauty, and version 2.2 of Traces, as a gzipped tar file (∼3.4 MB).
See the file changes24-28.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.
After this procedure, the directory nauty2_8_9 contains all the executables. Move them somewhere else as you wish.
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.
You are invited to join the nauty mailing list so that you can receive notices of updates and exchange information with other users.
Version 2_8_9 of nauty and Traces has been released on Aug 26, 2024. See the file changes24-28.txt for a summary of recent changes. Please report problems with the programs or errors in the documentation to one of the authors (see Contacts below). Download Nauty&Traces 2_8_9
Version 2.5r9 of nauty and traces is available here. Previous versions of nauty are available at Brendan McKay's nauty page.
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.
dretodot is a tool for drawing graphs in dreadnaut format; it produces a .dot file which can be rendered by Graphviz. Click below for a short video tutorial.
Licensed
under the Apache License, Version 2.0 (the "License");
you may not use this software except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0.
Earlier (pre-2.6) versions of this package carried a different notice: "Permission is hereby given for use and/or distribution with the exception of sale for profit or application with nontrivial military significance." These days most people use nauty via a larger package such as Magma, Sage, or GAP, and often they don't even know they are using nauty. Due to the legal nonsense that large package distributors need to worry about, it has proved too much trouble to maintain an idiosyncratic licence. I didn't change my opinion about military use, but it is no longer part of the formal notice. Brendan McKay (Jan 20, 2016)
go to
Brendan McKay's nauty page →
