-
Notifications
You must be signed in to change notification settings - Fork 9
README
This is an unofficial repository of nauty and traces.
This is the meta-readme. It is stored in the wiki in order to avoid modifying the repository. Please file issues here about how this archive is managed. Issues regarding the library itself are better sent to the mailing lists or directly to the maintainers.
Nauty and Traces have no public source control, and releases are not always announced. nauty26r11, for example, was posted to the website without fanfare. These quiet releases will probably not show up here.
Within a week of an update announcement on the the mailing list this repository will be updated with a tag and accompanying 'release'. Branches tracking each major:minor lineage will also be updated with announced releases and may be updated with unannounced releases since the last branch update. The default branch of the repo will be the latest stable branch.
Prior to Oct 2019 the default branch was master and roughly tracked the 2.6 branch. In Oct 2019 some changes from a 2.7 release candidate were backported, effectively diverging the history and necessitating multiple branches. Since there's no public source control, this is a best effort attempt to manage the history of the project. The master branch has been left to avoid breaking existing forks but is no longer the default.
All files in this archive are licensed under Apache 2.0. Versions 2.6r3 and earlier used a different license. Check the official website if you need early versions.
nauty and Traces are programs for computing automorphism groups of graphs and digraphs [at present, Traces does not accept 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.
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, http://dx.doi.org/10.1016/j.jsc.2013.09.003 (a BibTex entry is here).
...
You are invited to join the nauty mailing list so that you can receive notices of updates and exchange information with other users.