gtools

nauty (No AUTomorphisms, Yes?) is a suite of C programs for computing the automorphism group of a graph or digraph and for producing a canonical labelling, a relabelled copy of the graph that is identical for every member of its isomorphism class. It was created by Brendan McKay at the Australian National University, with the original design published in his 1981 paper "Practical Graph Isomorphism." The companion program Traces, by Adolfo Piperno (Sapienza Università di Roma), solves the same problems with a different search strategy and is distributed in the same package. Both use the individualization-refinement paradigm with search-tree pruning, and the modern algorithms are described in the joint McKay-Piperno work. Because canonical forms make isomorphism testing a simple string comparison, nauty is the de facto reference implementation of practical graph isomorphism and is embedded in systems such as SageMath, GAP, and Magma.

The package ships with a small toolkit called gtools that is directly relevant to graph-data workflows. geng rapidly enumerates all non-isomorphic graphs on a given number of vertices; further generators cover bipartite graphs, trees, digraphs, and multigraphs. Filtering and manipulation utilities such as labelg (canonical relabelling), shortg (remove isomorphs from a list), pickg (select by property), listg, and amtog round out the set. These operate on nauty's own compact text encodings, format:graph6, format:sparse6, and format:digraph6, single-line printable-ASCII strings where graph6 length depends only on vertex count (best for small or dense graphs) and sparse6 is variable-length and far more economical for large sparse graphs. amtog converts adjacency matrices, and copyg can emit digraph6.

In the format-conversion landscape nauty occupies a narrow but foundational niche: its formats are the standard interchange for large catalogues of small graphs, and canonical labelling underpins deduplication of graph collections. The graph6 family is widely read elsewhere; libraries such as tool:networkx, tool:igraph, and dedicated packages like tool:rgraph6 and tool:perl-graph-graph6 import and export it, and general converters like tool:graphinout can bridge it to richer formats.

Its strengths are speed, mathematical rigour, and decades of hardening. The limitations are equally clear: it targets plain graphs and digraphs with vertex colourings, not attributed property graphs; the ASCII formats carry no labels, weights, or metadata beyond structure; and it is a command-line and C-library tool aimed at researchers rather than a general data-integration platform. It is free for research use under the terms in its COPYRIGHT file, and comes with no warranty.