Nauty

Nauty
Name	Nauty
Author	Brendan McKay
Developer	McKay Research Group
Released	1981 (concept), 1983 (first implementation)
Latest release version	2.8 (example)
Operating system	Cross-platform
License	Mixed (Proprietary and GPL components)
Genre	Graph isomorphism, graph automorphism

Nauty is a software package and algorithmic suite for determining graph isomorphism, computing automorphism groups of graphs, and producing canonical labellings of combinatorial structures. It was developed to address computational problems in graph theory and combinatorics and has been used in research associated with chemical graph theory, design theory, finite geometry, computer algebra, and network science. Nauty's methods are closely tied to partition refinement and backtracking strategies that interact with algebraic structures such as permutation groups and group actions studied in group theory and algebraic combinatorics.

Overview

Nauty provides tools for detecting whether two finite graphs are isomorphic, for listing automorphisms of a graph, and for producing canonical forms that permit fast isomorphism testing via equality checks. The package interfaces with data formats commonly used in projects hosted by DIMACS, Library of Congress computational collections, and software ecosystems like SageMath and NetworkX; it also complements systems such as GAP and Magma that study permutation groups and symmetry. Nauty's canonical labelling and automorphism computations underpin tasks in chemical informatics where graph-based representations of molecules are compared, in finite incidence structures classification, and in exhaustive search programs used by research groups at institutions like CSIRO and University of Waterloo.

History and Development

Nauty originated in research by Brendan McKay in the early 1980s while addressing enumerative problems in graph theory and exhaustive classification tasks connected to projects at Australian National University. Early implementations refined ideas from partition refinement methods and individualization-refinement paradigms formalized in the literature of the 1970s and 1980s. Subsequent development involved collaborations and contributions from researchers engaged with conferences such as STOC and ICALP and workshops organized by groups at DIMACS and DIMACS Challenge venues. Over decades, Nauty evolved through successive releases improving performance, robustness, and interoperability with systems like SageMath, with code maintenance coordinated by research groups familiar with computational combinatorics and supported by academic users across universities including Princeton University and University of Sydney.

Algorithms and Techniques

At its core Nauty uses a refined version of the individualization-refinement technique: vertices are partitioned into colour classes which are refined using neighborhood information, with strategic individualization leading to a search tree explored by backtracking. The approach interleaves combinatorial partitioning with algebraic pruning via group-theoretic stabilizers and orbits computed using methods found in group theory literature and implemented in systems like GAP. Nauty implements heuristics for choosing individualization targets and for detecting equitable partitions, and uses canonical augmentation principles studied in combinatorics to ensure canonical labellings are unique representatives of isomorphism classes. The algorithm draws on concepts from research published in venues such as Journal of Algorithms and SIAM Journal on Computing, and builds on foundational work in automorphism group computation developed in the context of permutation group algorithms studied at University of Illinois and MIT.

Software Implementation and Features

The Nauty distribution is primarily implemented in the C programming language and provides a command-line interface as well as a library API enabling integration with projects like SageMath and NetworkX. Features include canonical labelling functions, routines to compute generators of automorphism groups, facilities for graph generation and filtering, and support for reading common graph formats used by DIMACS challenge datasets. The software exposes options for control of individualization/refinement heuristics, support for dense and sparse graph representations, and utilities for handling directed graphs and vertex-coloured graphs arising in chemical graph theory and design theory applications. Bindings and wrappers have been developed to interoperate with languages and systems including Python (programming language), Perl, and Haskell in some research projects.

Performance and Applications

Nauty's performance is noted for practical efficiency on many classes of graphs encountered in applied and theoretical problems; empirical comparisons often involve test suites from DIMACS and benchmarks drawn from chemical databases curated by organizations such as PubChem and research consortia at CNRS. For tasks like canonicalisation of molecular graphs, automorphism group enumeration in incidence structures, and exhaustive search in design theory classification, Nauty has been applied in published work appearing in outlets like Journal of Chemical Information and Modeling and European Journal of Combinatorics. Large-scale applications have included symmetry detection for constraint-solving systems used in projects at IBM Research and graph mining in datasets handled by teams at Microsoft Research. Performance depends heavily on graph structure; worst-case instances relate to theoretical constructions studied in complexity theory and the graph isomorphism problem studied through the lens of work by researchers connected to László Babai and others.

Licensing and Availability

Nauty has been distributed under licensing terms maintained by its author and hosting institutions; historically, source code releases included a mix of permissive redistribution terms and conditions reflecting academic use, with some portions re-released under more modern open-source licenses to enable integration with projects such as SageMath and GAP. Official distributions and source tarballs have been circulated via academic webpages and archived mirrors used by universities and research labs including Australian National University and University of Melbourne. Users seeking to embed Nauty in commercial products commonly consult the author and institutional policies to clarify licensing, while open-source projects often rely on wrappers and ports maintained under compatible licenses.

Category:Graph theory software