This package provides an interface from Macaulay2 to many of the functions provided in the software nauty by Brendan D. McKay, available at http://cs.anu.edu.au/~bdm/nauty/. The nauty package provides very efficient methods for determining whether given graphs are isomorphic, generating all graphs with particular properties, generating random graphs, and more.
Most methods can handle graphs in either the Macaulay2 Graph type as provided by the EdgeIdeals package or as Graph6 and Sparse6 strings as used by nauty. The purpose of this is that graphs stored as strings are greatly more efficient than graphs stored as instances of the class Graph. (See Comparison of Graph6 and Sparse6 formats.)
It is recommended to work with graphs represented as strings while using nauty-provided methods and then converting the graphs to instances fo the class Graph for further work (e.g., computing the chromatic number).
Version 1.4.1 of this package was accepted for publication in volume 3 of the journal The Journal of Software for Algebra and Geometry: Macaulay2 on 2011-04-20, in the article Nauty in Macaulay2. That version can be obtained from the journal or from the Macaulay2 source code repository, after installing subversion, with the following shell command:
svn export -r 13224 svn://svn.macaulay2.com/Macaulay2/trunk/M2/Macaulay2/packages/Nauty.m2
The following command will display the log messages accompanying any changes to the file in the repository since publication.
svn log -r 13225:HEAD svn://svn.macaulay2.com/Macaulay2/trunk/M2/Macaulay2/packages/Nauty.m2
The following command will summarize the changes to the file in the repository since publication, in the format the program diff uses: lines starting with + have been added, and lines starting with - have been removed. (Changes to white space or end of line style will not be reported.)
svn diff -x "-b --ignore-eol-style" -r 13224:HEAD svn://svn.macaulay2.com/Macaulay2/trunk/M2/Macaulay2/packages/Nauty.m2
The differences between two releases in the repository mentioned in the log can be displayed by replacing 13224:HEAD by the pair of release numbers separated by a colon.