= Traces graph isomorphism software
{c}
\b[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.<Search Space Contraction in Canonical Labeling of Graphs by Adolfo Piperno>[Abstract and introduction, Traces and the search-space design]{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>.<Practical graph isomorphism, II by Brendan D. McKay and Adolfo Piperno>[Framework and Traces implementation]{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.
Back to article page
