Traces graph isomorphism software

Traces is software for computing graph automorphisms and canonical graph labeling, developed by Adolfo Piperno and distributed with nauty. A canonical result permits two graphs to be compared without depending on their input vertex names. Traces uses individualization-refinement graph search, with strategies designed to reduce the explored search space.^[ref]

Refinement groups vertices according to structural information, including their numbers of neighbors in existing vertex classes. When this does not distinguish all vertices, individualization temporarily gives a selected vertex its own class and refinement continues. Discovering equivalent choices and distinguishing branches can avoid repeated work; the validity of the framework and implementation strategies are developed with Brendan McKay.^[ref]

An original example shows why a coarse invariant is insufficient. A cycle on6vertices and two separate triangles both have6vertices and every vertex has2neighbors. Starting with one vertex class, neighbor-count refinement leaves one class in both cases. Yet the graphs are not isomorphic: one is connected and the other is not. Their correct canonical graph encodings must therefore differ.

Conversely, two differently numbered copies of the same6-cycle should give the same canonical result when processed with the same canonicalization convention. The example illustrates the required behavior, not a benchmark of a particular Traces version.

Performance depends on the graph family and search strategy. The practical success of the program does not by itself establish a polynomial worst-case bound for graph isomorphism. A reproducible comparison should keep the canonicalization settings consistent rather than assume all programs must choose an identical representative.