Nauty: graph isomorphism

Overview

Nauty is a graphic isomorphism program (its name stands for no automorphism, yes? ) written by Brendan McKay. A typical graph question is that given two graphs, can we transform one to the other by a vertex permutation? If the answer is yes, it means that the two graphs are isomorphic with each other. A related task is to compute a canonical label, which is a unique representative graph for all isomorphic graphs. That is, if two graphs are isomorphic, their canonical labels are the same.

A related program Traces by Adolfo Piperno appears to perform similar tasks. The two programs now share the same official web pages.

The original code can be found from authors’ websites

• Brendan McKay’s page for nauty and Traces
• Adolfo Piperno’s site for nauty and Traces

Minimalist version

Additionally, we provide a self-contained header nau0s.h covering essential features in the official version 2.5r6. Several features are deleted to make the header smaller.

• Schreier method.
• Dynamically allocated graphs.
• User-supplied functions.
• A few functions writemarker() and writeperm().

Usage

The typical usage of nau0s.h is the following. First you needed to define MAXN and WORDSIZE and then include nau0s.h. A complete example can be found in ex1.c.

WORDSIZE is the word size, which is typically 32 or 64. MAXN is the maximal number of vertices in a graph. It does not have to be a multiple of WORDSIZE but it will be rounded to the next multiple automatically. Note, you can use graphs with vertices fewer than MAXN. The dynamic allocation feature in the original package is disabled here for a smaller header, so MAXN must be defined.

  #define MAXN 128
  #define WORDSIZE 32
  #include "nau0s.h"

  int main(void) {
    ...
  }