nauty and Traces

In Traces, the trace is an invariant of the refinement process. Its primary components are the sizes and positions of the cells in the order that they are created by the refinement procedure. The advantage is that it often enables the comparison of nodes of the search tree to be made while the computation of a refinement is only partly complete. A limited form of this idea appeared in bliss, and also appears in a recent version of saucy. For many difficult graph families, only a fraction of all refinement operations need to be completed, as in the shown dreadnaut/Traces session.