 nauty

nauty is software for computing graph automorphisms and canonical graph labeling, originally developed by Brendan McKay. It is distributed with Traces graph isomorphism software and auxiliary graph-generation and manipulation tools.^[ref]

An automorphism result describes relabelings that preserve adjacency. For an original example, the graph with6vertices and no edges permits every vertex permutation, so its automorphism group is the symmetric group $S_6$ of orderA compact generator description can use a transposition $(12)$ and a cycle $(123456)$. Conjugating the transposition by powers of the cycle produces adjacent transpositions, which generate the whole symmetric group. These are illustrative generators, not a claim about the exact generator list returned by a particular run.

A canonical result serves another purpose. If $\mathrm{can}(G)$ denotes the chosen canonical graph encoding, correctness requiresRenaming vertices changes the input representation but must not change that chosen result. This permits duplicate elimination when generating graphs and comparison of structures supplied with unrelated labels.

nauty combines structural refinement with a search over unresolved choices, exploiting discovered graph automorphisms to reduce equivalent work. Its theoretical framework and relationship to Traces are described in the authors' joint paper.^[ref]

A generating set for symmetries and a canonical encoding are different outputs. The first describes equivalences within a graph; the second makes equivalence between independently labeled graphs directly testable.